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

src/objects.cc

 // Copyright 2006-2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 6484 matching lines @@
   IteratePointers(v,
                   kElementsStartOffset,
                   kHeaderSize + length() * kPointerSize);
 }
 
 
 template<typename Shape, typename Key>
 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);
     HashTable::cast(obj)->SetCapacity(capacity);
   }
   return obj;
 }
 
 
 
 // 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 mask = Capacity() - 1;
+  uint32_t hash = Shape::Hash(key);
 
-  uint32_t capacity = Capacity();
-  uint32_t hash = Shape::Hash(key);
-  uint32_t entry = GetProbe(hash, 0, capacity);
+  // 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);
+  }
 
-  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 (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;
 }
 
 
 template<typename Shape, typename Key>
 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
   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;
   HashTable* table = HashTable::cast(obj);
   WriteBarrierMode mode = table->GetWriteBarrierMode();
 
   // Copy prefix to new array.
   for (int i = kPrefixStartIndex;
        i < kPrefixStartIndex + Shape::kPrefixSize;
        i++) {
@@ skipping 12 matching lines @@
       }
     }
   }
   table->SetNumberOfElements(NumberOfElements());
   return table;
 }
 
 
 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;
 }
 
 // Force instantiation of template instances class.
 // Please note this list is compiler dependent.
 
 template class HashTable<SymbolTableShape, HashTableKey*>;
 
 template class HashTable<CompilationCacheShape, HashTableKey*>;
 
@@ skipping 58 matching lines @@
 
 template Object* Dictionary<StringDictionaryShape, String*>::AddEntry(
     String*, Object*, PropertyDetails, uint32_t);
 
 template
 int Dictionary<NumberDictionaryShape, uint32_t>::NumberOfEnumElements();
 
 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) {
   ASSERT(!HasFastElements());
   // Must stay in dictionary mode, either because of requires_slow_elements,
   // or because we are not going to sort (and therefore compact) all of the
   // elements.
   NumberDictionary* dict = element_dictionary();
   HeapNumber* result_double = NULL;
   if (limit > static_cast<uint32_t>(Smi::kMaxValue)) {
@@ skipping 335 matching lines @@
       if (o->get(i) != symbols_->get(i)) return false;
     }
     return true;
   }
 
   uint32_t Hash() { return HashForObject(symbols_); }
 
   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();
     }
     return hash;
   }
 
   Object* AsObject() { return symbols_; }
 
  private:
   FixedArray* symbols_;
@@ skipping 712 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal