Speed up GrResourceCache add and lookup by using TDynamicHash

src/gpu/GrResourceCache.h

Index: src/gpu/GrResourceCache.h
diff --git a/src/gpu/GrResourceCache.h b/src/gpu/GrResourceCache.h
index ca30732bbc176fed947b048779022412004fcc94..7ff05b72ed0a1209f475e3b3d6dde6e3aa0bfe68 100644
--- a/src/gpu/GrResourceCache.h
+++ b/src/gpu/GrResourceCache.h
@@ -13,22 +13,16 @@
 
 #include "GrConfig.h"
 #include "GrTypes.h"
-#include "GrTHashTable.h"
 #include "GrBinHashKey.h"
+#include "GrResource.h"
 #include "SkMessageBus.h"
+#include "SkTDynamicHash.h"
 #include "SkTInternalLList.h"
 
-class GrResource;
 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 {
@@ -130,69 +115,58 @@ struct GrResourceInvalidatedMessage {
 
 ///////////////////////////////////////////////////////////////////////////////
 
+/** GrResourceEntry represents one entry in lookup cache (hash). It might represent multiple entries

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

I think we need to rework this comment.

/** GrResourceEntry is one lookup hash entry, which represents all resources
with the same key.

?

+ * (resources) in the GrResourceCache.
+ */
 class GrResourceEntry {
+    SK_DECLARE_NAMED_INTERNAL_LLIST(GrResource, CacheEntryResources, fResources);
+
 public:
-    GrResource* resource() const { return fResource; }
     const GrResourceKey& key() const { return fKey; }
 
-#ifdef SK_DEBUG
-    void validate() const;
-#else
-    void validate() const {}
-#endif
+    void addResource(GrResource* resource);
+    /** Returns true if entry should be deleted. */

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

For consistency with the other methods below, it'd be nice if these returned
false when they should be deleted instead of true.

+    bool removeResource(GrResource* resource);
+    /** Returns true if entry should be deleted. */
+    bool removeExclusiveResource(GrResource* resource);
+
+    void makeExclusive(GrResource* resource);
+    void makeNonExclusive(GrResource* resource);
+
+    CacheEntryResourcesInternalLListType& resources() { return fResources; }
+
+    static const GrResourceKey& GetKey(const GrResourceEntry& e) { return e.key(); }
+    static uint32_t GetKeyHash(const GrResourceKey& key) { return key.getHash(); }
+    static bool EqualsKey(const GrResourceEntry& a, const GrResourceKey& b) {
+        return a.key() == b;
+    }
 
 private:
-    GrResourceEntry(const GrResourceKey& key, GrResource* resource);
+    GrResourceEntry(const GrResourceKey& key, GrResource* firstResource);
     ~GrResourceEntry();
 
-    GrResourceKey    fKey;
-    GrResource*      fResource;
+    bool isEmpty() const { return fExclusiveCount == 0 && fResources.isEmpty(); }
 
-    // we're a linked list
-    SK_DECLARE_INTERNAL_LLIST_INTERFACE(GrResourceEntry);
+    GrResourceKey    fKey;
+    int fExclusiveCount;
 
     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
@@ -291,23 +265,26 @@ public:
     bool hasKey(const GrResourceKey& key) const { return NULL != fCache.find(key); }
 
     /**
-     * Hide 'entry' so that future searches will not find it. Such
-     * hidden entries will not be purged. The entry still counts against
+     * Hide 'resource' so that future searches will not find it. Such
+     * hidden resources will not be purged. The resource still counts against
      * the cache's budget and should be made non-exclusive when exclusive access
      * is no longer needed.
      */
-    void makeExclusive(GrResourceEntry* entry);
+    void makeExclusive(GrResource* resource);
 
     /**
      * Restore 'entry' so that it can be found by future searches. 'entry'
      * will also be purgeable (provided its lock count is now 0.)
      */
-    void makeNonExclusive(GrResourceEntry* entry);
+    void makeNonExclusive(GrResource*);

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

I don't mind not naming parameters when it's obvious what's going on---and
indeed I think I prefer it---but please be consistent.  Either name this one or
remove "resource" from makeExclusive, etc.  The comments need updating.

 
     /**
-     * Remove a resource from the cache and delete it!
+     * Delete a resource from the cache.
      */
-    void deleteResource(GrResourceEntry* entry);
+    void deleteResource(GrResource* resource) {
+        SkASSERT(1 == resource->getRefCnt());
+        this->removeResource(resource);
+    }
 
     /**
      * Removes every resource in the cache that isn't locked.
@@ -343,20 +320,25 @@ private:
         kIgnore_BudgetBehavior
     };
 
-    void internalDetach(GrResourceEntry*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
-    void attachToHead(GrResourceEntry*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
+    /** Returns true if entry holding the resource is still valid. */
+    bool removeResource(GrResource* resource);
+
+    void internalDetach(GrResource*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
+    void attachToHead(GrResource*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
 
-    void removeInvalidResource(GrResourceEntry* entry);
+    void removeInvalidResource(GrResource* resource);
 
-    GrTHashTable<GrResourceEntry, GrResourceKey, 8> fCache;
+    SkTDynamicHash<GrResourceEntry,
+                   GrResourceKey,
+                   GrResourceEntry::GetKey,
+                   GrResourceEntry::GetKeyHash,
+                   GrResourceEntry::EqualsKey> fCache;
 
-    // We're an internal doubly linked list
-    typedef SkTInternalLList<GrResourceEntry> EntryList;
-    EntryList      fList;
+    SK_DECLARE_NAMED_INTERNAL_LLIST(GrResource, CacheLRU, fList);
 
 #ifdef SK_DEBUG
     // These objects cannot be returned by a search
-    EntryList      fExclusiveList;
+    CacheLRUInternalLListType fExclusiveList;
 #endif
 
     // our budget, used in purgeAsNeeded()
@@ -389,7 +371,7 @@ private:
     void purgeInvalidated();
 
 #ifdef SK_DEBUG
-    static size_t countBytes(const SkTInternalLList<GrResourceEntry>& list);
+    static size_t countBytes(const CacheLRUInternalLListType& list);
 #endif
 };