Introduce cache of resolved names in library

runtime/vm/object.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/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 41 matching lines @@
     "When possible, partially or fully overlap the type arguments of a type "
     "with the type arguments of its super type.");
 DEFINE_FLAG(bool, show_internal_names, false,
     "Show names of internal classes (e.g. \"OneByteString\") in error messages "
     "instead of showing the corresponding interface names (e.g. \"String\")");
 DEFINE_FLAG(bool, trace_disabling_optimized_code, false,
     "Trace disabling optimized code.");
 DEFINE_FLAG(bool, throw_on_javascript_int_overflow, false,
     "Throw an exception when the result of an integer calculation will not "
     "fit into a javascript integer.");
+DEFINE_FLAG(bool, use_lib_cache, true, "Use library name cache");
+
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
 DECLARE_FLAG(bool, error_on_bad_override);
 DECLARE_FLAG(bool, trace_compiler);
 DECLARE_FLAG(bool, trace_deoptimization);
 DECLARE_FLAG(bool, trace_deoptimization_verbose);
 DECLARE_FLAG(bool, verbose_stacktrace);
 DECLARE_FLAG(charp, coverage_dir);
 
 static const char* kGetterPrefix = "get:";
@@ skipping 6210 matching lines @@
   return "RedirectionData class";
 }
 
 
 void RedirectionData::PrintToJSONStream(JSONStream* stream, bool ref) const {
   JSONObject jsobj(stream);
 }
 
 
 RawString* Field::GetterName(const String& field_name) {
+  CompilerStats::make_accessor_name++;
   return String::Concat(Symbols::GetterPrefix(), field_name);
 }
 
 
 RawString* Field::GetterSymbol(const String& field_name) {
   const String& str = String::Handle(Field::GetterName(field_name));
   return Symbols::New(str);
 }
 
 
 RawString* Field::SetterName(const String& field_name) {
+  CompilerStats::make_accessor_name++;
   return String::Concat(Symbols::SetterPrefix(), field_name);
 }
 
 
 RawString* Field::SetterSymbol(const String& field_name) {
   const String& str = String::Handle(Field::SetterName(field_name));
   return Symbols::New(str);
 }
 
 
 RawString* Field::NameFromGetter(const String& getter_name) {
+  CompilerStats::make_field_name++;
   return String::SubString(getter_name, strlen(kGetterPrefix));
 }
 
 
 RawString* Field::NameFromSetter(const String& setter_name) {
+  CompilerStats::make_field_name++;
   return String::SubString(setter_name, strlen(kSetterPrefix));
 }
 
 
 bool Field::IsGetterName(const String& function_name) {
   return function_name.StartsWith(Symbols::GetterPrefix());
 }
 
 
 bool Field::IsSetterName(const String& function_name) {
@@ skipping 1550 matching lines @@
                                      field.token_pos());
     if (metadata.IsArray()) {
       ASSERT(Array::Cast(metadata).raw() != Object::empty_array().raw());
       field.set_value(Array::Cast(metadata));
     }
   }
   return metadata.raw();
 }
 
 
+RawObject* Library::ResolveName(const String& name) const {
+  Object& obj = Object::Handle();
+  if (FLAG_use_lib_cache && LookupResolvedNamesCache(name, &obj)) {
+    return obj.raw();
+  }
+  obj = LookupLocalObject(name);
+  if (!obj.IsNull()) {
+    // Names that are in this library's dictionary and are unmangled
+    // are not cached. This reduces the size of the the cache.
+    return obj.raw();
+  }
+  String& accessor_name = String::Handle(Field::GetterName(name));
+  obj = LookupLocalObject(accessor_name);
+  if (obj.IsNull()) {
+    accessor_name = Field::SetterName(name);
+    obj = LookupLocalObject(accessor_name);
+    if (obj.IsNull()) {
+      obj = LookupImportedObject(name);
+    }
+  }
+  AddResolvedName(name, obj);

[siva, 2014/02/06 21:01:29]

AddToResolvedNamesCache would be a more readable method name here.

[hausner, 2014/02/06 21:31:45]

Done.

+  return obj.raw();
+}
+
+
+static intptr_t ResolvedNameCacheSize(const Array& cache) {
+  return (cache.Length() - 1) / 2;
+}
+
+
+// Returns true if the name is found in the cache, false no cache hit.
+// obj is set to the cached entry. It may be null, indicating that the
+// name does not resolve to anything in this library.
+bool Library::LookupResolvedNamesCache(const String& name,
+                                       Object* obj) const {
+  const Array& cache = Array::Handle(resolved_names());
+  const intptr_t cache_size = ResolvedNameCacheSize(cache);
+  intptr_t index = name.Hash() % cache_size;
+  String& entry_name = String::Handle();
+  entry_name ^= cache.At(index);
+  while (!entry_name.IsNull()) {
+    if (entry_name.Equals(name)) {
+      CompilerStats::num_lib_cache_hit++;
+      *obj = cache.At(index + cache_size);
+      return true;
+    }
+    index = (index + 1) % cache_size;
+    entry_name ^= cache.At(index);
+  }
+  *obj = Object::null();
+  return false;
+}
+
+
+void Library::GrowResolvedNamesCache() const {
+  const Array& old_cache = Array::Handle(resolved_names());
+  const intptr_t old_cache_size = ResolvedNameCacheSize(old_cache);
+
+  // Create empty new cache and add entries from the old cache.
+  const intptr_t new_cache_size = old_cache_size * 3 / 2;
+  InitResolvedNamesCache(new_cache_size);
+  String& name = String::Handle();
+  Object& entry = Object::Handle();
+  for (intptr_t i = 0; i < old_cache_size; i++) {
+    name ^= old_cache.At(i);
+    if (!name.IsNull()) {
+      entry = old_cache.At(i + old_cache_size);
+      AddResolvedName(name, entry);
+    }
+  }
+}
+
+
+// Add a name to the resolved name cache. This name resolves to the
+// given object in this library scope. obj may be null, which means
+// the name does not resolve to anything in this library scope.
+void Library::AddResolvedName(const String& name, const Object& obj) const {
+  if (!FLAG_use_lib_cache) {
+    return;
+  }
+  const Array& cache = Array::Handle(resolved_names());
+  // let N = cache.Length();
+  // The entry cache[N-1] is used a counter

[siva, 2014/02/06 21:01:29]

used as a counter

[hausner, 2014/02/06 21:31:45]

Done

+  // The array entries [0..N-2] are used as cache entries.
+  //   cache[i] contains the name of the entry
+  //   cache[i+(N-1)/2] contains the resolved entity, or NULL if that name
+  //   is not present in the library.
+  const intptr_t counter_index = cache.Length() - 1;
+  intptr_t cache_size = ResolvedNameCacheSize(cache);
+  intptr_t index = name.Hash() % cache_size;
+  String& entry_name = String::Handle();
+  entry_name ^= cache.At(index);
+  // An empty spot will be found because we keep the hash set at most 75% full.
+  while (!entry_name.IsNull()) {
+    index = (index + 1) % cache_size;
+    entry_name ^= cache.At(index);
+  }
+  // Insert the object at the empty slot.
+  cache.SetAt(index, name);
+  ASSERT(cache.At(index + cache_size) == Object::null());
+  cache.SetAt(index + cache_size, obj);
+
+  // One more element added.
+  intptr_t num_used = Smi::Value(Smi::RawCast(cache.At(counter_index))) + 1;
+  cache.SetAt(counter_index, Smi::Handle(Smi::New(num_used)));
+  CompilerStats::num_names_cached++;
+
+  // Rehash if symbol_table is 75% full.
+  if (num_used > ((cache_size / 4) * 3)) {
+    CompilerStats::num_names_cached -= num_used;
+    GrowResolvedNamesCache();
+  }
+}
+
+
+void Library::InvalidateResolvedName(const String& name) const {
+  Object& entry = Object::Handle();
+  if (LookupResolvedNamesCache(name, &entry)) {
+    InvalidateResolvedNamesCache();
+  }
+}
+
+
+void Library::InvalidateResolvedNamesCache() const {
+  const intptr_t kInvalidatedCacheSize = 16;
+  InitResolvedNamesCache(kInvalidatedCacheSize);
+}
+
+
 void Library::GrowDictionary(const Array& dict, intptr_t dict_size) const {
   // TODO(iposva): Avoid exponential growth.
   intptr_t new_dict_size = dict_size * 2;
   const Array& new_dict =
       Array::Handle(Array::New(new_dict_size + 1, Heap::kOld));
   // Rehash all elements from the original dictionary
   // to the newly allocated array.
   Object& entry = Class::Handle();
   String& entry_name = String::Handle();
   Object& new_entry = Object::Handle();
@@ skipping 112 matching lines @@
 
   intptr_t index;
   LookupEntry(name, &index);
   // The value is guaranteed to be found.
   const Array& dict = Array::Handle(dictionary());
   dict.SetAt(index, obj);
 }
 
 
 void Library::AddClass(const Class& cls) const {
-  AddObject(cls, String::Handle(cls.Name()));
+  const String& class_name = String::Handle(cls.Name());
+  AddObject(cls, class_name);
   // Link class to this library.
   cls.set_library(*this);
+  InvalidateResolvedName(class_name);

[siva, 2014/02/06 21:01:29]

Should we also invalidate this cache when a class gets compiled lazily.

[hausner, 2014/02/06 21:31:45]

I don't think this is necessary. The name of the class is in the library scope
already when it gets compiled, is it not? And by compiling the class nothing
gets added to the library's name space, only to the name space of the class.

 }
 
 static void AddScriptIfUnique(const GrowableObjectArray& scripts,
                               Script& candidate) {
   if (candidate.IsNull()) {
     return;
   }
   Script& script_obj = Script::Handle();
 
   for (int i = 0; i < scripts.Length(); i++) {
@@ skipping 161 matching lines @@
   // Do not look up private names in imported libraries.
   if (ShouldBePrivate(name)) {
     return Object::null();
   }
 
   // Now check if name is found in any imported libs.
   return LookupImportedObject(name);
 }
 
 
-RawObject* Library::LookupObject(const String& name) const {
-  // First check if name is found in the local scope of the library.
-  Object& obj = Object::Handle(LookupLocalObject(name));
-  if (!obj.IsNull()) {
-    return obj.raw();
-  }
-  // Now check if name is found in any imported libs.
-  return LookupImportedObject(name);
-}
-
-
 RawObject* Library::LookupImportedObject(const String& name) const {
   Object& obj = Object::Handle();
   Namespace& import = Namespace::Handle();
   Library& import_lib = Library::Handle();
   String& import_lib_url = String::Handle();
   String& first_import_lib_url = String::Handle();
   Object& found_obj = Object::Handle();
   for (intptr_t i = 0; i < num_imports(); i++) {
     import ^= ImportAt(i);
     obj = import.Lookup(name);
@@ skipping 18 matching lines @@
           return Object::null();
         }
       }
     }
   }
   return found_obj.raw();
 }
 
 
 RawClass* Library::LookupClass(const String& name) const {
-  Object& obj = Object::Handle(LookupObject(name));
+  Object& obj = Object::Handle(ResolveName(name));
   if (obj.IsClass()) {
     return Class::Cast(obj).raw();
   }
   return Class::null();
 }
 
 
 RawClass* Library::LookupLocalClass(const String& name) const {
   Object& obj = Object::Handle(LookupLocalObject(name));
   if (obj.IsClass()) {
@@ skipping 118 matching lines @@
 // re-exports are quite rare.
 void Library::AddExport(const Namespace& ns) const {
   Array &exports = Array::Handle(this->exports());
   intptr_t num_exports = exports.Length();
   exports = Array::Grow(exports, num_exports + 1);
   StorePointer(&raw_ptr()->exports_, exports.raw());
   exports.SetAt(num_exports, ns);
 }
 
 
+static RawArray* NewDictionary(intptr_t initial_size) {
+  const Array& dict = Array::Handle(Array::New(initial_size + 1, Heap::kOld));
+  // The last element of the dictionary specifies the number of in use slots.
+  dict.SetAt(initial_size, Smi::Handle(Smi::New(0)));
+  return dict.raw();
+}
+
+
+void Library::InitResolvedNamesCache(intptr_t size) const {
+  // Need space for 'size' names and 'size' resolved object entries.
+  StorePointer(&raw_ptr()->resolved_names_, NewDictionary(2 * size));
+}
+
+
 void Library::InitClassDictionary() const {
-  // The last element of the dictionary specifies the number of in use slots.
   // TODO(iposva): Find reasonable initial size.
   const int kInitialElementCount = 16;
-
-  const Array& dictionary =
-      Array::Handle(Array::New(kInitialElementCount + 1, Heap::kOld));
-  dictionary.SetAt(kInitialElementCount, Smi::Handle(Smi::New(0)));
-  StorePointer(&raw_ptr()->dictionary_, dictionary.raw());
+  StorePointer(&raw_ptr()->dictionary_, NewDictionary(kInitialElementCount));
 }
 
 
 void Library::InitImportList() const {
   const Array& imports =
       Array::Handle(Array::New(kInitialImportsCapacity, Heap::kOld));
   StorePointer(&raw_ptr()->imports_, imports.raw());
   raw_ptr()->num_imports_ = 0;
 }
 
 
 RawLibrary* Library::New() {
   ASSERT(Object::library_class() != Class::null());
   RawObject* raw = Object::Allocate(Library::kClassId,
                                     Library::InstanceSize(),
                                     Heap::kOld);
   return reinterpret_cast<RawLibrary*>(raw);
 }
 
 
 RawLibrary* Library::NewLibraryHelper(const String& url,
                                       bool import_core_lib) {
   const Library& result = Library::Handle(Library::New());
   result.StorePointer(&result.raw_ptr()->name_, Symbols::Empty().raw());
   result.StorePointer(&result.raw_ptr()->url_, url.raw());
   result.raw_ptr()->private_key_ = Scanner::AllocatePrivateKey(result);
+  result.raw_ptr()->resolved_names_ = Object::empty_array().raw();
   result.raw_ptr()->dictionary_ = Object::empty_array().raw();
   result.StorePointer(&result.raw_ptr()->metadata_,
                       GrowableObjectArray::New(4, Heap::kOld));
   result.raw_ptr()->anonymous_classes_ = Object::empty_array().raw();
   result.raw_ptr()->num_anonymous_ = 0;
   result.raw_ptr()->imports_ = Object::empty_array().raw();
   result.raw_ptr()->exports_ = Object::empty_array().raw();
   result.raw_ptr()->loaded_scripts_ = Array::null();
   result.set_native_entry_resolver(NULL);
   result.raw_ptr()->corelib_imported_ = true;
   result.set_debuggable(false);
   result.raw_ptr()->load_state_ = RawLibrary::kAllocated;
   result.raw_ptr()->index_ = -1;
+  const intptr_t initial_name_cache_size = 64;

[siva, 2014/02/06 21:01:29]

const intptr_t kInitialNameCacheSize = 64;

[hausner, 2014/02/06 21:31:45]

Done.

+  result.InitResolvedNamesCache(initial_name_cache_size);
   result.InitClassDictionary();
   result.InitImportList();
   if (import_core_lib) {
     const Library& core_lib = Library::Handle(Library::CoreLibrary());
     ASSERT(!core_lib.IsNull());
     const Namespace& ns = Namespace::Handle(
         Namespace::New(core_lib, Object::null_array(), Object::null_array()));
     result.AddImport(ns);
   }
   return result.raw();
@@ skipping 54 matching lines @@
                 kNameLength,
                 "%s%d",
                 kNativeWrappersClass,
                 fld_cnt);
     cls_name = Symbols::New(name_buffer);
     Class::NewNativeWrapper(native_flds_lib, cls_name, fld_cnt);
   }
 }
 
 
+// Returns library with given url in current isolate, or NULL.
 RawLibrary* Library::LookupLibrary(const String &url) {
   Isolate* isolate = Isolate::Current();
   Library& lib = Library::Handle(isolate, Library::null());
   String& lib_url = String::Handle(isolate, String::null());
   GrowableObjectArray& libs = GrowableObjectArray::Handle(
       isolate, isolate->object_store()->libraries());
   for (int i = 0; i < libs.Length(); i++) {
     lib ^= libs.At(i);
     lib_url ^= lib.url();
     if (lib_url.Equals(url)) {
@@ skipping 8802 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart