channel.go

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}
}

Concurrent map benchmarks

To benchmark:

go test -bench=".*" > machine_description.txt

concurrent_test.go

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))
}

darwin_amd64_coreduo.txt

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

interface.go

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
}

simple.go

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()
}

slotted.go

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
}

ubuntu_amd64.txt

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