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

Issue 7543043: code review 7543043: runtime: faster & safer hash function (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
11 years ago by khr
Modified:
11 years ago
Reviewers:
CC:
rsc, r, bradfitz, remyoudompheng, khr1, dsymonds, minux1, elias.naur, golang-dev
Visibility:
Public.

Description

runtime: faster & safer hash function Uses AES hardware instructions on 386/amd64 to implement a fast hash function. Incorporates a random key to thwart hash collision DOS attacks. Depends on CL#7548043 for new assembly instructions. Update issue 3885 Helps some by making hashing faster. Go time drops from 0.65s to 0.51s.

Patch Set 1 #

Patch Set 2 : diff -r 67fc3cb0d3aa https://code.google.com/p/go/ #

Patch Set 3 : diff -r 37d4691df584 https://code.google.com/p/go/ #

Total comments: 3

Patch Set 4 : diff -r 37d4691df584 https://code.google.com/p/go/ #

Total comments: 7

Patch Set 5 : diff -r 37d4691df584 https://code.google.com/p/go/ #

Patch Set 6 : diff -r 479ac38abfc9 https://code.google.com/p/go/ #

Total comments: 1

Patch Set 7 : diff -r 479ac38abfc9 https://code.google.com/p/go/ #

Patch Set 8 : diff -r 479ac38abfc9 https://code.google.com/p/go/ #

Patch Set 9 : diff -r 479ac38abfc9 https://code.google.com/p/go/ #

Patch Set 10 : diff -r b4a4e1fab659 https://code.google.com/p/go/ #

Patch Set 11 : diff -r b4a4e1fab659 https://code.google.com/p/go/ #

Total comments: 12

Patch Set 12 : diff -r b4a4e1fab659 https://code.google.com/p/go/ #

Patch Set 13 : diff -r 7b6b3b170d9a https://code.google.com/p/go/ #

Total comments: 2

Patch Set 14 : diff -r a45e271add6c https://code.google.com/p/go/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+891 lines, -8 lines) Patch
M src/pkg/runtime/alg.c View 1 2 3 4 5 6 7 8 9 10 11 12 1 chunk +35 lines, -0 lines 0 comments Download
M src/pkg/runtime/asm_386.s View 1 2 3 4 5 6 7 8 9 3 chunks +270 lines, -0 lines 0 comments Download
M src/pkg/runtime/asm_amd64.s View 1 2 3 4 5 6 7 8 9 3 chunks +174 lines, -0 lines 0 comments Download
M src/pkg/runtime/asm_arm.s View 1 2 3 4 5 6 7 8 9 2 chunks +15 lines, -0 lines 0 comments Download
A src/pkg/runtime/mapspeed_test.go View 1 2 3 4 5 6 7 8 9 10 11 1 chunk +96 lines, -0 lines 0 comments Download
M src/pkg/runtime/runtime.h View 1 2 3 4 5 6 7 8 9 10 11 12 13 4 chunks +19 lines, -1 line 0 comments Download
M src/pkg/runtime/runtime.c View 1 1 chunk +5 lines, -0 lines 0 comments Download
M src/pkg/runtime/signal_linux_386.c View 1 2 3 4 5 6 7 8 9 10 11 12 2 chunks +7 lines, -1 line 0 comments Download
M src/pkg/runtime/sys_darwin_386.s View 1 2 3 4 5 6 7 1 chunk +15 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_darwin_amd64.s View 1 2 3 4 5 6 7 1 chunk +22 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_freebsd_386.s View 1 2 3 4 5 6 7 1 chunk +15 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_freebsd_amd64.s View 1 2 3 4 5 6 7 1 chunk +22 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_netbsd_386.s View 1 2 3 4 5 6 7 1 chunk +15 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_netbsd_amd64.s View 1 2 3 4 5 6 7 1 chunk +22 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_openbsd_386.s View 1 2 3 4 5 6 7 1 chunk +15 lines, -0 lines 0 comments Download
M src/pkg/runtime/sys_openbsd_amd64.s View 1 2 3 4 5 6 7 1 chunk +22 lines, -0 lines 0 comments Download
M src/pkg/runtime/thread_darwin.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +16 lines, -0 lines 0 comments Download
M src/pkg/runtime/thread_freebsd.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +16 lines, -0 lines 0 comments Download
M src/pkg/runtime/thread_linux.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 2 chunks +26 lines, -4 lines 0 comments Download
M src/pkg/runtime/thread_netbsd.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +16 lines, -0 lines 0 comments Download
M src/pkg/runtime/thread_openbsd.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 1 chunk +16 lines, -0 lines 0 comments Download
M src/pkg/runtime/thread_windows.c View 1 2 3 4 5 6 7 8 9 10 11 12 13 3 chunks +24 lines, -0 lines 0 comments Download
M src/pkg/runtime/vdso_linux_amd64.c View 1 2 3 4 5 6 7 8 9 10 11 2 chunks +8 lines, -2 lines 0 comments Download

Messages

Total messages: 29
khr
Hello rsc@golang.org (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go/
11 years ago (2013-03-06 23:06:42 UTC) #1
r
Can you capture your timings in a benchmark, then use misc/benchcmp to report the numbers?
11 years ago (2013-03-06 23:09:40 UTC) #2
bradfitz
You might want to split off the assembler/linker changes into their own CL. That part ...
11 years ago (2013-03-06 23:14:33 UTC) #3
remyoudompheng
https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h File src/cmd/8l/8.out.h (right): https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h#newcode156 src/cmd/8l/8.out.h:156: AMOVQ, MOVQ is SSE2, is it for consistency with ...
11 years ago (2013-03-06 23:36:33 UTC) #4
khr1
Here's some testing numbers: benchmark old ns/op new ns/op delta BenchmarkHashSpeed 63 49 -22.48% Here's ...
11 years ago (2013-03-06 23:51:08 UTC) #5
khr1
I've split out the assembly part into https://codereview.appspot.com/7548043/ On Wed, Mar 6, 2013 at 3:36 ...
11 years ago (2013-03-06 23:58:22 UTC) #6
remyoudompheng
On 2013/3/7 Keith Randall <khr@google.com> wrote: > Here's some testing numbers: > > benchmark old ...
11 years ago (2013-03-06 23:58:26 UTC) #7
khr1
The low-hanging fruit is to speed up map[String]... I agree that the more types we ...
11 years ago (2013-03-07 00:01:07 UTC) #8
khr1
benchmark old ns/op new ns/op delta BenchmarkHashStringSpeed 63 50 -20.22% BenchmarkHashInt32Speed 44 40 -7.26% BenchmarkHashInt64Speed ...
11 years ago (2013-03-07 00:04:31 UTC) #9
dsymonds
Unless you mean to benchmark fmt and the map construction too, you'll want to use ...
11 years ago (2013-03-07 02:10:23 UTC) #10
rsc
Or just call b.ResetTimer and don't worry about stop. I don't see the benchmark in ...
11 years ago (2013-03-07 03:11:33 UTC) #11
rsc
Looks good but where are the benchmarks? https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c File src/pkg/runtime/alg.c (right): https://codereview.appspot.com/7543043/diff/9002/src/pkg/runtime/alg.c#newcode470 src/pkg/runtime/alg.c:470: // TODO: ...
11 years ago (2013-03-07 03:23:08 UTC) #12
khr1
On Wed, Mar 6, 2013 at 7:23 PM, <rsc@golang.org> wrote: > Looks good but where ...
11 years ago (2013-03-07 03:50:01 UTC) #13
rsc
The linker (dodata in src/cmd/ld) already aligns data objects based on their size. Bigger objects ...
11 years ago (2013-03-07 03:56:23 UTC) #14
khr1
On Wed, Mar 6, 2013 at 3:36 PM, <remyoudompheng@gmail.com> wrote: > > https://codereview.appspot.**com/7543043/diff/5001/src/cmd/**8l/8.out.h<https://codereview.appspot.com/7543043/diff/5001/src/cmd/8l/8.out.h> > File ...
11 years ago (2013-03-07 04:12:31 UTC) #15
khr1
You mean something like this? Seems to work... --- a/src/cmd/ld/data.c Thu Mar 07 12:54:00 2013 ...
11 years ago (2013-03-07 21:18:51 UTC) #16
minux1
https://codereview.appspot.com/7543043/diff/37001/src/pkg/runtime/thread_netbsd.c File src/pkg/runtime/thread_netbsd.c (right): https://codereview.appspot.com/7543043/diff/37001/src/pkg/runtime/thread_netbsd.c#newcode181 src/pkg/runtime/thread_netbsd.c:181: runtime·hashinit(nil); all *BSD have /dev/urandom, so you can just ...
11 years ago (2013-03-07 21:33:45 UTC) #17
rsc
On Thu, Mar 7, 2013 at 4:18 PM, Keith Randall <khr@google.com> wrote: > You mean ...
11 years ago (2013-03-07 23:45:55 UTC) #18
elias.naur
On 2013/03/07 03:50:01, khr1 wrote: > > There doesn't seem to be any obviously good ...
11 years ago (2013-03-08 12:24:25 UTC) #19
khr1
Ok, this change is ready to go. Anyone want to take a last look? The ...
11 years ago (2013-03-11 18:37:43 UTC) #20
r
https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/alg.c File src/pkg/runtime/alg.c (right): https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/alg.c#newcode483 src/pkg/runtime/alg.c:483: if ((runtime·cpuid_ecx & (1 << 25)) != 0 && ...
11 years ago (2013-03-11 19:48:22 UTC) #21
rsc
Despite the file name, osinit is about per-process os startup, not just a single thread. ...
11 years ago (2013-03-11 20:19:25 UTC) #22
r
https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darwin.c File src/pkg/runtime/thread_darwin.c (right): https://codereview.appspot.com/7543043/diff/58001/src/pkg/runtime/thread_darwin.c#newcode71 src/pkg/runtime/thread_darwin.c:71: static byte urandom_data[HashRandomBytes]; I said separate function, not separate ...
11 years ago (2013-03-11 20:40:30 UTC) #23
rsc
Sorry, I can't see the files anymore. Rietveld keeps giving me chunk mismatch errors. The ...
11 years ago (2013-03-11 20:48:41 UTC) #24
r
On Mon, Mar 11, 2013 at 1:48 PM, Russ Cox <rsc@golang.org> wrote: > As long ...
11 years ago (2013-03-11 20:54:27 UTC) #25
rsc
sgtm
11 years ago (2013-03-11 20:57:47 UTC) #26
khr1
I've made a separate function and called it from hashinit, not osinit. That way we ...
11 years ago (2013-03-12 16:21:09 UTC) #27
rsc
LGTM Thanks very much. Looks great. Apologies for the code formatting nits. They apply to ...
11 years ago (2013-03-12 16:32:28 UTC) #28
khr
11 years ago (2013-03-12 17:47:48 UTC) #29
*** Submitted as https://code.google.com/p/go/source/detail?r=e3a5e1e9db71 ***

runtime: faster & safer hash function

Uses AES hardware instructions on 386/amd64 to implement
a fast hash function.  Incorporates a random key to
thwart hash collision DOS attacks.
Depends on CL#7548043 for new assembly instructions.

Update issue 3885
Helps some by making hashing faster.  Go time drops from
0.65s to 0.51s.

R=rsc, r, bradfitz, remyoudompheng, khr, dsymonds, minux.ma, elias.naur
CC=golang-dev
https://codereview.appspot.com/7543043
Sign in to reply to this message.

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