Sync: Improve Bookmark association time when running with 10K+ bookmarks.

Sync: Improve Bookmark association time when running with 10K+ bookmarks.

I profiled Bookmark Sync association code on a Windows workstation with about 16K folders and bookmarks. This was for the scenario when bookmarks had been already synced and and BookmarkModelAssociator::BuildAssociations needed to match sync data to the already existing bookmark model.

While it was fairly fast in absolute terms (less than 1 sec on my rather powerful workstation), I verified that 59% of samples for the UI thread were in BookmarkModelAssociator::BuildAssociations.

The top 3 functions called from BuildAssociations and their costs in terms of UI thread sample counts are:

browser_sync::BookmarkNodeFinder::FindBookmarkNode	- 20.7%
browser_sync::BookmarkChangeProcessor::UpdateBookmarkWithSyncData	- 14.6%
browser_sync::BookmarkNodeFinder::BookmarkNodeFinder - 13.9%

Altogether BookmarkNodeFinder was responsible for almost 35% of all UI thread samples.
Furthermore UTF16ToUTF8 function alone was responsible for 24% of UI thread samples.

The reason UTF16ToUTF8 is so expensive is because it is used in custom comparator used with multiset which is a part of BookmarkNodeFinder implementation.
Each bookmark node gets added and searched to BookmarkNodeFinder once.
Altogether that results in approx 2*2*(N*logN/2) calls of UTF16ToUTF8 (and
also N calls of UTF8ToUTF16). Each conversion involves an allocation.
On a mobile platform the relative cost of this should be even higher because
memory tends to be slower and CPU caches smaller.

The fix replaces multiset with a hash_multimap where the key is the converted
bookmark title. Therefore UTF16ToUTF8 ends up being called only once for each node and due to different lookup (by title vs. by node) UTF8ToUTF16 calls are eliminated.
Also hashing should work more efficiently for long bookmark/folder titles than the binary search.

Measurement showed that improved combined cost of BookmarkNodeFinder::BookmarkNodeFinder and BookmarkNodeFinder::FindBookmarkNode - close to 5x. And the overall cost of bookmark association - improved by 1.5-2x (when measured on my windows dev workstation).

There is also an opportunity to optimize UpdateBookmarkWithSyncData which blindly applies data even when it guaranteed to be exactly the same, but I didn't touch it in this change.

BUG=238621
Committed: https://crrev.com/2af5d96b379df6df01133e985051311adc581935
Cr-Commit-Position: refs/heads/master@{#297349}

[stanisc, 2014-09-25 22:26:42]

Patchset #1 (id:1) has been deleted

[stanisc, 2014-09-26 06:29:02]

Patchset #1 (id:20001) has been deleted

[stanisc, 2014-09-26 06:29:21]

Patchset #1 (id:40001) has been deleted

[stanisc, 2014-09-26 06:30:39]

stanisc@chromium.org changed reviewers:
+ zea@chromium.org

[Nicolas Zea, 2014-09-29 18:33:56]

Mostly LG. You mentioned that there was an issue with your initial
implementation that resulted in mismatches when used on real data, right? Does
it make sense to add a unit test to cover that case?

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
File chrome/browser/sync/glue/bookmark_model_associator.cc (right):

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:84: // Maps bookmark node
titles to instances, duplicates allowed
nit: Comment that the title is stored in sync internal server format.

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:120:
syncer::SyncAPINameToServerName(title, &title);
nit: probably good to go ahead and pull this and the truncate call into a single
helper method.

[stanisc, 2014-09-29 22:34:22]

I've addressed the CR feedback.

Regarding the issue with the title mismatch in the initial implementation,
it was due to the missing conversion to the internal sync
name in BookmarkNodeFinder::FindBookmarkNode method.
I thought that since the name came from the directory it was already in the
right format but it turned out the
match failed for folders with empty (zero-length) names.

There is already a unit test that catches that:
ProfileSyncServiceBookmarkTest.CornerCaseNames
I verified that if I remove the title conversion from
BookmarkNodeFinder::FindBookmarkNode the test fails.

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
File chrome/browser/sync/glue/bookmark_model_associator.cc (right):

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:84: // Maps bookmark node
titles to instances, duplicates allowed
On 2014/09/29 18:33:56, Nicolas Zea wrote:
> nit: Comment that the title is stored in sync internal server format.

Done.

https://codereview.chromium.org/603153005/diff/60001/chrome/browser/sync/glue...
chrome/browser/sync/glue/bookmark_model_associator.cc:120:
syncer::SyncAPINameToServerName(title, &title);
On 2014/09/29 18:33:56, Nicolas Zea wrote:
> nit: probably good to go ahead and pull this and the truncate call into a
single
> helper method.

Done.

[Nicolas Zea, 2014-09-29 22:36:00]

LGTM, nice job!

[stanisc, 2014-09-30 02:50:36]

The CQ bit was checked by stanisc@chromium.org

[commit-bot: I haz the power, 2014-09-30 02:52:33]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/603153005/80001

[commit-bot: I haz the power, 2014-09-30 03:06:35]

Committed patchset #2 (id:80001) as 87135e1bc4166ff310a3d48add0ef01c0ed045a6

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

Patchset 2 (id:??) landed as
https://crrev.com/2af5d96b379df6df01133e985051311adc581935
Cr-Commit-Position: refs/heads/master@{#297349}