Skip to content

Instantly share code, notes, and snippets.

@meddulla
Forked from donovanhide/Concurrent map benchmarks
Created November 26, 2013 20:23
Show Gist options
  • Save meddulla/7665572 to your computer and use it in GitHub Desktop.
Save meddulla/7665572 to your computer and use it in GitHub Desktop.
package concurrency
type Instruction struct {
Operation OpCode
Key int
Value int
Result chan int
}
type ChannelIntMap struct {
m map[int]int
c chan Instruction
}
func NewChannelIntMap(bufferSize int) *ChannelIntMap {
m := make(map[int]int)
c := make(chan Instruction, bufferSize)
go func() {
for i := range c {
switch i.Operation {
case Get:
i.Result <- m[i.Key]
case Set:
m[i.Key] = i.Value
case Delete:
delete(m, i.Key)
case Len:
i.Result <- len(m)
}
}
}()
return &ChannelIntMap{m, c}
}
func (m *ChannelIntMap) Len() int {
i := Instruction{Len, 0, 0, make(chan int)}
m.c <- i
return <-i.Result
}
func (m *ChannelIntMap) Get(key int) int {
i := Instruction{Get, key, 0, make(chan int)}
m.c <- i
return <-i.Result
}
func (m *ChannelIntMap) Set(key, value int) {
m.c <- Instruction{Set, key, value, nil}
}
func (m *ChannelIntMap) Delete(key int) {
m.c <- Instruction{Delete, key, 0, nil}
}
To benchmark:
go test -bench=".*" > machine_description.txt
package concurrency
import (
"math/rand"
"runtime"
"sync"
"testing"
)
func worker(n int, m ConcurrentIntMap, wg *sync.WaitGroup) {
for i := 0; i < n; i++ {
switch OpCode(rand.Intn(3)) {
case Set:
m.Set(rand.Int(), rand.Int())
case Get:
m.Get(rand.Int())
case Delete:
m.Delete(rand.Int())
}
}
wg.Done()
}
func runBenchmark(n int, m ConcurrentIntMap) int {
rand.Seed(12345)
var wg sync.WaitGroup
for i := 0; i < 100; i++ {
wg.Add(1)
go worker(n/100, m, &wg)
}
wg.Wait()
return m.Len()
}
func BenchmarkSlottedIntMap(b *testing.B) {
m := NewSlottedIntMap(uint(runtime.NumCPU() >> 1))
b.Logf("SlottedIntMap Operations: %d Length: %d Load:%v\n", b.N, runBenchmark(b.N, m), m.LoadFactors())
}
func BenchmarkChannelIntMap(b *testing.B) {
m := NewChannelIntMap(100)
b.Logf("ChannelIntMap Operations: %d Length: %d\n", b.N, runBenchmark(b.N, m))
}
func BenchmarkSimpleIntMap(b *testing.B) {
m := NewSimpleIntMap()
b.Logf("SimpleIntMap Operations: %d Length: %d\n", b.N, runBenchmark(b.N, m))
}
PASS
BenchmarkSlottedIntMap 5000000 728 ns/op
--- BENCH: BenchmarkSlottedIntMap
concurrent_test.go:37: SlottedIntMap Operations: 1 Length: 0 Load:[0 0]
concurrent_test.go:37: SlottedIntMap Operations: 100 Length: 33 Load:[15 18]
concurrent_test.go:37: SlottedIntMap Operations: 10000 Length: 3252 Load:[1632 1620]
concurrent_test.go:37: SlottedIntMap Operations: 1000000 Length: 334101 Load:[166956 167145]
concurrent_test.go:37: SlottedIntMap Operations: 5000000 Length: 1667106 Load:[834155 832951]
BenchmarkChannelIntMap 1000000 1367 ns/op
--- BENCH: BenchmarkChannelIntMap
concurrent_test.go:42: ChannelIntMap Operations: 1 Length: 0
concurrent_test.go:42: ChannelIntMap Operations: 100 Length: 33
concurrent_test.go:42: ChannelIntMap Operations: 10000 Length: 3252
concurrent_test.go:42: ChannelIntMap Operations: 1000000 Length: 334101
BenchmarkSimpleIntMap 5000000 678 ns/op
--- BENCH: BenchmarkSimpleIntMap
concurrent_test.go:47: SimpleIntMap Operations: 1 Length: 0
concurrent_test.go:47: SimpleIntMap Operations: 100 Length: 33
concurrent_test.go:47: SimpleIntMap Operations: 10000 Length: 3252
concurrent_test.go:47: SimpleIntMap Operations: 1000000 Length: 334101
concurrent_test.go:47: SimpleIntMap Operations: 5000000 Length: 1667106
ok _/Users/donovanhide/Desktop/4502606 9.978s
package concurrency
type OpCode int
const (
Get OpCode = iota
Set
Delete
Len
)
type ConcurrentIntMap interface {
Get(key int) int
Set(key, value int)
Delete(key int)
Len() int
}
package concurrency
import (
"sync"
)
type SimpleIntMap struct {
lock sync.RWMutex
m map[int]int
}
func NewSimpleIntMap() *SimpleIntMap {
return &SimpleIntMap{
m: make(map[int]int),
}
}
func (m *SimpleIntMap) Len() int {
m.lock.RLock()
length := len(m.m)
m.lock.RUnlock()
return length
}
func (m *SimpleIntMap) Get(key int) int {
m.lock.RLock()
value := m.m[key]
m.lock.RUnlock()
return value
}
func (m *SimpleIntMap) Set(key, value int) {
m.lock.Lock()
m.m[key] = value
m.lock.Unlock()
}
func (m *SimpleIntMap) Delete(key int) {
m.lock.Lock()
delete(m.m, key)
m.lock.Unlock()
}
package concurrency
import (
"sync"
)
type SlottedIntMap struct {
slots int
maps []map[int]int
locks []sync.RWMutex
}
// lockHint is the left shift to ensure number of slots is a power of 2
func NewSlottedIntMap(lockHint uint) *SlottedIntMap {
slots := 1 << lockHint
m := &SlottedIntMap{
slots: slots,
maps: make([]map[int]int, slots),
locks: make([]sync.RWMutex, slots),
}
for i := range m.maps {
m.maps[i] = make(map[int]int)
}
return m
}
func (m *SlottedIntMap) Len() int {
length := 0
for _, l := range m.LoadFactors() {
length += l
}
return length
}
func (m *SlottedIntMap) Get(key int) int {
slot := key & (m.slots - 1)
m.locks[slot].RLock()
value := m.maps[slot][key]
m.locks[slot].RUnlock()
return value
}
func (m *SlottedIntMap) Set(key, value int) {
slot := key & (m.slots - 1)
m.locks[slot].Lock()
m.maps[slot][key] = value
m.locks[slot].Unlock()
}
func (m *SlottedIntMap) Delete(key int) {
slot := key & (m.slots - 1)
m.locks[slot].Lock()
delete(m.maps[slot], key)
m.locks[slot].Unlock()
}
func (m *SlottedIntMap) LoadFactors() []int {
load := make([]int, m.slots)
for i := range m.locks {
m.locks[i].RLock()
load[i] = len(m.maps[i])
m.locks[i].RUnlock()
}
return load
}
PASS
BenchmarkSlottedIntMap 5000000 448 ns/op
--- BENCH: BenchmarkSlottedIntMap
concurrent_test.go:37: SlottedIntMap Operations: 1 Length: 0 Load:[0 0 0 0]
concurrent_test.go:37: SlottedIntMap Operations: 100 Length: 33 Load:[10 12 5 6]
concurrent_test.go:37: SlottedIntMap Operations: 10000 Length: 3252 Load:[837 797 795 823]
concurrent_test.go:37: SlottedIntMap Operations: 1000000 Length: 334101 Load:[83340 83738 83616 83407]
concurrent_test.go:37: SlottedIntMap Operations: 5000000 Length: 1667106 Load:[416512 416755 417643 416196]
BenchmarkChannelIntMap 2000000 759 ns/op
--- BENCH: BenchmarkChannelIntMap
concurrent_test.go:42: ChannelIntMap Operations: 1 Length: 0
concurrent_test.go:42: ChannelIntMap Operations: 100 Length: 33
concurrent_test.go:42: ChannelIntMap Operations: 10000 Length: 3252
concurrent_test.go:42: ChannelIntMap Operations: 1000000 Length: 334101
concurrent_test.go:42: ChannelIntMap Operations: 2000000 Length: 666614
ok _/usr/local/code/4502606 4.907s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment