Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1124)

Issue 6304062: code review 6304062: runtime: improved continuity in hash computation (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
9 years, 7 months ago by atom
Modified:
9 years, 4 months ago
Reviewers:
rsc
CC:
r, dfc, golang-dev
Visibility:
Public.

Description

runtime: improved continuity in hash computation Adds dumpmap() function as a side-effect. Fixes issue 3695.

Patch Set 1 #

Total comments: 4

Patch Set 2 : diff -r f33da81baac2 https://go.googlecode.com/hg/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+124 lines, -19 lines) Patch
M src/pkg/runtime/alg.c View 6 chunks +11 lines, -17 lines 0 comments Download
M src/pkg/runtime/hashmap.c View 1 4 chunks +113 lines, -2 lines 0 comments Download

Messages

Total messages: 12
atom
Hello golang-dev@googlegroups.com, I'd like you to review this change to https://go.googlecode.com/hg/
9 years, 7 months ago (2012-06-10 15:31:09 UTC) #1
r
what do you mean by "improved continuity"? not sure the new debugging stuff carries its ...
9 years, 7 months ago (2012-06-10 17:10:22 UTC) #2
atom
On 2012/06/10 17:10:22, r wrote: > what do you mean by "improved continuity"? with the ...
9 years, 7 months ago (2012-06-10 17:57:52 UTC) #3
dfc
Thank you for this. I think the use of a macro makes the hash algos ...
9 years, 7 months ago (2012-06-11 01:28:58 UTC) #4
atom
Hello golang-dev@googlegroups.com, r@golang.org, dave@cheney.net (cc: golang-dev@googlegroups.com), Please take another look.
9 years, 7 months ago (2012-06-11 05:29:52 UTC) #5
atom
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: > ...
9 years, 7 months ago (2012-06-11 05:31:35 UTC) #6
rsc
LGTM Thank you very much for tracking this down. The hash computation fixes are very ...
9 years, 7 months ago (2012-06-13 19:27:13 UTC) #7
rsc
*** Submitted as http://code.google.com/p/go/source/detail?r=c8d163b7930e *** runtime: improved continuity in hash computation Fixes issue 3695. R=r, ...
9 years, 7 months ago (2012-06-13 19:53:41 UTC) #8
atom
On 2012/06/13 19:27:13, rsc wrote: >I don't want to add all the hash printing code, ...
9 years, 7 months ago (2012-06-13 21:01:22 UTC) #9
rsc
On 2012/06/13 21:01:22, atom wrote: > On 2012/06/13 19:27:13, rsc wrote: > >I don't want ...
9 years, 7 months ago (2012-06-14 04:59:46 UTC) #10
atom
On 2012/06/14 04:59:46, rsc wrote: > On 2012/06/13 21:01:22, atom wrote: > > On 2012/06/13 ...
9 years, 7 months ago (2012-06-14 09:39:49 UTC) #11
rsc
9 years, 7 months ago (2012-06-14 15:18:20 UTC) #12
> 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
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b