Hash tables templates, wrapping Array.

runtime/vm/object.cc

Index: runtime/vm/object.cc
===================================================================
--- runtime/vm/object.cc	(revision 36956)
+++ runtime/vm/object.cc	(working copy)
@@ -29,6 +29,7 @@
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
 #include "vm/growable_array.h"
+#include "vm/hash_table.h"
 #include "vm/heap.h"
 #include "vm/intermediate_language.h"
 #include "vm/intrinsifier.h"
@@ -8493,9 +8494,16 @@
 }
 
 
-static intptr_t ResolvedNameCacheSize(const Array& cache) {
-  return (cache.Length() - 1) / 2;
-}
+class StringEqualsTraits {
+ public:
+  static bool IsMatch(const Object& a, const Object& b) {
+    return String::Cast(a).Equals(String::Cast(b));
+  }
+  static uword Hash(const Object& obj) {
+    return String::Cast(obj).Hash();
+  }
+};
+typedef UnorderedHashMap<StringEqualsTraits> ResolvedNamesMap;
 
 
 // Returns true if the name is found in the cache, false no cache hit.
@@ -8503,44 +8511,14 @@
 // 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;
+  ResolvedNamesMap cache(Array::Handle(resolved_names()));
+  bool present = false;
+  *obj = cache.GetOrNull(name, &present);
+  ASSERT(cache.Release() == resolved_names());

[siva, 2014/06/13 19:51:19]

Strange that you are calling Release which has a side effect in the
ASSERT that would mean no side effect in the 'release' build.

[koda, 2014/06/23 19:44:56]

Done.

+  return present;
 }
 
 
-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.
@@ -8549,45 +8527,16 @@
   if (!FLAG_use_lib_cache) {
     return;
   }
-  ASSERT(!Field::IsGetterName(name) && !Field::IsSetterName(name));
-  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();
-  }
+  ResolvedNamesMap cache(Array::Handle(resolved_names()));
+  cache.UpdateOrInsert(name, obj);
+  StorePointer(&raw_ptr()->resolved_names_, cache.Release());
 }
 
 
 void Library::InvalidateResolvedName(const String& name) const {
   Object& entry = Object::Handle();
   if (LookupResolvedNamesCache(name, &entry)) {
+    // TODO(koda): Support deleted sentinel in snapshots and remove only 'name'.
     InvalidateResolvedNamesCache();
   }
 }
@@ -9104,8 +9053,8 @@
 
 
 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));
+  Array& cache = Array::Handle(HashTables::New<ResolvedNamesMap>(size));

[siva, 2014/06/13 19:51:19]

const Array& cache = ...;

[koda, 2014/06/23 19:44:56]

Done.

+  StorePointer(&raw_ptr()->resolved_names_, cache.raw());
 }