Create frequently used symbols in the vm isolate

vm/symbols.cc

+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#include "vm/symbols.h"
+
+#include "vm/isolate.h"
+#include "vm/object.h"
+#include "vm/object_store.h"
+#include "vm/raw_object.h"
+#include "vm/unicode.h"
+#include "vm/visitor.h"
+
+namespace dart {
+
+const char* Symbols::kDot = ".";
+RawString* Symbols::dot_ = String::null();
+
+
+void Symbols::InitOnce(Isolate* isolate) {
+  // Should only be run by the vm isolate.
+  ASSERT(isolate == Dart::vm_isolate());
+
+  // Create and setup a symbol table in the vm isolate.
+  SetupSymbolTable(isolate);
+
+  // Create all predefined symbols.
+  const Array& symbol_table =
+      Array::Handle(isolate->object_store()->symbol_table());
+  OneByteString& str = OneByteString::Handle();
+
+  str = OneByteString::New(kDot, Heap::kOld);
+  Add(symbol_table, str);  // "."
+  dot_ = str.raw();
+}
+
+
+void Symbols::SetupSymbolTable(Isolate* isolate) {
+  ASSERT(isolate != NULL);
+
+  // Setup the symbol table used within the String class.
+  const Array& array = Array::Handle(Array::New(kInitialSymbolTableSize + 1));
+
+  // Last element contains the count of used slots.
+  array.SetAt(kInitialSymbolTableSize, Smi::Handle(Smi::New(0)));
+  isolate->object_store()->set_symbol_table(array);
+}
+
+
+void Symbols::Add(const Array& symbol_table, const String& str) {
+  // Should only be run by the vm isolate.
+  ASSERT(Isolate::Current() == Dart::vm_isolate());
+  intptr_t hash = str.Hash();
+  intptr_t index = FindIndex(symbol_table, str, 0, str.Length(), hash);
+  ASSERT(symbol_table.At(index) == String::null());
+  InsertIntoSymbolTable(symbol_table, str, index);
+}
+
+
+RawString* Symbols::New(const char* str) {
+  intptr_t width = 0;
+  intptr_t len = Utf8::CodePointCount(str, &width);
+  intptr_t size = len * width;
+  Zone* zone = Isolate::Current()->current_zone();
+  if (len == 0) {
+    return Symbols::New(reinterpret_cast<uint8_t*>(NULL), 0);
+  } else if (width == 1) {
+    uint8_t* characters = reinterpret_cast<uint8_t*>(zone->Allocate(size));
+    Utf8::Decode(str, characters, len);
+    return New(characters, len);
+  } else if (width == 2) {
+    uint16_t* characters = reinterpret_cast<uint16_t*>(zone->Allocate(size));
+    Utf8::Decode(str, characters, len);
+    return New(characters, len);
+  }
+  ASSERT(width == 4);
+  uint32_t* characters = reinterpret_cast<uint32_t*>(zone->Allocate(size));
+  Utf8::Decode(str, characters, len);
+  return New(characters, len);
+}
+
+
+template<typename T>
+RawString* Symbols::New(const T* characters, intptr_t len) {
+  Isolate* isolate = Isolate::Current();
+  ASSERT(isolate != Dart::vm_isolate());
+  String& symbol = String::Handle(isolate, String::null());
+  Array& symbol_table = Array::Handle(isolate, Array::null());
+
+  // Calculate the String hash for this sequence of characters.
+  intptr_t hash = String::Hash(characters, len);
+
+  // First check if a symbol exists in the vm isolate for these characters.
+  symbol_table = Dart::vm_isolate()->object_store()->symbol_table();
+  intptr_t index = FindIndex(symbol_table, characters, len, hash);
+  symbol ^= symbol_table.At(index);
+  if (symbol.IsNull()) {
+    // Now try in the symbol table of the current isolate.
+    symbol_table = isolate->object_store()->symbol_table();
+    index = FindIndex(symbol_table, characters, len, hash);
+    // Since we leave enough room in the table to guarantee, that we find an
+    // empty spot, index is the insertion point if symbol is null.
+    symbol ^= symbol_table.At(index);
+    if (symbol.IsNull()) {
+      // Allocate new result string.
+      symbol = String::New(characters, len, Heap::kOld);
+      symbol.SetHash(hash);  // Remember the calculated hash value.
+      InsertIntoSymbolTable(symbol_table, symbol, index);
+    }
+  }
+  ASSERT(symbol.IsSymbol());
+  return symbol.raw();
+}
+
+template RawString* Symbols::New(const uint8_t* characters, intptr_t len);
+template RawString* Symbols::New(const uint16_t* characters, intptr_t len);
+template RawString* Symbols::New(const uint32_t* characters, intptr_t len);
+
+
+RawString* Symbols::New(const String& str) {
+  if (str.IsSymbol()) {
+    return str.raw();
+  }
+  return New(str, 0, str.Length());
+}
+
+
+RawString* Symbols::New(const String& str, intptr_t begin_index, intptr_t len) {
+  ASSERT(begin_index >= 0);
+  ASSERT(len >= 0);
+  ASSERT((begin_index + len) <= str.Length());
+  Isolate* isolate = Isolate::Current();
+  ASSERT(isolate != Dart::vm_isolate());
+  String& symbol = String::Handle(isolate, String::null());
+  Array& symbol_table = Array::Handle(isolate, Array::null());
+
+  // Calculate the String hash for this sequence of characters.
+  intptr_t hash = (begin_index == 0 && len == str.Length()) ? str.Hash() :
+      String::Hash(str, begin_index, len);
+
+  // First check if a symbol exists in the vm isolate for these characters.
+  symbol_table = Dart::vm_isolate()->object_store()->symbol_table();
+  intptr_t index = FindIndex(symbol_table, str, begin_index, len, hash);
+  symbol ^= symbol_table.At(index);
+  if (symbol.IsNull()) {
+    // Now try in the symbol table of the current isolate.
+    symbol_table = isolate->object_store()->symbol_table();
+    index = FindIndex(symbol_table, str, begin_index, len, hash);
+    // Since we leave enough room in the table to guarantee, that we find an
+    // empty spot, index is the insertion point if symbol is null.
+    symbol ^= symbol_table.At(index);
+    if (symbol.IsNull()) {
+      if (str.IsOld() && begin_index == 0 && len == str.Length()) {
+        // Reuse the incoming str as the symbol value.
+        symbol = str.raw();
+      } else {
+        // Allocate a copy in old space.
+        symbol = String::SubString(str, begin_index, len, Heap::kOld);
+        symbol.SetHash(hash);
+      }
+      InsertIntoSymbolTable(symbol_table, symbol, index);
+    }
+  }
+  ASSERT(symbol.IsSymbol());
+  return symbol.raw();
+}
+
+
+void Symbols::GrowSymbolTable(const Array& symbol_table) {
+  // TODO(iposva): Avoid exponential growth.
+  intptr_t table_size = symbol_table.Length() - 1;
+  intptr_t new_table_size = table_size * 2;
+  Array& new_symbol_table = Array::Handle(Array::New(new_table_size + 1));
+  // Copy all elements from the original symbol table to the newly allocated
+  // array.
+  String& element = String::Handle();
+  Object& new_element = Object::Handle();
+  for (intptr_t i = 0; i < table_size; i++) {
+    element ^= symbol_table.At(i);
+    if (!element.IsNull()) {
+      intptr_t hash = element.Hash();
+      intptr_t index = hash % new_table_size;
+      new_element = new_symbol_table.At(index);
+      while (!new_element.IsNull()) {
+        index = (index + 1) % new_table_size;  // Move to next element.
+        new_element = new_symbol_table.At(index);
+      }
+      new_symbol_table.SetAt(index, element);
+    }
+  }
+  // Copy used count.
+  new_element = symbol_table.At(table_size);
+  new_symbol_table.SetAt(new_table_size, new_element);
+  // Remember the new symbol table now.
+  Isolate::Current()->object_store()->set_symbol_table(new_symbol_table);
+}
+
+
+void Symbols::InsertIntoSymbolTable(const Array& symbol_table,
+                                    const String& symbol,
+                                    intptr_t index) {
+  intptr_t table_size = symbol_table.Length() - 1;
+  symbol.SetCanonical();  // Mark object as being canonical.
+  symbol_table.SetAt(index, symbol);  // Remember the new symbol.
+  Smi& used = Smi::Handle();
+  used ^= symbol_table.At(table_size);
+  intptr_t used_elements = used.Value() + 1;  // One more element added.
+  used = Smi::New(used_elements);
+  symbol_table.SetAt(table_size, used);  // Update used count.
+
+  // Rehash if symbol_table is 75% full.
+  if (used_elements > ((table_size / 4) * 3)) {
+    GrowSymbolTable(symbol_table);
+  }
+}
+
+
+template<typename T>
+intptr_t Symbols::FindIndex(const Array& symbol_table,
+                            const T* characters,
+                            intptr_t len,
+                            intptr_t hash) {
+  // Last element of the array is the number of used elements.
+  intptr_t table_size = symbol_table.Length() - 1;
+  intptr_t index = hash % table_size;
+
+  String& symbol = String::Handle();
+  symbol ^= symbol_table.At(index);
+  while (!symbol.IsNull() && !symbol.Equals(characters, len)) {
+    index = (index + 1) % table_size;  // Move to next element.
+    symbol ^= symbol_table.At(index);
+  }
+  return index;  // Index of symbol if found or slot into which to add symbol.
+}
+
+
+template intptr_t Symbols::FindIndex(const Array& symbol_table,
+                                     const uint8_t* characters,
+                                     intptr_t len,
+                                     intptr_t hash);
+template intptr_t Symbols::FindIndex(const Array& symbol_table,
+                                     const uint16_t* characters,
+                                     intptr_t len,
+                                     intptr_t hash);
+template intptr_t Symbols::FindIndex(const Array& symbol_table,
+                                     const uint32_t* characters,
+                                     intptr_t len,
+                                     intptr_t hash);
+
+
+intptr_t Symbols::FindIndex(const Array& symbol_table,
+                            const String& str,
+                            intptr_t begin_index,
+                            intptr_t len,
+                            intptr_t hash) {
+  // Last element of the array is the number of used elements.
+  intptr_t table_size = symbol_table.Length() - 1;
+  intptr_t index = hash % table_size;
+
+  String& symbol = String::Handle();
+  symbol ^= symbol_table.At(index);
+  while (!symbol.IsNull() && !symbol.Equals(str, begin_index, len)) {
+    index = (index + 1) % table_size;  // Move to next element.
+    symbol ^= symbol_table.At(index);
+  }
+  return index;  // Index of symbol if found or slot into which to add symbol.
+}
+
+}  // namespace dart