From c274f8f942bf756fc78ab01992aecb855231f9e3 Mon Sep 17 00:00:00 2001 From: Florin Malita Date: Wed, 18 Apr 2018 16:57:32 -0400 Subject: 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 Commit-Queue: Florin Malita --- tests/DynamicHashTest.cpp | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) (limited to 'tests/DynamicHashTest.cpp') 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 }; -- cgit v1.2.3