[base] Decrease probing in hashmap

[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.

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

[Leszek Swirski, 2016-09-19 09:17:03]

leszeks@chromium.org changed reviewers:
+ rmcilroy@chromium.org

[rmcilroy, 2016-09-19 10:43:13]

LGTM (remember to update description if you remove the ResizeAndProbe change as
suggested).

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h
File src/base/hashmap.h (right):

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode287
src/base/hashmap.h:287: TemplateHashMapImpl<Key, Value,
AllocationPolicy>::FillEmptyProbe(
nit - FullEmptyEntry.

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode288
src/base/hashmap.h:288: Entry* probe, const Key& key, const Value& value,
uint32_t hash) {
nit - p for consistency (or even better, rename p->probe throughout file).

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode338
src/base/hashmap.h:338: }
I'm not convinced that saving one probe out of N during the resize is worth it,
and ResizeAndProbe is a bit of a confusing name. Maybe just drop this part of
the CL?

[Leszek Swirski, 2016-09-19 12:42:51]

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h
File src/base/hashmap.h (right):

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode287
src/base/hashmap.h:287: TemplateHashMapImpl<Key, Value,
AllocationPolicy>::FillEmptyProbe(
On 2016/09/19 10:43:13, rmcilroy wrote:
> nit - FullEmptyEntry.

Done.

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode288
src/base/hashmap.h:288: Entry* probe, const Key& key, const Value& value,
uint32_t hash) {
On 2016/09/19 10:43:13, rmcilroy wrote:
> nit - p for consistency (or even better, rename p->probe throughout file).

Done, renaming p->entry throughout (except for in Remove, where there was no
good replacement for q and r)

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode338
src/base/hashmap.h:338: }
On 2016/09/19 10:43:13, rmcilroy wrote:
> I'm not convinced that saving one probe out of N during the resize is worth
it,
> and ResizeAndProbe is a bit of a confusing name. Maybe just drop this part of
> the CL?

It might be a bit of a premature optimisation, but we literally never call
resize without calling probe after, so I don't think it's unreasonable? I agree
that I don't love the name though.

[Leszek Swirski, 2016-09-19 12:56:51]

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h
File src/base/hashmap.h (right):

https://codereview.chromium.org/2349163002/diff/1/src/base/hashmap.h#newcode338
src/base/hashmap.h:338: }
On 2016/09/19 12:42:50, Leszek Swirski wrote:
> On 2016/09/19 10:43:13, rmcilroy wrote:
> > I'm not convinced that saving one probe out of N during the resize is worth
> it,
> > and ResizeAndProbe is a bit of a confusing name. Maybe just drop this part
of
> > the CL?
> 
> It might be a bit of a premature optimisation, but we literally never call
> resize without calling probe after, so I don't think it's unreasonable? I
agree
> that I don't love the name though.

No, upon reflection, you're right, the name is too awful and it doesn't save
much.

[Leszek Swirski, 2016-09-19 12:57:05]

Description was changed from

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in particular:

1. Probing a second time in LookupOrInsert after the first probe came
   up with an empty value, and
2. Probing after a resize, when the probe could be combined with the
   resize's rehashing.
==========

to

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in particular probing a
second time in LookupOrInsert after the first probe came up with an empty value,
and.
==========

[rmcilroy, 2016-09-19 13:19:18]

Description was changed from

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in particular probing a
second time in LookupOrInsert after the first probe came up with an empty value,
and.
==========

to

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in particular probing a
second time in LookupOrInsert after the first probe came up with an empty value.
==========

[Leszek Swirski, 2016-09-19 16:11:47]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-09-19 16:11:47]

The patchset sent to the CQ was uploaded after l-g-t-m from
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/2349163002/#ps40001
(title: "Remove ResizeAndProbe because the name is horrible")

[commit-bot: I haz the power, 2016-09-19 16:11:57]

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

[commit-bot: I haz the power, 2016-09-19 16:11:58]

This CL has an open dependency (Issue 2345233003 Patch 20001). Please resolve
the dependency and try again.
If you are sure that there is no real dependency, please use one of the options
listed in https://goo.gl/9Es4OR to land the CL.

[Leszek Swirski, 2016-09-19 16:11:58]

Description was changed from

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in particular probing a
second time in LookupOrInsert after the first probe came up with an empty value.
==========

to

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.
==========

[Leszek Swirski, 2016-09-20 10:54:06]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-09-20 10:54:06]

The patchset sent to the CQ was uploaded after l-g-t-m from
rmcilroy@chromium.org
Link to the patchset: https://codereview.chromium.org/2349163002/#ps60001
(title: "Rebase")

[commit-bot: I haz the power, 2016-09-20 10:54:23]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-09-20 11:30:03]

Description was changed from

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.
==========

to

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.
==========

[commit-bot: I haz the power, 2016-09-20 11:30:04]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-09-20 11:30:56]

Description was changed from

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.
==========

to

==========
[base] Decrease probing in hashmap

Removes some unnecessary probing in TemplateHashMapImpl, in
particular probing a second time in LookupOrInsert after the
first probe came up with an empty value.

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

[commit-bot: I haz the power, 2016-09-20 11:30:57]

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