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

src/arm/ic-arm.cc

 // Copyright 2006-2008 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 85 matching lines @@
   __ ldr(r3, FieldMemOperand(t0, kCapacityOffset));
   __ mov(r3, Operand(r3, ASR, kSmiTagSize));  // convert smi to int
   __ sub(r3, r3, Operand(1));
 
   const int kElementsStartOffset =
       Array::kHeaderSize + StringDictionary::kElementsStartIndex * kPointerSize;
 
   // Generate an unrolled loop that performs a few probes before
   // giving up. Measurements done on Gmail indicate that 2 probes
   // cover ~93% of loads from dictionaries.
-  static const int kProbes = 4;
-  for (int i = 0; i < kProbes; i++) {
-    // Compute the masked index: (hash + i + i * i) & mask.
+  static const uint32_t kProbes =
+      HashTable<StringDictionaryShape, String*>::kNofFastProbes;
+  static const uint32_t kShift =
+      HashTable<StringDictionaryShape, String*>::kHashRotateShift;
+
+  for (uint32_t i = 0; i < kProbes; i++) {
+    // Compute the masked index.
     __ ldr(t1, FieldMemOperand(r2, String::kLengthOffset));
     __ mov(t1, Operand(t1, LSR, String::kHashShift));
-    if (i > 0) {
-      __ add(t1, t1, Operand(StringDictionary::GetProbeOffset(i)));
-    }
-    __ and_(t1, t1, Operand(r3));
+    __ and_(t1, r3, Operand(t1, ROR, (kShift * i) % kBitsPerInt));

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

Maybe this needs to be guarded with something like i > 0, becuase I'm not sure
ROR is legal with a count of zero on ARM.

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

Fixed, good catch.

 
     // Scale the index by multiplying by the element size.
     ASSERT(StringDictionary::kEntrySize == 3);
     __ add(t1, t1, Operand(t1, LSL, 1));  // t1 = t1 * 3
 
     // Check if the key is identical to the name.
     __ add(t1, t0, Operand(t1, LSL, 2));
     __ ldr(ip, FieldMemOperand(t1, kElementsStartOffset));
     __ cmp(r2, Operand(ip));
     if (i != kProbes - 1) {
@@ skipping 683 matching lines @@
 
   // Perform tail call to the entry.
   __ TailCallRuntime(f, 3);
 }
 
 
 #undef __
 
 
 } }  // namespace v8::internal