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);
+    }
+  }
+  AddToResolvedNamesCache(name, obj);
+  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);
+      AddToResolvedNamesCache(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::AddToResolvedNamesCache(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 as a counter
+  // 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);
 }
 
 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 kInitialNameCacheSize = 64;
+  result.InitResolvedNamesCache(kInitialNameCacheSize);
   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