Speed up GrResourceCache lookup by inlining GrBinHashKey comparisons

Speed up GrResourceCache lookup by inlining GrBinHashKey comparisons

The GCC compilers for Android and Ubuntu do not seem to be able to
inline the memcmp operations on GrBinHashKey data. Write the comparisons
manually. Also shortcut GrBinHashKey::EQ to skip comparison when hashes
do not match.

Speeds up grresourcecache_find test on ARM and x86_64. Speeds up
grresourcecache_add on x86_64.

In order to test the change, moves ad hoc Gr unit tests from
src/gr_unittest.cpp to tests/GrUnitTests to be consistent with other
tests and enables GrUnitTests.

Fixes a regression from r2863 with where re-setting GrBinHashKey data
would not set the hash correctly. This should also improve the hash
function itself. The regression caused many of the hash operations be
no-ops. This is caught by the unit test.

Renames the comparison functions that GrHashTable needs from EQ, LT to
Equals, LessThan.

Renames GrTBinHashKey to GrBinHashKey. The GrTBinHashKey used to
forward comparison functions to an ENTRY template class, which would
extract the key and call back to the GrTBinHashKey. This would save
the user from writing one comparison function when comparison was done
with int ENTRY::compare(). There's no real benefit in this now. Also
this was used only for one class (GrTextureStripAtlas). The other use
in GrResourceKey was not actually using the provided "shortcut". The
new GrBinHashKey is not templated with the entry, rather just provides
== and < functions. The users of GrTHashTable provide the needed
functions now.

Adds explicit documentation of functions that are actually needed
GrTHashTable for the Key template. Adds SK_DEBUG guards according to
the contract.

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

[mtklein, 2013-11-26 14:20:43]

I have only structural comments.  The thrust of this CL looks great to me.  For
reference, here are the numbers I see (best to view in monospace).

Nexus 5
               bench conf    time        old        new       diff    diffP 
 grresourcecache_add GPU            11665.77   10576.83   +1088.94    +9.3% 
 grresourcecache_add NULLGPU        11573.88   10475.56   +1098.32    +9.5% 
grresourcecache_find GPU             1379.31    1001.39    +377.92   +27.4% 
grresourcecache_find NULLGPU         1383.68    1002.02    +381.66   +27.6% 

Desktop
               bench conf    time        old        new       diff    diffP 
 grresourcecache_add GPU             1904.15    1545.39    +358.76   +18.8% 
 grresourcecache_add NULLGPU         1907.98    1545.37    +362.61   +19.0% 
grresourcecache_find NULLGPU          466.80     310.86    +155.94   +33.4% 
grresourcecache_find GPU              609.28     310.58    +298.70   +49.0%

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h
File src/gpu/GrBinHashKey.h (right):

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode55
src/gpu/GrBinHashKey.h:55: 
I'd somewhat prefer 4 to sizeof(fData[0]) here.

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode75
src/gpu/GrBinHashKey.h:75: 
Is the name EQ required by some convention?  If not, -> equals?

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode88
src/gpu/GrBinHashKey.h:88: 
same here with lessThan

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrResourceCache.h
File src/gpu/GrResourceCache.h (left):

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrResourceCache.h#old...
src/gpu/GrResourceCache.h:136: 
Does this intermediate Key struct really need to exist?  Those chains of
GrResourceEntry.GrResourceKey.Key.HashedKey are pretty silly looking down there.
 I think I'd like it a bit more if they read something like:
  return entry.key().hashedKey().lessThan(key.hashedKey());

If we can keep lessThan and equals methods on GrResourceKey that inline, I'd
like this even better:
  return entry.key().lessThan(key);

If you are having trouble getting methods to reliably inline, we've now got
SK_ALWAYS_INLINE to force it.

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp
File tests/GrUnitTests.cpp (right):

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp#newcode8
tests/GrUnitTests.cpp:8: #include "GrRedBlackTree.h"
Given the opportunity to start fresh, personally I'd do

#include "Test.h"
#include "TestClassDef.h"

DEF_TEST(GrUnitTests_bsearch, reporter) {
  ...
}

DEF_TEST(GrUnitTests_binHashKey, reporter) {
  ...
}

DEF_TEST(GrUnitTests_redBlackTree, reporter) {
  ...
}

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp#newcode10
tests/GrUnitTests.cpp:10: // FIXME: needs to be in a header
Do any of these actually require SK_SUPPORT_GPU?  Seems like they're mostly data
structure tests.  If they do, that's fine.  If only some of them do, it'd be
nice to run the others all the time.

[bsalomon, 2013-11-26 15:24:14]

Not directly part of this change, but should the benchs be marked as
non-rendering? Running them in GPU and NULLGPU doesn't seem necessary.

[Kimmo Kinnunen, 2013-11-27 08:16:54]

Thanks for the review. How about this?

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h
File src/gpu/GrBinHashKey.h (right):

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode55
src/gpu/GrBinHashKey.h:55: 
On 2013/11/26 14:20:43, mtklein wrote:
> I'd somewhat prefer 4 to sizeof(fData[0]) here.

Done. Changed the division below to be consistent with this preference. (I think
not hardcoding it is better, but does not make a difference here anyway)

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode75
src/gpu/GrBinHashKey.h:75: 
On 2013/11/26 14:20:43, mtklein wrote:
> Is the name EQ required by some convention?  If not, -> equals?

Well, not strictly required..
Done.

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrBinHashKey.h#newcode88
src/gpu/GrBinHashKey.h:88: 
On 2013/11/26 14:20:43, mtklein wrote:
> same here with lessThan

Done.

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrResourceCache.h
File src/gpu/GrResourceCache.h (left):

https://codereview.chromium.org/88113002/diff/1/src/gpu/GrResourceCache.h#old...
src/gpu/GrResourceCache.h:136: 
On 2013/11/26 14:20:43, mtklein wrote:
> Does this intermediate Key struct really need to exist?  Those chains of
> GrResourceEntry.GrResourceKey.Key.HashedKey are pretty silly looking down
there.

Well, it might not be the only thing in this construct that is silly...
I tried to go along the lines of what you suggest. See if it's ok.

>  I think I'd like it a bit more if they read something like:
>   return entry.key().hashedKey().lessThan(key.hashedKey());
> 
> If we can keep lessThan and equals methods on GrResourceKey that inline, I'd
> like this even better:
>   return entry.key().lessThan(key);

Done.

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp
File tests/GrUnitTests.cpp (right):

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp#newcode8
tests/GrUnitTests.cpp:8: #include "GrRedBlackTree.h"
On 2013/11/26 14:20:43, mtklein wrote:
> Given the opportunity to start fresh, personally I'd do
> 
> #include "Test.h"
> #include "TestClassDef.h"
> 
> DEF_TEST(GrUnitTests_bsearch, reporter) {
>   ...
> }
> 
> DEF_TEST(GrUnitTests_binHashKey, reporter) {
>   ...
> }
> 
> DEF_TEST(GrUnitTests_redBlackTree, reporter) {
>   ...
> }

Done.

https://codereview.chromium.org/88113002/diff/1/tests/GrUnitTests.cpp#newcode10
tests/GrUnitTests.cpp:10: // FIXME: needs to be in a header
On 2013/11/26 14:20:43, mtklein wrote:
> Do any of these actually require SK_SUPPORT_GPU?  Seems like they're mostly
data
> structure tests.  If they do, that's fine.  If only some of them do, it'd be
> nice to run the others all the time.

Well, I thought the general line of thought is:
 -> SK_SUPPORT_GPU => Gr not compiled in
 -> Gr not compiled in => none of Gr can be expected to work
 -> none of Gr can be expected to work => do not test any functionality that
today might work only with includes. Tomorrow they might need something from the
"compiled files", too. 

In other words: currently most of the stuff in these tests are implemented
inline. If any of the functionality ever gains non-inline implementations, it
won't work.

[Kimmo Kinnunen, 2013-11-27 08:19:53]

On 2013/11/26 15:24:14, bsalomon wrote:
> Not directly part of this change, but should the benchs be marked as
> non-rendering? Running them in GPU and NULLGPU doesn't seem necessary.

It would need either support for mocking or writing GrResourceCache in a way
that would support it. GrResourceCache needs GrGpu, and as far as I understand,
the normal operation demands dominate the testing demands in current codebase?
Eg. if in normal code GrResourceCache always has a GrGpu, then it's documented
in the structure of the code by not having conditional paths just the sake of
running a bench test in non-rendering mode.

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

I'm fine with that reasoning.  I suppose what we ought to do is look at pulling
more of this support code out into a place that doesn't know about GPUs.

This LGTM (with a couple small requests).  Please let Brian get happy with the
change before submitting.

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
File src/gpu/effects/GrTextureStripAtlas.h (right):

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
src/gpu/effects/GrTextureStripAtlas.h:184: inline bool
GrTextureStripAtlas::AtlasHashKey::equals(const AtlasEntry& entry, const
AtlasHashKey& key) {
Wrap these guys to 100 columns?

https://codereview.chromium.org/88113002/diff/20001/tests/GrUnitTests.cpp
File tests/GrUnitTests.cpp (right):

https://codereview.chromium.org/88113002/diff/20001/tests/GrUnitTests.cpp#new...
tests/GrUnitTests.cpp:73: GrRedBlackTree<int>::UnitTest();
Can you add a little // TODO(mtklein): unwrap this and use reporter  ?

[bsalomon, 2013-11-27 14:46:01]

My comments are purely cosmetic. I'm happy with the change.

https://codereview.chromium.org/88113002/diff/20001/src/gpu/GrBinHashKey.h
File src/gpu/GrBinHashKey.h (right):

https://codereview.chromium.org/88113002/diff/20001/src/gpu/GrBinHashKey.h#ne...
src/gpu/GrBinHashKey.h:94: uint32_t            fData[KEY_SIZE / 4];  // Buffer
for key storage.
minor nit... I prefer sizeof(uint32_t) just as documentation of why this is
being done. (Also, you can ignore this :) )

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
File src/gpu/effects/GrTextureStripAtlas.h (right):

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
src/gpu/effects/GrTextureStripAtlas.h:141: static bool equals(const AtlasEntry&
entry, const AtlasHashKey& key);
I prefer the new names as well. But static functions in Skia are supposed to
begin with a capital letter (Equals, LessThan).

[Kimmo Kinnunen, 2013-11-28 07:38:34]

Thanks!

https://codereview.chromium.org/88113002/diff/20001/src/gpu/GrBinHashKey.h
File src/gpu/GrBinHashKey.h (right):

https://codereview.chromium.org/88113002/diff/20001/src/gpu/GrBinHashKey.h#ne...
src/gpu/GrBinHashKey.h:94: uint32_t            fData[KEY_SIZE / 4];  // Buffer
for key storage.
On 2013/11/27 14:46:01, bsalomon wrote:
> minor nit... I prefer sizeof(uint32_t) just as documentation of why this is
> being done. (Also, you can ignore this :) )

Done.
Though this was explicitly changed to not use sizeof due to the other place was
requested to hardcode the other half of the same idea. Now the code is
inconsistent.

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
File src/gpu/effects/GrTextureStripAtlas.h (right):

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
src/gpu/effects/GrTextureStripAtlas.h:141: static bool equals(const AtlasEntry&
entry, const AtlasHashKey& key);
On 2013/11/27 14:46:01, bsalomon wrote:
> I prefer the new names as well. But static functions in Skia are supposed to
> begin with a capital letter (Equals, LessThan).

Done.

https://codereview.chromium.org/88113002/diff/20001/src/gpu/effects/GrTexture...
src/gpu/effects/GrTextureStripAtlas.h:184: inline bool
GrTextureStripAtlas::AtlasHashKey::equals(const AtlasEntry& entry, const
AtlasHashKey& key) {
On 2013/11/27 14:36:54, mtklein wrote:
> Wrap these guys to 100 columns?

Done.

https://codereview.chromium.org/88113002/diff/20001/tests/GrUnitTests.cpp
File tests/GrUnitTests.cpp (right):

https://codereview.chromium.org/88113002/diff/20001/tests/GrUnitTests.cpp#new...
tests/GrUnitTests.cpp:73: GrRedBlackTree<int>::UnitTest();
On 2013/11/27 14:36:54, mtklein wrote:
> Can you add a little // TODO(mtklein): unwrap this and use reporter  ?

Done. (Though this TODO can be fixed also by removing the code altogether, since
it's dead code.)

[commit-bot: I haz the power, 2013-11-28 08:12:39]

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

[commit-bot: I haz the power, 2013-11-28 08:24:33]

Change committed as 12426