From bd58febffb103ea830bf027c5a95313548f7ea8e Mon Sep 17 00:00:00 2001 From: "commit-bot@chromium.org" Date: Fri, 17 Jan 2014 17:56:21 +0000 Subject: [PATCH] Speed up GrResourceCache add and lookup by using TDynamicHash Speed up GrResourceCache add and lookup by using TDynamicHash instead of GrTHashTable. GrTHashTable spends most of its time memmoving the array elements while sorting after an add. Lookup is not particularly fast either. R=mtklein@google.com, bsalomon@google.com, reed@google.com Author: kkinnunen@nvidia.com Review URL: https://codereview.chromium.org/91453002 git-svn-id: http://skia.googlecode.com/svn/trunk@13122 2bbb7eff-a529-9590-31e7-b0007b416f81 --- src/gpu/GrResourceCache.cpp | 3 -- src/gpu/GrResourceCache.h | 63 ++++++----------------- src/gpu/GrTMultiMap.h | 119 ++++++++++++++++++++++++++++++++++++++++++++ tests/ResourceCacheTest.cpp | 47 +++++++++++++++++ 4 files changed, 182 insertions(+), 50 deletions(-) create mode 100644 src/gpu/GrTMultiMap.h diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp index 1ba60e8..938f016 100644 --- a/src/gpu/GrResourceCache.cpp +++ b/src/gpu/GrResourceCache.cpp @@ -428,9 +428,6 @@ void GrResourceCache::validate() const { SkASSERT(fClientDetachedCount <= fEntryCount); SkASSERT((fEntryCount - fClientDetachedCount) == fCache.count()); - fCache.validate(); - - EntryList::Iter iter; // check that the exclusively held entries are okay diff --git a/src/gpu/GrResourceCache.h b/src/gpu/GrResourceCache.h index ca30732..41c6b51 100644 --- a/src/gpu/GrResourceCache.h +++ b/src/gpu/GrResourceCache.h @@ -13,7 +13,7 @@ #include "GrConfig.h" #include "GrTypes.h" -#include "GrTHashTable.h" +#include "GrTMultiMap.h" #include "GrBinHashKey.h" #include "SkMessageBus.h" #include "SkTInternalLList.h" @@ -23,12 +23,6 @@ class GrResourceEntry; class GrResourceKey { public: - enum { - kHashBits = 7, - kHashCount = 1 << kHashBits, - kHashMask = kHashCount - 1 - }; - static GrCacheID::Domain ScratchDomain() { static const GrCacheID::Domain gDomain = GrCacheID::GenerateDomain(); return gDomain; @@ -61,9 +55,8 @@ public: this->init(id.getDomain(), id.getKey(), type, flags); } - //!< returns hash value [0..kHashMask] for the key - int getHash() const { - return fKey.getHash() & kHashMask; + uint32_t getHash() const { + return fKey.getHash(); } bool isScratch() const { @@ -83,14 +76,6 @@ public: } bool operator==(const GrResourceKey& other) const { return fKey == other.fKey; } - bool operator<(const GrResourceKey& other) const { return fKey < other.fKey; } - - 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 { @@ -135,6 +120,11 @@ public: GrResource* resource() const { return fResource; } const GrResourceKey& key() const { return fKey; } + static const GrResourceKey& GetKey(const GrResourceEntry& e) { return e.key(); } + static uint32_t Hash(const GrResourceKey& key) { return key.getHash(); } + static bool Equal(const GrResourceEntry& a, const GrResourceKey& b) { + return a.key() == b; + } #ifdef SK_DEBUG void validate() const; #else @@ -148,51 +138,26 @@ private: GrResourceKey fKey; GrResource* fResource; - // we're a linked list + // Linked list for the LRU ordering. SK_DECLARE_INTERNAL_LLIST_INTERFACE(GrResourceEntry); friend class GrResourceCache; - friend class GrDLinkedList; }; -inline bool GrResourceKey::LessThan(const GrResourceEntry& entry, const GrResourceKey& key) { - return entry.key() < key; -} - -inline bool GrResourceKey::Equals(const GrResourceEntry& entry, const GrResourceKey& key) { - return entry.key() == key; -} - -#ifdef SK_DEBUG -inline bool GrResourceKey::LessThan(const GrResourceEntry& a, const GrResourceEntry& b) { - return a.key() < b.key(); -} - -inline bool GrResourceKey::Equals(const GrResourceEntry& a, const GrResourceEntry& b) { - return a.key() == b.key(); -} -#endif - /////////////////////////////////////////////////////////////////////////////// /** * Cache of GrResource objects. * * These have a corresponding GrResourceKey, built from 128bits identifying the - * resource. + * resource. Multiple resources can map to same GrResourceKey. * * The cache stores the entries in a double-linked list, which is its LRU. * When an entry is "locked" (i.e. given to the caller), it is moved to the * head of the list. If/when we must purge some of the entries, we walk the * list backwards from the tail, since those are the least recently used. * - * For fast searches, we maintain a sorted array (based on the GrResourceKey) - * which we can bsearch. When a new entry is added, it is inserted into this - * array. - * - * For even faster searches, a hash is computed from the Key. If there is - * a collision between two keys with the same hash, we fall back on the - * bsearch, and update the hash to reflect the most recent Key requested. + * For fast searches, we maintain a hash map based on the GrResourceKey. * * It is a goal to make the GrResourceCache the central repository and bookkeeper * of all resources. It should replace the linked list of GrResources that @@ -348,7 +313,11 @@ private: void removeInvalidResource(GrResourceEntry* entry); - GrTHashTable fCache; + GrTMultiMap fCache; // We're an internal doubly linked list typedef SkTInternalLList EntryList; diff --git a/src/gpu/GrTMultiMap.h b/src/gpu/GrTMultiMap.h new file mode 100644 index 0000000..c887214 --- /dev/null +++ b/src/gpu/GrTMultiMap.h @@ -0,0 +1,119 @@ + +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef GrTMultiMap_DEFINED +#define GrTMultiMap_DEFINED + +#include "GrTypes.h" +#include "SkTDynamicHash.h" + +/** A set that contains pointers to instances of T. Instances can be looked up with key Key. + * Multiple (possibly same) values can have the same key. + */ +template +class GrTMultiMap { + struct ValueList { + explicit ValueList(T* value) : fValue(value), fNext(NULL) {} + + static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); } + static uint32_t ListHash(const Key& key) { return Hash(key); } + static bool ListEqual(const ValueList& a, const Key& b) { + return Equal(*a.fValue, b); + } + T* fValue; + ValueList* fNext; + }; +public: + GrTMultiMap() : fCount(0) {} + + ~GrTMultiMap() { + SkASSERT(fCount == 0); + SkASSERT(fHash.count() == 0); + } + + void insert(const Key& key, T* value) { + ValueList* list = fHash.find(key); + if (NULL != list) { + // The new ValueList entry is inserted as the second element in the + // linked list, and it will contain the value of the first element. + ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue)); + newEntry->fNext = list->fNext; + // The existing first ValueList entry is updated to contain the + // inserted value. + list->fNext = newEntry; + list->fValue = value; + } else { + fHash.add(SkNEW_ARGS(ValueList, (value))); + } + + ++fCount; + } + + void remove(const Key& key, const T* value) { + ValueList* list = fHash.find(key); + // Since we expect the caller to be fully aware of what is stored, just + // assert that the caller removes an existing value. + SkASSERT(NULL != list); + ValueList* prev = NULL; + while (list->fValue != value) { + prev = list; + list = list->fNext; + } + + if (NULL != list->fNext) { + ValueList* next = list->fNext; + list->fValue = next->fValue; + list->fNext = next->fNext; + SkDELETE(next); + } else if (NULL != prev) { + prev->fNext = NULL; + SkDELETE(list); + } else { + fHash.remove(key); + SkDELETE(list); + } + + --fCount; + } + + T* find(const Key& key) const { + ValueList* list = fHash.find(key); + if (NULL != list) { + return list->fValue; + } + return NULL; + } + + template + T* find(const Key& key, const FindPredicate f) { + ValueList* list = fHash.find(key); + while (NULL != list) { + if (f(list->fValue)){ + return list->fValue; + } + list = list->fNext; + } + return NULL; + } + + int count() const { return fCount; } + +private: + SkTDynamicHash fHash; + int fCount; +}; + +#endif diff --git a/tests/ResourceCacheTest.cpp b/tests/ResourceCacheTest.cpp index c912ae0..b60cde9 100644 --- a/tests/ResourceCacheTest.cpp +++ b/tests/ResourceCacheTest.cpp @@ -130,6 +130,52 @@ static void test_purge_invalidated(skiatest::Reporter* reporter, GrContext* cont REPORTER_ASSERT(reporter, 0 == TestResource::alive()); } +static void test_cache_delete_on_destruction(skiatest::Reporter* reporter, + GrContext* context) { + GrCacheID::Domain domain = GrCacheID::GenerateDomain(); + GrCacheID::Key keyData; + keyData.fData64[0] = 5; + keyData.fData64[1] = 0; + GrResourceKey::ResourceType t = GrResourceKey::GenerateResourceType(); + + GrResourceKey key(GrCacheID(domain, keyData), t, 0); + + { + { + GrResourceCache cache(3, 30000); + TestResource* a = new TestResource(context->getGpu()); + TestResource* b = new TestResource(context->getGpu()); + cache.addResource(key, a); + cache.addResource(key, b); + + a->setDeleteWhenDestroyed(&cache, b); + b->setDeleteWhenDestroyed(&cache, a); + + a->unref(); + b->unref(); + REPORTER_ASSERT(reporter, 2 == TestResource::alive()); + } + REPORTER_ASSERT(reporter, 0 == TestResource::alive()); + } + { + GrResourceCache cache(3, 30000); + TestResource* a = new TestResource(context->getGpu()); + TestResource* b = new TestResource(context->getGpu()); + cache.addResource(key, a); + cache.addResource(key, b); + + a->setDeleteWhenDestroyed(&cache, b); + b->setDeleteWhenDestroyed(&cache, a); + + a->unref(); + b->unref(); + + cache.deleteResource(a->getCacheEntry()); + + REPORTER_ASSERT(reporter, 0 == TestResource::alive()); + } +} + //////////////////////////////////////////////////////////////////////////////// DEF_GPUTEST(ResourceCache, reporter, factory) { for (int type = 0; type < GrContextFactory::kLastGLContextType; ++type) { @@ -154,6 +200,7 @@ DEF_GPUTEST(ResourceCache, reporter, factory) { test_cache(reporter, context, &canvas); test_purge_invalidated(reporter, context); + test_cache_delete_on_destruction(reporter, context); } } -- 2.7.4