Improve WTF::HashTable performance by changing probing method

Improve WTF::HashTable performance by changing probing method

Our current HashTable implementation uses a linear probing system where
the delta is a hash of the given hash, which for integers requires
numerous shift and add operations to compute. This patch takes some
inspiration from CPython's dict implementation[1] to improve average
performance.

The new probing system is based off CPython's implementation -- we use a
linear congruential generator (x <- x*5+1), but for the first few probes
we also mix in the original hash (we shift this right by 5 each probe,
so we should use all the bits of the hash if the hash table is at least
32 objects big).

[1] http://svn.python.org/projects/python/trunk/Objects/dictobject.c

BUG=

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=153057

[Timothy Loh, 2013-06-24 04:49:36]

Hi guys,

This patch tweaks the WTF::HashTable implementation for performance. I think it
should make us faster overall, except I can't seem to get consistent test timing
locally (I'm getting stddevs of about 10-20% when running tests). Perhaps we
could see what the perf bots say and decide from those reuslts whether we want
this patch?

[abarth-chromium, 2013-06-24 04:53:06]

What machine are you running these perf measurements on?  Please be aware that
the z620s are useless for performance measurements.

Would you be willing to get performance numbers from a Nexus 7 and a more stable
machine on Windows?

[abarth-chromium, 2013-06-24 04:57:02]

Also, we can start by focusing on html5-full-render and expand from there to
other perf tests if the full suite is overwhelming.

[Timothy Loh, 2013-06-24 10:33:38]

On 2013/06/24 04:53:06, abarth wrote:
> What machine are you running these perf measurements on?  Please be aware that
> the z620s are useless for performance measurements.

D'oh!

> Would you be willing to get performance numbers from a Nexus 7 and a more
stable
> machine on Windows?

OK. I don't have a Windows machine for testing, but some Nexus 7 numbers for
html5-full-render (also updated the description) with 3 runs each.

master: 34307 +- 348 ms
[34192.944, 34146.995, 34558.282, 34271.669, 33597.835]
[34256.157, 34290.198, 34303.775, 34165.240, 33734.058]
[34977.977, 34894.718, 34370.961, 34542.064, 34297.122]

patch: 33818 +- 334 ms
[33849.537, 34308.434, 33658.353, 34098.279, 33997.564]
[33867.453, 33101.452, 33167.666, 33706.741, 33663.582]
[34101.053, 33757.971, 33855.714, 34305.655, 33833.575]

So it looks like this improves performance on html5-full-render by 1-2%.
Of course it's possible that some benchmarks will regress slightly, but
I think this should be an improvement overall.

[abarth-chromium, 2013-06-24 16:55:08]

On 2013/06/24 10:33:38, Timothy Loh wrote:
> So it looks like this improves performance on html5-full-render by 1-2%.

That's great.  I'll study your CL in detail today.

[abarth-chromium, 2013-06-25 05:03:38]

Won't this cause problems for hash tables that actually use integer keys?  Maybe
I've misunderstood, but it sounds like you wanted to change how we do probing
but you've also changed the initial distribution for integer-keyed hash
tables...

https://codereview.chromium.org/17583004/diff/1/Source/wtf/HashTable.h
File Source/wtf/HashTable.h (left):

https://codereview.chromium.org/17583004/diff/1/Source/wtf/HashTable.h#oldcod...
Source/wtf/HashTable.h:667: int sizeMask = m_tableSizeMask;
Is there a reason you remove the copy of m_tableSizeMask into a local variable?

[Timothy Loh, 2013-06-25 06:40:08]

On 2013/06/25 05:03:38, abarth wrote:
> Won't this cause problems for hash tables that actually use integer keys? 
Maybe
> I've misunderstood, but it sounds like you wanted to change how we do probing
> but you've also changed the initial distribution for integer-keyed hash
> tables...

I originally was playing around with changing the probing, but figured
that we could also simplify the IntHash functions since we spend a
nontrivial amount of time in these. So there are two distinct patches
here, one for changing IntHash (HashFunctions.h) and one for changing
the probing (HashTable.h). Each change should work on it's own.

I previously tested each change individually on this z620 and decided
on doing both changes at once, but given how unreliable the z620s are
for measurements, I've performed some measurements on a Nexus 7:

Master (no change):
 [34057.367, 34260.811, 34324.080, 34466.701, 34187.677]
 [34380.655, 33860.043, 34229.197, 33733.791, 34055.825]
- Avg: 34156, SD: 219, Min: 33734, Max: 34467

Probe change:
 [34070.129, 34166.107, 33685.190, 33647.802, 33570.770]
 [33649.524, 33441.995, 33817.049, 33737.195, 33759.194]
- Avg: 33754, SD: 208, Min: 33442, Max: 34166

IntHash change:
 [33923.608, 33873.535, 34242.828, 33992.279, 33528.036]
 [33580.648, 33322.257, 33765.881, 33649.864, 34358.917]
- Avg: 33824, SD: 306, Min: 33322, Max: 34359

Both changes (i.e. the patch posted):
 [34010.251, 33847.601, 33828.330, 34163.022, 34045.018]
 [34200.638, 33854.578, 33879.398, 33197.394, 33637.089]
- Avg: 33866, SD: 275, Min: 33197, Max: 34201

Here it looks like either or both of the IntHash and probing changes
nets us ~1%, but there's too much variation to decide what's better
here. I can run the tests more times, or run the entire blink_perf
suite, but perhaps you have better ideas?

> https://codereview.chromium.org/17583004/diff/1/Source/wtf/HashTable.h
> File Source/wtf/HashTable.h (left):
> 
>
https://codereview.chromium.org/17583004/diff/1/Source/wtf/HashTable.h#oldcod...
> Source/wtf/HashTable.h:667: int sizeMask = m_tableSizeMask;
> Is there a reason you remove the copy of m_tableSizeMask into a local
variable?

I didn't think having the variable was any useful (in the original
code it's only used once outside the loop), but we could see if it
makes any difference.

[abarth-chromium, 2013-06-25 08:10:53]

On 2013/06/25 06:40:08, Timothy Loh wrote:
> Here it looks like either or both of the IntHash and probing changes
> nets us ~1%, but there's too much variation to decide what's better
> here. I can run the tests more times, or run the entire blink_perf
> suite, but perhaps you have better ideas?

One thing we can do is to make the changes separately and get perf results from
the full performance test suite.

The probe changes make more sense to me.  I'm less sure about the int hash
changes.  Do we still spend much time in these functions after changing probing?
 I would imagine that we rarely key hash tables off integers unless we use the
"already hashed" trait,

>
https://codereview.chromium.org/17583004/diff/1/Source/wtf/HashTable.h#oldcod...
> > Source/wtf/HashTable.h:667: int sizeMask = m_tableSizeMask;
> > Is there a reason you remove the copy of m_tableSizeMask into a local
> variable?
> 
> I didn't think having the variable was any useful (in the original
> code it's only used once outside the loop), but we could see if it
> makes any difference.

These classes are extremely widely used throughout the codebase.  We should be
careful when changing them.  I'd prefer if we made small, incremental changes. 
It's possible that copying the table size to a local variable allows the
compiler to do different optimizations because it knows the value cannot change
during the execution of the function.

[Timothy Loh, 2013-06-26 06:33:26]

On 2013/06/25 08:10:53, abarth wrote:
> These classes are extremely widely used throughout the codebase.  We should be
> careful when changing them.  I'd prefer if we made small, incremental changes.

> It's possible that copying the table size to a local variable allows the
> compiler to do different optimizations because it knows the value cannot
change
> during the execution of the function.

OK. Undid this part of the change for perf testing.

> The probe changes make more sense to me.  I'm less sure about the int hash
> changes.  Do we still spend much time in these functions after changing
probing?
>  I would imagine that we rarely key hash tables off integers unless we use the
> "already hashed" trait,

I'm also changing PtrHash here, so any Foo* and RefPtr<Foo> also get a faster
hash here.

> One thing we can do is to make the changes separately and get perf results
from
> the full performance test suite.

Ok, I ran the full suite 5 times for each set of changes (none/hash/probe/both).
I'm not sure what numbers I should be computing on these results. I guess that
taking the average improvement over all blink perf tests isn't a very good
metric and we should actually be using e.g. page cyclers.

Average improvement of best run on patch vs master:
both  0.0153
probe 0.0096
hash  0.0079

Average improvement of average run on patch vs master:
both  0.0169
probe 0.0152
hash  0.0092

Raw data: http://pastebin.com/ZegYnzyN

[abarth-chromium, 2013-06-26 06:40:24]

Sorry, I wasn't clear.  I think we should land the changes the probing and see
what the bots tell us about performance over the full matrix of configurations
and tests (beyond just the PerformanceTests suite).

Once the dust settles on that change, we can decide what to do about the integer
hashing changes.

This might seem pretty conservative, but I this code is very widely used and I
think we'll benefit from making changes in a controlled way.

[Timothy Loh, 2013-06-26 06:53:04]

On 2013/06/26 06:40:24, abarth wrote:
> Sorry, I wasn't clear.  I think we should land the changes the probing and see
> what the bots tell us about performance over the full matrix of configurations
> and tests (beyond just the PerformanceTests suite).
> 
> Once the dust settles on that change, we can decide what to do about the
integer
> hashing changes.
> 
> This might seem pretty conservative, but I this code is very widely used and I
> think we'll benefit from making changes in a controlled way.

Alright, I've uploaded just the probing part of the change. Could you take
another look?

[abarth-chromium, 2013-06-26 07:15:35]

lgtm

Thanks!  Let's see how it goes.  :)

[commit-bot: I haz the power, 2013-06-26 07:15:49]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/timloh@chromium.org/17583004/10001

[commit-bot: I haz the power, 2013-06-26 08:09:09]

Retried try job too often on linux_layout_rel for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=linux_layo...

[commit-bot: I haz the power, 2013-06-26 08:10:28]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/timloh@chromium.org/17583004/10001

[commit-bot: I haz the power, 2013-06-26 08:36:30]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/timloh@chromium.org/17583004/29001

[commit-bot: I haz the power, 2013-06-26 10:00:51]

Change committed as 153057

[Timothy Loh, 2013-06-27 16:39:06]

On 2013/06/26 10:00:51, I haz the power (commit-bot) wrote:
> Change committed as 153057

Note: This was reverted, see https://codereview.chromium.org/17996003/