Bencher is available on the Github marketplace!

Map copy capacity hint

Introduction

Maps are bread and butter in the Go programming language to very fast storage and retrieval of items. Maps allows for keyed storages and accesses in constant time aka O(1) time.

Given that maps when passed around allow mutation by reference, it is necessary to copy them.

Populate and copy

Let’s populate the map

package main

func main() {
	isbns := make(map[int]int)
	// Fill in the values as they'd come in from the database.
	isbns[99] = 10
	isbns[212] = 12
	isbns[88] = 8
	isbns[47] = 4
	isbns[22] = 2
	isbns[1902] = 19
	isbns[88] = -88

	// Now copy the values
	copyIt(isbns)
}

func copyIt(m map[int]int) map[int]int {
	cp := make(map[int]int)
	for k, v := range m {
		cp[k] = v
	}
        return cp
}

Size hints

If we look at the specification for a map, we can see the following

diff --git a/maps/copy/copy.go b/maps/copy/copy.go
index d56e3f6..a20aafc 100644
--- a/maps/copy/copy.go
+++ b/maps/copy/copy.go
@@ -1,7 +1,7 @@
 package maps
 
 func copyIt(m map[int]int) map[int]int {
-       cp := make(map[int]int)
+       cp := make(map[int]int, len(m))
        for k, v := range m {
                cp[k] = v
        }
        return cp

Pop quiz

Which of the 2 styles above is the fastest and most efficient??

Set up benchmarking

To set up our shoot-out for benchmarking and solid data backed by numbers, we need to do the following:

Benchmark the code

To figure out how it performs, let’s start by benchmarking it.

package maps

import (
    "testing"
)

var sink interface{}

func BenchmarkCopyIt10(b *testing.B) {
    benchmarkCopyIt(b, 10)
}

func BenchmarkCopyIt100(b *testing.B) {
    benchmarkCopyIt(b, 100)
}

func BenchmarkCopyIt1000(b *testing.B) {
    benchmarkCopyIt(b, 1000)
}

func BenchmarkCopyIt10000(b *testing.B) {
    benchmarkCopyIt(b, 10000)
}

func BenchmarkCopyIt100000(b *testing.B) {
    benchmarkCopyIt(b, 100000)
}

func benchmarkCopyIt(b *testing.B, n int) {
    m := make(map[int]int)
    for i := 0; i < n; i++ {
        m[i] = i + 1
    }
    b.ResetTimer()
    b.ReportAllocs()

    for i := 0; i < b.N; i++ {
        sink = copyIt(m)
    }
    if sink == nil {
        b.Fatal("Benchmark didn't run")
    }
    sink = (interface{})(nil)
}

Commit the result

Having successfully added Bencher to our repository in two clicks, we mailed the first change. That made Bencher spawn the following:

Shoot-out

Add the capacity

If we apply the map capacity hint, with NOTHING else like this:

Results

We get the following results per https://dashboard.bencher.orijtech.com/benchmark/213d0080ec47409d95c512bca4a8a27e with a whole lot of improvements in every dimension!

Verdict

For the best performance, please use the map capacity hint when copying

func copyIt(m map[int]int) map[int]int {
    cp := make(map[int]int, len(m))
    for k, v := range m {
        cp[k] = v
    }
    return cp
}

References

Resource URL
map capacity hint in Map Types https://go.dev/ref/spec#Map_types