Speed up GrResourceCache lookup by inlining GrBinHashKey comparisons
The GCC compilers for Android and Ubuntu do not seem to be able to
inline the memcmp operations on GrBinHashKey data. Write the comparisons
manually. Also shortcut GrBinHashKey::EQ to skip comparison when hashes
do not match.
Speeds up grresourcecache_find test on ARM and x86_64. Speeds up
grresourcecache_add on x86_64.
In order to test the change, moves ad hoc Gr unit tests from
src/gr_unittest.cpp to tests/GrUnitTests to be consistent with other
tests and enables GrUnitTests.
Fixes a regression from r2863 with where re-setting GrBinHashKey data
would not set the hash correctly. This should also improve the hash
function itself. The regression caused many of the hash operations be
no-ops. This is caught by the unit test.
Renames the comparison functions that GrHashTable needs from EQ, LT to
Equals, LessThan.
Renames GrTBinHashKey to GrBinHashKey. The GrTBinHashKey used to
forward comparison functions to an ENTRY template class, which would
extract the key and call back to the GrTBinHashKey. This would save
the user from writing one comparison function when comparison was done
with int ENTRY::compare(). There's no real benefit in this now. Also
this was used only for one class (GrTextureStripAtlas). The other use
in GrResourceKey was not actually using the provided "shortcut". The
new GrBinHashKey is not templated with the entry, rather just provides
== and < functions. The users of GrTHashTable provide the needed
functions now.
Adds explicit documentation of functions that are actually needed
GrTHashTable for the Key template. Adds SK_DEBUG guards according to
the contract.
R=bsalomon@google.com, mtklein@google.com
Author: kkinnunen@nvidia.com
Review URL: https://codereview.chromium.org/88113002
git-svn-id: http://skia.googlecode.com/svn/trunk/src@12426 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gpu/GrBinHashKey.h b/gpu/GrBinHashKey.h
index 7d4aa0f..585a1a1 100644
--- a/gpu/GrBinHashKey.h
+++ b/gpu/GrBinHashKey.h
@@ -13,37 +13,19 @@
#include "GrTypes.h"
/**
- * Hash function class that can take a data chunk of any predetermined length. The hash function
- * used is the One-at-a-Time Hash (http://burtleburtle.net/bob/hash/doobs.html).
- *
- * Keys are computed from ENTRY objects. ENTRY must be fully ordered by a member:
- * int compare(const GrTBinHashKey<ENTRY, ..>& k);
- * which returns negative if the ENTRY < k, 0 if it equals k, and positive if k < the ENTRY.
- * Additionally, ENTRY must be flattenable into the key using setKeyData.
- *
- * This class satisfies the requirements to be a key for a GrTHashTable.
+ * GrBinHashKey is a hash key class that can take a data chunk of any predetermined
+ * length. The hash function used is the One-at-a-Time Hash
+ * (http://burtleburtle.net/bob/hash/doobs.html).
*/
-template<typename ENTRY, size_t KEY_SIZE>
-class GrTBinHashKey {
+template<size_t KEY_SIZE>
+class GrBinHashKey {
public:
enum { kKeySize = KEY_SIZE };
- GrTBinHashKey() {
+ GrBinHashKey() {
this->reset();
}
- GrTBinHashKey(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) {
- *this = other;
- }
-
- GrTBinHashKey<ENTRY, KEY_SIZE>& operator=(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) {
- memcpy(this, &other, sizeof(*this));
- return *this;
- }
-
- ~GrTBinHashKey() {
- }
-
void reset() {
fHash = 0;
#ifdef SK_DEBUG
@@ -52,39 +34,49 @@
}
void setKeyData(const uint32_t* SK_RESTRICT data) {
- SkASSERT(GrIsALIGN4(KEY_SIZE));
+ SK_COMPILE_ASSERT(KEY_SIZE % 4 == 0, key_size_mismatch);
memcpy(&fData, data, KEY_SIZE);
uint32_t hash = 0;
size_t len = KEY_SIZE;
while (len >= 4) {
hash += *data++;
- hash += (fHash << 10);
+ hash += (hash << 10);
hash ^= (hash >> 6);
len -= 4;
}
- hash += (fHash << 3);
- hash ^= (fHash >> 11);
- hash += (fHash << 15);
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
#ifdef SK_DEBUG
fIsValid = true;
#endif
fHash = hash;
}
- int compare(const GrTBinHashKey<ENTRY, KEY_SIZE>& key) const {
+ bool operator==(const GrBinHashKey<KEY_SIZE>& key) const {
SkASSERT(fIsValid && key.fIsValid);
- return memcmp(fData, key.fData, KEY_SIZE);
+ if (fHash != key.fHash) {
+ return false;
+ }
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fData); ++i) {
+ if (fData[i] != key.fData[i]) {
+ return false;
+ }
+ }
+ return true;
}
- static bool EQ(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) {
- SkASSERT(key.fIsValid);
- return 0 == entry.compare(key);
- }
-
- static bool LT(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) {
- SkASSERT(key.fIsValid);
- return entry.compare(key) < 0;
+ bool operator<(const GrBinHashKey<KEY_SIZE>& key) const {
+ SkASSERT(fIsValid && key.fIsValid);
+ for (size_t i = 0; i < SK_ARRAY_COUNT(fData); ++i) {
+ if (fData[i] < key.fData[i]) {
+ return true;
+ } else if (fData[i] > key.fData[i]) {
+ return false;
+ }
+ }
+ return false;
}
uint32_t getHash() const {
@@ -94,12 +86,12 @@
const uint8_t* getData() const {
SkASSERT(fIsValid);
- return fData;
+ return reinterpret_cast<const uint8_t*>(fData);
}
private:
uint32_t fHash;
- uint8_t fData[KEY_SIZE]; // Buffer for key storage
+ uint32_t fData[KEY_SIZE / sizeof(uint32_t)]; // Buffer for key storage.
#ifdef SK_DEBUG
public:
diff --git a/gpu/GrResourceCache.h b/gpu/GrResourceCache.h
index 38378ac..ca30732 100644
--- a/gpu/GrResourceCache.h
+++ b/gpu/GrResourceCache.h
@@ -54,7 +54,7 @@
}
GrResourceKey() {
- fKey.fHashedKey.reset();
+ fKey.reset();
}
void reset(const GrCacheID& id, ResourceType type, ResourceFlags flags) {
@@ -63,41 +63,34 @@
//!< returns hash value [0..kHashMask] for the key
int getHash() const {
- return fKey.fHashedKey.getHash() & kHashMask;
+ return fKey.getHash() & kHashMask;
}
bool isScratch() const {
return ScratchDomain() ==
- *reinterpret_cast<const GrCacheID::Domain*>(fKey.fHashedKey.getData() +
+ *reinterpret_cast<const GrCacheID::Domain*>(fKey.getData() +
kCacheIDDomainOffset);
}
ResourceType getResourceType() const {
- return *reinterpret_cast<const ResourceType*>(fKey.fHashedKey.getData() +
+ return *reinterpret_cast<const ResourceType*>(fKey.getData() +
kResourceTypeOffset);
}
ResourceFlags getResourceFlags() const {
- return *reinterpret_cast<const ResourceFlags*>(fKey.fHashedKey.getData() +
+ return *reinterpret_cast<const ResourceFlags*>(fKey.getData() +
kResourceFlagsOffset);
}
- int compare(const GrResourceKey& other) const {
- return fKey.fHashedKey.compare(other.fKey.fHashedKey);
- }
+ bool operator==(const GrResourceKey& other) const { return fKey == other.fKey; }
+ bool operator<(const GrResourceKey& other) const { return fKey < other.fKey; }
- static bool LT(const GrResourceKey& a, const GrResourceKey& b) {
- return a.compare(b) < 0;
- }
-
- static bool EQ(const GrResourceKey& a, const GrResourceKey& b) {
- return 0 == a.compare(b);
- }
-
- inline static bool LT(const GrResourceEntry& entry, const GrResourceKey& key);
- inline static bool EQ(const GrResourceEntry& entry, const GrResourceKey& key);
- inline static bool LT(const GrResourceEntry& a, const GrResourceEntry& b);
- inline static bool EQ(const GrResourceEntry& a, const GrResourceEntry& b);
+ static bool LessThan(const GrResourceEntry& entry, const GrResourceKey& key);
+ static bool Equals(const GrResourceEntry& entry, const GrResourceKey& key);
+#ifdef SK_DEBUG
+ static bool LessThan(const GrResourceEntry& a, const GrResourceEntry& b);
+ static bool Equals(const GrResourceEntry& a, const GrResourceEntry& b);
+#endif
private:
enum {
@@ -125,21 +118,9 @@
memcpy(k + kResourceTypeOffset, &type, sizeof(ResourceType));
memcpy(k + kResourceFlagsOffset, &flags, sizeof(ResourceFlags));
memset(k + kPadOffset, 0, kPadSize);
- fKey.fHashedKey.setKeyData(keyData.fKey32);
+ fKey.setKeyData(keyData.fKey32);
}
-
- struct Key;
- typedef GrTBinHashKey<Key, kKeySize> HashedKey;
-
- struct Key {
- int compare(const HashedKey& hashedKey) const {
- return fHashedKey.compare(hashedKey);
- }
-
- HashedKey fHashedKey;
- };
-
- Key fKey;
+ GrBinHashKey<kKeySize> fKey;
};
// The cache listens for these messages to purge junk resources proactively.
@@ -174,21 +155,23 @@
friend class GrDLinkedList;
};
-bool GrResourceKey::LT(const GrResourceEntry& entry, const GrResourceKey& key) {
- return LT(entry.key(), key);
+inline bool GrResourceKey::LessThan(const GrResourceEntry& entry, const GrResourceKey& key) {
+ return entry.key() < key;
}
-bool GrResourceKey::EQ(const GrResourceEntry& entry, const GrResourceKey& key) {
- return EQ(entry.key(), key);
+inline bool GrResourceKey::Equals(const GrResourceEntry& entry, const GrResourceKey& key) {
+ return entry.key() == key;
}
-bool GrResourceKey::LT(const GrResourceEntry& a, const GrResourceEntry& b) {
- return LT(a.key(), b.key());
+#ifdef SK_DEBUG
+inline bool GrResourceKey::LessThan(const GrResourceEntry& a, const GrResourceEntry& b) {
+ return a.key() < b.key();
}
-bool GrResourceKey::EQ(const GrResourceEntry& a, const GrResourceEntry& b) {
- return EQ(a.key(), b.key());
+inline bool GrResourceKey::Equals(const GrResourceEntry& a, const GrResourceEntry& b) {
+ return a.key() == b.key();
}
+#endif
///////////////////////////////////////////////////////////////////////////////
diff --git a/gpu/GrTHashTable.h b/gpu/GrTHashTable.h
index 3b32977..83462c7 100644
--- a/gpu/GrTHashTable.h
+++ b/gpu/GrTHashTable.h
@@ -16,8 +16,10 @@
/**
* Key needs
- * static bool EQ(const Entry&, const HashKey&);
- * static bool LT(const Entry&, const HashKey&);
+ * static bool Equals(const Entry&, const Key&);
+ * static bool LessThan(const Entry&, const Key&);
+ * static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
+ * static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
* uint32_t getHash() const;
*
* Allows duplicate key entries but on find you may get
@@ -90,7 +92,7 @@
int low = 0;
while (high > low) {
int index = (low + high) >> 1;
- if (Key::LT(*array[index], key)) {
+ if (Key::LessThan(*array[index], key)) {
low = index + 1;
} else {
high = index;
@@ -98,15 +100,15 @@
}
// check if we found it
- if (Key::EQ(*array[high], key)) {
+ if (Key::Equals(*array[high], key)) {
// above search should have found the first occurrence if there
// are multiple.
- SkASSERT(0 == high || Key::LT(*array[high - 1], key));
+ SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
return high;
}
// now return the ~ of where we should insert it
- if (Key::LT(*array[high], key)) {
+ if (Key::LessThan(*array[high], key)) {
high += 1;
}
return ~high;
@@ -119,7 +121,7 @@
int hashIndex = hash2Index(key.getHash());
T* elem = fHash[hashIndex];
- if (NULL != elem && Key::EQ(*elem, key) && filter(elem)) {
+ if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
return elem;
}
@@ -133,9 +135,9 @@
// above search should have found the first occurrence if there
// are multiple.
- SkASSERT(0 == index || Key::LT(*array[index - 1], key));
+ SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
- for ( ; index < count() && Key::EQ(*array[index], key); ++index) {
+ for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
if (filter(fSorted[index])) {
// update the hash
fHash[hashIndex] = fSorted[index];
@@ -192,8 +194,8 @@
void GrTHashTable<T, Key, kHashBits>::validate() const {
int count = fSorted.count();
for (int i = 1; i < count; i++) {
- SkASSERT(Key::LT(*fSorted[i - 1], *fSorted[i]) ||
- Key::EQ(*fSorted[i - 1], *fSorted[i]));
+ SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
+ Key::Equals(*fSorted[i - 1], *fSorted[i]));
}
}
diff --git a/gpu/GrTextStrike_impl.h b/gpu/GrTextStrike_impl.h
index 4297185..0691eaa 100644
--- a/gpu/GrTextStrike_impl.h
+++ b/gpu/GrTextStrike_impl.h
@@ -19,10 +19,10 @@
intptr_t getHash() const { return fFontScalerKey->getHash(); }
- static bool LT(const GrTextStrike& strike, const Key& key) {
+ static bool LessThan(const GrTextStrike& strike, const Key& key) {
return *strike.getFontScalerKey() < *key.fFontScalerKey;
}
- static bool EQ(const GrTextStrike& strike, const Key& key) {
+ static bool Equals(const GrTextStrike& strike, const Key& key) {
return *strike.getFontScalerKey() == *key.fFontScalerKey;
}
@@ -88,10 +88,10 @@
uint32_t getHash() const { return fPackedID; }
- static bool LT(const GrGlyph& glyph, const Key& key) {
+ static bool LessThan(const GrGlyph& glyph, const Key& key) {
return glyph.fPackedID < key.fPackedID;
}
- static bool EQ(const GrGlyph& glyph, const Key& key) {
+ static bool Equals(const GrGlyph& glyph, const Key& key) {
return glyph.fPackedID == key.fPackedID;
}
diff --git a/gpu/effects/GrTextureStripAtlas.h b/gpu/effects/GrTextureStripAtlas.h
index e56e736..e06e273 100644
--- a/gpu/effects/GrTextureStripAtlas.h
+++ b/gpu/effects/GrTextureStripAtlas.h
@@ -136,12 +136,15 @@
// Hash table entry for atlases
class AtlasEntry;
- typedef GrTBinHashKey<AtlasEntry, sizeof(GrTextureStripAtlas::Desc)> AtlasHashKey;
+ class AtlasHashKey : public GrBinHashKey<sizeof(GrTextureStripAtlas::Desc)> {
+ public:
+ static bool Equals(const AtlasEntry& entry, const AtlasHashKey& key);
+ static bool LessThan(const AtlasEntry& entry, const AtlasHashKey& key);
+ };
class AtlasEntry : public ::SkNoncopyable {
public:
AtlasEntry() : fAtlas(NULL) {}
~AtlasEntry() { SkDELETE(fAtlas); }
- int compare(const AtlasHashKey& key) const { return fKey.compare(key); }
AtlasHashKey fKey;
GrTextureStripAtlas* fAtlas;
};
@@ -178,4 +181,14 @@
SkTDArray<AtlasRow*> fKeyTable;
};
+inline bool GrTextureStripAtlas::AtlasHashKey::Equals(const AtlasEntry& entry,
+ const AtlasHashKey& key) {
+ return entry.fKey == key;
+}
+
+inline bool GrTextureStripAtlas::AtlasHashKey::LessThan(const AtlasEntry& entry,
+ const AtlasHashKey& key) {
+ return entry.fKey < key;
+}
+
#endif
diff --git a/gpu/gr_unittests.cpp b/gpu/gr_unittests.cpp
deleted file mode 100644
index ae9f67f..0000000
--- a/gpu/gr_unittests.cpp
+++ /dev/null
@@ -1,80 +0,0 @@
-
-/*
- * Copyright 2010 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "GrBinHashKey.h"
-#include "GrDrawTarget.h"
-#include "SkMatrix.h"
-#include "GrRedBlackTree.h"
-
-// FIXME: needs to be in a header
-void gr_run_unittests();
-
-// If we aren't inheriting these as #defines from elsewhere,
-// clang demands they be declared before we #include the template
-// that relies on them.
-#ifdef SK_DEBUG
-static bool LT(const int& elem, int value) {
- return elem < value;
-}
-static bool EQ(const int& elem, int value) {
- return elem == value;
-}
-#include "GrTBSearch.h"
-
-static void test_bsearch() {
- const int array[] = {
- 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99
- };
-
- for (int n = 0; n < static_cast<int>(GR_ARRAY_COUNT(array)); ++n) {
- for (int i = 0; i < n; i++) {
- int index = GrTBSearch<int, int>(array, n, array[i]);
- SkASSERT(index == (int) i);
- index = GrTBSearch<int, int>(array, n, -array[i]);
- SkASSERT(index < 0);
- }
- }
-}
-#endif
-
-// bogus empty class for GrBinHashKey
-class BogusEntry {};
-
-static void test_binHashKey()
-{
- const char* testStringA_ = "abcdABCD";
- const char* testStringB_ = "abcdBBCD";
- const uint32_t* testStringA = reinterpret_cast<const uint32_t*>(testStringA_);
- const uint32_t* testStringB = reinterpret_cast<const uint32_t*>(testStringB_);
- enum {
- kDataLenUsedForKey = 8
- };
-
- GrTBinHashKey<BogusEntry, kDataLenUsedForKey> keyA;
- keyA.setKeyData(testStringA);
- // test copy constructor and comparison
- GrTBinHashKey<BogusEntry, kDataLenUsedForKey> keyA2(keyA);
- SkASSERT(keyA.compare(keyA2) == 0);
- SkASSERT(keyA.getHash() == keyA2.getHash());
- // test re-init
- keyA2.setKeyData(testStringA);
- SkASSERT(keyA.compare(keyA2) == 0);
- SkASSERT(keyA.getHash() == keyA2.getHash());
- // test sorting
- GrTBinHashKey<BogusEntry, kDataLenUsedForKey> keyB;
- keyB.setKeyData(testStringB);
- SkASSERT(keyA.compare(keyB) < 0);
- SkASSERT(keyA.getHash() != keyB.getHash());
-}
-
-
-void gr_run_unittests() {
- SkDEBUGCODE(test_bsearch();)
- test_binHashKey();
- GrRedBlackTree<int>::UnitTest();
-}
