First-time sync: asymptotic running time improvement

sync: Optimize GetFirstChildId and ComputePrevIdFromServerPosition by having the parent/child index be sorted by SERVER_POSITION_IN_PARENT, rather than arbitrarily.

This fixes two longstanding TODOs and yields the following perf improvement on "SyncerTest.OneBajillionUpdates":
Release build (7000ms -> 500ms)
Debug build (70000ms -> 3000ms)

BUG=60236, chromium-os:11226
TEST=sync_unit_tests (SyncerPosition* gives good coverage)

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=76700

[ncarter (slow), 2011-03-02 17:11:19]

Hi Nicolas,

Please review.

[tim (not reviewing), 2011-03-02 17:17:57]

On 2011/03/02 17:11:19, ncarter wrote:
> Hi Nicolas,
> 
> Please review.

awesome
drive-by: base URL looks weird? is that normal?

[Nicolas Zea, 2011-03-02 22:58:01]

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
File chrome/browser/sync/syncable/syncable.cc (right):

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:1628:
GetParentChildIndexUpperBound(lock, parent_id);
The first candidate will actually have parent_id+1, so should not be a valid
child of this parent right?

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:1662: while (sibling != first_sibling)
{
I think this prevents the possibility of having the candidate be first_sibling
(since lowerbound can be a valid entry right?). Should it not be a while
(not_done), and at the end of the loop if (sibling == first_sibling) break;

[ncarter (slow), 2011-03-02 23:58:16]

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
File chrome/browser/sync/syncable/syncable.cc (right):

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:1628:
GetParentChildIndexUpperBound(lock, parent_id);
On 2011/03/02 22:58:02, nzea wrote:
> The first candidate will actually have parent_id+1, so should not be a valid
> child of this parent right?

It's subtle, but I think it's okay.  The pattern used by this loop is:

for (; lo != hi; hi--) {
  do something with (hi - 1)
}

http://codereview.chromium.org/6588119/diff/6001/chrome/browser/sync/syncable...
chrome/browser/sync/syncable/syncable.cc:1662: while (sibling != first_sibling)
{
On 2011/03/02 22:58:02, nzea wrote:
> I think this prevents the possibility of having the candidate be first_sibling
> (since lowerbound can be a valid entry right?). Should it not be a while
> (not_done), and at the end of the loop if (sibling == first_sibling) break;

I think it works okay for the same reason as the previous comment.

[Nicolas Zea, 2011-03-03 00:15:58]

Once you figure out the bug and trybots pass, LGTM

[ncarter (slow), 2011-03-03 02:03:55]

On 2011/03/03 00:15:58, nzea wrote:
> Once you figure out the bug and trybots pass, LGTM

Found the bug; I've updated syncable_id.cc and added a unittest to
syncable_id_unittest.cc .  Will submit once trybots are all green.