Benchmarks

map_test.go

package golangbench

import (
	"fmt"
	"hash/fnv"
	"math/rand"
	"runtime"
	"sync"
	"sync/atomic"
	"testing"
	"unsafe"
)

type kv struct {
	key   string
	value string
}

func getInputEntries(b *testing.B) []kv {
	entries := make([]kv, 0, b.N)
	for i := 0; i < b.N; i++ {
		entries = append(entries, kv{
			key:   fmt.Sprintf("map_key_xxxxxxxxxxxxxxxxxxx_%d", i),
			value: fmt.Sprintf("map_value_%d", i),
		})
	}
	rand.Shuffle(len(entries), func(i, j int) {
		tmp := entries[i]
		entries[i] = entries[j]
		entries[j] = tmp
	})
	runtime.GC()

	return entries
}

func BenchmarkMap(b *testing.B) {
	entries := getInputEntries(b)
	b.ResetTimer()
	m := make(map[string]string)
	for i := range entries {
		m[entries[i].key] = entries[i].value
	}
	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkMapWithCapacity(b *testing.B) {
	entries := getInputEntries(b)
	b.ResetTimer()
	m := make(map[string]string, b.N)
	for i := range entries {
		m[entries[i].key] = entries[i].value
	}
	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkMutexGuardedMap(b *testing.B) {
	entries := getInputEntries(b)
	lock := &sync.Mutex{}
	m := make(map[string]string)
	i := &atomic.Int64{}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			lock.Lock()
			m[entries[index].key] = entries[index].value
			lock.Unlock()
		}
	})

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkMutexGuardedMapWithCapacity(b *testing.B) {
	entries := getInputEntries(b)
	lock := &sync.Mutex{}
	m := make(map[string]string, b.N)
	i := &atomic.Int64{}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			lock.Lock()
			m[entries[index].key] = entries[index].value
			lock.Unlock()
		}
	})

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkChannelMap(b *testing.B) {
	entries := getInputEntries(b)

	c := make(chan kv, 4096)
	m := make(map[string]string)
	i := &atomic.Int64{}

	done := make(chan struct{})
	go func() {
		for kv := range c {
			m[kv.key] = kv.value
		}
		close(done)
	}()

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			c <- entries[index]
		}
	})
	close(c)
	<-done

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkChannelMapWithCapacity(b *testing.B) {
	entries := getInputEntries(b)

	c := make(chan kv, 4096)
	m := make(map[string]string, b.N)
	i := &atomic.Int64{}

	done := make(chan struct{})
	go func() {
		for kv := range c {
			m[kv.key] = kv.value
		}
		close(done)
	}()

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			c <- entries[index]
		}
	})
	close(c)
	<-done

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkSyncMap(b *testing.B) {
	entries := getInputEntries(b)
	m := sync.Map{}
	i := &atomic.Int64{}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			m.Store(entries[index].key, entries[index].value)
		}
	})

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

func BenchmarkConcurrentMap(b *testing.B) {
	entries := getInputEntries(b)
	m := NewConcurrentHashmap(b.N * 2)
	i := &atomic.Int64{}

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			index := i.Add(1) - 1
			m.Put(entries[index].key, entries[index].value)
		}
	})

	b.ReportMetric(float64(b.N)/b.Elapsed().Seconds(), "ops/sec")
}

type concurrentHashmap struct {
	bins []bin
}

type bin struct {
	m      sync.RWMutex
	keys   []string
	values []string
}

func NewConcurrentHashmap(capacity int) *concurrentHashmap {
	if capacity <= 0 {
		panic("capacity should be positive")
	}

	return &concurrentHashmap{
		bins: make([]bin, capacity),
	}
}

func (c *concurrentHashmap) Put(key string, value string) {
	hasher := fnv.New64()
	b := unsafe.Slice(unsafe.StringData(key), len(key))
	_, _ = hasher.Write(b)
	hash := hasher.Sum64()
	binId := hash % uint64(len(c.bins))

	bin := &c.bins[binId]
	bin.m.Lock()
	defer bin.m.Unlock()

	for i, binKey := range bin.keys {
		if binKey == key {
			bin.values[i] = value
			return
		}
	}

	bin.keys = append(bin.keys, key)
	bin.values = append(bin.values, value)
}

func (c *concurrentHashmap) Get(key string) (value string, ok bool) {
	hasher := fnv.New64()
	b := unsafe.Slice(unsafe.StringData(key), len(key))
	_, _ = hasher.Write(b)
	hash := hasher.Sum64()
	binId := hash % uint64(len(c.bins))

	bin := &c.bins[binId]
	bin.m.RLock()
	defer bin.m.RUnlock()

	for i, binKey := range bin.keys {
		if binKey == key {
			return bin.values[i], true
		}
	}

	return "", false
}

// Result:
// ❯ go test ./... -bench=. -v -benchmem
// goos: linux
// goarch: amd64
// pkg: example.com/golangbench
// cpu: AMD Ryzen 9 7900X 12-Core Processor
// BenchmarkMap
// BenchmarkMap-24                                  3990435               331.0 ns/op         3021555 ops/sec           158 B/op          0 allocs/op
// BenchmarkMapWithCapacity
// BenchmarkMapWithCapacity-24                     11080148               147.6 ns/op         6775880 ops/sec            56 B/op          0 allocs/op
// BenchmarkMutexGuardedMap
// BenchmarkMutexGuardedMap-24                      3881275               392.6 ns/op         2547017 ops/sec           163 B/op          0 allocs/op
// BenchmarkMutexGuardedMapWithCapacity
// BenchmarkMutexGuardedMapWithCapacity-24          7982047               156.8 ns/op         6375912 ops/sec             0 B/op          0 allocs/op
// BenchmarkChannelMap
// BenchmarkChannelMap-24                           2518930               498.7 ns/op         2005098 ops/sec           125 B/op          0 allocs/op
// BenchmarkChannelMapWithCapacity
// BenchmarkChannelMapWithCapacity-24               3916059               303.3 ns/op         3297012 ops/sec             0 B/op          0 allocs/op
// BenchmarkSyncMap
// BenchmarkSyncMap-24                              1928942               646.4 ns/op         1546985 ops/sec           197 B/op          5 allocs/op
// BenchmarkConcurrentMap
// BenchmarkConcurrentMap-24                       27698618                58.59 ns/op       17068035 ops/sec            40 B/op          1 allocs/op
// PASS
// ok      example.com/golangbench 26.502s