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>

1 files changed, 29 insertions, 0 deletions

diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go
index 59e9c94c3f..f31ef22f3e 100644
--- a/src/runtime/map_test.go
+++ b/src/runtime/map_test.go
@@ -596,6 +596,35 @@ func TestIgnoreBogusMapHint(t *testing.T) {
 	}
 }
 
+func TestMapBuckets(t *testing.T) {
+	// Test that maps of different sizes have the right number of buckets.
+	// These tests depend on bucketCnt and loadFactor* in hashmap.go.
+	for _, tt := range [...]struct {
+		n, b int
+	}{
+		{8, 1},
+		{9, 2},
+		{13, 2},
+		{14, 4},
+		{26, 4},
+	} {
+		m := map[int]int{}
+		for i := 0; i < tt.n; i++ {
+			m[i] = i
+		}
+		if got := runtime.MapBuckets(m); got != tt.b {
+			t.Errorf("no hint n=%d want %d buckets, got %d", tt.n, tt.b, got)
+		}
+		m = make(map[int]int, tt.n)
+		for i := 0; i < tt.n; i++ {
+			m[i] = i
+		}
+		if got := runtime.MapBuckets(m); got != tt.b {
+			t.Errorf("hint n=%d want %d buckets, got %d", tt.n, tt.b, got)
+		}
+	}
+}
+
 func benchmarkMapPop(b *testing.B, n int) {
 	m := map[int]int{}
 	for i := 0; i < b.N; i++ {