sparse-dense vs generations map

perf_test.go

package main

import (
	"math"
	"testing"
)

// Run with -benchtime=10000x to avoid the benchmarks to run ~forever.
// See https://github.com/golang/go/issues/27217

//go:noinline
func mapset(m map[uint16]int, k uint16, v int) {
	m[k] = v
}

//go:noinline
func mapget(m map[uint16]int, k uint16) int {
	return m[k]
}

//go:noinline
func sliceset(s []int, k uint, v int) {
	if k < uint(len(s)) {
		s[k] = v
	}
}

//go:noinline
func sliceget(s []int, k uint) int {
	if k < uint(len(s)) {
		return s[k]
	}
	return 0
}

//go:noinline
func sparseset(s *sparseMap[int], k int32, v int) {
	s.Set(k, v)
}

//go:noinline
func genget(m *generationsMap[int], k uint) int {
	return m.Get(k)
}

//go:noinline
func genset(m *generationsMap[int], k uint, v int) {
	m.Set(k, v)
}

//go:noinline
func sparseget(s *sparseMap[int], k int32) int {
	return s.Get(k)
}

type sparseEntry[T any] struct {
	key int32
	val T
}

type sparseMap[T any] struct {
	dense  []sparseEntry[T]
	sparse []int32
}

func newSparseMap[T any](n int) *sparseMap[T] {
	return &sparseMap[T]{dense: nil, sparse: make([]int32, n)}
}

func (s *sparseMap[T]) Get(k int32) T {
	i := s.sparse[k]
	if i < int32(len(s.dense)) && s.dense[i].key == k {
		return s.dense[i].val
	}
	var zero T
	return zero
}

func (s *sparseMap[T]) Set(k int32, v T) {
	i := s.sparse[k]
	if i < int32(len(s.dense)) && s.dense[i].key == k {
		s.dense[i].val = v
		return
	}
	s.dense = append(s.dense, sparseEntry[T]{k, v})
	s.sparse[k] = int32(len(s.dense)) - 1
}

func (s *sparseMap[T]) Reset() {
	s.dense = s.dense[:0]
}

type generationsElem[T any] struct {
	seq uint32
	val T
}

type generationsMap[T any] struct {
	elems []generationsElem[T]
	seq   uint32
}

func newGenerationsMap[T any](n int) *generationsMap[T] {
	return &generationsMap[T]{
		elems: make([]generationsElem[T], n),
		seq:   1,
	}
}

func (m *generationsMap[T]) Get(k uint) T {
	if k < uint(len(m.elems)) {
		el := m.elems[k]
		if el.seq == m.seq {
			return el.val
		}
	}
	var zero T
	return zero
}

func (m *generationsMap[T]) Set(k uint, v T) {
	if k < uint(len(m.elems)) {
		m.elems[k] = generationsElem[T]{val: v, seq: m.seq}
	}
}

func (m *generationsMap[T]) Reset() {
	if m.seq == math.MaxUint32 {
		// For most users, this will never happen.
		// But to be safe, we need to handle this correctly.
		// m.gen will be 1, element gen will be 0.
		m.seq = 1
		clear(m.elems)
	} else {
		m.seq++
	}
}

func BenchmarkMap_Set5000(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		m := make(map[uint16]int, 5000)
		b.StartTimer()
		for j := 0; j < 5000; j++ {
			mapset(m, uint16(j), i)
		}
	}
}

func BenchmarkMap_Get5000(b *testing.B) {
	m := make(map[uint16]int, 5000)
	for j := 0; j < 5000; j++ {
		mapset(m, uint16(j), j*2)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < 5000; j++ {
			mapget(m, uint16(j))
		}
	}
}

func BenchmarkMap_Reset5000(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		m := make(map[uint16]int, 5000)
		for j := 0; j < 5000; j++ {
			mapset(m, uint16(j), j*2)
		}
		b.StartTimer()
		clear(m)
	}
}

func BenchmarkSlice_Set5000(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		s := make([]int, 0xffff)
		b.StartTimer()
		for j := 0; j < 5000; j++ {
			sliceset(s, uint(j), i)
		}
	}
}

func BenchmarkSlice_Get5000(b *testing.B) {
	s := make([]int, 0xffff)
	for j := 0; j < 5000; j++ {
		sliceset(s, uint(j), j*2)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < 5000; j++ {
			sliceget(s, uint(j))
		}
	}
}

func BenchmarkSlice_Reset5000(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		s := make([]int, 0xffff)
		for j := 0; j < 5000; j++ {
			sliceset(s, uint(j), j*2)
		}
		b.StartTimer()
		clear(s)
	}
}

func BenchmarkSparse_Set5000(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		s := newSparseMap[int](0xffff)
		b.StartTimer()
		for j := 0; j < 5000; j++ {
			sparseset(s, int32(j), i)
		}
	}
}

func BenchmarkSparse_Get5000(b *testing.B) {
	s := newSparseMap[int](0xffff)
	for j := 0; j < 5000; j++ {
		sparseset(s, int32(j), j*2)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < 5000; j++ {
			sparseget(s, int32(j))
		}
	}
}

func BenchmarkSparse_Reset5000(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		s := newSparseMap[int](0xffff)
		for j := 0; j < 5000; j++ {
			s.Set(int32(j), j*2)
		}
		b.StartTimer()
		s.Reset()
	}
}

func BenchmarkGenerations_Set5000(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		m := newGenerationsMap[int](0xffff)
		b.StartTimer()
		for j := 0; j < 5000; j++ {
			genset(m, uint(j), i)
		}
	}
}

func BenchmarkGenerations_Get5000(b *testing.B) {
	m := newGenerationsMap[int](0xffff)
	for j := 0; j < 5000; j++ {
		genset(m, uint(j), j*2)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < 5000; j++ {
			genget(m, uint(j))
		}
	}
}

func BenchmarkGenerations_Reset5000(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		m := newGenerationsMap[int](0xffff)
		for j := 0; j < 5000; j++ {
			m.Set(uint(j), j*2)
		}
		b.StartTimer()
		m.Reset()
	}
}