Prevent unnecessary/unbounded growth of SkTDynamicHash capacity

SkTDynamicHash doesn't immediately recycle slots for removed entries,
but instead just marks them as deleted.

The only way to reclaim deleted slots currently is when an exponential
grow/resize is triggered.

A consequence of this is that the capacity/allocated storage can grow
indefinitely when the hash is long-lived and churning -- even if the
number of active entries is small/stable.

To prevent this, I propose we only grow the capacity when the number of
active slots constitutes a significant portion.  Otherwise (when most
slots are deleted), we trigger a "purge" (resize to the same capacity)
to clear the tombstones.

Bug: chromium:832482
Change-Id: Iefdcd7439f7d62ac021e176b71007d207c8bc876
Reviewed-on: https://skia-review.googlesource.com/122082
Reviewed-by: Mike Klein <mtklein@chromium.org>
Commit-Queue: Florin Malita <fmalita@chromium.org>

2 files changed, 42 insertions, 1 deletions

diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index b144d18d48..77d020fa39 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -242,7 +242,16 @@ private:
 
     void maybeGrow() {
         if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
-            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
+            auto newCapacity = fCapacity > 0 ? fCapacity : 4;
+
+            // Only grow the storage when most non-empty entries are
+            // in active use.  Otherwise, just purge the tombstones.
+            if (fCount > fDeleted) {
+                newCapacity *= 2;
+            }
+            SkASSERT(newCapacity > fCount + 1);
+
+            this->resize(newCapacity);
         }
     }
 
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
index 289b332c02..a857506fd0 100644
--- a/tests/DynamicHashTest.cpp
+++ b/tests/DynamicHashTest.cpp
@@ -63,6 +63,38 @@ DEF_TEST(DynamicHash_growth, reporter) {
     ASSERT(hash.count() == 5);
 }
 
+DEF_TEST(DynamicHash_growth_bounded, reporter) {
+    Entry a = { 1, 2.0 };
+    Entry b = { 2, 3.0 };
+    Entry c = { 3, 4.0 };
+    Entry d = { 4, 5.0 };
+    Entry e = { 5, 6.0 };
+
+    Hash hash;
+    ASSERT(hash.capacity() == 0);
+
+    hash.add(&a);
+    ASSERT(hash.capacity() == 4);
+
+    hash.remove(a.key);
+    hash.add(&b);
+    ASSERT(hash.capacity() == 4);
+
+    hash.remove(b.key);
+    hash.add(&c);
+    ASSERT(hash.capacity() == 4);
+
+    hash.remove(c.key);
+    hash.add(&d);
+    ASSERT(hash.capacity() == 4);
+
+    hash.remove(d.key);
+    hash.add(&e);
+    ASSERT(hash.capacity() == 4);
+
+    ASSERT(hash.count() == 1);
+}
+
 DEF_TEST(DynamicHash_add, reporter) {
     Hash hash;
     Entry a = { 1, 2.0 };