Add one-char string table for faster String.charAt to the VM.

Add one-char string table for faster String.charAt to the VM.

This is used for a fast lookup when executing String.charAt.
Currently it is only used in the C-runtime, but the plan is to
generate optimized code for the table lookup for speeding up
String.charAt.
Committed: https://code.google.com/p/dart/source/detail?r=15088

[Florian Schneider, 2012-11-15 05:16:59]

First attempt with only runtime support.

snapshot_test.cc is already in the current VM when using the '.' instead of 'A'
in the test case.

I'm still inclined to do a per-isolate lazily allocated/initialized array. It
would fit better in our optimizing compiler by allowing to reuse the existing
LoadIndexed-IL for lookup.

[Ivan Posva, 2012-11-15 09:07:10]

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc
File runtime/vm/symbols.cc (left):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#oldcode121
runtime/vm/symbols.cc:121: ASSERT(isolate != Dart::vm_isolate());
If single char was handled in names, you would not need to remove this assertion
either.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc
File runtime/vm/symbols.cc (right):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#newcode31
runtime/vm/symbols.cc:31: const char* Symbols::Name(SymbolId symbol) {
I find it unfortunate that we cannot access the name over the full range of
valid SymbolIds.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#newcode32
runtime/vm/symbols.cc:32: ASSERT((symbol > kIllegal) && (symbol <
kMaxPredefinedId));
I find it unfortunate that we cannot access the names over the full SymbolId
range.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#newcode52
runtime/vm/symbols.cc:52: for (intptr_t i = 1; i < Symbols::kMaxPredefinedId;
i++) {
if the single char strings would be part of the names table, then you would not
need to have special handling here.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#newcode54
runtime/vm/symbols.cc:54: Add(symbol_table, str);
The naked Add into the symbol table seems rather suspicious here. I know this is
not in your code, but we should verify that the symbol table never grows as we
keep it cached throughout this loop.

Fixed with https://chromiumcodereview.appspot.com/11308032/

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h
File runtime/vm/symbols.h (right):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h#newcode149
runtime/vm/symbols.h:149: static const uint32_t kMaxOneByteCharCode = 0x7F;
There is no reason to limit this to the maximum one byte char code. How about
just calling it kMaxCharCode and setting it to 255 to get all Latin-1 characters
out of the way.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h#newcode159
runtime/vm/symbols.h:159: kMaxPredefinedId,
This causes us to have a hole in the used strings. How about this or something
similar?
#undef DEFINE_SYMBOL_INDEX
    kNullCharId,
    // Further ids for single char code symbols.
    kMaxId = kNullCharId + kMaxCharCode + 1,
    kMaxPredefinedId = kNullCharId,
  };

[Florian Schneider, 2012-11-15 21:54:42]

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc
File runtime/vm/symbols.cc (left):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#oldcode121
runtime/vm/symbols.cc:121: ASSERT(isolate != Dart::vm_isolate());
On 2012/11/15 09:07:10, Ivan Posva wrote:
> If single char was handled in names, you would not need to remove this
assertion
> either.

It is a bit unfortunate, but I also want to avoid duplicates between the
predefined symbols and all one-char strings. It should not hurt to invoke
Symbols::New inside the vm-isolate, except that the code below will try twice to
find any non-existing string before adding it.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc
File runtime/vm/symbols.cc (right):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.cc#newcode31
runtime/vm/symbols.cc:31: const char* Symbols::Name(SymbolId symbol) {
On 2012/11/15 09:07:10, Ivan Posva wrote:
> I find it unfortunate that we cannot access the name over the full range of
> valid SymbolIds.

Yes, but not sure if the names are actually needed for those >= kMaxPredefined.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h
File runtime/vm/symbols.h (right):

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h#newcode149
runtime/vm/symbols.h:149: static const uint32_t kMaxOneByteCharCode = 0x7F;
On 2012/11/15 09:07:10, Ivan Posva wrote:
> There is no reason to limit this to the maximum one byte char code. How about
> just calling it kMaxCharCode and setting it to 255 to get all Latin-1
characters
> out of the way.

For now I only want to deal with OneByteStrings in the VM isolate. We can extend
it to more characters if needed.

https://codereview.chromium.org/11369259/diff/1/runtime/vm/symbols.h#newcode159
runtime/vm/symbols.h:159: kMaxPredefinedId,
On 2012/11/15 09:07:10, Ivan Posva wrote:
> This causes us to have a hole in the used strings. How about this or something
> similar?
> #undef DEFINE_SYMBOL_INDEX
>     kNullCharId,
>     // Further ids for single char code symbols.
>     kMaxId = kNullCharId + kMaxCharCode + 1,
>     kMaxPredefinedId = kNullCharId,
>   };

Done. kNullCharId is an alias for kMaxPredefinedId.

[Ivan Posva, 2012-11-17 01:30:58]

LGTM with comments.

-Ivan

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/snapshot...
File runtime/vm/snapshot_test.cc (left):

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/snapshot...
runtime/vm/snapshot_test.cc:1843: EXPECT_EQ(root->value.as_array.values[0],
element);
I am not clear why you needed to remove these expectations.

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/snapshot...
runtime/vm/snapshot_test.cc:2018: EXPECT_EQ(root->value.as_array.values[0],
element);
ditto

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/symbols.h
File runtime/vm/symbols.h (right):

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/symbols....
runtime/vm/symbols.h:149: enum { kMaxOneByteCharCode = 0xFF };
kMaxOneCharCodeSymbol or similar. It is not related to the storage size per se.

[Florian Schneider, 2012-11-19 16:04:02]

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/snapshot...
File runtime/vm/snapshot_test.cc (left):

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/snapshot...
runtime/vm/snapshot_test.cc:1843: EXPECT_EQ(root->value.as_array.values[0],
element);
On 2012/11/17 01:30:58, Ivan Posva wrote:
> I am not clear why you needed to remove these expectations.

Done. Not needed anymore. sgjesse@ landed a fix in
http://code.google.com/p/dart/source/detail?r=15082.

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/symbols.h
File runtime/vm/symbols.h (right):

https://chromiumcodereview.appspot.com/11369259/diff/9005/runtime/vm/symbols....
runtime/vm/symbols.h:149: enum { kMaxOneByteCharCode = 0xFF };
On 2012/11/17 01:30:58, Ivan Posva wrote:
> kMaxOneCharCodeSymbol or similar. It is not related to the storage size per
se.

Done.