Add an LRU cache plus hashing primitives
This patch adds a hashtable-based LRU cache. This should be
significantly higher performance than the GenerationCache it is intended
to replace. It is a large part of the fix for bug 7271109
TextLayoutCache low-level performance issues.
We added a new method to BasicHashtable to detect when rehashing is
needed, because the internal linked list pointers would get invalidated
by that rehashing.
Also, the hash_type specialized to pointers had a small flaw.
Change-Id: I950c2083f96519777b851dbe157100e0a334caec
diff --git a/libs/utils/tests/LruCache_test.cpp b/libs/utils/tests/LruCache_test.cpp
new file mode 100644
index 0000000..e573952
--- /dev/null
+++ b/libs/utils/tests/LruCache_test.cpp
@@ -0,0 +1,291 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdlib.h>
+#include <utils/JenkinsHash.h>
+#include <utils/LruCache.h>
+#include <cutils/log.h>
+#include <gtest/gtest.h>
+
+namespace android {
+
+typedef int SimpleKey;
+typedef const char* StringValue;
+
+struct ComplexKey {
+ int k;
+
+ explicit ComplexKey(int k) : k(k) {
+ instanceCount += 1;
+ }
+
+ ComplexKey(const ComplexKey& other) : k(other.k) {
+ instanceCount += 1;
+ }
+
+ ~ComplexKey() {
+ instanceCount -= 1;
+ }
+
+ bool operator ==(const ComplexKey& other) const {
+ return k == other.k;
+ }
+
+ bool operator !=(const ComplexKey& other) const {
+ return k != other.k;
+ }
+
+ static ssize_t instanceCount;
+};
+
+ssize_t ComplexKey::instanceCount = 0;
+
+template<> inline hash_t hash_type(const ComplexKey& value) {
+ return hash_type(value.k);
+}
+
+struct ComplexValue {
+ int v;
+
+ explicit ComplexValue(int v) : v(v) {
+ instanceCount += 1;
+ }
+
+ ComplexValue(const ComplexValue& other) : v(other.v) {
+ instanceCount += 1;
+ }
+
+ ~ComplexValue() {
+ instanceCount -= 1;
+ }
+
+ static ssize_t instanceCount;
+};
+
+ssize_t ComplexValue::instanceCount = 0;
+
+typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
+
+class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
+public:
+ EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
+ ~EntryRemovedCallback() {}
+ void operator()(SimpleKey& k, StringValue& v) {
+ callbackCount += 1;
+ lastKey = k;
+ lastValue = v;
+ }
+ ssize_t callbackCount;
+ SimpleKey lastKey;
+ StringValue lastValue;
+};
+
+class LruCacheTest : public testing::Test {
+protected:
+ virtual void SetUp() {
+ ComplexKey::instanceCount = 0;
+ ComplexValue::instanceCount = 0;
+ }
+
+ virtual void TearDown() {
+ ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+ }
+
+ void assertInstanceCount(ssize_t keys, ssize_t values) {
+ if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
+ FAIL() << "Expected " << keys << " keys and " << values << " values "
+ "but there were actually " << ComplexKey::instanceCount << " keys and "
+ << ComplexValue::instanceCount << " values";
+ }
+ }
+};
+
+TEST_F(LruCacheTest, Empty) {
+ LruCache<SimpleKey, StringValue> cache(100);
+
+ EXPECT_EQ(NULL, cache.get(0));
+ EXPECT_EQ(0u, cache.size());
+}
+
+TEST_F(LruCacheTest, Simple) {
+ LruCache<SimpleKey, StringValue> cache(100);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ EXPECT_STREQ("one", cache.get(1));
+ EXPECT_STREQ("two", cache.get(2));
+ EXPECT_STREQ("three", cache.get(3));
+ EXPECT_EQ(3u, cache.size());
+}
+
+TEST_F(LruCacheTest, MaxCapacity) {
+ LruCache<SimpleKey, StringValue> cache(2);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ EXPECT_EQ(NULL, cache.get(1));
+ EXPECT_STREQ("two", cache.get(2));
+ EXPECT_STREQ("three", cache.get(3));
+ EXPECT_EQ(2u, cache.size());
+}
+
+TEST_F(LruCacheTest, RemoveLru) {
+ LruCache<SimpleKey, StringValue> cache(100);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ cache.removeOldest();
+ EXPECT_EQ(NULL, cache.get(1));
+ EXPECT_STREQ("two", cache.get(2));
+ EXPECT_STREQ("three", cache.get(3));
+ EXPECT_EQ(2u, cache.size());
+}
+
+TEST_F(LruCacheTest, GetUpdatesLru) {
+ LruCache<SimpleKey, StringValue> cache(100);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ EXPECT_STREQ("one", cache.get(1));
+ cache.removeOldest();
+ EXPECT_STREQ("one", cache.get(1));
+ EXPECT_EQ(NULL, cache.get(2));
+ EXPECT_STREQ("three", cache.get(3));
+ EXPECT_EQ(2u, cache.size());
+}
+
+uint32_t hash_int(int x) {
+ return JenkinsHashWhiten(JenkinsHashMix(0, x));
+}
+
+TEST_F(LruCacheTest, StressTest) {
+ const size_t kCacheSize = 512;
+ LruCache<SimpleKey, StringValue> cache(512);
+ const size_t kNumKeys = 16 * 1024;
+ const size_t kNumIters = 100000;
+ char* strings[kNumKeys];
+
+ for (size_t i = 0; i < kNumKeys; i++) {
+ strings[i] = (char *)malloc(16);
+ sprintf(strings[i], "%d", i);
+ }
+
+ srandom(12345);
+ int hitCount = 0;
+ for (size_t i = 0; i < kNumIters; i++) {
+ int index = random() % kNumKeys;
+ uint32_t key = hash_int(index);
+ const char *val = cache.get(key);
+ if (val != NULL) {
+ EXPECT_EQ(strings[index], val);
+ hitCount++;
+ } else {
+ cache.put(key, strings[index]);
+ }
+ }
+ size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys;
+ EXPECT_LT(int(expectedHitCount * 0.9), hitCount);
+ EXPECT_GT(int(expectedHitCount * 1.1), hitCount);
+ EXPECT_EQ(kCacheSize, cache.size());
+
+ for (size_t i = 0; i < kNumKeys; i++) {
+ free((void *)strings[i]);
+ }
+}
+
+TEST_F(LruCacheTest, NoLeak) {
+ ComplexCache cache(100);
+
+ cache.put(ComplexKey(0), ComplexValue(0));
+ cache.put(ComplexKey(1), ComplexValue(1));
+ EXPECT_EQ(2, cache.size());
+ assertInstanceCount(2, 3); // the null value counts as an instance
+}
+
+TEST_F(LruCacheTest, Clear) {
+ ComplexCache cache(100);
+
+ cache.put(ComplexKey(0), ComplexValue(0));
+ cache.put(ComplexKey(1), ComplexValue(1));
+ EXPECT_EQ(2, cache.size());
+ assertInstanceCount(2, 3);
+ cache.clear();
+ assertInstanceCount(0, 1);
+}
+
+TEST_F(LruCacheTest, ClearNoDoubleFree) {
+ {
+ ComplexCache cache(100);
+
+ cache.put(ComplexKey(0), ComplexValue(0));
+ cache.put(ComplexKey(1), ComplexValue(1));
+ EXPECT_EQ(2, cache.size());
+ assertInstanceCount(2, 3);
+ cache.removeOldest();
+ cache.clear();
+ assertInstanceCount(0, 1);
+ }
+ assertInstanceCount(0, 0);
+}
+
+TEST_F(LruCacheTest, ClearReuseOk) {
+ ComplexCache cache(100);
+
+ cache.put(ComplexKey(0), ComplexValue(0));
+ cache.put(ComplexKey(1), ComplexValue(1));
+ EXPECT_EQ(2, cache.size());
+ assertInstanceCount(2, 3);
+ cache.clear();
+ assertInstanceCount(0, 1);
+ cache.put(ComplexKey(0), ComplexValue(0));
+ cache.put(ComplexKey(1), ComplexValue(1));
+ EXPECT_EQ(2, cache.size());
+ assertInstanceCount(2, 3);
+}
+
+TEST_F(LruCacheTest, Callback) {
+ LruCache<SimpleKey, StringValue> cache(100);
+ EntryRemovedCallback callback;
+ cache.setOnEntryRemovedListener(&callback);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ EXPECT_EQ(3, cache.size());
+ cache.removeOldest();
+ EXPECT_EQ(1, callback.callbackCount);
+ EXPECT_EQ(1, callback.lastKey);
+ EXPECT_STREQ("one", callback.lastValue);
+}
+
+TEST_F(LruCacheTest, CallbackOnClear) {
+ LruCache<SimpleKey, StringValue> cache(100);
+ EntryRemovedCallback callback;
+ cache.setOnEntryRemovedListener(&callback);
+
+ cache.put(1, "one");
+ cache.put(2, "two");
+ cache.put(3, "three");
+ EXPECT_EQ(3, cache.size());
+ cache.clear();
+ EXPECT_EQ(3, callback.callbackCount);
+}
+
+}