Speed up GrResourceCache add and lookup by using TDynamicHash

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.

Committed: http://code.google.com/p/skia/source/detail?r=13122

[Kimmo Kinnunen, 2013-11-27 13:32:39]

Depends on https://codereview.chromium.org/88113002/

Difference to the depends:
Desktop:
grresourcecache_find GPU              342.32     201.30    +141.02   +41.2% 
 grresourcecache_add GPU             1682.56     714.04    +968.52   +57.6% 

Xoom:
 grresourcecache_add GPU            15062.12    6946.81   +8115.31   +53.9% 
grresourcecache_find GPU             5291.50    1892.77   +3398.73   +64.2%

[mtklein, 2013-11-27 14:21:54]

I'm happy to see such a speedup!

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (left):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#old...
src/core/SkTDynamicHash.h:26: SkASSERT(this->validate());
Please put validate back to how it was.  SkASSERT compiles away to a no-op when
NDEBUG is defined.  SkASSERT(this->validate()); costs nothing.

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (right):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:39: bool operator()(const T*) const { return true; }
I'm not a fan of this API.  I know it's replicating the existing GrResourceCache
API, but it's not something that's done any more efficiently here than in the
GrResourceCache itself.

Allowing multiple values with the same key is going to open up a bag of worms. 
There's more than one way you might want add(), remove(), find(), etc. to work
in the presence of duplicate keys, which makes me think it shouldn't be handled
here.  In contrast, if you require unique keys, there's really only one way
these things can work.

Here's what I propose:
  - GrResourceCache makes an SkTDynamicHash mapping from its key to a list
(SkTDArray, SkTArray, SkTLList, ...) of its entries.
  - Filtered lookups in GrResourceCache first call find() here then manually
iterate over the entries in the list until the filter is satisfied.

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:72: void remove(const T* entry) {
Generally, these should be const T&.  It's neither optional nor are we
NULL-checking it.

[Kimmo Kinnunen, 2013-11-28 06:40:07]

Thanks for the review. I'll upload another one.

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (left):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#old...
src/core/SkTDynamicHash.h:26: SkASSERT(this->validate());
On 2013/11/27 14:21:54, mtklein wrote:
> Please put validate back to how it was.  SkASSERT compiles away to a no-op
when
> NDEBUG is defined.  SkASSERT(this->validate()); costs nothing.

The commit msg actually said that when it is *run*, it is too costly.

In other words: if validating after every operation, debug build runs of "tests"
never finish.

I don't think DynamicHash has been used with any substantial amount of items
before.

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (right):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:39: bool operator()(const T*) const { return true; }
On 2013/11/27 14:21:54, mtklein wrote:
> I'm not a fan of this API.  I know it's replicating the existing
GrResourceCache
> API, but it's not something that's done any more efficiently here than in the
> GrResourceCache itself.
> 
> Allowing multiple values with the same key is going to open up a bag of worms.


Yeah.. Though, in this stage of this usage, I don't think it would  *in
practice* open any.

I see what I can do, but it is not that pretty.

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:72: void remove(const T* entry) {
On 2013/11/27 14:21:54, mtklein wrote:
> Generally, these should be const T&.  It's neither optional nor are we
> NULL-checking it.

A) This is set that stores pointers
B) Pointers are stored by adding a pointer
C) Pointers are removed by removing a reference

Does this summarize your suggestion?

[bsalomon, 2013-12-02 14:18:16]

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (right):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:72: void remove(const T* entry) {
On 2013/11/28 06:40:08, kkinnunen wrote:
> On 2013/11/27 14:21:54, mtklein wrote:
> > Generally, these should be const T&.  It's neither optional nor are we
> > NULL-checking it.
> 
> A) This is set that stores pointers
> B) Pointers are stored by adding a pointer
> C) Pointers are removed by removing a reference
> 
> Does this summarize your suggestion?

If the function (or something it calls) will retain a pointer to the passed
object then I *think* our convention is to pass by pointer not reference, though
our style guide makes no mention of this at present.

[Kimmo Kinnunen, 2013-12-02 14:19:47]

How about this new patch? It does not change dynamic hash semantics. 

Some convolution in internal llist needed due to avoiding heap instantiation
(which already is a slight problem for the cache)

[reed1, 2013-12-02 16:20:39]

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (right):

https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
src/core/SkTDynamicHash.h:72: void remove(const T* entry) {
On 2013/12/02 14:18:16, bsalomon wrote:
> On 2013/11/28 06:40:08, kkinnunen wrote:
> > On 2013/11/27 14:21:54, mtklein wrote:
> > > Generally, these should be const T&.  It's neither optional nor are we
> > > NULL-checking it.
> > 
> > A) This is set that stores pointers
> > B) Pointers are stored by adding a pointer
> > C) Pointers are removed by removing a reference
> > 
> > Does this summarize your suggestion?
> 
> If the function (or something it calls) will retain a pointer to the passed
> object then I *think* our convention is to pass by pointer not reference,
though
> our style guide makes no mention of this at present.

agreed -- passing a ptr is clearer (to me) that the caller *could* take
ownership. Passing a reference signifies to me that we're just trying to be more
efficient than passing by value, but with the same constness/ownership contract.

[bsalomon, 2013-12-02 16:27:30]

On 2013/12/02 16:20:39, reed1 wrote:
> https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h
> File src/core/SkTDynamicHash.h (right):
> 
>
https://codereview.chromium.org/91453002/diff/1/src/core/SkTDynamicHash.h#new...
> src/core/SkTDynamicHash.h:72: void remove(const T* entry) {
> On 2013/12/02 14:18:16, bsalomon wrote:
> > On 2013/11/28 06:40:08, kkinnunen wrote:
> > > On 2013/11/27 14:21:54, mtklein wrote:
> > > > Generally, these should be const T&.  It's neither optional nor are we
> > > > NULL-checking it.
> > > 
> > > A) This is set that stores pointers
> > > B) Pointers are stored by adding a pointer
> > > C) Pointers are removed by removing a reference
> > > 
> > > Does this summarize your suggestion?
> > 
> > If the function (or something it calls) will retain a pointer to the passed
> > object then I *think* our convention is to pass by pointer not reference,
> though
> > our style guide makes no mention of this at present.
> 
> agreed -- passing a ptr is clearer (to me) that the caller *could* take
> ownership. Passing a reference signifies to me that we're just trying to be
more
> efficient than passing by value, but with the same constness/ownership
contract.

I updated the style guide to reflect this.

[mtklein, 2013-12-03 19:02:01]

I hate to keep asking this sort of thing, but do you see any way to split this
up?  There more changes here than I can really keep in my head while reading the
code, particularly in GrResourceCache.{cpp,h}.

https://codereview.chromium.org/91453002/diff/80001/include/core/SkTInternalL...
File include/core/SkTInternalLList.h (right):

https://codereview.chromium.org/91453002/diff/80001/include/core/SkTInternalL...
include/core/SkTInternalLList.h:32: friend class
SkTInternalLListDefaultExtractor<ClassName>;       \
I'm somewhat worried about the general design of GrResourceCache if we're forced
to shove its elements into three separate intrusive linked lists.  That's hard
to think about.  I'm not outright opposed to these changes here, but it does
smell.  Any thoughts on how to not do this?

https://codereview.chromium.org/91453002/diff/80001/include/core/SkTInternalL...
include/core/SkTInternalLList.h:271: T* find(const PredicateFunctor& f) {
I'm still skeptical of adding a method like this.  There's nothing here that the
caller can't do itself just as efficiently through the list's public API.  This
sort of filtered lookup is unique to GrResourceCache, so it really should stay
there as much as possible.

https://codereview.chromium.org/91453002/diff/80001/include/gpu/GrResource.h
File include/gpu/GrResource.h (right):

https://codereview.chromium.org/91453002/diff/80001/include/gpu/GrResource.h#...
include/gpu/GrResource.h:115: SK_DECLARE_INTERNAL_LLIST_INTERFACE(GrResource);
It seems weird to have one default and two named lists.  Can we just used named
ones for each?  Please update the comments to remind us how each of the three
lists matters.

Isn't the default list used as LRU?  I'm confused that this new list is named
CacheLRU.

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (left):

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h...
src/core/SkTDynamicHash.h:26: SkASSERT(this->validate());
Let's put this guy back.  This will never be expensive.

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h
File src/core/SkTDynamicHash.h (right):

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h...
src/core/SkTDynamicHash.h:65: #ifdef SK_DEBUG
This is a little nit, but let's just move the #ifdef inside validate and have
one declaration instead of two.

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h...
src/core/SkTDynamicHash.h:67: #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if
(!(x)) return
If we're guarding by SK_DEBUG, we can just use SkASSERT directly instead of
SKTDYNAMICHASH_CHECK.  The "if (!(x)) return" should never run if the assert
fails.

https://codereview.chromium.org/91453002/diff/80001/src/core/SkTDynamicHash.h...
src/core/SkTDynamicHash.h:120: // These methods are used by tests only.
Can we now pull validate() down here too?

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.cpp
File src/gpu/GrResourceCache.cpp (right):

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.c...
src/gpu/GrResourceCache.cpp:31: addResource(firstResource);
this->

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.c...
src/gpu/GrResourceCache.cpp:34: GrResourceEntry::~GrResourceEntry() {
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?

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.c...
src/gpu/GrResourceCache.cpp:213: resource = iter.init(entry->resources(),
EntryResourcesIter::kTail_IterStart);
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?

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.c...
src/gpu/GrResourceCache.cpp:214: if (NULL != resource && resource->getRefCnt() >
1) {
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.

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.c...
src/gpu/GrResourceCache.cpp:371: } while (resource != NULL &&
this->removeResource(resource));
Hmm, won't this be O(N^2)?  This is a case where using the filtered find is
actually biting us.

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.h
File src/gpu/GrResourceCache.h (right):

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.h...
src/gpu/GrResourceCache.h:118: /** GrResourceEntry represents one entry in
lookup cache (hash). It might represent multiple entries
I think we need to rework this comment.

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

?

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.h...
src/gpu/GrResourceCache.h:128: /** Returns true if entry should be deleted. */
For consistency with the other methods below, it'd be nice if these returned
false when they should be deleted instead of true.

https://codereview.chromium.org/91453002/diff/80001/src/gpu/GrResourceCache.h...
src/gpu/GrResourceCache.h:279: void makeNonExclusive(GrResource*);
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.

https://codereview.chromium.org/91453002/diff/80001/tests/DynamicHashTest.cpp
File tests/DynamicHashTest.cpp (right):

https://codereview.chromium.org/91453002/diff/80001/tests/DynamicHashTest.cpp...
tests/DynamicHashTest.cpp:179: Entry entries[3333];
Can you just mark 3333 and 237 as arbitrary somehow?  They don't need fancy
names, as long as we know they don't really matter too much.

https://codereview.chromium.org/91453002/diff/80001/tests/DynamicHashTest.cpp...
tests/DynamicHashTest.cpp:183: entries[i].key = rand.nextU();
It's unlikely, but this could trigger a uniqueness assert.  Call find or use i
as the key?

[Kimmo Kinnunen, 2013-12-05 14:40:27]

New one, trying to avoid modifying said files.

Removing all a hash table entries should be O(n) amortized, filtered find is
biting nobody. (1 remove should be constant time amortized).

[Kimmo Kinnunen, 2013-12-16 14:24:58]

On 2013/12/05 14:40:27, kkinnunen wrote:
> New one, trying to avoid modifying said files.

Ping.. Would anybody have time to give some feedback on the new direction?

[mtklein, 2014-01-17 15:08:42]

Sorry it's taken me so long to look at this.  I have some nits, but otherwise
this looks good to me.

Do the bench numbers in the description still hold?

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h
File src/gpu/GrTMultiset.h (right):

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:23: class GrTMultiset {
I think I'd prefer it if this were SkTMultiMap, in src/core.  I don't mind
following up to do that rename if it's a pain.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:27: fNext(NULL) {
We generally put the ',' in front of fNext here.

In this case, I'd even just write

explicit ValueList(T* value) : fValue(value), fNext(NULL) {}

Please do add explicit.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:52: newEntry->fNext = list->fNext;
Can you just add a small comment here that we always insert at position 2 in the
list?  (Have I read this correctly?)

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:62: void remove(const Key& key, T* value) {
Curious, can we write this as const T* value?  We're only using it to establish
the identity of the removed T*, right?

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:63: ValueList* list = fHash.find(key);
NULL check list?  If it's safe how it's used, SkASSERT(list != NULL), otherwise
I guess just return?

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:74: delete next;
Please use SkDELETE for all these.  (There's no difference as far as I know, but
it's nice to balance SkNEW and SkDELETE.)

[Kimmo Kinnunen, 2014-01-17 17:14:44]

Thanks for the review. New version is up.

Numbers:

desktop:
grresourcecache_find GPU     c        307.54     163.33    +144.21   +46.9% 
 grresourcecache_add GPU     c       1333.73     637.02    +696.71   +52.2% 

arm:
 grresourcecache_add GPU     c       4650.29    3139.69   +1510.60   +32.5% 
grresourcecache_find GPU     c       1131.95     498.05    +633.90   +56.0%

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h
File src/gpu/GrTMultiset.h (right):

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:23: class GrTMultiset {
On 2014/01/17 15:08:43, mtklein wrote:
> I think I'd prefer it if this were SkTMultiMap, in src/core.  I don't mind
> following up to do that rename if it's a pain.

Done.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:27: fNext(NULL) {
On 2014/01/17 15:08:43, mtklein wrote:
> We generally put the ',' in front of fNext here.
> 
> In this case, I'd even just write
> 
> explicit ValueList(T* value) : fValue(value), fNext(NULL) {}
> 
> Please do add explicit.

Done.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:52: newEntry->fNext = list->fNext;
On 2014/01/17 15:08:43, mtklein wrote:
> Can you just add a small comment here that we always insert at position 2 in
the
> list?  (Have I read this correctly?)

Correct. Done.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:62: void remove(const Key& key, T* value) {
On 2014/01/17 15:08:43, mtklein wrote:
> Curious, can we write this as const T* value?  We're only using it to
establish
> the identity of the removed T*, right?

Done.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:63: ValueList* list = fHash.find(key);
On 2014/01/17 15:08:43, mtklein wrote:
> NULL check list?  If it's safe how it's used, SkASSERT(list != NULL),
otherwise
> I guess just return?

Done, added an assert.

https://codereview.chromium.org/91453002/diff/230001/src/gpu/GrTMultiset.h#ne...
src/gpu/GrTMultiset.h:74: delete next;
On 2014/01/17 15:08:43, mtklein wrote:
> Please use SkDELETE for all these.  (There's no difference as far as I know,
but
> it's nice to balance SkNEW and SkDELETE.)

Done.

[mtklein, 2014-01-17 17:29:00]

Thanks, those new comments really help.

lgtm

[commit-bot: I haz the power, 2014-01-17 17:38:27]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/kkinnunen@nvidia.com/91453002/340001

[commit-bot: I haz the power, 2014-01-17 17:56:32]

Change committed as 13122