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/Android.mk b/libs/utils/Android.mk
index c9f8fd4..73a98d5 100644
--- a/libs/utils/Android.mk
+++ b/libs/utils/Android.mk
@@ -25,6 +25,7 @@
Debug.cpp \
FileMap.cpp \
Flattenable.cpp \
+ JenkinsHash.cpp \
LinearTransform.cpp \
Log.cpp \
PropertyMap.cpp \
diff --git a/libs/utils/BasicHashtable.cpp b/libs/utils/BasicHashtable.cpp
index fb8ec9f..fd51b7b 100644
--- a/libs/utils/BasicHashtable.cpp
+++ b/libs/utils/BasicHashtable.cpp
@@ -80,7 +80,7 @@
SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets);
if (sb->onlyOwner()) {
destroyBuckets(mBuckets, mBucketCount);
- for (size_t i = 0; i < mSize; i++) {
+ for (size_t i = 0; i < mBucketCount; i++) {
Bucket& bucket = bucketAt(mBuckets, i);
bucket.cookie = 0;
}
diff --git a/libs/utils/JenkinsHash.cpp b/libs/utils/JenkinsHash.cpp
new file mode 100644
index 0000000..52c9bb7
--- /dev/null
+++ b/libs/utils/JenkinsHash.cpp
@@ -0,0 +1,64 @@
+/*
+ * 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.
+ */
+
+/* Implementation of Jenkins one-at-a-time hash function. These choices are
+ * optimized for code size and portability, rather than raw speed. But speed
+ * should still be quite good.
+ **/
+
+#include <utils/JenkinsHash.h>
+
+namespace android {
+
+hash_t JenkinsHashWhiten(uint32_t hash) {
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+ return hash;
+}
+
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size) {
+ hash = JenkinsHashMix(hash, (uint32_t)size);
+ size_t i;
+ for (i = 0; i < (size & -4); i += 4) {
+ uint32_t data = bytes[i] | (bytes[i+1] << 8) | (bytes[i+2] << 16) | (bytes[i+3] << 24);
+ hash = JenkinsHashMix(hash, data);
+ }
+ if (size & 3) {
+ uint32_t data = bytes[i];
+ data |= ((size & 3) > 1) ? (bytes[i+1] << 8) : 0;
+ data |= ((size & 3) > 2) ? (bytes[i+2] << 16) : 0;
+ hash = JenkinsHashMix(hash, data);
+ }
+ return hash;
+}
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size) {
+ hash = JenkinsHashMix(hash, (uint32_t)size);
+ size_t i;
+ for (i = 0; i < (size & -2); i += 2) {
+ uint32_t data = shorts[i] | (shorts[i+1] << 16);
+ hash = JenkinsHashMix(hash, data);
+ }
+ if (size & 1) {
+ uint32_t data = shorts[i];
+ hash = JenkinsHashMix(hash, data);
+ }
+ return hash;
+}
+
+}
+
diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk
index 5b2b5b1..a2ca9c8 100644
--- a/libs/utils/tests/Android.mk
+++ b/libs/utils/tests/Android.mk
@@ -7,6 +7,7 @@
BasicHashtable_test.cpp \
BlobCache_test.cpp \
Looper_test.cpp \
+ LruCache_test.cpp \
String8_test.cpp \
Unicode_test.cpp \
Vector_test.cpp \
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);
+}
+
+}