Speed up GrResourceCache add and lookup by using TDynamicHash

src/gpu/GrResourceCache.h

 
 /*
  * Copyright 2011 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 
 #ifndef GrResourceCache_DEFINED
 #define GrResourceCache_DEFINED
 
 #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;
     }
 
     /** Uniquely identifies the GrResource subclass in the key to avoid collisions
         across resource types. */
     typedef uint8_t ResourceType;
 
     /** Flags set by the GrResource subclass. */
@@ skipping 12 matching lines @@
     }
 
     GrResourceKey() {
         fKey.reset();
     }
 
     void reset(const GrCacheID& id, ResourceType type, ResourceFlags flags) {
         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 {
         return ScratchDomain() ==
             *reinterpret_cast<const GrCacheID::Domain*>(fKey.getData() +
                                                         kCacheIDDomainOffset);
     }
 
     ResourceType getResourceType() const {
         return *reinterpret_cast<const ResourceType*>(fKey.getData() +
                                                       kResourceTypeOffset);
     }
 
     ResourceFlags getResourceFlags() const {
         return *reinterpret_cast<const ResourceFlags*>(fKey.getData() +
                                                        kResourceFlagsOffset);
     }
 
     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 {
         kCacheIDKeyOffset = 0,
         kCacheIDDomainOffset = kCacheIDKeyOffset + sizeof(GrCacheID::Key),
         kResourceTypeOffset = kCacheIDDomainOffset + sizeof(GrCacheID::Domain),
         kResourceFlagsOffset = kResourceTypeOffset + sizeof(ResourceType),
         kPadOffset = kResourceFlagsOffset + sizeof(ResourceFlags),
         kKeySize = SkAlign4(kPadOffset),
         kPadSize = kKeySize - kPadOffset
@@ skipping 19 matching lines @@
     GrBinHashKey<kKeySize> fKey;
 };
 
 // The cache listens for these messages to purge junk resources proactively.
 struct GrResourceInvalidatedMessage {
     GrResourceKey key;
 };
 
 ///////////////////////////////////////////////////////////////////////////////
 
+/** 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();
 
+    bool isEmpty() const { return fExclusiveCount == 0 && fResources.isEmpty(); }
+
     GrResourceKey    fKey;
-    GrResource*      fResource;
-
-    // we're a linked list
-    SK_DECLARE_INTERNAL_LLIST_INTERFACE(GrResourceEntry);
+    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
  *  GrGpu uses to call abandon/release.
  */
 class GrResourceCache {
 public:
     GrResourceCache(int maxCount, size_t maxBytes);
     ~GrResourceCache();
 
@@ skipping 78 matching lines @@
                      GrResource* resource,
                      uint32_t ownershipFlags = 0);
 
     /**
      * Determines if the cache contains an entry matching a key. If a matching
      * entry exists but was detached then it will not be found.
      */
     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.
      */
     void purgeAllUnlocked();
 
     /**
      * Allow cache to purge unused resources to obey resource limitations
      * Note: this entry point will be hidden (again) once totally ref-driven
      * cache maintenance is implemented. Note that the overbudget callback
@@ skipping 15 matching lines @@
 #if GR_CACHE_STATS
     void printStats();
 #endif
 
 private:
     enum BudgetBehaviors {
         kAccountFor_BudgetBehavior,
         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 removeInvalidResource(GrResourceEntry* entry);
+    void internalDetach(GrResource*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
+    void attachToHead(GrResource*, BudgetBehaviors behavior = kAccountFor_BudgetBehavior);
 
-    GrTHashTable<GrResourceEntry, GrResourceKey, 8> fCache;
+    void removeInvalidResource(GrResource* resource);
 
-    // We're an internal doubly linked list
-    typedef SkTInternalLList<GrResourceEntry> EntryList;
-    EntryList      fList;
+    SkTDynamicHash<GrResourceEntry,
+                   GrResourceKey,
+                   GrResourceEntry::GetKey,
+                   GrResourceEntry::GetKeyHash,
+                   GrResourceEntry::EqualsKey> fCache;
+
+    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()
     int            fMaxCount;
     size_t         fMaxBytes;
 
     // our current stats, related to our budget
 #if GR_CACHE_STATS
     int            fHighWaterEntryCount;
     size_t         fHighWaterEntryBytes;
@@ skipping 12 matching lines @@
     PFOverbudgetCB fOverbudgetCB;
     void*          fOverbudgetData;
 
     void internalPurge(int extraCount, size_t extraBytes);
 
     // Listen for messages that a resource has been invalidated and purge cached junk proactively.
     SkMessageBus<GrResourceInvalidatedMessage>::Inbox fInvalidationInbox;
     void purgeInvalidated();
 
 #ifdef SK_DEBUG
-    static size_t countBytes(const SkTInternalLList<GrResourceEntry>& list);
+    static size_t countBytes(const CacheLRUInternalLListType& list);
 #endif
 };
 
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
     class GrAutoResourceCacheValidate {
     public:
         GrAutoResourceCacheValidate(GrResourceCache* cache) : fCache(cache) {
             cache->validate();
         }
         ~GrAutoResourceCacheValidate() {
             fCache->validate();
         }
     private:
         GrResourceCache* fCache;
     };
 #else
     class GrAutoResourceCacheValidate {
     public:
         GrAutoResourceCacheValidate(GrResourceCache*) {}
     };
 #endif
 
 #endif