Speed up GrResourceCache add and lookup by using TDynamicHash

src/gpu/GrResourceCache.cpp

Index: src/gpu/GrResourceCache.cpp
diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp
index 5cf3f82c7d780d1acc5ee53ca20d9f6140b1a7b4..49cd42d0b24b9475bd12ac4d441a860ae9caae87 100644
--- a/src/gpu/GrResourceCache.cpp
+++ b/src/gpu/GrResourceCache.cpp
@@ -25,25 +25,58 @@ GrResourceKey::ResourceType GrResourceKey::GenerateResourceType() {
 
 ///////////////////////////////////////////////////////////////////////////////
 
-GrResourceEntry::GrResourceEntry(const GrResourceKey& key, GrResource* resource)
-        : fKey(key), fResource(resource) {
-    // we assume ownership of the resource, and will unref it when we die
-    SkASSERT(resource);
-    resource->ref();
+GrResourceEntry::GrResourceEntry(const GrResourceKey& key, GrResource* firstResource)
+    : fKey(key)
+    , fExclusiveCount(0) {
+    addResource(firstResource);

[mtklein, 2013/12/03 19:02:02]

this->

 }
 
 GrResourceEntry::~GrResourceEntry() {

[mtklein, 2013/12/03 19:02:02]

The responsibility for resource ownership here seems pretty weird.  Am I reading
it right that deleting a GrResource could trigger deleting the GrResourceEntry
that owns it?  And that addResource/removeResource do manage ownership, but the
destructor requires that all elements have been removed?  Surely there's got to
be a more straightforward way to manage ownership?

-    fResource->setCacheEntry(NULL);
-    fResource->unref();
+    SkASSERT(isEmpty());
+ }
+
+void GrResourceEntry::addResource(GrResource* resource) {
+    // We assume ownership of the resource, and will unref it when resource is
+    // removed from the entry.
+    resource->ref();
+    resource->setCacheEntry(this);
+    fResources.addToHead(resource);
 }
 
-#ifdef SK_DEBUG
-void GrResourceEntry::validate() const {
-    SkASSERT(fResource);
-    SkASSERT(fResource->getCacheEntry() == this);
-    fResource->validate();
+bool GrResourceEntry::removeResource(GrResource* resource) {
+    fResources.remove(resource);
+
+    // The unref() might run destructor which would remove other resources from this entry and delete the
+    // entry. Temporarily increase exclusive count, so that entry stays alive.
+    ++fExclusiveCount;
+
+    resource->setCacheEntry(NULL);
+    resource->unref();
+
+    --fExclusiveCount;
+
+    return isEmpty();
+}
+
+bool GrResourceEntry::removeExclusiveResource(GrResource* resource) {
+    resource->setCacheEntry(NULL);
+    resource->unref();
+
+    // Decrease the count after unref(). See removeResource.
+    --fExclusiveCount;
+
+    return isEmpty();
+}
+
+void GrResourceEntry::makeExclusive(GrResource* resource) {
+    fResources.remove(resource);
+    fExclusiveCount++;
+}
+
+void GrResourceEntry::makeNonExclusive(GrResource* resource) {
+    fResources.addToHead(resource);
+    fExclusiveCount--;
 }
-#endif
 
 ///////////////////////////////////////////////////////////////////////////////
 
@@ -71,20 +104,12 @@ GrResourceCache::GrResourceCache(int maxCount, size_t maxBytes) :
 GrResourceCache::~GrResourceCache() {
     GrAutoResourceCacheValidate atcv(this);
 
-    EntryList::Iter iter;
-
-    // Unlike the removeAll, here we really remove everything, including locked resources.
-    while (GrResourceEntry* entry = fList.head()) {
+    while (GrResource* resource = fList.head()) {
         GrAutoResourceCacheValidate atcv(this);
-
-        // remove from our cache
-        fCache.remove(entry->fKey, entry);
-
-        // remove from our llist
-        this->internalDetach(entry);
-
-        delete entry;
+        this->removeResource(resource);
     }
+
+    SkASSERT(fCache.count() == 0);
 }
 
 void GrResourceCache::getLimits(int* maxResources, size_t* maxResourceBytes) const{
@@ -107,14 +132,14 @@ void GrResourceCache::setLimits(int maxResources, size_t maxResourceBytes) {
     }
 }
 
-void GrResourceCache::internalDetach(GrResourceEntry* entry,
+void GrResourceCache::internalDetach(GrResource* resource,
                                      BudgetBehaviors behavior) {
-    fList.remove(entry);
+    fList.remove(resource);
 
     // update our stats
     if (kIgnore_BudgetBehavior == behavior) {
         fClientDetachedCount += 1;
-        fClientDetachedBytes += entry->resource()->sizeInBytes();
+        fClientDetachedBytes += resource->sizeInBytes();
 
 #if GR_CACHE_STATS
         if (fHighWaterClientDetachedCount < fClientDetachedCount) {
@@ -129,23 +154,23 @@ void GrResourceCache::internalDetach(GrResourceEntry* entry,
         SkASSERT(kAccountFor_BudgetBehavior == behavior);
 
         fEntryCount -= 1;
-        fEntryBytes -= entry->resource()->sizeInBytes();
+        fEntryBytes -= resource->sizeInBytes();
     }
 }
 
-void GrResourceCache::attachToHead(GrResourceEntry* entry,
+void GrResourceCache::attachToHead(GrResource* resource,
                                    BudgetBehaviors behavior) {
-    fList.addToHead(entry);
+    fList.addToHead(resource);
 
     // update our stats
     if (kIgnore_BudgetBehavior == behavior) {
         fClientDetachedCount -= 1;
-        fClientDetachedBytes -= entry->resource()->sizeInBytes();
+        fClientDetachedBytes -= resource->sizeInBytes();
     } else {
         SkASSERT(kAccountFor_BudgetBehavior == behavior);
 
         fEntryCount += 1;
-        fEntryBytes += entry->resource()->sizeInBytes();
+        fEntryBytes += resource->sizeInBytes();
 
 #if GR_CACHE_STATS
         if (fHighWaterEntryCount < fEntryCount) {
@@ -163,37 +188,55 @@ void GrResourceCache::attachToHead(GrResourceEntry* entry,
 // is relying on the texture.
 class GrTFindUnreffedFunctor {
 public:
-    bool operator()(const GrResourceEntry* entry) const {
-        return entry->resource()->unique();
+    bool operator()(const GrResource* resource) const {
+        return resource->unique();
     }
 };
 
 GrResource* GrResourceCache::find(const GrResourceKey& key, uint32_t ownershipFlags) {
     GrAutoResourceCacheValidate atcv(this);
 
-    GrResourceEntry* entry = NULL;
+    GrResourceEntry* entry = fCache.find(key);
+    if (NULL == entry) {
+        return NULL;
+    }
 
+    GrResource* resource;
     if (ownershipFlags & kNoOtherOwners_OwnershipFlag) {
         GrTFindUnreffedFunctor functor;
-
-        entry = fCache.find<GrTFindUnreffedFunctor>(key, functor);
+        resource = entry->resources().find(functor);
     } else {
-        entry = fCache.find(key);
+        // Find a resource not referenced outside cache, or the least referenced one.
+        typedef GrResourceEntry::CacheEntryResourcesInternalLListType::Iter EntryResourcesIter;
+
+        EntryResourcesIter iter;
+        resource = iter.init(entry->resources(), EntryResourcesIter::kTail_IterStart);

[mtklein, 2013/12/03 19:02:02]

If we don't need to iterate both ways down the list, InternalLListType may be
overkill.  It might be easier to reason about a simple pointer to the next?

+        if (NULL != resource && resource->getRefCnt() > 1) {

[mtklein, 2013/12/03 19:02:02]

Oooh, calls to getRefCnt() make me super scared.  There must be a way to not do
this.  This CL is sort of dead in the water if not.  Immediately after
resource->getRefCnt() > 1 returns true, it could become false.  That refCount
local at best represents a ref-count the object definitely had at some point,
though there's no guarantee at all it is now correct.  The only safe
what's-my-refcount operation is unique() (or this->getRefCnt() == 1), and even
then you can only believe it if it returns true.

+            int refCount = resource->getRefCnt();
+            for (GrResource* nextResource = iter.next();
+                 NULL != nextResource && refCount > 1;
+                 nextResource = iter.next()) {
+                if (nextResource->getRefCnt() > refCount) {
+                    resource = nextResource;
+                    refCount = nextResource->getRefCnt();
+                }
+            }
+        }
     }
 
-    if (NULL == entry) {
+    if (NULL == resource) {
         return NULL;
     }
 
     if (ownershipFlags & kHide_OwnershipFlag) {
-        this->makeExclusive(entry);
+        this->makeExclusive(resource);
     } else {
         // Make this resource MRU
-        this->internalDetach(entry);
-        this->attachToHead(entry);
+        this->internalDetach(resource);
+        this->attachToHead(resource);
     }
 
-    return entry->fResource;
+    return resource;
 }
 
 void GrResourceCache::addResource(const GrResourceKey& key,
@@ -207,32 +250,34 @@ void GrResourceCache::addResource(const GrResourceKey& key,
     SkASSERT(!fPurging);
     GrAutoResourceCacheValidate atcv(this);
 
-    GrResourceEntry* entry = SkNEW_ARGS(GrResourceEntry, (key, resource));
-    resource->setCacheEntry(entry);
+    GrResourceEntry* entry = fCache.find(key);
+    if (NULL == entry) {
+        entry = SkNEW_ARGS(GrResourceEntry, (key, resource));
+        fCache.add(entry);
+    } else {
+        entry->addResource(resource);
+    }
 
-    this->attachToHead(entry);
-    fCache.insert(key, entry);
+    this->attachToHead(resource);
 
     if (ownershipFlags & kHide_OwnershipFlag) {
-        this->makeExclusive(entry);
+        this->makeExclusive(resource);
     }
-
 }
 
-void GrResourceCache::makeExclusive(GrResourceEntry* entry) {
+void GrResourceCache::makeExclusive(GrResource* resource) {
     GrAutoResourceCacheValidate atcv(this);
-
     // When scratch textures are detached (to hide them from future finds) they
     // still count against the resource budget
-    this->internalDetach(entry, kIgnore_BudgetBehavior);
-    fCache.remove(entry->key(), entry);
+    this->internalDetach(resource, kIgnore_BudgetBehavior);
+    resource->getCacheEntry()->makeExclusive(resource);
 
 #ifdef SK_DEBUG
-    fExclusiveList.addToHead(entry);
+    fExclusiveList.addToHead(resource);
 #endif
 }
 
-void GrResourceCache::removeInvalidResource(GrResourceEntry* entry) {
+void GrResourceCache::removeInvalidResource(GrResource* resource) {
     // If the resource went invalid while it was detached then purge it
     // This can happen when a 3D context was lost,
     // the client called GrContext::contextDestroyed() to notify Gr,
@@ -240,26 +285,31 @@ void GrResourceCache::removeInvalidResource(GrResourceEntry* entry) {
     // texture (which was invalidated at contextDestroyed time).
     fClientDetachedCount -= 1;
     fEntryCount -= 1;
-    size_t size = entry->resource()->sizeInBytes();
+    size_t size = resource->sizeInBytes();
     fClientDetachedBytes -= size;
     fEntryBytes -= size;
 }
 
-void GrResourceCache::makeNonExclusive(GrResourceEntry* entry) {
+void GrResourceCache::makeNonExclusive(GrResource* resource) {
     GrAutoResourceCacheValidate atcv(this);
 
 #ifdef SK_DEBUG
-    fExclusiveList.remove(entry);
+    fExclusiveList.remove(resource);
 #endif
 
-    if (entry->resource()->isValid()) {
+    if (resource->isValid()) {
         // Since scratch textures still count against the cache budget even
         // when they have been removed from the cache, re-adding them doesn't
         // alter the budget information.
-        attachToHead(entry, kIgnore_BudgetBehavior);
-        fCache.insert(entry->key(), entry);
+        attachToHead(resource, kIgnore_BudgetBehavior);
+        resource->getCacheEntry()->makeNonExclusive(resource);
     } else {
-        this->removeInvalidResource(entry);
+        this->removeInvalidResource(resource);
+        GrResourceEntry* entry = resource->getCacheEntry();
+        if (entry->removeExclusiveResource(resource)) {
+            fCache.remove(entry->key());
+            delete entry;
+        }
     }
 }
 
@@ -312,22 +362,27 @@ void GrResourceCache::purgeInvalidated() {
         //
         // This is complicated and confusing.  May try this in the future.  For
         // now, these resources are just LRU'd as if we never got the message.
-        GrResourceEntry* entry = fCache.find(invalidated[i].key, GrTFindUnreffedFunctor());
+        GrResourceEntry* entry = fCache.find(invalidated[i].key);
         if (entry) {
-            this->deleteResource(entry);
+            GrTFindUnreffedFunctor functor;
+            GrResource* resource;
+            do {
+                resource = entry->resources().find(functor);
+            } while (resource != NULL && this->removeResource(resource));

[mtklein, 2013/12/03 19:02:02]

Hmm, won't this be O(N^2)?  This is a case where using the filtered find is
actually biting us.

         }
     }
 }
 
-void GrResourceCache::deleteResource(GrResourceEntry* entry) {
-    SkASSERT(1 == entry->fResource->getRefCnt());
-
-    // remove from our cache
-    fCache.remove(entry->key(), entry);
+bool GrResourceCache::removeResource(GrResource* resource) {
+    GrResourceEntry* entry = resource->getCacheEntry();
+    this->internalDetach(resource);
+    if (entry->removeResource(resource)) {
+        fCache.remove(entry->key());
+        delete entry;
+        return false;
+    }
 
-    // remove from our llist
-    this->internalDetach(entry);
-    delete entry;
+    return true;
 }
 
 void GrResourceCache::internalPurge(int extraCount, size_t extraBytes) {
@@ -339,7 +394,7 @@ void GrResourceCache::internalPurge(int extraCount, size_t extraBytes) {
     // The purging process is repeated several times since one pass
     // may free up other resources
     do {
-        EntryList::Iter iter;
+        CacheLRUInternalLListType::Iter iter;
 
         changed = false;
 
@@ -347,9 +402,9 @@ void GrResourceCache::internalPurge(int extraCount, size_t extraBytes) {
         // doubly linked list doesn't invalidate its data/pointers
         // outside of the specific area where a deletion occurs (e.g.,
         // in internalDetach)
-        GrResourceEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);
+        GrResource* resource = iter.init(fList, CacheLRUInternalLListType::Iter::kTail_IterStart);
 
-        while (NULL != entry) {
+        while (NULL != resource) {
             GrAutoResourceCacheValidate atcv(this);
 
             if ((fEntryCount+extraCount) <= fMaxCount &&
@@ -358,12 +413,12 @@ void GrResourceCache::internalPurge(int extraCount, size_t extraBytes) {
                 break;
             }
 
-            GrResourceEntry* prev = iter.prev();
-            if (entry->fResource->unique()) {
+            GrResource* prev = iter.prev();
+            if (resource->unique()) {
                 changed = true;
-                this->deleteResource(entry);
+                this->deleteResource(resource);
             }
-            entry = prev;
+            resource = prev;
         }
     } while (!withinBudget && changed);
 }
@@ -384,14 +439,12 @@ void GrResourceCache::purgeAllUnlocked() {
 #ifdef SK_DEBUG
     SkASSERT(fExclusiveList.countEntries() == fClientDetachedCount);
     SkASSERT(countBytes(fExclusiveList) == fClientDetachedBytes);
-    if (!fCache.count()) {
-        // Items may have been detached from the cache (such as the backing
-        // texture for an SkGpuDevice). The above purge would not have removed
-        // them.
-        SkASSERT(fEntryCount == fClientDetachedCount);
-        SkASSERT(fEntryBytes == fClientDetachedBytes);
-        SkASSERT(fList.isEmpty());
-    }
+    // Items may have been detached from the cache (such as the backing
+    // texture for an SkGpuDevice). The above purge would not have removed
+    // them.
+    SkASSERT(fEntryCount == fClientDetachedCount);
+    SkASSERT(fEntryBytes == fClientDetachedBytes);
+    SkASSERT(fList.isEmpty());
 #endif
 
     fMaxBytes = savedMaxBytes;
@@ -401,16 +454,15 @@ void GrResourceCache::purgeAllUnlocked() {
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
-size_t GrResourceCache::countBytes(const EntryList& list) {
+size_t GrResourceCache::countBytes(const CacheLRUInternalLListType& list) {
     size_t bytes = 0;
 
-    EntryList::Iter iter;
-
-    const GrResourceEntry* entry = iter.init(const_cast<EntryList&>(list),
-                                             EntryList::Iter::kTail_IterStart);
+    CacheLRUInternalLListType::Iter iter;
+    const GrResource* resource = iter.init(const_cast<CacheLRUInternalLListType&>(list),
+                                           CacheLRUInternalLListType::Iter::kTail_IterStart);
 
-    for ( ; NULL != entry; entry = iter.prev()) {
-        bytes += entry->resource()->sizeInBytes();
+    for ( ; NULL != resource; resource = iter.prev()) {
+        bytes += resource->sizeInBytes();
     }
     return bytes;
 }
@@ -426,28 +478,25 @@ void GrResourceCache::validate() const {
     SkASSERT(both_zero_or_nonzero(fClientDetachedCount, fClientDetachedBytes));
     SkASSERT(fClientDetachedBytes <= fEntryBytes);
     SkASSERT(fClientDetachedCount <= fEntryCount);
-    SkASSERT((fEntryCount - fClientDetachedCount) == fCache.count());
-
-    fCache.validate();
-
 
-    EntryList::Iter iter;
+    CacheLRUInternalLListType::Iter iter;
 
     // check that the exclusively held entries are okay
-    const GrResourceEntry* entry = iter.init(const_cast<EntryList&>(fExclusiveList),
-                                             EntryList::Iter::kHead_IterStart);
+    GrResource* resource = iter.init(const_cast<CacheLRUInternalLListType&>(fExclusiveList),
+                                     CacheLRUInternalLListType::Iter::kHead_IterStart);
 
-    for ( ; NULL != entry; entry = iter.next()) {
-        entry->validate();
+    for ( ; NULL != resource; resource = iter.next()) {
+        resource->validate();
     }
 
     // check that the shareable entries are okay
-    entry = iter.init(const_cast<EntryList&>(fList), EntryList::Iter::kHead_IterStart);
+    resource = iter.init(const_cast<CacheLRUInternalLListType&>(fList),
+                         CacheLRUInternalLListType::Iter::kHead_IterStart);
 
     int count = 0;
-    for ( ; NULL != entry; entry = iter.next()) {
-        entry->validate();
-        SkASSERT(fCache.find(entry->key()));
+    for ( ; NULL != resource; resource = iter.next()) {
+        resource->validate();
+        SkASSERT(fCache.find(resource->getCacheEntry()->key()));
         count += 1;
     }
     SkASSERT(count == fEntryCount - fClientDetachedCount);
@@ -469,12 +518,12 @@ void GrResourceCache::validate() const {
 void GrResourceCache::printStats() {
     int locked = 0;
 
-    EntryList::Iter iter;
+    CacheLRUInternalLListType::Iter iter;
 
-    GrResourceEntry* entry = iter.init(fList, EntryList::Iter::kTail_IterStart);
+    GrResource* resource = iter.init(fList, CacheLRUInternalLListType::Iter::kTail_IterStart);
 
-    for ( ; NULL != entry; entry = iter.prev()) {
-        if (entry->fResource->getRefCnt() > 1) {
+    for ( ; NULL != resource; resource = iter.prev()) {
+        if (resource->getRefCnt() > 1) {
             ++locked;
         }
     }