[v8-dev] Avoid unnecessary hashing in OrderedHashTable (issue 373323002 by [email protected])

adamk Tue, 08 Jul 2014 15:55:30 -0700

Reviewers: Michael Starzinger,

Description:
Avoid unnecessary hashing in OrderedHashTable


Add an overload of OrderedHashTable::FindEntry that takes
a hash along with the key to allow callsites which need to
re-use the hash (such as Add()) to avoid recomputing it.

On my Macbook this results in improvements on the Collections
microbenchmarks:
  Map-Collections: +4%
  Set-Collections: +5%

Please review this at https://codereview.chromium.org/373323002/

SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge

Affected files (+27, -10 lines):
  M src/objects.h
  M src/objects.cc


Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc

indexf4522db01d9e2fadba75d3e0dc9c4ffe315e1877..f65a2e7fb587175eb273d10c11801c036e58efb6100644

--- a/src/objects.cc
+++ b/src/objects.cc

@@ -16140,14 +16140,12 @@ Handle<Derived> OrderedHashTable<Derived,Iterator, entrysize>::Rehash(


 template<class Derived, class Iterator, int entrysize>
 int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(
-    Handle<Object> key) {
+    Handle<Object> key, int hash) {
   ASSERT(!IsObsolete());

   DisallowHeapAllocation no_gc;
   ASSERT(!key->IsTheHole());
-  Object* hash = key->GetHash();
-  if (hash->IsUndefined()) return kNotFound;
-  for (int entry = HashToEntry(Smi::cast(hash)->value());
+  for (int entry = HashToEntry(hash);
        entry != kNotFound;
        entry = ChainAt(entry)) {
     Object* candidate = KeyAt(entry);

@@ -16159,6 +16157,16 @@ int OrderedHashTable<Derived, Iterator,entrysize>::FindEntry(



 template<class Derived, class Iterator, int entrysize>
+int OrderedHashTable<Derived, Iterator, entrysize>::FindEntry(
+    Handle<Object> key) {
+  DisallowHeapAllocation no_gc;
+  Object* hash = key->GetHash();
+  if (!hash->IsSmi()) return kNotFound;
+  return FindEntry(key, Smi::cast(hash)->value());
+}
+
+
+template<class Derived, class Iterator, int entrysize>
 int OrderedHashTable<Derived, Iterator, entrysize>::AddEntry(int hash) {
   ASSERT(!IsObsolete());

@@ -16208,6 +16216,9 @@ OrderedHashTable<OrderedHashSet, JSSetIterator,1>::Remove(


 template int
 OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(
+    Handle<Object> key, int hash);
+template int
+OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(
     Handle<Object> key);

 template int

@@ -16239,6 +16250,9 @@ OrderedHashTable<OrderedHashMap, JSMapIterator,2>::Remove(


 template int
 OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::FindEntry(
+    Handle<Object> key, int hash);
+template int
+OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::FindEntry(
     Handle<Object> key);

 template int

@@ -16255,12 +16269,12 @@ bool OrderedHashSet::Contains(Handle<Object> key){


 Handle<OrderedHashSet> OrderedHashSet::Add(Handle<OrderedHashSet> table,
                                            Handle<Object> key) {
-  if (table->FindEntry(key) != kNotFound) return table;
+  int hash = GetOrCreateHash(table->GetIsolate(), key)->value();
+  if (table->FindEntry(key, hash) != kNotFound) return table;

   table = EnsureGrowable(table);

-  Handle<Smi> hash = GetOrCreateHash(table->GetIsolate(), key);
-  int index = table->AddEntry(hash->value());
+  int index = table->AddEntry(hash);
   table->set(index, *key);
   return table;
 }

@@ -16279,7 +16293,8 @@ Handle<OrderedHashMap>OrderedHashMap::Put(Handle<OrderedHashMap> table,

                                            Handle<Object> value) {
   ASSERT(!key->IsTheHole());

-  int entry = table->FindEntry(key);
+  int hash = GetOrCreateHash(table->GetIsolate(), key)->value();
+  int entry = table->FindEntry(key, hash);

   if (entry != kNotFound) {
     table->set(table->EntryToIndex(entry) + kValueOffset, *value);

@@ -16288,8 +16303,7 @@ Handle<OrderedHashMap>OrderedHashMap::Put(Handle<OrderedHashMap> table,


   table = EnsureGrowable(table);

-  Handle<Smi> hash = GetOrCreateHash(table->GetIsolate(), key);
-  int index = table->AddEntry(hash->value());
+  int index = table->AddEntry(hash);
   table->set(index, *key);
   table->set(index + kValueOffset, *value);
   return table;
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h

indexa5a312bd9cb16ba060e756404bbe103ce7de3f7a..ab40007f2228ae5f641a0e8589f32ceea30506f7100644

--- a/src/objects.h
+++ b/src/objects.h
@@ -4351,6 +4351,9 @@ class OrderedHashTable: public FixedArray {
       bool* was_present);

   // Returns kNotFound if the key isn't present.
+  int FindEntry(Handle<Object> key, int hash);
+
+  // Like the above, but doesn't require the caller to provide a hash.
   int FindEntry(Handle<Object> key);

   int NumberOfElements() {


--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev

---You received this message because you are subscribed to the Google Groups "v8-dev" group.

To unsubscribe from this group and stop receiving emails from it, send an email 
to [email protected].
For more options, visit https://groups.google.com/d/optout.

[v8-dev] Avoid unnecessary hashing in OrderedHashTable (issue 373323002 by [email protected])

Reply via email to