- Avoid calling % in a loop when probing.

runtime/vm/hash_table.h

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_HASH_TABLE_H_
 #define VM_HASH_TABLE_H_
 
 // Temporarily used when sorting the indices in EnumIndexHashTable.
 // TODO(koda): Remove these dependencies before using in production.
 #include <map>
@@ skipping 133 matching lines @@
 
   // Returns whether 'key' matches any key in the table.
   template<typename Key>
   bool ContainsKey(const Key& key) const {
     return FindKey(key) != -1;
   }
 
   // Returns the entry that matches 'key', or -1 if none exists.
   template<typename Key>
   intptr_t FindKey(const Key& key) const {
-    ASSERT(NumOccupied() < NumEntries());
+    const intptr_t num_entries = NumEntries();
+    ASSERT(NumOccupied() < num_entries);
     // TODO(koda): Add salt.
-    intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries();
+    uword hash = KeyTraits::Hash(key);
+    intptr_t probe = hash % num_entries;
     // TODO(koda): Consider quadratic probing.
-    for (; ; probe = (probe + 1) % NumEntries()) {
+    while (true) {
       if (IsUnused(probe)) {
         return -1;
-      } else if (IsDeleted(probe)) {
-        continue;
-      } else {
+      } else if (!IsDeleted(probe)) {
         key_handle_ = GetKey(probe);
         if (KeyTraits::IsMatch(key, key_handle_)) {
           return probe;
         }
       }
+      // Advance probe.
+      probe++;
+      probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
     return -1;
   }
 
   // Sets *entry to either:
   // - an occupied entry matching 'key', and returns true, or
   // - an unused/deleted entry where a matching key may be inserted,
   //   and returns false.
   template<typename Key>
   bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const {
+    const intptr_t num_entries = NumEntries();
     ASSERT(entry != NULL);
-    ASSERT(NumOccupied() < NumEntries());
-    intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries();
+    ASSERT(NumOccupied() < num_entries);
+    uword hash = KeyTraits::Hash(key);
+    intptr_t probe = hash % num_entries;
     intptr_t deleted = -1;
     // TODO(koda): Consider quadratic probing.
-    for (; ; probe = (probe + 1) % NumEntries()) {
+    while (true) {
       if (IsUnused(probe)) {
         *entry = (deleted != -1) ? deleted : probe;
         return false;
       } else if (IsDeleted(probe)) {
         if (deleted == -1) {
           deleted = probe;
         }
       } else {
         key_handle_ = GetKey(probe);
         if (KeyTraits::IsMatch(key, key_handle_)) {
           *entry = probe;
           return true;
         }
       }
+      // Advance probe.
+      probe++;
+      probe = (probe == num_entries) ? 0 : probe;
     }
     UNREACHABLE();
     return false;
   }
 
   // Sets the key of a previously unoccupied entry. This must not be the last
   // unoccupied entry.
   void InsertKey(intptr_t entry, const Object& key) const {
     ASSERT(!IsOccupied(entry));
     AdjustSmiValueAt(kOccupiedEntriesIndex, 1);
@@ skipping 493 matching lines @@
 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > {
  public:
   typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet;
   explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {}
   EnumIndexHashSet(Zone* zone, RawArray* data) : BaseSet(zone, data) {}
 };
 
 }  // namespace dart
 
 #endif  // VM_HASH_TABLE_H_