Tweak validate() to check less as the size of the hash grows.

src/core/SkTDynamicHash.h

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTDynamicHash_DEFINED
 #define SkTDynamicHash_DEFINED
 
@@ skipping 32 matching lines @@
             index = this->nextIndex(index, round);
         }
         SkASSERT(fCapacity == 0);
         return NULL;
     }
 
     // Add an entry with this key.  We require that no entry with newEntry's key is already present.
     void add(T* newEntry) {
         SkASSERT(NULL == this->find(GetKey(*newEntry)));
         this->maybeGrow();
-        SkASSERT(this->validate());
         this->innerAdd(newEntry);
         SkASSERT(this->validate());
     }
 
     // Remove the entry with this key.  We reqire that an entry with this key is present.
     void remove(const Key& key) {
         SkASSERT(NULL != this->find(key));
         this->innerRemove(key);
         SkASSERT(this->validate());
     }
@@ skipping 17 matching lines @@
         return 0;
     }
 
 private:
     // We have two special values to indicate an empty or deleted entry.
     static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
     static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
 
     bool validate() const {
         #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
+        static const int kLarge = 50;  // Arbitrary, tweak to suit your patience.
 
+        // O(1) checks, always done.
         // Is capacity sane?
         SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
 
-        // Is fCount correct?
-        int count = 0;
-        for (int i = 0; i < fCapacity; i++) {
-            if (Empty() != fArray[i] && Deleted() != fArray[i]) {
+        // O(N) checks, skipped when very large.
+        // Are fCount and fDeleted correct, and are all elements findable?
+        int count = 0, deleted = 0;
+        for (int i = 0; i < fCapacity && fCount < kLarge * kLarge; i++) {
+            if (Deleted() == fArray[i]) {
+                deleted++;
+            } else if (Empty() != fArray[i]) {
                 count++;
+                SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])));
             }
         }
         SKTDYNAMICHASH_CHECK(count == fCount);

[bsalomon, 2014/01/16 15:54:48]

won't this fail if fCount is very large?

[mtklein, 2014/01/16 16:01:45]

How large?  count and fCount are both ints (as are fCapacity and fDeleted), so
they should fit at least 2B entries before we have a problem.  If we ever make a
hash table with 2B entries, I'd be quite surprised: even if we were just mapping
ints to ints, that's 16G of RAM consumed by one table.

-
-        // Is fDeleted correct?
-        int deleted = 0;
-        for (int i = 0; i < fCapacity; i++) {
-            if (Deleted() == fArray[i]) {
-                deleted++;
-            }
-        }
         SKTDYNAMICHASH_CHECK(deleted == fDeleted);
 
-        // Are all entries findable?
-        for (int i = 0; i < fCapacity; i++) {
+        // O(N^2) checks, skipped when large.
+        // Are all entries unique?
+        for (int i = 0; i < fCapacity && fCount < kLarge; i++) {
             if (Empty() == fArray[i] || Deleted() == fArray[i]) {
                 continue;
             }
-            SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])));
-        }
-
-        // Are all entries unique?
-        for (int i = 0; i < fCapacity; i++) {
-            if (Empty() == fArray[i] || Deleted() == fArray[i]) {
-                continue;
-            }
             for (int j = i+1; j < fCapacity; j++) {
                 if (Empty() == fArray[j] || Deleted() == fArray[j]) {
                     continue;
                 }
                 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
                 SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
                 SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
             }
         }
         #undef SKTDYNAMICHASH_CHECK
@@ skipping 71 matching lines @@
         return (index + round + 1) & this->hashMask();
     }
 
     int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
     int fDeleted;   // Number of Deleted() entries in fArray.
     int fCapacity;  // Number of entries in fArray.  Always a power of 2.
     T** fArray;
 };
 
 #endif