Changed hash table to use more of the hash value when probing.

src/objects.cc

Index: src/objects.cc
===================================================================
--- src/objects.cc	(revision 2481)
+++ src/objects.cc	(working copy)
@@ -6502,7 +6502,8 @@
 Object* HashTable<Shape, Key>::Allocate(
     int at_least_space_for) {
   int capacity = RoundUpToPowerOf2(at_least_space_for);
-  if (capacity < 4) capacity = 4;  // Guarantee min capacity.
+  static const int kMinCapacity = 16;
+  if (capacity < kMinCapacity) capacity = kMinCapacity;
   Object* obj = Heap::AllocateHashTable(EntryToIndex(capacity));
   if (!obj->IsFailure()) {
     HashTable::cast(obj)->SetNumberOfElements(0);
@@ -6516,26 +6517,25 @@
 // Find entry for key otherwise return -1.
 template<typename Shape, typename Key>
 int HashTable<Shape, Key>::FindEntry(Key key) {
-  uint32_t nof = NumberOfElements();
-  if (nof == 0) return kNotFound;  // Bail out if empty.
-
-  uint32_t capacity = Capacity();
+  uint32_t mask = Capacity() - 1;
   uint32_t hash = Shape::Hash(key);
-  uint32_t entry = GetProbe(hash, 0, capacity);
 
-  Object* element = KeyAt(entry);
-  uint32_t passed_elements = 0;
-  if (!element->IsNull()) {
-    if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
-    if (++passed_elements == nof) return kNotFound;
+  // For the first probes rotate the hash to ensure a proper spread.
+  for (uint32_t i = 0; i < kNofFastProbes; i++) {
+    int entry = hash & mask;
+    Object* element = KeyAt(entry);
+    if (element->IsUndefined()) return kNotFound;
+    if (!element->IsNull() && Shape::IsMatch(key, element)) return entry;
+    hash = RotateRight(hash, kHashRotateShift);
   }
-  for (uint32_t i = 1; !element->IsUndefined(); i++) {
-    entry = GetProbe(hash, i, capacity);
-    element = KeyAt(entry);
-    if (!element->IsNull()) {
-      if (!element->IsUndefined() && Shape::IsMatch(key, element)) return entry;
-      if (++passed_elements == nof) return kNotFound;
-    }
+
+
+  // In this unlikely event, do a linear scan.
+  for (uint32_t i = 1; i <= mask; i++) {
+    int entry = ++hash & mask;
+    Object* element = KeyAt(entry);
+    if (element->IsUndefined()) return kNotFound;
+    if (!element->IsNull() && Shape::IsMatch(key, element)) return entry;
   }
   return kNotFound;
 }
@@ -6546,7 +6546,7 @@
   int capacity = Capacity();
   int nof = NumberOfElements() + n;
   // Make sure 50% is free
-  if (nof + (nof >> 1) <= capacity) return this;
+  if (nof + (nof>>1) <= capacity) return this;

[Kasper Lund, 2009/07/16 12:41:43]

Why did you remove the whitespace here?

[bak, 2009/07/16 12:52:41]

Too old to remember. I've added the missing spaces.

 
   Object* obj = Allocate(nof * 2);
   if (obj->IsFailure()) return obj;
@@ -6579,15 +6579,23 @@
 
 template<typename Shape, typename Key>
 uint32_t HashTable<Shape, Key>::FindInsertionEntry(uint32_t hash) {
-  uint32_t capacity = Capacity();
-  uint32_t entry = GetProbe(hash, 0, capacity);
-  Object* element = KeyAt(entry);
+  uint32_t mask = Capacity() - 1;
+  int entry;
+  Object* element;
 
-  for (uint32_t i = 1; !(element->IsUndefined() || element->IsNull()); i++) {
-    entry = GetProbe(hash, i, capacity);
+  // For the first probes rotate the hash to ensure a proper spread.
+  for (uint32_t i = 0; i < kNofFastProbes; i++) {
+    entry = hash & mask;
     element = KeyAt(entry);
+    if (element->IsUndefined() || element->IsNull()) return entry;
+    hash = RotateRight(hash, kHashRotateShift);
   }
 
+  do {
+    entry = ++hash & mask;
+    element = KeyAt(entry);
+  } while(!(element->IsUndefined() || element->IsNull()));
+
   return entry;
 }
 
@@ -6666,6 +6674,10 @@
 template
 int Dictionary<StringDictionaryShape, String*>::NumberOfEnumElements();
 
+template
+int HashTable<NumberDictionaryShape, uint32_t>::FindEntry(uint32_t key);
+
+
 // Collates undefined and unexisting elements below limit from position
 // zero of the elements. The object stays in Dictionary mode.
 Object* JSObject::PrepareSlowElementsForSort(uint32_t limit) {
@@ -7021,7 +7033,7 @@
   uint32_t HashForObject(Object* obj) {
     FixedArray* symbols = FixedArray::cast(obj);
     int len = symbols->length();
-    uint32_t hash = 0;
+    uint32_t hash = 40617523; // In case the array is empty.
     for (int i = 0; i < len; i++) {
       hash ^= String::cast(symbols->get(i))->Hash();
     }