Move second internal recursion to a precomputation in layer_tree_host_common.cc

Move second internal recursion to a precomputation in layer_tree_host_common.cc

Asymptotically, the recursive algorithm in calculateDrawTransforms is O(n^2)
because of a secondary recursion that occurs for every layer in
subtreeShouldRenderToSeparateSurface.

This patch moves the internal secondary recursion into a pre-walk, caching
the meaningful result of that recursion, so that the algorithm is O(2 * n).

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=172682

[shawnsingh, 2012-12-03 08:02:17]

Summary: performance doesn't improve, seems to stay approximately the same.  So
James I'm not sure this patch is worth doing.  But it's done anyway so I
uploaded just for kicks.

But, here's something interesting - My first version actually performed
marginally worse that the original tip-of-tree code on cc_perftests.

Patch 2 performs approximately the same, as far as I can tell.  The only
difference is that I cache the boolean value that avoids making the virtual
function call 3-4 times.

I guess it's a pretty obvious thing to do in retrospect, but that leads to
another optimization point that we should seriously consider - reducing the
number of virtuals we have, particularly for trivial data accessors like this.

[danakj, 2012-12-03 18:33:41]

https://codereview.chromium.org/11419284/diff/2001/cc/layer_impl.h
File cc/layer_impl.h (right):

https://codereview.chromium.org/11419284/diff/2001/cc/layer_impl.h#newcode103
cc/layer_impl.h:103: virtual int numDescendantsThatDrawContent() { return
m_numDescendantsThatDrawContent; }
i like the function name

https://codereview.chromium.org/11419284/diff/2001/cc/layer_impl.h#newcode104
cc/layer_impl.h:104: void setNumDescendantsThatDrawContent(int num) {
m_numDescendantsThatDrawContent = num; }
I kinda don't like this. Set/get seems simple but then sometimes the set does
nothing, even tho the variable would be set on the class. Then maybe members of
layer_impl.cc end up using m_numDescendantsThatDrawContent instead of the
function and have the wrong value..

It seems awkward to me.

https://codereview.chromium.org/11419284/diff/2001/cc/layer_tree_host_common.cc
File cc/layer_tree_host_common.cc (right):

https://codereview.chromium.org/11419284/diff/2001/cc/layer_tree_host_common....
cc/layer_tree_host_common.cc:269: bool atLeastTwoLayersInSubtreeDrawContent =
numDescendantsThatDrawContent > 0
i like this var name

https://codereview.chromium.org/11419284/diff/2001/cc/layer_tree_host_common....
cc/layer_tree_host_common.cc:270: && (layer->drawsContent() ||
numDescendantsThatDrawContent > 1);
the "if" seems to have disappeared entirely.

[shawnsingh, 2012-12-03 19:40:34]

Ohhh, I'm really sorry I made you review this.  I should have said "NOT FOR
REVIEW".

The truth is, I don't think the gains of this patch were significant enough. 
Actually I uploaded it only for jamesr@ to try, if he wanted to try testing
performance on other platforms.  I only tried on linux z620.

If we do move forward with it, I'll address these comments, though.

[slavi, 2012-12-03 21:33:32]

It's interesting that we don't see any improvement from that patch. 

It will never do more work than what we were doing before. And it's also
guaranteed to always be O(n) while we might get O(n^2) in the worst case from
code checking in right now.

I'm in favor of checking in a cleaned up version of that.

Besides the comments I made on the code, I would love to see
m_numDescendantsThatDrawContent and it's getters and setters out of Layer and
LayerImpl since cc/layer_tree_host_common.cc is the only place they're used. How
about a hashtable unordered_map<Layer*, int> in layer_tree_host_common.cc that
gets filled with one linear traversal?

[slavi, 2012-12-03 21:33:42]

https://codereview.chromium.org/11419284/diff/2001/cc/layer.h
File cc/layer.h (right):

https://codereview.chromium.org/11419284/diff/2001/cc/layer.h#newcode419
cc/layer.h:419: bool m_numDescendantsThatDrawContent;
That should be an int.

https://codereview.chromium.org/11419284/diff/2001/cc/layer_impl.h
File cc/layer_impl.h (right):

https://codereview.chromium.org/11419284/diff/2001/cc/layer_impl.h#newcode425
cc/layer_impl.h:425: bool m_numDescendantsThatDrawContent;
That should be an int.

[shawnsingh, 2012-12-03 23:05:12]

So after offline discussion with slavi and jamesr:

Slavi had the very good point that the cc_perftests benchmark I was running is a
very wide and shallow tree structure that wouldn't benefit from this patch
anyway.  There are other very common cases where deeper tree structures may
still benefit.  I should try running other tests, perhaps scrolling_benchmark to
test other common pages.

Will upload new patch after addressing comments.

[jamesr, 2012-12-04 06:09:01]

On 2012/12/03 21:33:32, slavi wrote:
> Besides the comments I made on the code, I would love to see
> m_numDescendantsThatDrawContent and it's getters and setters out of Layer and
> LayerImpl since cc/layer_tree_host_common.cc is the only place they're used.
How
> about a hashtable unordered_map<Layer*, int> in layer_tree_host_common.cc that
> gets filled with one linear traversal?

I think that's overkill - having a map on the side will cost a fair bit of
memory and setup/shutdown cost.  We can put it on the shared DrawProperties
struct from https://codereview.chromium.org/11280263/ so it doesn't live
directly on either Layer type and is clearly calculated as a side effect of
layer_tree_host_common

[shawnsingh, 2012-12-12 11:54:52]

This patch is rebooted now.  PTAL, thanks!

[jamesr, 2012-12-12 16:54:25]

lgtm

https://codereview.chromium.org/11419284/diff/12001/cc/layer_tree_host_common.cc
File cc/layer_tree_host_common.cc (right):

https://codereview.chromium.org/11419284/diff/12001/cc/layer_tree_host_common...
cc/layer_tree_host_common.cc:286: (numDescendantsThatDrawContent > 0 &&
(layer->drawsContent() || numDescendantsThatDrawContent > 1));
nit: odd indentation. 4 spaces for a continuation

https://codereview.chromium.org/11419284/diff/12001/cc/layer_tree_host_common...
cc/layer_tree_host_common.cc:912:
cc::preCalculateMetaInformation<Layer>(rootLayer);
we're in namespace cc:: here, aren't we? we shouldn't need the cc:: prefix

https://codereview.chromium.org/11419284/diff/12001/cc/layer_tree_host_common...
cc/layer_tree_host_common.cc:941:
cc::preCalculateMetaInformation<LayerImpl>(rootLayer);
ditto

[slavi, 2012-12-12 21:46:01]

Awesome lgtm.