[golang] map の初期化時はサイズを与えるべき

目的

map の初期化時は、なるべくサイズを与えるべきということを理解する。

考察

マップが拡大する場合、すべてのキーがすべてのバケットへ再配置されます。そのため、最悪の場合、キーの挿入は、マップの要素の総数を n としたとき、O(n)の処理になる可能性があります。

訳注: キーと値の組を挿入する際に、配列の大きさを2倍にすると判断された場合、すでに入っているキーと値の組をすべて再配置する必要があります。

2つ目のベンチマークは、初期サイズを指定することで、約50%高速化されています。サイズを指定することで、挿入された要素に対応するためにマップが拡大することを防いでいます。

私の検証では、一つ目のベンチマークに初期サイズを指定しているが、「354,550,989 / 462,570,698 = 0.7664」なので、23.4 ％くらい高速化されている。
上記の書籍の結果ほど、高速化はされなかった。

検証

~/praprago$ go version
go version go1.23.2 linux/amd64

pra_map_test.go

package main

import "testing"

var MyMap map[string]int

// /////////////////////////////////////////////////////////
// ///////////////////////////////////////////////////////// (1)
func BenchmarkPraMap1(b *testing.B) {
	var tmpMap map[string]int
	for i := 0; i < b.N; i++ {
		tmpMap = PraMap1()
	}
	MyMap = tmpMap
}

// /////////////////////////////////////////////////////////
// ///////////////////////////////////////////////////////// (2)
func BenchmarkPraMap2(b *testing.B) {
	var tmpMap map[string]int
	for i := 0; i < b.N; i++ {
		tmpMap = PraMap2()
	}
	MyMap = tmpMap
}

pra_map.go

package main

import "strconv"

// /////////////////////////////////////////////////////////
// ///////////////////////////////////////////////////////// (1)
// 初期サイズを与えて map を作成する
func PraMap1() map[string]int {
	m := make(map[string]int, 1000_000)
	for i := 0; i < 1000_000; i++ {
		m[strconv.Itoa(i)] = i
	}
	return m
}

// /////////////////////////////////////////////////////////
// ///////////////////////////////////////////////////////// (2)
// 初期サイズを与えずに map を作成する
func PraMap2() map[string]int {
	m := make(map[string]int)
	for i := 0; i < 1000_000; i++ {
		m[strconv.Itoa(i)] = i
	}
	return m
}

~/praprago$ go test -bench=. -benchmem
goos: linux
goarch: amd64
pkg: github.com/XXX/praprago
cpu: Intel(R) Xeon(R) CPU E5-2686 v4 @ 2.30GHz
BenchmarkPraMap1-2             3         354550989 ns/op        65652786 B/op     999903 allocs/op
BenchmarkPraMap2-2             3         462570698 ns/op        131546952 B/op   1038107 allocs/op
PASS
ok      github.com/XXX/praprago 5.091s

参考

Note: Providing the size here doesn’t mean that map doesn’t grow. It only allocates the given size, but the size will grow if we add more elements to it.