code review 7029053: runtime: Use SipHash-2-4 for hashmaps.

runtime: Use SipHash-2-4 for hashmaps on amd64.

Fixes issue 4604.

[mdempsky, 2013-01-04 01:46:50]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[mdempsky, 2013-01-04 01:51:34]

Like I said in the description, this was mostly for proof-of-concept and
personal exercise.  It passes all.bash's testing, but I haven't benchmarked
anything.  I don't know what a good benchmark for a map-heavy workload is. 
Assuming it doesn't slow things down too much though, I think it would be
worthwhile change.

Also, I know there's terrible things like inconsistent formatting and
unnamespaced names.  I can fix the formatting, and rename things as recommended.
 Just thought I'd mail it out since it seems to be in a working state at the
moment.

[dave_cheney.net, 2013-01-04 01:57:46]

I think there are some map benchmarks in the runtime package. If not, I
think tests of ints and strings as keys for sizes of 10s, 100s, 10,000s and
1,000,000 would be a good general purpose benchmark. The net/http package
uses maps for headers, so look there for improvements/regressions.

I would be concerned if this proposal made map access /insertion slower,
maps are already known to be slower than folks hoped for.

Without trying to discourage your contributions, they are most welcome, the
general policy is to discuss changes first, before implementation.
On 4 Jan 2013 12:51, <mdempsky@google.com> wrote:

> Like I said in the description, this was mostly for proof-of-concept and
> personal exercise.  It passes all.bash's testing, but I haven't
> benchmarked anything.  I don't know what a good benchmark for a
> map-heavy workload is.  Assuming it doesn't slow things down too much
> though, I think it would be worthwhile change.
>
> Also, I know there's terrible things like inconsistent formatting and
> unnamespaced names.  I can fix the formatting, and rename things as
> recommended.  Just thought I'd mail it out since it seems to be in a
> working state at the moment.
>
>
https://codereview.appspot.**com/7029053/<https://codereview.appspot.com/7029...
>

[dsymonds, 2013-01-04 02:00:57]

On Fri, Jan 4, 2013 at 12:57 PM, Dave Cheney <dave@cheney.net> wrote:

> Without trying to discourage your contributions, they are most welcome, the
> general policy is to discuss changes first, before implementation.

In particular, please read http://golang.org/doc/contribute.html.

[dave_cheney.net, 2013-01-04 02:11:58]

Some minor stylistic comments.

I think benchmarks for int, string and time.Time in the ranges 10, 100, 10,000
and 1,000,000 would be useful.

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c
File src/pkg/runtime/alg.c (right):

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcode8
src/pkg/runtime/alg.c:8: // XXX(mdempsky): cc doesn't optimize this into a ROT
instruction. :(
Go uses TODO(mdempsky) rather than the pythonic XXX, you can also use BUG. I
think both, or at least the latter are recognised by godoc.

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcode9
src/pkg/runtime/alg.c:9: #define ROTATE(x,b) x = (x << b) | (x >> (64 - b))
That might be fixable.

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcod...
src/pkg/runtime/alg.c:178: siphash_update(h, s, a);
You've probably figured out cc doesn't inline simple methods either :(

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/iface.c
File src/pkg/runtime/iface.c (right):

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/iface.c#newc...
src/pkg/runtime/iface.c:556: return; // XXX(mdempsky): Hash something?
// TODO

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/iface.c#newc...
src/pkg/runtime/iface.c:576: return; // XXX(mdempsky): Hash something?
ditto

[mdempsky, 2013-01-04 02:22:09]

On Thu, Jan 3, 2013 at 6:00 PM, David Symonds <dsymonds@golang.org> wrote:

> On Fri, Jan 4, 2013 at 12:57 PM, Dave Cheney <dave@cheney.net> wrote:
>
> > Without trying to discourage your contributions, they are most welcome,
> the
> > general policy is to discuss changes first, before implementation.
>

Sure, I saw that in the Contribution Guidelines document, but for the
previous simple changes I submitted it just seemed like a wasteful extra
round-trip to first email golang-dev with "hey, I noticed X; should I
submit a CL to change it to Y?"  Just sending the CL seems easier all
around, and my feelings won't get hurt if they're rejected or if someone
decides it's easier to steal the CL and tweak/submit it themselves.  :)

This particular change I realize is worth discussing further, which is why
I mailed it out for discussion now rather than after trying to polish
things further.  I just wanted to implement this change for fun anyway,
regardless of whether it gets accepted or not.

 In particular, please read http://golang.org/doc/contribute.html.
>

Thanks, I read that---it's how I figured out how to upload CLs in the first
place! :)  Is sending a CL to start a discussion about something considered
bad form?  Or is there something else you think I overlooked?

[mdempsky, 2013-01-04 02:27:25]

I'll look into benchmarks.

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c
File src/pkg/runtime/alg.c (right):

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcode8
src/pkg/runtime/alg.c:8: // XXX(mdempsky): cc doesn't optimize this into a ROT
instruction. :(
On 2013/01/04 02:11:58, dfc wrote:
> Go uses TODO(mdempsky) rather than the pythonic XXX, you can also use BUG. I
> think both, or at least the latter are recognised by godoc.

Done.  (Here and elsewhere.)

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcode9
src/pkg/runtime/alg.c:9: #define ROTATE(x,b) x = (x << b) | (x >> (64 - b))
On 2013/01/04 02:11:58, dfc wrote:
> That might be fixable.

Yeah, I looked into fixing it, but the cc code is still kinda hairy to me.  It
wasn't clear to me what the best way to do so was either, so I punted on that
since it doesn't prevent the code from working.

https://codereview.appspot.com/7029053/diff/9001/src/pkg/runtime/alg.c#newcod...
src/pkg/runtime/alg.c:178: siphash_update(h, s, a);
On 2013/01/04 02:11:58, dfc wrote:
> You've probably figured out cc doesn't inline simple methods either :(

Yeah.  I considered getting rid of the siphash_update() function and just having
people call runtime.memhash() directly, or renaming the latter or something, but
figured that's something golang-dev could better suggest than I could figure out
on my own.

[dsymonds, 2013-01-04 02:30:52]

On Fri, Jan 4, 2013 at 1:21 PM, Matthew Dempsky <mdempsky@google.com> wrote:

>> In particular, please read http://golang.org/doc/contribute.html.
>
>
> Thanks, I read that---it's how I figured out how to upload CLs in the first
> place! :)  Is sending a CL to start a discussion about something considered
> bad form?  Or is there something else you think I overlooked?

Please re-read the section section, titled "Discuss your design".

[pmylund, 2013-01-04 03:24:10]

Thanks for submitting this. You were quicker than me :)

This is issue 4604: http://code.google.com/p/go/issues/detail?id=4604

Please let me know if you are planning to discontinue/abandon this CL. Thanks.

[rsc, 2013-01-18 21:40:17]

As I mentioned on the bug, I'd like to put this on hold until after Go 1.1.

[mdempsky, 2013-01-18 21:44:16]

On 2013/01/18 21:40:17, rsc wrote:
> As I mentioned on the bug, I'd like to put this on hold until after Go 1.1.

Yep, that's fine by me.  Is there a proper way to retract the CL from
consideration until then while keeping it available for people who might be
interested?

[rsc, 2013-01-18 21:49:24]

You can clear the R= line but keep the CC= line, by using hg change 7029053.

[khr, 2013-07-22 19:36:07]

R=close

This change is obsoleted by the aeshash implementation (CL 7543043).