Optimize region intersection if A contains B

Optimize region intersection if A contains B

This patchset is to optimize the region intersection if one region contains another. The fix is straightforward, but I also wrote a bench to cover this.
Test command:
time out/Release/bench --match region_contain_sect --repeat 10000

Test result:
Original code:
running bench [640 480]          region_contain_sect  8888: cmsecs =   0.67
out/Release/bench --match region_contain_sect --repeat 10000  7.04s user 0.07s system 99% cpu 7.153 total

Optimized code:
running bench [640 480]          region_contain_sect  8888: cmsecs =   0.06
out/Release/bench --match region_contain_sect --repeat 10000  0.88s user 0.07s system 97% cpu 0.979 total

It's about 10x speedup.

BUG=

[reed1, 2013-01-30 13:54:19]

Patch looks clean. Do we see any real slow-down in the case where one does *not*
contain the other?

[gyagp, 2013-01-30 14:38:21]

> -----Original Message-----
> From: reed@google.com [mailto:reed@google.com]
> Sent: Wednesday, January 30, 2013 9:54 PM
> To: Gu, Yang; reed@android.com; epoger@google.com; rmistry@google.com;
> djsollen@google.com
> Cc: skia-review@googlegroups.com; reply@codereview-hr.appspotmail.com
> Subject: Re: Optimize region intersection if A contains B (issue 7237055)
> 
> Patch looks clean. Do we see any real slow-down in the case where one does
*not*
> contain the other?

There are four basic ops: difference, union, xor and intersect. Xor is not
meaningful (result is either rgna or rgnb or empty) even if one contains
another. And for the other two, difference and union, current code already does
this kind of optimization. That is, the bounds of region has already been
calculated, so the overhead of this patch for *not* contain case should be
trivial. There is no reason intersect should miss this optimization. 


Regards,
-Yang

[reed1, 2013-01-30 15:00:54]

My question is: have you run the other benchmarks for region to see if there was
any negative impact on them (in the intersect case) w/ your patch.

For example, do we have a bench that times calling intersect where your new
tests fail, and we still have to fall through to the current code? I don't
expect to see it, but I think its good practice to measure this before we land
the change.

[gyagp, 2013-01-30 15:56:13]

> -----Original Message-----
> From: reed@google.com [mailto:reed@google.com]
> Sent: Wednesday, January 30, 2013 11:01 PM
> To: Gu, Yang; reed@android.com; epoger@google.com; rmistry@google.com;
> djsollen@google.com
> Cc: skia-review@googlegroups.com; reply@codereview-hr.appspotmail.com
> Subject: Re: Optimize region intersection if A contains B (issue 7237055)
> 
> My question is: have you run the other benchmarks for region to see if there
was any
> negative impact on them (in the intersect case) w/ your patch.
> 
> For example, do we have a bench that times calling intersect where your new
tests
> fail, and we still have to fall through to the current code? I don't expect to
see it, but
> I think its good practice to measure this before we land the change.

Thanks for the comment! 
I did below change in my submitted RegionContainBench.cpp
- fB.setRect(0, 0, H, W); // W == 200
+ fB.setRect(0, 0, H, 20);

In the submitted bench code, fB is big enough to contain fA. With this change,
fB will be no longer (or at least most of time as fA generates in random)
contain fA, so we will fall through to current code with my patch. Below are the
test results (test command is same as before):
Original code (3 times):
running bench [640 480]          region_contain_sect  8888: cmsecs =   0.32
out/Release/bench --match region_contain_sect --repeat 10000  3.36s user 0.02s
system 99% cpu 3.414 total

running bench [640 480]          region_contain_sect  8888: cmsecs =   0.32
out/Release/bench --match region_contain_sect --repeat 10000  3.36s user 0.02s
system 98% cpu 3.420 total

running bench [640 480]          region_contain_sect  8888: cmsecs =   0.32
out/Release/bench --match region_contain_sect --repeat 10000  3.36s user 0.02s
system 99% cpu 3.417 total

Optimized code (3 times):
running bench [640 480]          region_contain_sect  8888: cmsecs =   0.33
out/Release/bench --match region_contain_sect --repeat 10000  3.40s user 0.02s
system 99% cpu 3.462 total

running bench [640 480]          region_contain_sect  8888: cmsecs =   0.33
out/Release/bench --match region_contain_sect --repeat 10000  3.41s user 0.02s
system 99% cpu 3.463 total

running bench [640 480]          region_contain_sect  8888: cmsecs =   0.32
out/Release/bench --match region_contain_sect --repeat 10000  3.38s user 0.02s
system 99% cpu 3.408 total

The results fluctuated a little, but overall there is no obvious overhead for my
patch. Please kindly comment if I should do more tests. 

Regards,
-Yang

[reed1, 2013-01-30 17:01:45]

That is exactly the test I wanted to see performed. I agree that any slowdown
seems to be insignificant.

LGTM

[rmistry, 2013-01-30 17:10:59]

https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp
File bench/RegionContainBench.cpp (right):

https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp#ne...
bench/RegionContainBench.cpp:3: * Copyright 2011 Google Inc.
nit: 2011 -> 2013

[gyagp, 2013-01-31 02:39:03]

Fixed and please review it again. Thanks!


On 2013/01/30 17:10:59, rmistry wrote:
> https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp
> File bench/RegionContainBench.cpp (right):
> 
>
https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp#ne...
> bench/RegionContainBench.cpp:3: * Copyright 2011 Google Inc.
> nit: 2011 -> 2013

[gyagp, 2013-01-31 02:49:40]

https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp
File bench/RegionContainBench.cpp (right):

https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp#ne...
bench/RegionContainBench.cpp:3: * Copyright 2011 Google Inc.
On 2013/01/30 17:10:59, rmistry wrote:
> nit: 2011 -> 2013

Fixed, and please review again. Thanks!

[rmistry, 2013-01-31 13:38:26]

On 2013/01/31 02:49:40, gyagp wrote:
> https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp
> File bench/RegionContainBench.cpp (right):
> 
>
https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp#ne...
> bench/RegionContainBench.cpp:3: * Copyright 2011 Google Inc.
> On 2013/01/30 17:10:59, rmistry wrote:
> > nit: 2011 -> 2013
> 
> Fixed, and please review again. Thanks!

LGTM from me since Mike LGTM'ed.

[reed1, 2013-01-31 15:02:50]

On 2013/01/31 13:38:26, rmistry wrote:
> On 2013/01/31 02:49:40, gyagp wrote:
> > https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp
> > File bench/RegionContainBench.cpp (right):
> > 
> >
>
https://codereview.appspot.com/7237055/diff/1/bench/RegionContainBench.cpp#ne...
> > bench/RegionContainBench.cpp:3: * Copyright 2011 Google Inc.
> > On 2013/01/30 17:10:59, rmistry wrote:
> > > nit: 2011 -> 2013
> > 
> > Fixed, and please review again. Thanks!
> 
> LGTM from me since Mike LGTM'ed.

Having trouble applying the patch. Please be sure you build your patch/diff from
the trunk of skia...

skia/trunk> gcl change foo
skia/trunk> gcl upload foo

[DerekS, 2013-01-31 15:15:06]

just use -p1 on the patch command to strip out the a/b directory stuff that git
adds to the diff path

[reed1, 2013-01-31 15:24:42]

committed in rev. 7491

[epoger, 2013-01-31 16:39:23]

On 2013/01/31 15:15:06, DerekS wrote:
> just use -p1 on the patch command to strip out the a/b directory stuff that
git
> adds to the diff path

This and related tips can be found at
https://sites.google.com/site/skiadocs/developer-documentation/contributing-c...

[lux.kochetkov, 2016-09-07 20:30:46]

On 2013/01/31 16:39:23, epoger wrote:
> On 2013/01/31 15:15:06, DerekS wrote:
> > just use -p1 on the patch command to strip out the a/b directory stuff that
> git
> > adds to the diff path
> 
> This and related tips can be found at
>
https://sites.google.com/site/skiadocs/developer-documentation/contributing-c...

[lux.kochetkov, 2016-09-07 20:35:18]

More of an old 👵

[reed1, 2016-09-07 20:44:57]

The optimization seems to be in the code (not sure when it was added). So can we
close this CL?

[status.rpni, 2019-08-07 19:38:03]

Publikasi