code review 6304062: runtime: improved continuity in hash computation

runtime: improved continuity in hash computation

Adds dumpmap() function as a side-effect.
Fixes issue 3695.

[atom, 2012-06-10 15:31:09]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg/

[r, 2012-06-10 17:10:22]

what do you mean by "improved continuity"?

not sure the new debugging stuff carries its weight.

[atom, 2012-06-10 17:57:52]

On 2012/06/10 17:10:22, r wrote:
> what do you mean by "improved continuity"?

with the previous version of alg.c there was a much higher chance that the value
of *h would reset to its previous state during hashcode computation.
"continuity" means that the value should now depend on all previous values. it
was "chunky", it is "continuous" now.
 
> not sure the new debugging stuff carries its weight.

dumpmap() allowed me to figure out where the problem was. it was illuminating to
see what Hmap looks like in memory if there are many collisions. dumpmap() may
be useful if there turns out to be another problem (performance issue, or bug)
with the memory layout of a map.

[dfc, 2012-06-11 01:28:58]

Thank you for this. I think the use of a macro makes the hash algos easier to
read, I hope they are raised above the bar for inclusion of new macros.

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c
File src/pkg/runtime/hashmap.c (right):

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c#newcode67
src/pkg/runtime/hashmap.c:67: Debug = 0,
can this be made debug to reduce the size of the lines changed below ?

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c#newcode68
src/pkg/runtime/hashmap.c:68: DumpOnInsert = 0,
ditto, but only because it shouldn't look like an exported value.

[atom, 2012-06-11 05:29:52]

Hello golang-dev@googlegroups.com, r@golang.org, dave@cheney.net (cc:
golang-dev@googlegroups.com),

Please take another look.

[atom, 2012-06-11 05:31:35]

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c
File src/pkg/runtime/hashmap.c (right):

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c#newcode67
src/pkg/runtime/hashmap.c:67: Debug = 0,
On 2012/06/11 01:28:59, dfc wrote:
> can this be made debug to reduce the size of the lines changed below ?

Done.

http://codereview.appspot.com/6304062/diff/1/src/pkg/runtime/hashmap.c#newcode68
src/pkg/runtime/hashmap.c:68: DumpOnInsert = 0,
On 2012/06/11 01:28:59, dfc wrote:
> ditto, but only because it shouldn't look like an exported value.

Done.

[rsc, 2012-06-13 19:27:13]

LGTM

Thank you very much for tracking this down.

The hash computation fixes are very important, enough that I am going to pick
them up for Go 1.0.2. I don't want to add all the hash printing code, though, at
least not right now, so I will revert that file before submitting this.

[rsc, 2012-06-13 19:53:41]

*** Submitted as http://code.google.com/p/go/source/detail?r=c8d163b7930e ***

runtime: improved continuity in hash computation

Fixes issue 3695.

R=r, dave, rsc
CC=golang-dev
http://codereview.appspot.com/6304062

Committer: Russ Cox <rsc@golang.org>

[atom, 2012-06-13 21:01:22]

On 2012/06/13 19:27:13, rsc wrote:
>I don't want to add all the hash printing code, though, at
> least not right now, so I will revert that file before submitting this.

There are 2 lines of new code in hashmap.c that aren't related to printing. They
start with "if((hash & HASH_MASK) == HASH_SUBHASH) ...".

[rsc, 2012-06-14 04:59:46]

On 2012/06/13 21:01:22, atom wrote:
> On 2012/06/13 19:27:13, rsc wrote:
> >I don't want to add all the hash printing code, though, at
> > least not right now, so I will revert that file before submitting this.
> 
> There are 2 lines of new code in hashmap.c that aren't related to printing.
They
> start with "if((hash & HASH_MASK) == HASH_SUBHASH) ...".

I never received this message via email, strangely. Apologies for not replying
earlier.

Did you run into this case in the actual code? Skimming it I don't see how this
can happen.

[atom, 2012-06-14 09:39:49]

On 2012/06/14 04:59:46, rsc wrote:
> On 2012/06/13 21:01:22, atom wrote:
> > On 2012/06/13 19:27:13, rsc wrote:
> > >I don't want to add all the hash printing code, though, at
> > > least not right now, so I will revert that file before submitting this.
> > 
> > There are 2 lines of new code in hashmap.c that aren't related to printing.
> They
> > start with "if((hash & HASH_MASK) == HASH_SUBHASH) ...".
> 
> I never received this message via email, strangely. Apologies for not replying
> earlier.

I wasn't sure what the "Send mail to reviewers" button does so I unchecked it
when sending the message. Now I know how it works.

> Did you run into this case in the actual code? Skimming it I don't see how
this
> can happen.

There is a while loop containing the line:

    hash += (e_hash == hash);    /* adjust hash if it collides */

If there are many successive collisions, (hash & HASH_MASK) will be equal to
HASH_SUBHASH.

The older alg.c allowed the programmer to make a lot of distinct hashmap
insertions that were all using the same hash (issue 3695). The newer alg.c makes
it harder for the programmer to (intentionally or unintentionally) create such a
situation.

[rsc, 2012-06-14 15:18:20]

> There is a while loop containing the line:
>
>    hash += (e_hash == hash);    /* adjust hash if it collides */
>
> If there are many successive collisions, (hash & HASH_MASK) will be
> equal to HASH_SUBHASH.

I think you're right that it can happen, but only if you can get 64
different elements in the map to collide with the same 26-bit (or, on
a 64-bit platform, 58-bit) hash. So this is protecting against bugs in
the calling code, like the one you fixed. The combination of fixing
the hash function to use all its input and using a random hash
function should make that extremely unlikely.

I think the assertion should probably be up higher, near the loop that
is doing the collision handling. I'll talk to the original author of
this code.

Thanks again.
Russ