Issue 7504044: code review 7504044: runtime: faster hashmap implementation. (Closed)
Descriptionruntime: faster hashmap implementation.
Hashtable is arranged as an array of
8-entry buckets with chained overflow.
Each bucket has 8 extra hash bits
per key to provide quick lookup within
a bucket. Table is grown incrementally.
Update issue 3885
Go time drops from 0.51s to 0.34s.
Patch Set 1 #Patch Set 2 : diff -r 332e552cd896 https://code.google.com/p/go/ #Patch Set 3 : diff -r 332e552cd896 https://code.google.com/p/go/ #Patch Set 4 : diff -r 332e552cd896 https://code.google.com/p/go/ #Patch Set 5 : diff -r 332e552cd896 https://code.google.com/p/go/ #Patch Set 6 : diff -r e4e13824b6a3 https://code.google.com/p/go/ #Patch Set 7 : diff -r e4e13824b6a3 https://code.google.com/p/go/ #Patch Set 8 : diff -r f9e10e016342 https://code.google.com/p/go/ #
Total comments: 11
Patch Set 9 : diff -r f9e10e016342 https://code.google.com/p/go/ #
Total comments: 4
Patch Set 10 : diff -r f9e10e016342 https://code.google.com/p/go/ #
Total comments: 1
Patch Set 11 : diff -r 7e8e36b5c813 https://code.google.com/p/go/ #Patch Set 12 : diff -r 61fa5c7d741f https://code.google.com/p/go/ #
Total comments: 1
MessagesTotal messages: 43
Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go/
Sign in to reply to this message.
Wonderful. Can you please add some benchmark data to the issue description.
Sign in to reply to this message.
hasmap_fast looks like C, but isn't named *.c. Is it built? or leftover debugging? On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote: > Reviewers: r, rsc, m3b_google.com, > > Message: > Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: > golang-dev@googlegroups.com), > > I'd like you to review this change to > https://code.google.com/p/go/ > > > Description: > runtime: faster hashmap implementation. > > Hashtable is arranged as an array of > 8-entry buckets with chained overflow. > Each bucket has 8 extra hash bits > per key to provide quick lookup within > a bucket. Table is grown incrementally. > > Please review this at https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... > > Affected files: > M src/cmd/gc/builtin.c > M src/cmd/gc/range.c > M src/cmd/gc/walk.c > M src/cmd/ld/dwarf.c > M src/pkg/runtime/hashmap.c > M src/pkg/runtime/hashmap.h > A src/pkg/runtime/hashmap_fast > A src/pkg/runtime/map_test.go > M src/pkg/runtime/runtime.c > M src/pkg/runtime/runtime.h > > > -- > > ---You received this message because you are subscribed to the Google > Groups "golang-dev" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... > . > For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... > . > > >
Sign in to reply to this message.
https://codereview.appspot.com/7504044/diff/13012/src/cmd/gc/walk.c File src/cmd/gc/walk.c (right): https://codereview.appspot.com/7504044/diff/13012/src/cmd/gc/walk.c#newcode1022 src/cmd/gc/walk.c:1022: (widthptr == 8 && (t->down->etype == TINT || t->down->etype == TUINT || t->down->etype == TUINTPTR))) { Does etype TUINTPTR include pointers like map[*MyType]T or only explicit uintptr?
Sign in to reply to this message.
It is #included multiple times from hashmap.c using different macro settings. I'd like to name it hashmap_fast.c but then the build tries to compile it naked and it fails. On Mon, Mar 18, 2013 at 4:45 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > hasmap_fast looks like C, but isn't named *.c. Is it built? or leftover > debugging? > > On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote: > >> Reviewers: r, rsc, m3b_google.com, >> >> Message: >> Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: >> golang-dev@googlegroups.com), >> >> I'd like you to review this change to >> https://code.google.com/p/go/ >> >> >> Description: >> runtime: faster hashmap implementation. >> >> Hashtable is arranged as an array of >> 8-entry buckets with chained overflow. >> Each bucket has 8 extra hash bits >> per key to provide quick lookup within >> a bucket. Table is grown incrementally. >> >> Please review this at https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >> >> Affected files: >> M src/cmd/gc/builtin.c >> M src/cmd/gc/range.c >> M src/cmd/gc/walk.c >> M src/cmd/ld/dwarf.c >> M src/pkg/runtime/hashmap.c >> M src/pkg/runtime/hashmap.h >> A src/pkg/runtime/hashmap_fast >> A src/pkg/runtime/map_test.go >> M src/pkg/runtime/runtime.c >> M src/pkg/runtime/runtime.h >> >> >> >> -- >> >> ---You received this message because you are subscribed to the Google >> Groups "golang-dev" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... >> . >> For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... >> . >> >> >> >
Sign in to reply to this message.
Did you try // +build ignore near the top of the file? On Mon, Mar 18, 2013 at 4:49 PM, Keith Randall <khr@google.com> wrote: > It is #included multiple times from hashmap.c using different macro > settings. I'd like to name it hashmap_fast.c but then the build tries to > compile it naked and it fails. > > > On Mon, Mar 18, 2013 at 4:45 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > >> hasmap_fast looks like C, but isn't named *.c. Is it built? or leftover >> debugging? >> >> On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote: >> >>> Reviewers: r, rsc, m3b_google.com, >>> >>> Message: >>> Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: >>> golang-dev@googlegroups.com), >>> >>> I'd like you to review this change to >>> https://code.google.com/p/go/ >>> >>> >>> Description: >>> runtime: faster hashmap implementation. >>> >>> Hashtable is arranged as an array of >>> 8-entry buckets with chained overflow. >>> Each bucket has 8 extra hash bits >>> per key to provide quick lookup within >>> a bucket. Table is grown incrementally. >>> >>> Please review this at https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >>> >>> Affected files: >>> M src/cmd/gc/builtin.c >>> M src/cmd/gc/range.c >>> M src/cmd/gc/walk.c >>> M src/cmd/ld/dwarf.c >>> M src/pkg/runtime/hashmap.c >>> M src/pkg/runtime/hashmap.h >>> A src/pkg/runtime/hashmap_fast >>> A src/pkg/runtime/map_test.go >>> M src/pkg/runtime/runtime.c >>> M src/pkg/runtime/runtime.h >>> >>> >>> >>> -- >>> >>> ---You received this message because you are subscribed to the Google >>> Groups "golang-dev" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... >>> . >>> For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... >>> . >>> >>> >>> >> >
Sign in to reply to this message.
a small start. https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast File src/pkg/runtime/hashmap_fast (right): https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fas... src/pkg/runtime/hashmap_fast:1: // Copyright 2013 The Go Authors. All rights reserved. i'd prefer this file's name to have a suffix, either .c or .h. among other things, this means code search tools will scan it. https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fas... src/pkg/runtime/hashmap_fast:28: runtime·prints("; key="); why not use runtime·printf? https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fas... src/pkg/runtime/hashmap_fast:56: if(h->oldbuckets != nil) growWork(t, h, bucket); two lines please https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fas... src/pkg/runtime/hashmap_fast:59: if(top == 0) top = 1; two lines please https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go File src/pkg/runtime/map_test.go (right): https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:141: if (v & 16) == 0 { parens unnecessary https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:145: s |= (v & 15) parens unnecessary https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:147: if (v & 16) == 16 { parens unnecessary https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:195: if (k & 1) == 1 { parens unnecessary https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:225: if bitmask != (1<<16)-1 { parens unnecessary https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:252: t.Error("missing key", keys[i]) include the index of the loop in these error prints t.Errorf("#%d: missing key: %v", i, keys[i])
Sign in to reply to this message.
I think it is only explicit uintptr. There are separate TPTR32 and TPTR64 etypes. Maybe I should add those also. On Mon, Mar 18, 2013 at 4:48 PM, <bradfitz@golang.org> wrote: > > https://codereview.appspot.**com/7504044/diff/13012/src/**cmd/gc/walk.c<https... > File src/cmd/gc/walk.c (right): > > https://codereview.appspot.**com/7504044/diff/13012/src/** > cmd/gc/walk.c#newcode1022<https://codereview.appspot.com/7504044/diff/13012/src/cmd/gc/walk.c#newcode1022> > src/cmd/gc/walk.c:1022: (widthptr == 8 && (t->down->etype == TINT || > t->down->etype == TUINT || t->down->etype == TUINTPTR))) { > Does etype TUINTPTR include pointers like map[*MyType]T or only explicit > uintptr? > > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >
Sign in to reply to this message.
Ah, secret sauce. Fixed. On Mon, Mar 18, 2013 at 4:52 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > Did you try > > // +build ignore > > near the top of the file? > > > On Mon, Mar 18, 2013 at 4:49 PM, Keith Randall <khr@google.com> wrote: > >> It is #included multiple times from hashmap.c using different macro >> settings. I'd like to name it hashmap_fast.c but then the build tries to >> compile it naked and it fails. >> >> >> On Mon, Mar 18, 2013 at 4:45 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: >> >>> hasmap_fast looks like C, but isn't named *.c. Is it built? or >>> leftover debugging? >>> >>> On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote: >>> >>>> Reviewers: r, rsc, m3b_google.com, >>>> >>>> Message: >>>> Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: >>>> golang-dev@googlegroups.com), >>>> >>>> I'd like you to review this change to >>>> https://code.google.com/p/go/ >>>> >>>> >>>> Description: >>>> runtime: faster hashmap implementation. >>>> >>>> Hashtable is arranged as an array of >>>> 8-entry buckets with chained overflow. >>>> Each bucket has 8 extra hash bits >>>> per key to provide quick lookup within >>>> a bucket. Table is grown incrementally. >>>> >>>> Please review this at https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >>>> >>>> Affected files: >>>> M src/cmd/gc/builtin.c >>>> M src/cmd/gc/range.c >>>> M src/cmd/gc/walk.c >>>> M src/cmd/ld/dwarf.c >>>> M src/pkg/runtime/hashmap.c >>>> M src/pkg/runtime/hashmap.h >>>> A src/pkg/runtime/hashmap_fast >>>> A src/pkg/runtime/map_test.go >>>> M src/pkg/runtime/runtime.c >>>> M src/pkg/runtime/runtime.h >>>> >>>> >>>> >>>> -- >>>> >>>> ---You received this message because you are subscribed to the Google >>>> Groups "golang-dev" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... >>>> . >>>> For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... >>>> . >>>> >>>> >>>> >>> >> >
Sign in to reply to this message.
I wrote up some quick benchmarks, but at least the random ones I picked
don't seem faster:
bradfitz@bradfitzlap:~/mapbench$ ~/go/misc/benchcmp before after
benchmark old ns/op new ns/op delta
BenchmarkMegMap 299663 299978 +0.11%
BenchmarkMegEmpty 298985 300747 +0.59%
BenchmarkSmallStrMap 50 52 +3.98%
BenchmarkIntMap 54 60 +10.24%
bradfitz@bradfitzlap:~/mapbench$ cat map_test.go
package main
import (
"fmt"
"strings"
"testing"
)
func BenchmarkMegMap(b *testing.B) {
m := make(map[string]bool)
for suffix := 'A'; suffix <= 'G'; suffix++ {
m[strings.Repeat("X", 1<<20-1) + fmt.Sprint(suffix)] = true
}
key := strings.Repeat("X", 1<<20-1) + "k"
b.ResetTimer()
for i := 0; i < b.N; i++ {
_, _ = m[key]
}
}
func BenchmarkMegEmpty(b *testing.B) {
m := make(map[string]bool)
key := strings.Repeat("X", 1<<20-1) + "k"
b.ResetTimer()
for i := 0; i < b.N; i++ {
_, _ = m[key]
}
}
func BenchmarkSmallStrMap(b *testing.B) {
m := make(map[string]bool)
for suffix := 'A'; suffix <= 'G'; suffix++ {
m[fmt.Sprint(suffix)] = true
}
key := "k"
b.ResetTimer()
for i := 0; i < b.N; i++ {
_, _ = m[key]
}
}
func BenchmarkIntMap(b *testing.B) {
m := make(map[int]bool)
for i := 0; i < 8; i++ {
m[i] = true
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
_, _ = m[7]
}
}
On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote:
> Reviewers: r, rsc, m3b_google.com,
>
> Message:
> Hello r@golang.org, rsc@golang.org, m3b@google.com (cc:
> golang-dev@googlegroups.com),
>
> I'd like you to review this change to
> https://code.google.com/p/go/
>
>
> Description:
> runtime: faster hashmap implementation.
>
> Hashtable is arranged as an array of
> 8-entry buckets with chained overflow.
> Each bucket has 8 extra hash bits
> per key to provide quick lookup within
> a bucket. Table is grown incrementally.
>
> Please review this at
https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504...
>
> Affected files:
> M src/cmd/gc/builtin.c
> M src/cmd/gc/range.c
> M src/cmd/gc/walk.c
> M src/cmd/ld/dwarf.c
> M src/pkg/runtime/hashmap.c
> M src/pkg/runtime/hashmap.h
> A src/pkg/runtime/hashmap_fast
> A src/pkg/runtime/map_test.go
> M src/pkg/runtime/runtime.c
> M src/pkg/runtime/runtime.h
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>
Sign in to reply to this message.
You're triggering mapaccess2, I've only optimized mapaccess1. Try "_ = m[x]" instead of "_, _ = m[x]" and it's a lot faster. mapaccess2 shouldn't be hard to include as well. On Mon, Mar 18, 2013 at 5:12 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > I wrote up some quick benchmarks, but at least the random ones I picked > don't seem faster: > > bradfitz@bradfitzlap:~/mapbench$ ~/go/misc/benchcmp before after > benchmark old ns/op new ns/op delta > BenchmarkMegMap 299663 299978 +0.11% > BenchmarkMegEmpty 298985 300747 +0.59% > BenchmarkSmallStrMap 50 52 +3.98% > BenchmarkIntMap 54 60 +10.24% > > bradfitz@bradfitzlap:~/mapbench$ cat map_test.go > package main > > import ( > "fmt" > "strings" > "testing" > ) > > func BenchmarkMegMap(b *testing.B) { > m := make(map[string]bool) > for suffix := 'A'; suffix <= 'G'; suffix++ { > m[strings.Repeat("X", 1<<20-1) + fmt.Sprint(suffix)] = true > } > key := strings.Repeat("X", 1<<20-1) + "k" > b.ResetTimer() > for i := 0; i < b.N; i++ { > _, _ = m[key] > } > } > > func BenchmarkMegEmpty(b *testing.B) { > m := make(map[string]bool) > key := strings.Repeat("X", 1<<20-1) + "k" > b.ResetTimer() > for i := 0; i < b.N; i++ { > _, _ = m[key] > } > } > > func BenchmarkSmallStrMap(b *testing.B) { > m := make(map[string]bool) > for suffix := 'A'; suffix <= 'G'; suffix++ { > m[fmt.Sprint(suffix)] = true > } > key := "k" > b.ResetTimer() > for i := 0; i < b.N; i++ { > _, _ = m[key] > } > } > func BenchmarkIntMap(b *testing.B) { > m := make(map[int]bool) > for i := 0; i < 8; i++ { > m[i] = true > } > b.ResetTimer() > for i := 0; i < b.N; i++ { > _, _ = m[7] > } > } > > > On Mon, Mar 18, 2013 at 4:37 PM, <khr@golang.org> wrote: > >> Reviewers: r, rsc, m3b_google.com, >> >> Message: >> Hello r@golang.org, rsc@golang.org, m3b@google.com (cc: >> golang-dev@googlegroups.com), >> >> I'd like you to review this change to >> https://code.google.com/p/go/ >> >> >> Description: >> runtime: faster hashmap implementation. >> >> Hashtable is arranged as an array of >> 8-entry buckets with chained overflow. >> Each bucket has 8 extra hash bits >> per key to provide quick lookup within >> a bucket. Table is grown incrementally. >> >> Please review this at https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >> >> Affected files: >> M src/cmd/gc/builtin.c >> M src/cmd/gc/range.c >> M src/cmd/gc/walk.c >> M src/cmd/ld/dwarf.c >> M src/pkg/runtime/hashmap.c >> M src/pkg/runtime/hashmap.h >> A src/pkg/runtime/hashmap_fast >> A src/pkg/runtime/map_test.go >> M src/pkg/runtime/runtime.c >> M src/pkg/runtime/runtime.h >> >> >> >> -- >> >> ---You received this message because you are subscribed to the Google >> Groups "golang-dev" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou... >> . >> For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o... >> . >> >> >> >
Sign in to reply to this message.
On Mon, Mar 18, 2013 at 5:29 PM, Keith Randall <khr@google.com> wrote: > You're triggering mapaccess2, I've only optimized mapaccess1. Try "_ = > m[x]" instead of "_, _ = m[x]" and it's a lot faster. > Ah, indeed. $ ~/go/misc/benchcmp before after benchmark old ns/op new ns/op delta BenchmarkMegMap 251565 253182 +0.64% BenchmarkMegEmpty 251516 253086 +0.62% BenchmarkSmallStrMap 41 21 -48.18% BenchmarkIntMap 48 14 -69.85% Seems like mapaccess (1 or 2) on an empty map should be a little quicker.
Sign in to reply to this message.
On Mon, Mar 18, 2013 at 5:35 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > On Mon, Mar 18, 2013 at 5:29 PM, Keith Randall <khr@google.com> wrote: > >> You're triggering mapaccess2, I've only optimized mapaccess1. Try "_ = >> m[x]" instead of "_, _ = m[x]" and it's a lot faster. >> > > Ah, indeed. > > $ ~/go/misc/benchcmp before after > benchmark old ns/op new ns/op delta > BenchmarkMegMap 251565 253182 +0.64% > BenchmarkMegEmpty 251516 253086 +0.62% > BenchmarkSmallStrMap 41 21 -48.18% > BenchmarkIntMap 48 14 -69.85% > > Seems like mapaccess (1 or 2) on an empty map should be a little quicker. > Updated benchmarks: (benchmark code attached to https://code.google.com/p/go/issues/detail?id=3885#c18) $ ~/go/misc/benchcmp before after benchmark old ns/op new ns/op delta BenchmarkBigStr_0 251329 251929 +0.24% BenchmarkBigStr_4 255585 252836 -1.08% BenchmarkBigStr_8 253203 252005 -0.47% BenchmarkBigStr_16 256934 251436 -2.14% BenchmarkBigStr_32 260725 252255 -3.25% BenchmarkBigStr_64 251684 251478 -0.08% BenchmarkBigStr_512 252046 250445 -0.64% BenchmarkBigStr2_0 251376 254504 +1.24% BenchmarkBigStr2_4 273891 251535 -8.16% BenchmarkBigStr2_8 252239 251404 -0.33% BenchmarkBigStr2_16 250466 251354 +0.35% BenchmarkBigStr2_32 250904 255760 +1.94% BenchmarkBigStr2_64 251077 253722 +1.05% BenchmarkBigStr2_512 252529 251344 -0.47% BenchmarkSmallStr_0 37 19 -47.20% BenchmarkSmallStr_4 36 38 +5.75% BenchmarkSmallStr_8 37 60 +61.29% BenchmarkSmallStr_16 44 33 -26.34% BenchmarkSmallStr_32 36 33 -8.82% BenchmarkSmallStr_64 43 33 -23.62% BenchmarkSmallStr_512 41 33 -20.86% BenchmarkSmallStr_1024 42 32 -22.59% BenchmarkSmallStr_1M 52 33 -36.76% BenchmarkSmallStr2_0 37 44 +19.79% BenchmarkSmallStr2_4 37 44 +19.62% BenchmarkSmallStr2_8 42 44 +5.15% BenchmarkSmallStr2_16 45 45 -1.53% BenchmarkSmallStr2_32 40 46 +14.00% BenchmarkSmallStr2_64 40 47 +16.79% BenchmarkSmallStr2_512 37 56 +50.67% BenchmarkSmallStr2_1024 38 46 +21.05% BenchmarkSmallStr2_1M 46 44 -5.76% BenchmarkInt_0 32 19 -40.43% BenchmarkInt_4 33 17 -49.10% BenchmarkInt_8 37 16 -55.91% BenchmarkInt_16 33 25 -23.03% BenchmarkInt_32 39 25 -36.02% BenchmarkInt_64 48 25 -46.58% BenchmarkInt_512 36 25 -31.34% BenchmarkInt_1024 36 25 -30.00% BenchmarkInt_1M 41 25 -39.86% BenchmarkInt2_0 34 40 +17.89% BenchmarkInt2_4 35 40 +12.26% BenchmarkInt2_8 42 40 -4.93% BenchmarkInt2_16 34 40 +18.82% BenchmarkInt2_32 37 40 +7.77% BenchmarkInt2_64 39 40 +1.25% BenchmarkInt2_512 34 40 +18.71% BenchmarkInt2_1024 37 40 +8.36% BenchmarkInt2_1M 46 40 -13.33% BenchmarkPtr_32 41 37 -10.31% BenchmarkPtr2_32 33 40 +21.02%
Sign in to reply to this message.
I have not read the C code yet. https://codereview.appspot.com/7504044/diff/23001/src/cmd/gc/walk.c File src/cmd/gc/walk.c (right): https://codereview.appspot.com/7504044/diff/23001/src/cmd/gc/walk.c#newcode1015 src/cmd/gc/walk.c:1015: } else if(t->down->etype == TINT32 || t->down->etype == TUINT32 || if(t->type->width > 128) { n = ... goto ret; } (now we don't need the giant else chain) switch(simtype[t->down->etype]) { case TINT32: case TUINT32: ... case TINT64: case TUINT64: ... default: ... } goto ret; Also, you seem to be excluding pointer keys from the fast routines. Why? If pointers are okay (and I don't see why not), then you can switch on simsimtype(t->down) instead of simtype[t->down->etype]. https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.c File src/pkg/runtime/hashmap.c (right): https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.c#n... src/pkg/runtime/hashmap.c:1: // Copyright 2013 The Go Authors. All rights reserved. Don't bother updating copyright years. https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.h File src/pkg/runtime/hashmap.h (right): https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.h#n... src/pkg/runtime/hashmap.h:1: // Copyright 2013 The Go Authors. All rights reserved. Don't bother updating copyright years. https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/map_test.go File src/pkg/runtime/map_test.go (right): https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/map_test.go... src/pkg/runtime/map_test.go:1: package runtime_test insert standard copyright block here, followed by a blank line so it's not a doc comment.
Sign in to reply to this message.
LGTM I read a printout. It looks good. Some general notes that apply throughout. I'm happy after the minor fixes below. Thanks very much. 1. Some shifts say (uintptr)1 << B and others say 1 << B. Probably they should all have the cast, just to be sure. Grep for cast-less shifts. 2. There's a TODO about checking whether it's too expensive to do the big allocation in one chunk. It seems fine to me. If the allocation triggers a collection, that will be more expensive than the zeroing for sure. 3. It would be nice to use the CanFree flags in a followup CL. The main reason they exist is to avoid leaving them around as possible sources of leaks, if something happens to point into them accidentally due to the imprecise collection. 4. Please pick up the changes in https://codereview.appspot.com/7913043 if they are relevant (seems like they would be). 5. growWork is not named consistently with everything else. grow_work? 6. A few small style things. I apologize for nitpicking but it does help make the code easier to skim if it looks like the surrounding code. - Please declare variables separately from initialization, and almost always at the top of the function. That way I can skip over the declaration blocks without missing actual computation. - Please always put the body of a compound statement on its own line. Egrep '(if|while).*\) [^{]'.
Sign in to reply to this message.
On Mon, Mar 18, 2013 at 4:55 PM, <r@golang.org> wrote: > a small start. > > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/hashmap_fast<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast> > File src/pkg/runtime/hashmap_fast (right): > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/hashmap_fast#**newcode1<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast#newcode1> > src/pkg/runtime/hashmap_fast:**1: // Copyright 2013 The Go Authors. All > rights reserved. > i'd prefer this file's name to have a suffix, either .c or .h. among > other things, this means code search tools will scan it. > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/hashmap_fast#**newcode28<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast#newcode28> > src/pkg/runtime/hashmap_fast:**28: runtime·prints("; key="); > why not use runtime·printf? > > No reason. This just matches the rest of the debug prints in hashmap.c. > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/hashmap_fast#**newcode56<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast#newcode56> > src/pkg/runtime/hashmap_fast:**56: if(h->oldbuckets != nil) growWork(t, h, > bucket); > two lines please > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/hashmap_fast#**newcode59<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/hashmap_fast#newcode59> > src/pkg/runtime/hashmap_fast:**59: if(top == 0) top = 1; > two lines please > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go> > File src/pkg/runtime/map_test.go (right): > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode141<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode141> > src/pkg/runtime/map_test.go:**141: if (v & 16) == 0 { > parens unnecessary > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode145<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode145> > src/pkg/runtime/map_test.go:**145: s |= (v & 15) > parens unnecessary > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode147<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode147> > src/pkg/runtime/map_test.go:**147: if (v & 16) == 16 { > parens unnecessary > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode195<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode195> > src/pkg/runtime/map_test.go:**195: if (k & 1) == 1 { > parens unnecessary > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode225<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode225> > src/pkg/runtime/map_test.go:**225: if bitmask != (1<<16)-1 { > parens unnecessary > > https://codereview.appspot.**com/7504044/diff/13012/src/** > pkg/runtime/map_test.go#**newcode252<https://codereview.appspot.com/7504044/diff/13012/src/pkg/runtime/map_test.go#newcode252> > src/pkg/runtime/map_test.go:**252: t.Error("missing key", keys[i]) > include the index of the loop in these error prints > t.Errorf("#%d: missing key: %v", i, keys[i]) > > All fixed. > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >
Sign in to reply to this message.
I've added an empty map check, plus a check to not call hash for a
one-entry map (because equals will be at least as fast as hash, and in this
case much faster):
func BenchmarkMegOne(b *testing.B) {
m := make(map[string]bool)
m[strings.Repeat("X", 1<<20)] = true
key := strings.Repeat("Y", 1<<20)
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = m[key]
}
}
I'll add all of your benchmarks plus this one to mapspeed_test.go
I've also added fast assign2 functions.
On Mon, Mar 18, 2013 at 5:35 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote:
> On Mon, Mar 18, 2013 at 5:29 PM, Keith Randall <khr@google.com> wrote:
>
>> You're triggering mapaccess2, I've only optimized mapaccess1. Try "_ =
>> m[x]" instead of "_, _ = m[x]" and it's a lot faster.
>>
>
> Ah, indeed.
>
> $ ~/go/misc/benchcmp before after
> benchmark old ns/op new ns/op delta
> BenchmarkMegMap 251565 253182 +0.64%
> BenchmarkMegEmpty 251516 253086 +0.62%
> BenchmarkSmallStrMap 41 21 -48.18%
> BenchmarkIntMap 48 14 -69.85%
>
> Seems like mapaccess (1 or 2) on an empty map should be a little quicker.
>
>
Sign in to reply to this message.
On Tue, Mar 19, 2013 at 11:59 AM, <rsc@golang.org> wrote: > I have not read the C code yet. > > > > https://codereview.appspot.**com/7504044/diff/23001/src/**cmd/gc/walk.c<https... > File src/cmd/gc/walk.c (right): > > https://codereview.appspot.**com/7504044/diff/23001/src/** > cmd/gc/walk.c#newcode1015<https://codereview.appspot.com/7504044/diff/23001/src/cmd/gc/walk.c#newcode1015> > src/cmd/gc/walk.c:1015: } else if(t->down->etype == TINT32 || > t->down->etype == TUINT32 || > if(t->type->width > 128) { > n = ... > goto ret; > } > > (now we don't need the giant else chain) > > switch(simtype[t->down->etype]**) { > case TINT32: > case TUINT32: > ... > case TINT64: > case TUINT64: > ... > default: > ... > } > goto ret; > > Also, you seem to be excluding pointer keys from the fast routines. Why? > If pointers are okay (and I don't see why not), then you can switch on > simsimtype(t->down) instead of simtype[t->down->etype]. > > Sure, I'll do that. > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/hashmap.c<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.c> > File src/pkg/runtime/hashmap.c (right): > > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/hashmap.c#newcode1<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.c#newcode1> > src/pkg/runtime/hashmap.c:1: // Copyright 2013 The Go Authors. All > rights reserved. > Don't bother updating copyright years. > Done > > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/hashmap.h<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.h> > File src/pkg/runtime/hashmap.h (right): > > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/hashmap.h#newcode1<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/hashmap.h#newcode1> > src/pkg/runtime/hashmap.h:1: // Copyright 2013 The Go Authors. All > rights reserved. > Don't bother updating copyright years. > Done > > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/map_test.go<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/map_test.go> > File src/pkg/runtime/map_test.go (right): > > https://codereview.appspot.**com/7504044/diff/23001/src/** > pkg/runtime/map_test.go#**newcode1<https://codereview.appspot.com/7504044/diff/23001/src/pkg/runtime/map_test.go#newcode1> > src/pkg/runtime/map_test.go:1: package runtime_test > insert standard copyright block here, followed by a blank line so it's > not a doc comment. > Done > > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... > Could you recheck walk.c, in particular the access2 stuff I just added? I'm very unsure I did that part correctly.
Sign in to reply to this message.
On Tue, Mar 19, 2013 at 1:46 PM, <rsc@golang.org> wrote: > LGTM > > I read a printout. It looks good. Some general notes that apply > throughout. I'm happy after the minor fixes below. Thanks very much. > > 1. Some shifts say (uintptr)1 << B and others say 1 << B. Probably they > should all have the cast, just to be sure. Grep for cast-less shifts. > Done. > 2. There's a TODO about checking whether it's too expensive to do the > big allocation in one chunk. It seems fine to me. If the allocation > triggers a collection, that will be more expensive than the zeroing for > sure. Deleted. > > 3. It would be nice to use the CanFree flags in a followup CL. The main > reason they exist is to avoid leaving them around as possible sources of > leaks, if something happens to point into them accidentally due to the > imprecise collection. > Yes, I'm planning on that as a next step. > > 4. Please pick up the changes in https://codereview.appspot.**com/7913043<https://codereview.appspot.com/7913043> > if they are relevant (seems like they would be). > > That is relevant, but not a problem for my implementation. During insert I make sure to update tophash[i] last, which atomically (with respect to GC) marks the entry as present. The fact that an empty (tophash[i]==0) entry has its key and value slots in a partially updated state doesn't affect the GC. (That would be another way to fix 7913043 - do both mallocs before writing anything into the data structure.) It can be tricky, though. Because the pointers are being written to empty entries which won't be scanned by the GC, you need to make sure the code doesn't drop the pointer to the newly allocated key & value until after the allocations are done. 5. growWork is not named consistently with everything else. grow_work? > > Ok. > 6. A few small style things. I apologize for nitpicking but it does help > make the code easier to skim if it looks like the surrounding code. > - Please declare variables separately from initialization, and almost > always at the top of the function. That way I can skip over the > declaration blocks without missing actual computation. > - Please always put the body of a compound statement on its own line. > Egrep '(if|while).*\) [^{]'. > > Fixed. > > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >
Sign in to reply to this message.
On Tue, Mar 19, 2013 at 5:06 PM, Keith Randall <khr@google.com> wrote: > I've added an empty map check, plus a check to not call hash for a > one-entry map (because equals will be at least as fast as hash, and in this > case much faster): > > func BenchmarkMegOne(b *testing.B) { > m := make(map[string]bool) > m[strings.Repeat("X", 1<<20)] = true > key := strings.Repeat("Y", 1<<20) > b.ResetTimer() > for i := 0; i < b.N; i++ { > _ = m[key] > } > } > > I'll add all of your benchmarks plus this one to mapspeed_test.go > > I've also added fast assign2 functions. > Awesome, thanks. I also see that with string keys, you could defer computing the hash until you encounter the first existing key with the same length as the lookup key. These benchmarks (with a bunch of small of map keys, but either a 1M key or a tiny key) could be the same speed: BenchmarkStrMapManySmall_BigKey 10000 250190 ns/op BenchmarkStrMapManySmall_SmallKey 50000000 33.2 ns/op From: func BenchmarkStrMapManySmall_BigKey(b *testing.B) { benchmarkStrMapMany(b, strings.Repeat("X", 1<<20)) } func BenchmarkStrMapManySmall_SmallKey(b *testing.B) { benchmarkStrMapMany(b, "small") } func benchmarkStrMapMany(b *testing.B, key string) { m := make(map[string]bool) for i := 0; i < 1<<20; i++ { m[fmt.Sprint(i)] = true } b.ResetTimer() for i := 0; i < b.N; i++ { _ = m[key] } }
Sign in to reply to this message.
LGTM https://codereview.appspot.com/7504044/diff/36001/src/cmd/gc/walk.c File src/cmd/gc/walk.c (right): https://codereview.appspot.com/7504044/diff/36001/src/cmd/gc/walk.c#newcode678 src/cmd/gc/walk.c:678: } else { drop else {, unindent block. i thought there was a missing final break on first reading.
Sign in to reply to this message.
On 2013/03/18 23:37:02, khr wrote: > Hello mailto:r@golang.org, mailto:rsc@golang.org, mailto:m3b@google.com (cc: > mailto:golang-dev@googlegroups.com), > > I'd like you to review this change to > https://code.google.com/p/go/ Hi, You included fast paths for 4-byte and 8-byte integers. Can we also include for 1 and 2-byte integers? I have code that maps bytes to functions, and they could take advantage of this fast path. I couldn't really make out performance of Interface keys (e.g. reflect.Type). Does this help somewhat with interfaces, especially those like reflect.Type who have concrete types that already define a hash value? Also, while testing, I got the error below: ---------------------------------------------- fatal error: value align bigger than size goroutine 1 [running]: [fp=0x7f6ef4e6edd8] runtime.throw(0x7f14ca) /opt/go-contrib/src/pkg/runtime/panic.c:473 +0x67 [fp=0x7f6ef4e6ee40] hash_init(0x5cafe0, 0xc2000d7120, 0x7f6e0000000b) /opt/go-contrib/src/pkg/runtime/hashmap.c:-207 +0x117 [fp=0x7f6ef4e6ee88] runtime.makemap_c(0x5cafe0, 0xb) /opt/go-contrib/src/pkg/runtime/hashmap.c:971 +0xaf [fp=0x7f6ef4e6eea0] runtime.makemap(0x5cafe0, 0xb, 0xb) /opt/go-contrib/src/pkg/runtime/hashmap.c:988 +0x2f [fp=0x7f6ef4e6ef28] ugorji.net/scratch.init·1() /home/ugorji/depot/golang/src/ugorji.net/scratch/map_vs_slice_test.go:113 +0x1ca <<snip>> ---------------------------------------------- This error was got from making a map with value type: struct{} i.e. make(map[int]struct{}, 4) Seems error came from hash_init function, where it did: if(t->elem->align > t->elem->size) runtime·throw("value align bigger than size");
Sign in to reply to this message.
Can't you use a (256)T array to map 1-byte integers to things? It seems more efficient. Rémy. 2013/3/20, ugorji@gmail.com <ugorji@gmail.com>: > On 2013/03/18 23:37:02, khr wrote: >> Hello mailto:r@golang.org, mailto:rsc@golang.org, > mailto:m3b@google.com (cc: >> mailto:golang-dev@googlegroups.com), > >> I'd like you to review this change to >> https://code.google.com/p/go/ > > Hi, > > You included fast paths for 4-byte and 8-byte integers. Can we also > include for 1 and 2-byte integers? I have code that maps bytes to > functions, and they could take advantage of this fast path. > > I couldn't really make out performance of Interface keys (e.g. > reflect.Type). Does this help somewhat with interfaces, especially those > like reflect.Type who have concrete types that already define a hash > value? > > Also, while testing, I got the error below: > ---------------------------------------------- > fatal error: value align bigger than size > > goroutine 1 [running]: > [fp=0x7f6ef4e6edd8] runtime.throw(0x7f14ca) > /opt/go-contrib/src/pkg/runtime/panic.c:473 +0x67 > [fp=0x7f6ef4e6ee40] hash_init(0x5cafe0, 0xc2000d7120, 0x7f6e0000000b) > /opt/go-contrib/src/pkg/runtime/hashmap.c:-207 +0x117 > [fp=0x7f6ef4e6ee88] runtime.makemap_c(0x5cafe0, 0xb) > /opt/go-contrib/src/pkg/runtime/hashmap.c:971 +0xaf > [fp=0x7f6ef4e6eea0] runtime.makemap(0x5cafe0, 0xb, 0xb) > /opt/go-contrib/src/pkg/runtime/hashmap.c:988 +0x2f > [fp=0x7f6ef4e6ef28] ugorji.net/scratch.init·1() > /home/ugorji/depot/golang/src/ugorji.net/scratch/map_vs_slice_test.go:113 > +0x1ca > <<snip>> > ---------------------------------------------- > > This error was got from making a map with value type: struct{} > i.e. make(map[int]struct{}, 4) > > Seems error came from hash_init function, where it did: > if(t->elem->align > t->elem->size) > runtime·throw("value align bigger than size"); > > > > > https://codereview.appspot.com/7504044/ > > -- > > --- > You received this message because you are subscribed to the Google Groups > "golang-dev" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-dev+unsubscribe@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > >
Sign in to reply to this message.
The thing is that only a few bytes may be mapped. Currently, I do a linear search. However, the library will soon expand these tags to include 2-byte integers (up to MaxInt16), and a map would be perfect there. I could always wrap it in a int32 as my key, but that requires implementation knowledge. It would be nice if the rule is simply that map access with integer keys are fastest, and string keys are optimized. On 2013/03/20 17:53:08, remyoudompheng wrote: > Can't you use a (256)T array to map 1-byte integers to things? It > seems more efficient. > > Rémy. > > > 2013/3/20, mailto:ugorji@gmail.com <ugorji@gmail.com>: > > On 2013/03/18 23:37:02, khr wrote: > >> Hello mailto:r@golang.org, mailto:rsc@golang.org, > > mailto:m3b@google.com (cc: > >> mailto:golang-dev@googlegroups.com), > > > >> I'd like you to review this change to > >> https://code.google.com/p/go/ > > > > Hi, > > > > You included fast paths for 4-byte and 8-byte integers. Can we also > > include for 1 and 2-byte integers? I have code that maps bytes to > > functions, and they could take advantage of this fast path. > > > > I couldn't really make out performance of Interface keys (e.g. > > reflect.Type). Does this help somewhat with interfaces, especially those > > like reflect.Type who have concrete types that already define a hash > > value? > > > > Also, while testing, I got the error below: > > ---------------------------------------------- > > fatal error: value align bigger than size > > > > goroutine 1 [running]: > > [fp=0x7f6ef4e6edd8] runtime.throw(0x7f14ca) > > /opt/go-contrib/src/pkg/runtime/panic.c:473 +0x67 > > [fp=0x7f6ef4e6ee40] hash_init(0x5cafe0, 0xc2000d7120, 0x7f6e0000000b) > > /opt/go-contrib/src/pkg/runtime/hashmap.c:-207 +0x117 > > [fp=0x7f6ef4e6ee88] runtime.makemap_c(0x5cafe0, 0xb) > > /opt/go-contrib/src/pkg/runtime/hashmap.c:971 +0xaf > > [fp=0x7f6ef4e6eea0] runtime.makemap(0x5cafe0, 0xb, 0xb) > > /opt/go-contrib/src/pkg/runtime/hashmap.c:988 +0x2f > > [fp=0x7f6ef4e6ef28] ugorji.net/scratch.init·1() > > /home/ugorji/depot/golang/src/ugorji.net/scratch/map_vs_slice_test.go:113 > > +0x1ca > > <<snip>> > > ---------------------------------------------- > > > > This error was got from making a map with value type: struct{} > > i.e. make(map[int]struct{}, 4) > > > > Seems error came from hash_init function, where it did: > > if(t->elem->align > t->elem->size) > > runtime·throw("value align bigger than size"); > > > > > > > > > > https://codereview.appspot.com/7504044/ > > > > -- > > > > --- > > You received this message because you are subscribed to the Google Groups > > "golang-dev" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to mailto:golang-dev+unsubscribe@googlegroups.com. > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > >
Sign in to reply to this message.
On Wed, Mar 20, 2013 at 10:53 AM, Rémy Oudompheng <remyoudompheng@gmail.com>wrote: > Can't you use a (256)T array to map 1-byte integers to things? It > seems more efficient. > That was my knee-jerk reaction too, but then I realized maps should be fast for almost all cases. If people are always second-guessing the map implementation and rolling their own, well.. that's kinda where we're already at.
Sign in to reply to this message.
I don't believe it is worth the bloat for 1 and 2 byte keys, at least not without data showing that they happen all the time as opposed to just in one program. Russ
Sign in to reply to this message.
Bit of a catch-22. People won't use map[byte]T if it's slow, and we won't make it fast if people don't use it. On Wed, Mar 20, 2013 at 11:10 AM, Russ Cox <rsc@golang.org> wrote: > I don't believe it is worth the bloat for 1 and 2 byte keys, at least not > without data showing that they happen all the time as opposed to just in > one program. > > Russ > >
Sign in to reply to this message.
That seems a fine situation to me. -rob On Mar 20, 2013 11:12 AM, "Brad Fitzpatrick" <bradfitz@golang.org> wrote: > Bit of a catch-22. People won't use map[byte]T if it's slow, and we won't > make it fast if people don't use it. > > On Wed, Mar 20, 2013 at 11:10 AM, Russ Cox <rsc@golang.org> wrote: > >> I don't believe it is worth the bloat for 1 and 2 byte keys, at least not >> without data showing that they happen all the time as opposed to just in >> one program. >> >> Russ >> >> >
Sign in to reply to this message.
We could all just use C. It's a bit more of a pain in the ass than Go, and uglier in lots of places, but it can be faster. I'll drop it. On Wed, Mar 20, 2013 at 11:17 AM, Rob Pike <r@golang.org> wrote: > That seems a fine situation to me. > > -rob > On Mar 20, 2013 11:12 AM, "Brad Fitzpatrick" <bradfitz@golang.org> wrote: > >> Bit of a catch-22. People won't use map[byte]T if it's slow, and we won't >> make it fast if people don't use it. >> >> On Wed, Mar 20, 2013 at 11:10 AM, Russ Cox <rsc@golang.org> wrote: >> >>> I don't believe it is worth the bloat for 1 and 2 byte keys, at least >>> not without data showing that they happen all the time as opposed to just >>> in one program. >>> >>> Russ >>> >>> >>
Sign in to reply to this message.
On Wed, Mar 20, 2013 at 2:07 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > That was my knee-jerk reaction too, but then I realized maps should be > fast for almost all cases. If people are always second-guessing the map > implementation and rolling their own, well.. that's kinda where we're > already at. > If we generate a custom implementation for every possible key, C++ is where we'll be at. Russ
Sign in to reply to this message.
I'm with Brad here. Looking at the code, it's about 120 lines each for 2 more specific integer types to close it out, macro-included (about 240 lines altogether). It seems like a fair price to pay for having fast maps with integer keys of any type. Without this, in my code (and I envision others), they'd create a map[uint32]T when they need a map[int16]T, and always convert back and forth, and they'd only know to do this if they know the implementation fast-paths that type. In this case, I think the contained relatively small cost is justified. On 2013/03/20 18:19:19, bradfitz wrote: > We could all just use C. It's a bit more of a pain in the ass than Go, and > uglier in lots of places, but it can be faster. > > I'll drop it. > > On Wed, Mar 20, 2013 at 11:17 AM, Rob Pike <mailto:r@golang.org> wrote: > > > That seems a fine situation to me. > > > > -rob > > On Mar 20, 2013 11:12 AM, "Brad Fitzpatrick" <mailto:bradfitz@golang.org> wrote: > > > >> Bit of a catch-22. People won't use map[byte]T if it's slow, and we won't > >> make it fast if people don't use it. > >> > >> On Wed, Mar 20, 2013 at 11:10 AM, Russ Cox <mailto:rsc@golang.org> wrote: > >> > >>> I don't believe it is worth the bloat for 1 and 2 byte keys, at least > >>> not without data showing that they happen all the time as opposed to just > >>> in one program. > >>> > >>> Russ > >>> > >>> > >>
Sign in to reply to this message.
Let's start with just 4 and 8 please. Russ
Sign in to reply to this message.
Here's some speed and size graphs. The speed graphs are for lookups. On Wed, Mar 20, 2013 at 11:46 AM, Russ Cox <rsc@golang.org> wrote: > Let's start with just 4 and 8 please. > > Russ > >
Sign in to reply to this message.
On Wed, Mar 20, 2013 at 10:50 AM, <ugorji@gmail.com> wrote: > On 2013/03/18 23:37:02, khr wrote: > >> Hello mailto:r@golang.org, mailto:rsc@golang.org, >> > mailto:m3b@google.com (cc: > >> mailto:golang-dev@**googlegroups.com <golang-dev@googlegroups.com>), >> > > I'd like you to review this change to >> https://code.google.com/p/go/ >> > > Hi, > > You included fast paths for 4-byte and 8-byte integers. Can we also > include for 1 and 2-byte integers? I have code that maps bytes to > functions, and they could take advantage of this fast path. > > I couldn't really make out performance of Interface keys (e.g. > reflect.Type). Does this help somewhat with interfaces, especially those > like reflect.Type who have concrete types that already define a hash > value? > The map code should be ~20% faster even without the fast path. I don't know what the overhead of interface hashing is, but maybe that's swamping the improvements in the map proper. > > Also, while testing, I got the error below: > ------------------------------**---------------- > fatal error: value align bigger than size > > goroutine 1 [running]: > [fp=0x7f6ef4e6edd8] runtime.throw(0x7f14ca) > /opt/go-contrib/src/pkg/**runtime/panic.c:473 +0x67 > [fp=0x7f6ef4e6ee40] hash_init(0x5cafe0, 0xc2000d7120, 0x7f6e0000000b) > /opt/go-contrib/src/pkg/**runtime/hashmap.c:-207 +0x117 > [fp=0x7f6ef4e6ee88] runtime.makemap_c(0x5cafe0, 0xb) > /opt/go-contrib/src/pkg/**runtime/hashmap.c:971 +0xaf > [fp=0x7f6ef4e6eea0] runtime.makemap(0x5cafe0, 0xb, 0xb) > /opt/go-contrib/src/pkg/**runtime/hashmap.c:988 +0x2f > [fp=0x7f6ef4e6ef28] ugorji.net/scratch.init·1()<http://ugorji.net/scratch.init%C2%B71()> > /home/ugorji/depot/golang/src/**ugorji.net/scratch/map_vs_** > slice_test.go:113 <http://ugorji.net/scratch/map_vs_slice_test.go:113> > +0x1ca > <<snip>> > ------------------------------**---------------- > > This error was got from making a map with value type: struct{} > i.e. make(map[int]struct{}, 4) > > Seems error came from hash_init function, where it did: > if(t->elem->align > t->elem->size) > runtime·throw("value align bigger than size"); > > I've fixed zero-sized keys and values. Thanks for the bug report. > > > > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >
Sign in to reply to this message.
*** Submitted as https://code.google.com/p/go/source/detail?r=0fce55d10d18 *** runtime: faster hashmap implementation. Hashtable is arranged as an array of 8-entry buckets with chained overflow. Each bucket has 8 extra hash bits per key to provide quick lookup within a bucket. Table is grown incrementally. Update issue 3885 Go time drops from 0.51s to 0.34s. R=r, rsc, m3b, dave, bradfitz, khr, ugorji, remyoudompheng CC=golang-dev https://codereview.appspot.com/7504044
Sign in to reply to this message.
Message was sent while issue was closed.
https://codereview.appspot.com/7504044/diff/59001/src/pkg/runtime/hashmap.c File src/pkg/runtime/hashmap.c (right): https://codereview.appspot.com/7504044/diff/59001/src/pkg/runtime/hashmap.c#n... src/pkg/runtime/hashmap.c:225: if(valuesize >= MAXVALUESIZE) { should this be ">" instead of ">="?
Sign in to reply to this message.
Message was sent while issue was closed.
cmd/ld/dwarf.c reverted Russ' last DWARFv2 change, why?
Sign in to reply to this message.
runtime-gdb.py is broken after this change, please see https://code.google.com/p/go/issues/detail?id=5098.
Sign in to reply to this message.
Whoops, that was not intentional. Something sync'd strangely. I will fix. On Thu, Mar 21, 2013 at 12:35 PM, <minux.ma@gmail.com> wrote: > cmd/ld/dwarf.c reverted Russ' last DWARFv2 change, why? > > https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >
Sign in to reply to this message.
Yes, the internal format of maps has changed. I will work on the appropriate change to runtime-gdb.py. On Thu, Mar 21, 2013 at 12:51 PM, minux <minux.ma@gmail.com> wrote: > runtime-gdb.py is broken after this change, please see > https://code.google.com/p/go/issues/detail?id=5098. >
Sign in to reply to this message.
On Fri, Mar 22, 2013 at 4:27 AM, Keith Randall <khr@google.com> wrote: > Yes, the internal format of maps has changed. I will work on the > appropriate change to runtime-gdb.py. Thank you.
Sign in to reply to this message.
Ah, I see you fixed it already. https://code.google.com/p/go/source/detail?r=decec27a013432a3c00bb4928ce2316b... On Thu, Mar 21, 2013 at 1:26 PM, Keith Randall <khr@google.com> wrote: > Whoops, that was not intentional. Something sync'd strangely. I will fix. > > > On Thu, Mar 21, 2013 at 12:35 PM, <minux.ma@gmail.com> wrote: > >> cmd/ld/dwarf.c reverted Russ' last DWARFv2 change, why? >> >> https://codereview.appspot.**com/7504044/<https://codereview.appspot.com/7504... >> > >
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
