Mapping Values by a Combination of Two Keys¶
The topic was found during optimization. When the combination of 2 string type keys maps to a value, how do you maintain the mapping from keys to the value? Generally we can come up with 3 approaches listed below, which one is better?
type Result string
// 1d map, you need to concatenate 2 strings
var d1M map[string]Result
// 1d map and use struct as key
type Key struct {
S1, S2 string
}
var d1MS map[Key]Result
// 2d map
var d2M map[string]map[string]Result
The 1d mapping needs pay for the string concatenation, the 2d mapping is required for an additional map query per query and the 1d map with struct key requires additional calculation on map.
The conclusion is 2d map is fastest because string concatenation costs more. What's worse, inappropriate string concatenations causes higher memory usages and triggers more GC(result got from pprof). It has been verified in the real practice by my teammates as well.
Note that here the keys are string. If they're small integers we can consider to use bit operation to append them together. Hence, we can finish the map querying in 1 operation.
This blog is not intended to analyze which method to append string(fmt.Sprintf, +, strings.Builder, etc...) is better and why it's fastest. It shows the result only.
Map Allocation¶
To avoid map initialization disturbs benchmark of querying, I use TestMain to initialize them. However, this approach has missed the memory usage of each approach. I tried to use runtime.ReadMemStats to test the map allocation. Here it's a bit tricky to tackle temporary object allocations and GC.
TotalAlloc: cumulative bytes allocated for heap object and never decreases when GC frees objects.Alloc: the allocations on the heap, which will be affected by GC.
Hence, when I want to check the memory usage of each map, I cannot get rid of temporary object allocations or the GC. Finally, I choose to use Alloc and force GC by runtime.GC when I read the memory state.
func TestMain(m *testing.M) {
// ignore many lines...
runtime.GC()
var m1 runtime.MemStats
runtime.ReadMemStats(&m1)
for _, item := range list {
d1M[item.CombinedKey] = item.V
}
runtime.GC()
var m2 runtime.MemStats
runtime.ReadMemStats(&m2)
mapMemory := m2.Alloc - m1.Alloc
fmt.Printf("Memory consumed by map d1M: %7d bytes\n", mapMemory)
// ignore many lines...
m.Run()
}
func TestMain(m *testing.M) {
// ignore many lines...
var m1 runtime.MemStats
runtime.ReadMemStats(&m1)
for _, item := range list {
d1M[item.CombinedKey] = item.V
}
var m2 runtime.MemStats
runtime.ReadMemStats(&m2)
mapMemory := m2.TotalAlloc - m1.TotalAlloc
fmt.Printf("Memory consumed by map d1M: %7d bytes\n", mapMemory)
// ignore many lines...
m.Run()
}
The memory usage of d1M and d2M are similar, but the d1MS is 1.5x bigger.
Benchmark result¶
After checking the memory allocations for each map, I want to focus on the map query here. As the result output by running go test -benchmem -bench . -gcflags=all="-N -l" shows, 2D map is faster without additional allocation(depends on the string). So in the next time, using 2d map is a better choice!
Benchmark Iterations Time/op (ns) Bytes/op Allocs/op
===========================================================================================================
Benchmark1DMap_fmtSprintf-10 67 15794759 ns/op 3942296 B/op 300000 allocs/op
Benchmark1DMap_RawAddition-10 170 6998775 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_StringBuilder-10 140 8981449 ns/op 800000 B/op 100000 allocs/op
Benchmark1DMap_BytesAppend-10 135 9052651 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_WithoutConcatenate-10 219 5299534 ns/op 0 B/op 0 allocs/op
Benchmark2DMap-10 214 5281945 ns/op 0 B/op 0 allocs/op
Benchmark2DMap_Struct-10 178 6463023 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_fmtSprintf-10 68 15930520 ns/op 3942300 B/op 300000 allocs/op
Benchmark1DMap_RawAddition-10 171 7429119 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_StringBuilder-10 133 8249174 ns/op 800000 B/op 100000 allocs/op
Benchmark1DMap_BytesAppend-10 136 8124544 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_WithoutConcatenate-10 253 4736944 ns/op 0 B/op 0 allocs/op
Benchmark2DMap-10 225 5321423 ns/op 0 B/op 0 allocs/op
Benchmark1DMap_Struct-10 177 6121964 ns/op 0 B/op 0 allocs/op
Benchmark Source Code¶
Benchmark Source Code
package main_test
import (
"fmt"
"runtime"
"strconv"
"strings"
"testing"
)
type Result string
type Key struct {
S1, S2 string
}
var d2M map[string]map[string]Result
var d1M map[string]Result
var d1MS map[Key]Result
type Pair struct {
S1, S2 string
CombinedKey string
V Result
}
var list []Pair
func TestMain(m *testing.M) {
d2M = make(map[string]map[string]Result)
d1M = map[string]Result{}
d1MS = make(map[Key]Result)
for i := 0; i < 1000; i++ {
for j := 0; j < 100; j++ {
first := strconv.Itoa(i)
second := strconv.Itoa(j)
v := Result(strconv.Itoa(i * j))
list = append(list, Pair{
S1: first, S2: second,
// pre-calculate the concatenation to focus on the goal here.
CombinedKey: first + "+" + second,
V: v,
})
}
}
runtime.GC()
var m1 runtime.MemStats
runtime.ReadMemStats(&m1)
for _, item := range list {
d1M[item.CombinedKey] = item.V
}
runtime.GC()
var m2 runtime.MemStats
runtime.ReadMemStats(&m2)
mapMemory := m2.Alloc - m1.Alloc
fmt.Printf("Memory consumed by map d1M: %7d bytes\n", mapMemory)
for _, item := range list {
if d2M[item.S1] == nil {
d2M[item.S1] = map[string]Result{}
}
d2M[item.S1][item.S2] = item.V
}
runtime.GC()
var m3 runtime.MemStats
runtime.ReadMemStats(&m3)
mapMemory = m3.Alloc - m2.Alloc
fmt.Printf("Memory consumed by map d2M: %7d bytes\n", mapMemory)
for _, item := range list {
d1MS[Key{
S1: item.S1,
S2: item.S2,
}] = item.V
}
runtime.GC()
var m4 runtime.MemStats
runtime.ReadMemStats(&m4)
mapMemory = m4.Alloc - m3.Alloc
fmt.Printf("Memory consumed by map d1MS: %7d bytes\n", mapMemory)
m.Run()
}
func Benchmark1DMap_fmtSprintf(b *testing.B) {
combine := func(s1, s2 string) string {
return fmt.Sprintf("%s+%s", s1, s2)
}
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1M[combine(item.S1, item.S2)]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark1DMap_RawAddition(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1M[item.S1+"+"+item.S2]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark1DMap_StringBuilder(b *testing.B) {
combineByBuilder := func(s1, s2 string) string {
var bd strings.Builder
bd.WriteString(s1)
bd.WriteString("+")
bd.WriteString(s2)
return bd.String()
}
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1M[combineByBuilder(item.S1, item.S2)]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark1DMap_BytesAppend(b *testing.B) {
combine := func(s1, s2 string) string {
return string(append([]byte(s1+"+"), []byte(s2)...))
}
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1M[combine(item.S1, item.S2)]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark1DMap_WithoutConcatenate(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1M[item.CombinedKey]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark2DMap(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d2M[item.S1][item.S2]
if v != item.V {
panic("not eqaul")
}
}
}
}
func Benchmark2DMap_Struct(b *testing.B) {
for i := 0; i < b.N; i++ {
for _, item := range list {
v := d1MS[Key{
S1: item.S1,
S2: item.S2,
}]
if v != item.V {
panic("not eqaul")
}
}
}
}