Slightly faster quadtree searching

Slightly faster quadtree searching

BUG=skia:2125
Committed: http://code.google.com/p/skia/source/detail?r=13847

[iancottrell, 2014-03-17 13:13:59]

A version that does less maths because it knows you have 4 quadrants due to 2
axis aligned splits.

[robertphillips, 2014-03-17 13:26:51]

drive by nits

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:20: };
kTopLeft_Bit, etc.?

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:33: 
child_intersect

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:63: case kTopLeftBit:
this-> on all inserts

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:83: if (node->fEntries.getCount() > kSplitThreshold) {
this->split

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:128: if (intersect & (1 << index)) {
this->

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:149: int maxDepth = 0;
NULL != node

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:176: if (SkIRect::Intersects(fRootBounds, query)) {
this->

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:182: if (NULL != fRoot) {
this->INHERITED::  ?

[tomhudson, 2014-03-17 13:27:32]

How much faster?

There are a couple of other things going on here, like getting rid of explicitly
tracking the count...

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:82: // should I split?
Got rid of minimum size?

[mtklein, 2014-03-17 13:29:55]

On 2014/03/17 13:27:32, tomhudson wrote:
> How much faster?

≈ add a bench?

[iancottrell, 2014-03-17 13:49:35]

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:20: };
On 2014/03/17 13:26:52, robertphillips wrote:
> kTopLeft_Bit, etc.?

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:33: 
On 2014/03/17 13:26:52, robertphillips wrote:
> child_intersect

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:63: case kTopLeftBit:
On 2014/03/17 13:26:52, robertphillips wrote:
> this-> on all inserts

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:82: // should I split?
On 2014/03/17 13:27:32, tomhudson wrote:
> Got rid of minimum size?

Yes, turns out it has no benefit.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:83: if (node->fEntries.getCount() > kSplitThreshold) {
On 2014/03/17 13:26:52, robertphillips wrote:
> this->split

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:128: if (intersect & (1 << index)) {
On 2014/03/17 13:26:52, robertphillips wrote:
> this->

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:149: int maxDepth = 0;
On 2014/03/17 13:26:52, robertphillips wrote:
> NULL != node

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:176: if (SkIRect::Intersects(fRootBounds, query)) {
On 2014/03/17 13:26:52, robertphillips wrote:
> this->

Done.

https://codereview.chromium.org/196383026/diff/60001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:182: if (NULL != fRoot) {
On 2014/03/17 13:26:52, robertphillips wrote:
> this->INHERITED::  ?
No need for INHERITED, this-> added

[iancottrell, 2014-03-17 14:24:06]

On 2014/03/17 13:29:55, mtklein wrote:
> On 2014/03/17 13:27:32, tomhudson wrote:
> > How much faster?
> 
> ≈ add a bench?

The difference is really small, mostly because this code is a tiny fraction of
the cost anyway. I would rather not add a new bench given that I am only
submitting this code for history, I want to delete it all soon.

bbh_shootout results:

Before:
Average quadtree recording time: 0.471ms
Average quadtree playback time: 27.176ms

After:
Average quadtree recording time: 0.464ms
Average quadtree playback time: 26.976ms

[mtklein, 2014-03-17 15:05:14]

https://codereview.chromium.org/196383026/diff/80001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/196383026/diff/80001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:34: static int child_intersect(const SkIRect& query,
const SkIPoint& split) {
Might be clearer to work with U8CPU (which == unsigned) to make it clear this is
mask of <=8 bits, not a number?

[iancottrell, 2014-03-17 16:32:38]

https://codereview.chromium.org/196383026/diff/80001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/196383026/diff/80001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:34: static int child_intersect(const SkIRect& query,
const SkIPoint& split) {
On 2014/03/17 15:05:15, mtklein wrote:
> Might be clearer to work with U8CPU (which == unsigned) to make it clear this
is
> mask of <=8 bits, not a number?

Done.

[mtklein, 2014-03-17 19:41:29]

lgtm

[tomhudson, 2014-03-18 08:52:23]

lgtm

[commit-bot: I haz the power, 2014-03-18 08:52:35]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/iancottrell@google.com/196383026/90001

[commit-bot: I haz the power, 2014-03-18 09:07:30]

Change committed as 13847