Omnibox: BookmarksProvider: Make Multiple Prefix Matches Work

Omnibox: BookmarksProvider: Make Multiple Prefix Matches Work

This code significantly simplies the logic for matching.

Indeed, the old logic was buggy because multiple prefix matches could
results in explosive growth of the list of matches (even if only one
bookmark matches).  Reviewer, I would avoid reading and trying to
understand what CombineMatches() and the code that calls it is currently
broken.  See the second test case I added.  Before this
change, that test never terminates (in the time I waited) and explodes
the machine's memory.  Luckily this was rare; there are few reports on
crbug.

It's possible this new code is slower or faster than before (when the
old code behaved correctly).  I plan to look at the
Omnibox.Providertime.Bookmarks numbers before and after this change.

TBR=sky for owners stamp; review it if you feel like

BUG=450850, 434604
Committed: https://crrev.com/02f304ba896632433d2e91b57c381cca90d4c7b9
Cr-Commit-Position: refs/heads/master@{#313574}

[Mark P, 2015-01-28 00:07:54]

mpearson@chromium.org changed reviewers:
+ pkasting@chromium.org

[Mark P, 2015-01-28 00:08:13]

Peter, please take a look.

thanks,
mark

[Peter Kasting, 2015-01-28 01:59:40]

LGTM

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
File components/bookmarks/browser/bookmark_index.cc (right):

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:227:
CombineMatchesInPlace(i->second, matches);
Is the efficiency gain of this function important, versus doing:

  *matches = STLSetIntersection(i->second, *matches);

...using stl_util.h?  (2 places)

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:236: prefix_matches = matches;
Nit:

    NodeSet* prefix_matches = first_term ? matches : &tmp_prefix_matches;

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:258: // In case of an empty
intersection, skip the swap() for efficiency.
Nit: Can move this above conditional and eliminate {}

[Mark P, 2015-01-28 18:35:10]

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
File components/bookmarks/browser/bookmark_index.cc (right):

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:227:
CombineMatchesInPlace(i->second, matches);
On 2015/01/28 01:59:40, Peter Kasting wrote:
> Is the efficiency gain of this function important, versus doing:
> 
>   *matches = STLSetIntersection(i->second, *matches);
> 
> ...using stl_util.h?  (2 places)

I don't know anything about the efficiency gain; I merely know this is how the
function was before.  I'm inclined to go with your cleaner suggestion (both
places).  Removed the whole CombineMatchesInPlace function.

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:236: prefix_matches = matches;
On 2015/01/28 01:59:40, Peter Kasting wrote:
> Nit:
> 
>     NodeSet* prefix_matches = first_term ? matches : &tmp_prefix_matches;

Done.

https://codereview.chromium.org/882823004/diff/1/components/bookmarks/browser...
components/bookmarks/browser/bookmark_index.cc:258: // In case of an empty
intersection, skip the swap() for efficiency.
On 2015/01/28 01:59:40, Peter Kasting wrote:
> Nit: Can move this above conditional and eliminate {}

Now obsolete.

[Mark P, 2015-01-28 18:35:40]

The CQ bit was checked by mpearson@chromium.org

[commit-bot: I haz the power, 2015-01-28 18:37:54]

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

[commit-bot: I haz the power, 2015-01-28 18:46:31]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2015-01-28 18:46:32]

Try jobs failed on following builders:
  android_chromium_gn_compile_dbg on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/android_chromiu...)

[Mark P, 2015-01-28 19:22:04]

The CQ bit was checked by mpearson@chromium.org

[commit-bot: I haz the power, 2015-01-28 19:22:54]

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

[commit-bot: I haz the power, 2015-01-28 20:33:30]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-01-28 20:34:29]

Patchset 4 (id:??) landed as
https://crrev.com/02f304ba896632433d2e91b57c381cca90d4c7b9
Cr-Commit-Position: refs/heads/master@{#313574}

[Mark P, 2015-05-19 20:19:37]

For the record, I check the UMA dashboard.  It seems this change
(which, recall, I made for correctness, not speed) did end up
slowing down BookmarkProvider a bit.  I couldn't see the impact
of the change on either the median response time or the geometric
mean of response times but I did see it on the arthimetic mean
graph and on the 99th percentile graph.  When this change launched,
it slowed BookmarkProvider down on (arithmetic mean) average by
0.1ms (which is about 15% because the provider is normally fast)
and the 99th percentile by 0.4ms (which is also about 15%).

This is not enough to concern me, especially as I see that often
our major version revisions (due to other changes) cause larger
movements in these metrics.

--mark