Change HistoryInfoMap to use unordered_map.

Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large profile and checking the value of the Omnibox.CharTypedToRepaintLatency histogram.

This was also validated when profiling, where the find method was the top function where CPU cycles were consumed. After switching to a hash map, it was a non factor.

Note: As far as I can tell, the order is not important, so this change doesn't alter expected behavior.

BUG=574181
Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}

Committed: https://crrev.com/b7f91c31bce64a4bd61b16ce52cc9314e09cca57
Cr-Commit-Position: refs/heads/master@{#373349}

[Georges Khalil, 2015-11-25 18:18:42]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

BUG=
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests.

As far as I can tell, the order is not important, so this change doesn't alter
expected behavior.

BUG=
==========

[Georges Khalil, 2015-11-25 18:18:42]

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

[Georges Khalil, 2015-11-25 18:19:33]

Mark, PTAL.

I think this change doesn't change expected behavior, but you would know better.
Thanks.

[Mark P, 2015-11-25 19:13:21]

I'll have to think about this.  I know some of the stl containers in this file
must be sorted because we use STL helpers to do things like merge two sorted
lists.  I think you're probably right that this one doesn't have to be but I'll
have to dive deeper to see how it's being used.

CCing pkasting@ because he reviewed the original code and he can perhaps speak
to whether he paid attention to the ordered/unordered/hash nature of these STL
containers.

Have you tested this using about:omnibox (looking only at HistoryQuick provider
suggestions) on multi-word inputs, with words appearing in different orders, and
with URLs that have been visited in different orders?  Those the situations I'd
worry about.

--mark

[Georges Khalil, 2015-11-25 20:14:56]

In my tests, I did not see any difference.

[Peter Kasting, 2015-11-25 22:58:49]

I don't have any memory on this, so like Mark, I'd simply have to peer into the
code to see whether order mattered for this type.

However, std::unordered_map is still on the "to be discussed" list at
https://chromium-cpp.appspot.com/ , so even if this change is OK, it can't be
landed until the feature is approved.  You may want to start a discussion thread
requesting this feature if you haven't already.

[Mark P, 2015-11-25 23:05:05]

On 2015/11/25 22:58:49, Peter Kasting wrote:
> I don't have any memory on this, so like Mark, I'd simply have to peer into
the
> code to see whether order mattered for this type.
> 
> However, std::unordered_map is still on the "to be discussed" list at
> https://chromium-cpp.appspot.com/ , so even if this change is OK, it can't be
> landed until the feature is approved.  You may want to start a discussion
thread
> requesting this feature if you haven't already.

In the meantime, can you try a hash_map and see if you see the same performance
improvement?

For the record, how are you measuring the performance improvement?  The relevant
about:histogram?

--mark

[Mark P, 2015-11-30 21:14:08]

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

[Mark P, 2015-11-30 21:14:08]

Thanks for working on this omnibox performance improvement!

for the record, I (like you I imagine) audited the HistoryQuick provider code
and think an unordered or hash map would be fine for this structure.  As Peter
said, the unordered map hasn't been approved for use in chromium code.  Whenever
you revise this changelist, he can be the final approver.

Whenever you revive this changelist, please put in the changelist description
how you measured the performance improvement.

thanks,
mark

[Georges Khalil, 2015-12-01 20:49:06]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests.

As far as I can tell, the order is not important, so this change doesn't alter
expected behavior.

BUG=
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=
==========

[Georges Khalil, 2015-12-01 20:52:01]

Switched to hash_map (same result as unordered_map) and updated description.

LMK what you think.

[Mark P, 2015-12-01 21:03:41]

lgtm

For the record in case you plan to make additional improvements to the
InMemoryIndex, Omnibox.ProviderTime2.HistoryQuick is the better histogram to
examine.

Omnibox.CharTypedToRepaintLatency can be misleading because it can change
depending on typing speed.  (If you type too fast, the omnibox may skip certain
repaints it would otherwise to.)

--mark

[Peter Kasting, 2015-12-01 21:08:09]

Mark's approval is sufficient for this change; if he audited this and is fine
with it I have no further comments.

[Georges Khalil, 2015-12-01 21:16:34]

On 2015/12/01 21:08:09, Peter Kasting wrote:
> Mark's approval is sufficient for this change; if he audited this and is fine
> with it I have no further comments.

Thanks, sending this to CQ.

And I retested with Omnibox.ProviderTime2.HistoryQuick and I still see a small
improvement on my Z620.

[Georges Khalil, 2015-12-01 21:16:39]

The CQ bit was checked by georgesak@chromium.org

[commit-bot: I haz the power, 2015-12-01 21:17:16]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1482443002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1482443002/20001

[commit-bot: I haz the power, 2015-12-01 22:27:46]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=
==========

[commit-bot: I haz the power, 2015-12-01 22:27:47]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2015-12-01 22:28:32]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

[commit-bot: I haz the power, 2015-12-01 22:28:34]

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

[Georges Khalil, 2015-12-17 15:42:26]

On 2015/12/01 22:28:34, commit-bot: I haz the power wrote:
> Patchset 2 (id:??) landed as
> https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
> Cr-Commit-Position: refs/heads/master@{#362532}

Mark, Peter, I've been following the metrics on this one and it seems that we
regressed the long tail without much benefit overall. Ideally, I would have
liked to put that behind A/B testing, but since it's a type change, it would
have made the code really ugly.

I'm going to keep tracking it until after the holidays. If this trend continues,
we should revert this. I'll keep you posted.

[Georges Khalil, 2016-01-05 20:08:33]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=574181

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

[Georges Khalil, 2016-01-05 20:09:26]

A revert of this CL (patchset #2 id:20001) has been created in
https://codereview.chromium.org/1566443002/ by georgesak@chromium.org.

The reason for reverting is: This introduced a clear regression in the omnibox
performance. See bug 574181..

[Mark P, 2016-02-03 21:15:12]

On 2016/01/05 20:09:26, Georges Khalil wrote:
> A revert of this CL (patchset #2 id:20001) has been created in
> https://codereview.chromium.org/1566443002/ by mailto:georgesak@chromium.org.
> 
> The reason for reverting is: This introduced a clear regression in the omnibox
> performance. See bug 574181..

Georges,

now that we've figured out the true cause of the regression, and metrics
have stabilized after reverting the true cause,
I think it's time to resubmit this change of yours to see what effect it
has.  Can you please revive it and submit it?

thanks,
mark

[Georges Khalil, 2016-02-03 21:16:50]

The CQ bit was checked by georgesak@chromium.org

[Georges Khalil, 2016-02-03 21:17:29]

On 2016/02/03 21:15:12, Mark P wrote:
> On 2016/01/05 20:09:26, Georges Khalil wrote:
> > A revert of this CL (patchset #2 id:20001) has been created in
> > https://codereview.chromium.org/1566443002/ by
mailto:georgesak@chromium.org.
> > 
> > The reason for reverting is: This introduced a clear regression in the
omnibox
> > performance. See bug 574181..
> 
> Georges,
> 
> now that we've figured out the true cause of the regression, and metrics
> have stabilized after reverting the true cause,
> I think it's time to resubmit this change of yours to see what effect it
> has.  Can you please revive it and submit it?
> 
> thanks,
> mark

Done, sending this to CQ.

[commit-bot: I haz the power, 2016-02-03 21:17:51]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1482443002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1482443002/20001

[commit-bot: I haz the power, 2016-02-03 22:09:27]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=574181

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=574181

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

[commit-bot: I haz the power, 2016-02-03 22:09:27]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2016-02-03 22:10:57]

Description was changed from

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=574181

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}
==========

to

==========
Change HistoryInfoMap to use unordered_map.

This change speeds up the omnibox by 5-10% in my (limited) tests, using a large
profile and checking the value of the Omnibox.CharTypedToRepaintLatency
histogram.

This was also validated when profiling, where the find method was the top
function where CPU cycles were consumed. After switching to a hash map, it was a
non factor.

Note: As far as I can tell, the order is not important, so this change doesn't
alter expected behavior.

BUG=574181

Committed: https://crrev.com/6ddf83a44cb65d2540e8b78c4ff56d240a1d0597
Cr-Commit-Position: refs/heads/master@{#362532}

Committed: https://crrev.com/b7f91c31bce64a4bd61b16ce52cc9314e09cca57
Cr-Commit-Position: refs/heads/master@{#373349}
==========

[commit-bot: I haz the power, 2016-02-03 22:10:59]

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