R-Tree -- Don't sort draw commands unless specified.

R-Tree -- Don't sort draw commands unless specified.
We expect Webkit and Bink to give us draw commands in a reasonable x,y order.
We can maintain correctness and get a 17% recording speedup for the R-Tree by
not sorting in x and y when bulk-loading.

R=caryclark@google.com, reed@google.com

Committed: https://code.google.com/p/skia/source/detail?r=11037

[sglez, 2013-08-26 22:19:56]

Hi. This is the CL that makes the R-Tree avoid sorting.

https://memegen.googleplex.com/5459606331457536

I read the part of the paper that describes the algorithm.

Sorting by x and y is a heuristic to produce prettier trees. Getting a
kind-of-sorted set of draw calls from Webkit / Blink seems to be good enough.
Avoiding the multiple calls to SkTQSort() gives a recording speed boost of ~17%.
I see no meaningful difference in playback speed.

I added the option to sort the draws as a class field. A global variable would
avoid carrying a bool around but I figured it wasn't worth it. Please tell me if
I'm wrong.

[caryclark, 2013-08-27 11:54:17]

Looks fine. Please create a unit test that exercises the boolean -- to show that
it still works both ways, and to get a testbed to measure and replicate the 17%
performance gain. The unit test need not use a full-blown skp, just dummy data
that is unsorted and nearly sorted.

https://codereview.chromium.org/23480002/diff/3001/src/core/SkRTree.cpp
File src/core/SkRTree.cpp (right):

https://codereview.chromium.org/23480002/diff/3001/src/core/SkRTree.cpp#newco...
src/core/SkRTree.cpp:331: // We expect Webkit / Bink to give us a reasonable x,y
order.
s/Bink/Blink

https://codereview.chromium.org/23480002/diff/3001/src/core/SkRTree.cpp#newco...
src/core/SkRTree.cpp:332: // Avoiding this call is a very big performance win
for recording with
s/is a very big/resulted in a 17%/

[sglez, 2013-08-29 18:57:54]

Added benches, Changed default behavior to use sorting, but changed the places
where the R-Tree is created to choose not to sort.

[reed1, 2013-08-29 19:17:34]

lgtm, but defer to cary

https://codereview.chromium.org/23480002/diff/16001/src/core/SkRTree.h
File src/core/SkRTree.h (right):

https://codereview.chromium.org/23480002/diff/16001/src/core/SkRTree.h#newcode59
src/core/SkRTree.h:59: bool orderWhenBulkLoading = true);
add a comment above for this new param?

[caryclark, 2013-08-29 19:22:18]

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp
File bench/RTreeBench.cpp (right):

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:172: out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS /
3);
this allows the right and bottom to be less than left and top. Since each is 1
or greater, I expect these are supposed to be width and height?

out.fRight = out.fLeft + 1 + rand.nextU() ...

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:219: SkRTree::Create(5, 16)));
should the strings for Fact0 and Fact1 be different?

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:223: SkRTree::Create(5, 16, 1, false)));
should the string passed to Fact2 and Fact4 be different, so one can tell which
gets the BBoxQueryBench::kRandom_QueryType parameter?

[sglez, 2013-08-29 20:17:38]

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp
File bench/RTreeBench.cpp (right):

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:172: out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS /
3);
On 2013/08/29 19:22:18, caryclark wrote:
> this allows the right and bottom to be less than left and top. Since each is 1
> or greater, I expect these are supposed to be width and height?
> 
> out.fRight = out.fLeft + 1 + rand.nextU() ...

Thanks

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:219: SkRTree::Create(5, 16)));
On 2013/08/29 19:22:18, caryclark wrote:
> should the strings for Fact0 and Fact1 be different?

They are the same, but the final bench name will be different.
Since the class is BBoxBuildBench, it will append "_build"
The "true" param at the end of this line tells it to use bulk loading.
It will append "_bulk"

So the name will appear as XYordered_build_bulk,
where Fact0 will appear as XYordered_build.

https://codereview.chromium.org/23480002/diff/16001/bench/RTreeBench.cpp#newc...
bench/RTreeBench.cpp:223: SkRTree::Create(5, 16, 1, false)));
On 2013/08/29 19:22:18, caryclark wrote:
> should the string passed to Fact2 and Fact4 be different, so one can tell
which
> gets the BBoxQueryBench::kRandom_QueryType parameter?

Same as before, but instead of appending _build it appends _query.

[caryclark, 2013-08-29 20:38:40]

lgtm

[sglez, 2013-08-30 17:27:56]

Committed patchset #5 manually as r11037 (presubmit successful).