Revision: 22308
Author: [email protected]
Date: Wed Jul 9 16:19:53 2014 UTC
Log: 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%
[email protected]
Review URL: https://codereview.chromium.org/373323002
http://code.google.com/p/v8/source/detail?r=22308
Modified:
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/objects.cc Wed Jul 9 11:08:26 2014 UTC
+++ /branches/bleeding_edge/src/objects.cc Wed Jul 9 16:19:53 2014 UTC
@@ -16138,17 +16138,14 @@
}
-template<class Derived, class Iterator, int entrysize>
+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());
- entry != kNotFound;
+ for (int entry = HashToEntry(hash); entry != kNotFound;
entry = ChainAt(entry)) {
Object* candidate = KeyAt(entry);
if (candidate->SameValueZero(*key))
@@ -16158,7 +16155,17 @@
}
-template<class Derived, class Iterator, int entrysize>
+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());
@@ -16206,8 +16213,9 @@
OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::Remove(
Handle<OrderedHashSet> table, Handle<Object> key, bool* was_present);
-template int
-OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(
+template int OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(
+ Handle<Object> key, int hash);
+template int OrderedHashTable<OrderedHashSet, JSSetIterator, 1>::FindEntry(
Handle<Object> key);
template int
@@ -16237,8 +16245,9 @@
OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::Remove(
Handle<OrderedHashMap> table, Handle<Object> key, bool* was_present);
-template int
-OrderedHashTable<OrderedHashMap, JSMapIterator, 2>::FindEntry(
+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 +16264,12 @@
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 +16288,8 @@
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 +16298,7 @@
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;
=======================================
--- /branches/bleeding_edge/src/objects.h Wed Jul 9 11:08:26 2014 UTC
+++ /branches/bleeding_edge/src/objects.h Wed Jul 9 16:19:53 2014 UTC
@@ -4362,6 +4362,9 @@
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.
