sync: Count nodes more efficiently

sync: Count nodes more efficiently

The GetTotalNodesCount() function is called sufficiently often that it
makes sense to spend some effort optimizing its implementation.

The current implementation uses some traversal functions that are fairly
slow, especially since GetSuccessorId() was made more expensive by the
implementation of UniquePositions.

This change moves the implementation into the syncable::Directory.  This
allows it to take advantage of the Directory's internal data structures
and avoid unnecessary lookups. 

BUG=248143, 238621
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=202973

[rlarocque, 2013-05-21 00:09:06]

Please review.

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc
File sync/syncable/directory.cc (right):

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc...
sync/syncable/directory.cc:348: void Directory::GetTotalNodeCountImpl(
This is the main reason I wanted to use recursion.  I'm not sure how to name
this function.  If I use recursion, then this function is no longer necessary,
and the naming problem disappears.

[rlarocque, 2013-05-28 18:22:58]

Re-assigning to Nicolas because Tim will be OOO for a while.

The original review message references a discussion Tim and I had earlier about
whether or not it's a good idea to use recursion to traverse the
syncable::Directory.  There are some technical arguments in favor of not using
recursion, though I think the recursive version of the code is easier to
understand.  I'd be OK with either approach, though I have a slight preference
for the non-recursive version.

[Nicolas Zea, 2013-05-28 22:12:39]

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc
File sync/syncable/directory.cc (right):

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc...
sync/syncable/directory.cc:324: int Directory::GetTotalNodeCount(
this seems complex enough to warrant a unit test, or are there existing ones
that cover this?

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc...
sync/syncable/directory.cc:348: void Directory::GetTotalNodeCountImpl(
On 2013/05/21 00:09:07, rlarocque wrote:
> This is the main reason I wanted to use recursion.  I'm not sure how to name
> this function.  If I use recursion, then this function is no longer necessary,
> and the naming problem disappears.

Seems like it's just a child grabber right? Maybe something like
GetChildrenForKernel?

That said, this method seems like it's just a wrapper for GetChildren, and isn't
used anywhere else. Given that GetTotalNodeCount isn't doing much to being with,
you could just inline this logic, and avoid the naming issue altogether.

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.h
File sync/syncable/directory.h (right):

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.h#...
sync/syncable/directory.h:460: 
remove extra newline, and period at end of comment.

[rlarocque, 2013-05-29 19:01:13]

PTAL.

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc
File sync/syncable/directory.cc (right):

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc...
sync/syncable/directory.cc:324: int Directory::GetTotalNodeCount(
On 2013/05/28 22:12:39, Nicolas Zea wrote:
> this seems complex enough to warrant a unit test, or are there existing ones
> that cover this?

There are some existing tests.  See SyncApiTest.GetTotalNodeCount*.

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.cc...
sync/syncable/directory.cc:348: void Directory::GetTotalNodeCountImpl(
On 2013/05/28 22:12:39, Nicolas Zea wrote:
> On 2013/05/21 00:09:07, rlarocque wrote:
> > This is the main reason I wanted to use recursion.  I'm not sure how to name
> > this function.  If I use recursion, then this function is no longer
necessary,
> > and the naming problem disappears.
> 
> Seems like it's just a child grabber right? Maybe something like
> GetChildrenForKernel?

I like that general idea.  I decided to go with GetChildSetForKernel.

> That said, this method seems like it's just a wrapper for GetChildren, and
isn't
> used anywhere else. Given that GetTotalNodeCount isn't doing much to being
with,
> you could just inline this logic, and avoid the naming issue altogether.

It would have to be inlined at both line 334 and line 341.  I'd prefer to avoid
that.

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.h
File sync/syncable/directory.h (right):

https://codereview.chromium.org/15322003/diff/3001/sync/syncable/directory.h#...
sync/syncable/directory.h:460: 
On 2013/05/28 22:12:39, Nicolas Zea wrote:
> remove extra newline, and period at end of comment.

Done.

[Nicolas Zea, 2013-05-29 19:02:30]

lgtm

[commit-bot: I haz the power, 2013-05-29 19:03:50]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rlarocque@chromium.org/15322003/13001

[commit-bot: I haz the power, 2013-05-29 21:18:33]

Change committed as 202973