Map Test

benchmarkResult

goos: linux
goarch: amd64
BenchmarkGoMap-4                              10         152401135 ns/op        61921158 B/op      19104 allocs/op
BenchmarkFakeMap-4                             5         225634561 ns/op        105266198 B/op    519008 allocs/op
BenchmarkGoMapQuery-4                          3         337183233 ns/op        61943141 B/op      19210 allocs/op
BenchmarkFakeMapQuery-4                        3         383323147 ns/op        105281136 B/op    519060 allocs/op
BenchmarkGoMapQueryOnly-4                     10         177926115 ns/op               0 B/op          0 allocs/op
BenchmarkFakeMapQueryOnly-4                   10         156825677 ns/op               0 B/op          0 allocs/op
BenchmarkGoMapQueryAndUpdate-4                10         195413146 ns/op               0 B/op          0 allocs/op
BenchmarkFakeMapQueryAndUpdate-4              10         157194905 ns/op               0 B/op          0 allocs/op
PASS
ok      _/home/ejq/maptest      29.210s

main.go

package main

import (
	"bytes"
	"fmt"
	"reflect"
	"runtime"
	"unsafe"

	"github.com/spaolacci/murmur3"
)

type fakeMap struct {
	d map[uint64][]counterType
}

type goMap struct {
	d map[MutableString]uint64
}

type counterType struct {
	h1    uint64
	h2    uint64
	data  []byte
	count uint64
}

func groupElements2(data [][]byte) goMap {
	ret := make(map[MutableString]uint64)

	for k := range data {
		ret[String(data[k])]++
	}

	return goMap{d: ret}
}

func groupElements(data [][]byte) fakeMap {
	counter := make(map[uint64][]counterType)
	for k := range data {
		h1, h2 := murmur3.Sum128(data[k])
		vals, ok := counter[h1]
		if !ok {
			vals = make([]counterType, 0)
		}
		exists := false
		for i := range vals {
			if vals[i].h2 == h2 && bytes.Equal(vals[i].data, data[k]) {
				exists = true
				vals[i].count++
			}
		}
		if !exists {
			vals = append(vals, counterType{h1, h2, data[k], 1})
		}
		counter[h1] = vals
	}

	return fakeMap{d: counter}
}

func (c *fakeMap) queryAddTopN(h1, h2, count uint64, d []byte) (uint64, bool) {
	cnt, ok := c.d[h1]
	if !ok {
		return 0, false
	}
	for k := range cnt {
		if cnt[k].h2 == h2 && bytes.Equal(d, cnt[k].data) {
			if count != 0 {
				// Avoid potential data race
				cnt[k].count += count
			}
			return cnt[k].count, true
		}
	}
	return 0, false
}

func (c *goMap) queryAddTopN(h1, h2, count uint64, d []byte) (uint64, bool) {
	cnt, ok := c.d[String(d)]
	if ok && count != 0 {
		c.d[String(d)] = cnt + count
	}
	return cnt, ok
}

// MutableString can be used as string via string(MutableString) without performance loss.
type MutableString string

// String converts slice to MutableString without copy.
// The MutableString can be converts to string without copy.
// Use it at your own risk.
func String(b []byte) (s MutableString) {
	if len(b) == 0 {
		return ""
	}
	pbytes := (*reflect.SliceHeader)(unsafe.Pointer(&b))
	pstring := (*reflect.StringHeader)(unsafe.Pointer(&s))
	pstring.Data = pbytes.Data
	pstring.Len = pbytes.Len
	return
}

// Slice converts string to slice without copy.
// Use at your own risk.
func Slice(s string) (b []byte) {
	pbytes := (*reflect.SliceHeader)(unsafe.Pointer(&b))
	pstring := (*reflect.StringHeader)(unsafe.Pointer(&s))
	pbytes.Data = pstring.Data
	pbytes.Len = pstring.Len
	pbytes.Cap = pstring.Len
	return
}

func main() {
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	for n := 0; n < 5; n++ {
		a := groupElements(data)
		_ = a
		runtime.GC()
	}

	for n := 0; n < 5; n++ {
		a := groupElements2(data)
		_ = a
		runtime.GC()
	}
}

map_test.go

package main

import (
	"fmt"
	"runtime"
	"testing"

	"github.com/spaolacci/murmur3"
)

func BenchmarkGoMap(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		a := groupElements2(data2)
		_ = a
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkFakeMap(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		a := groupElements(data2)
		_ = a
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkGoMapQuery(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		a := groupElements2(data2)
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 0, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkFakeMapQuery(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		a := groupElements(data2)
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 0, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkGoMapQueryOnly(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	a := groupElements2(data2)
	runtime.GC()
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 0, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkFakeMapQueryOnly(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	a := groupElements(data2)
	runtime.GC()
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 0, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkGoMapQueryAndUpdate(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	a := groupElements2(data2)
	runtime.GC()
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 1, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}

func BenchmarkFakeMapQueryAndUpdate(b *testing.B) {
	b.StopTimer()
	data := make([][]byte, 0)
	for n := 0; n < 1000000; n++ {
		data = append(data, []byte(fmt.Sprintf("%d", n)))
	}
	data2 := data[:500000]
	a := groupElements(data2)
	runtime.GC()
	b.StartTimer()
	for n := 0; n < b.N; n++ {
		for i := range data {
			h1, h2 := murmur3.Sum128(data[i])
			e, ok := a.queryAddTopN(h1, h2, 1, data[i])
			_, _ = e, ok
		}
		b.StopTimer()
		runtime.GC()
		b.StartTimer()
	}
}