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/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h
index fdf9738..7a6c96c 100644
--- a/include/utils/BasicHashtable.h
+++ b/include/utils/BasicHashtable.h
@@ -328,6 +328,14 @@
BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
}
+ /* Determines whether there is room to add another entry without rehashing.
+ * When this returns true, a subsequent add() operation is guaranteed to
+ * complete without performing a rehash.
+ */
+ inline bool hasMoreRoom() const {
+ return mCapacity > mFilledBuckets;
+ }
+
protected:
static inline const TEntry& entryFor(const Bucket& bucket) {
return reinterpret_cast<const TEntry&>(bucket.entry);
diff --git a/include/utils/JenkinsHash.h b/include/utils/JenkinsHash.h
new file mode 100644
index 0000000..e964e6f
--- /dev/null
+++ b/include/utils/JenkinsHash.h
@@ -0,0 +1,44 @@
+/*
+ * 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/TypeHelpers.h>
+
+namespace android {
+
+/* The Jenkins hash of a sequence of 32 bit words A, B, C is:
+ * Whiten(Mix(Mix(Mix(0, A), B), C)) */
+
+inline uint32_t JenkinsHashMix(uint32_t hash, uint32_t data) {
+ hash += data;
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ return hash;
+}
+
+hash_t JenkinsHashWhiten(uint32_t hash);
+
+/* Helpful utility functions for hashing data in 32 bit chunks */
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size);
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size);
+
+}
+
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
new file mode 100644
index 0000000..af39315
--- /dev/null
+++ b/include/utils/LruCache.h
@@ -0,0 +1,199 @@
+/*
+ * 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 <utils/BasicHashtable.h>
+#include <utils/GenerationCache.h>
+#include <utils/UniquePtr.h>
+
+namespace android {
+
+// OnEntryRemoved is defined in GenerationCache.h, but maybe should move here.
+
+template <typename TKey, typename TValue>
+class LruCache {
+public:
+ explicit LruCache(uint32_t maxCapacity);
+
+ enum Capacity {
+ kUnlimitedCapacity,
+ };
+
+ void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
+ size_t size() const;
+ const TValue& get(const TKey& key);
+ bool put(const TKey& key, const TValue& value);
+ bool remove(const TKey& key);
+ bool removeOldest();
+ void clear();
+
+private:
+ LruCache(const LruCache& that); // disallow copy constructor
+
+ struct Entry {
+ TKey key;
+ TValue value;
+ Entry* parent;
+ Entry* child;
+
+ Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
+ }
+ const TKey& getKey() const { return key; }
+ };
+
+ void attachToCache(Entry& entry);
+ void detachFromCache(Entry& entry);
+ void rehash(size_t newCapacity);
+
+ UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+ OnEntryRemoved<TKey, TValue>* mListener;
+ Entry* mOldest;
+ Entry* mYoungest;
+ uint32_t mMaxCapacity;
+ TValue mNullValue;
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
+ mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
+ mListener(NULL) {
+};
+
+template<typename K, typename V>
+void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+ mListener = listener;
+}
+
+template <typename TKey, typename TValue>
+size_t LruCache<TKey, TValue>::size() const {
+ return mTable->size();
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
+ hash_t hash = hash_type(key);
+ ssize_t index = mTable->find(-1, hash, key);
+ if (index == -1) {
+ return mNullValue;
+ }
+ Entry& entry = mTable->editEntryAt(index);
+ detachFromCache(entry);
+ attachToCache(entry);
+ return entry.value;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
+ if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
+ removeOldest();
+ }
+
+ hash_t hash = hash_type(key);
+ ssize_t index = mTable->find(-1, hash, key);
+ if (index >= 0) {
+ return false;
+ }
+ if (!mTable->hasMoreRoom()) {
+ rehash(mTable->capacity() * 2);
+ }
+
+ // Would it be better to initialize a blank entry and assign key, value?
+ Entry initEntry(key, value);
+ index = mTable->add(hash, initEntry);
+ Entry& entry = mTable->editEntryAt(index);
+ attachToCache(entry);
+ return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::remove(const TKey& key) {
+ hash_t hash = hash_type(key);
+ ssize_t index = mTable->find(-1, hash, key);
+ if (index < 0) {
+ return false;
+ }
+ Entry& entry = mTable->editEntryAt(index);
+ if (mListener) {
+ (*mListener)(entry.key, entry.value);
+ }
+ detachFromCache(entry);
+ mTable->removeAt(index);
+ return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::removeOldest() {
+ if (mOldest != NULL) {
+ return remove(mOldest->key);
+ // TODO: should probably abort if false
+ }
+ return false;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::clear() {
+ if (mListener) {
+ for (Entry* p = mOldest; p != NULL; p = p->child) {
+ (*mListener)(p->key, p->value);
+ }
+ }
+ mYoungest = NULL;
+ mOldest = NULL;
+ mTable->clear();
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
+ if (mYoungest == NULL) {
+ mYoungest = mOldest = &entry;
+ } else {
+ entry.parent = mYoungest;
+ mYoungest->child = &entry;
+ mYoungest = &entry;
+ }
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
+ if (entry.parent != NULL) {
+ entry.parent->child = entry.child;
+ } else {
+ mOldest = entry.child;
+ }
+ if (entry.child != NULL) {
+ entry.child->parent = entry.parent;
+ } else {
+ mYoungest = entry.parent;
+ }
+
+ entry.parent = NULL;
+ entry.child = NULL;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
+ UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
+ Entry* oldest = mOldest;
+
+ mOldest = NULL;
+ mYoungest = NULL;
+ mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
+ for (Entry* p = oldest; p != NULL; p = p->child) {
+ put(p->key, p->value);
+ }
+}
+
+}
diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h
index 2bf33c3..13c9081 100644
--- a/include/utils/TypeHelpers.h
+++ b/include/utils/TypeHelpers.h
@@ -291,7 +291,7 @@
ANDROID_REINTERPRET_HASH(float, uint32_t)
ANDROID_REINTERPRET_HASH(double, uint64_t)
-template <typename T> inline hash_t hash_type(const T*& value) {
+template <typename T> inline hash_t hash_type(T* const & value) {
return hash_type(uintptr_t(value));
}