diff options
| author | Keith Randall <khr@golang.org> | 2017-09-01 12:32:38 -0700 |
|---|---|---|
| committer | Keith Randall <khr@golang.org> | 2017-09-02 05:44:23 +0000 |
| commit | dbe3522c7f45771bbd12228b7f17a3fc5ac9d7c7 (patch) | |
| tree | e023d1b9c3e54796b2d227a4f7a0445833324bb4 /src/runtime/hashmap_fast.go | |
| parent | a6a92b186732e293072daf94397d9c71eb81e2e9 (diff) | |
| download | go-dbe3522c7f45771bbd12228b7f17a3fc5ac9d7c7.tar.xz | |
runtime: fix hashmap load factor computation
overLoadFactor wasn't really doing what it says it does.
It was reporting overOrEqualToLoadFactor. That's actually what we
want when adding an entry to a map, but it isn't what we want when
constructing a map in the first place.
The impetus for this change is that if you make a map with a hint
of exactly 8 (which happens, for example, with the unitMap in
time/format.go), we allocate 2 buckets for it instead of 1.
Instead, make overLoadFactor really report when it is > the max
allowed load factor, not >=. Adjust the callers who want to ensure
that the map is no more than the max load factor after an insertion
by adding a +1 to the current (pre-addition) size.
Change-Id: Ie8d85344800a9a870036b637b1031ddd9e4b93f9
Reviewed-on: https://go-review.googlesource.com/61053
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Martin Möhrmann <moehrmann@google.com>
Diffstat (limited to 'src/runtime/hashmap_fast.go')
| -rw-r--r-- | src/runtime/hashmap_fast.go | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/src/runtime/hashmap_fast.go b/src/runtime/hashmap_fast.go index f117311439..21e1f68bf7 100644 --- a/src/runtime/hashmap_fast.go +++ b/src/runtime/hashmap_fast.go @@ -406,7 +406,7 @@ again: // If we hit the max load factor or we have too many overflow buckets, // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } @@ -495,7 +495,7 @@ again: // If we hit the max load factor or we have too many overflow buckets, // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } @@ -596,7 +596,7 @@ again: // If we hit the max load factor or we have too many overflow buckets, // and we're not already in the middle of growing, start growing. - if !h.growing() && (overLoadFactor(h.count, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { + if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } |