Skip to content

Instantly share code, notes, and snippets.

@OneOfOne

OneOfOne/xxhash_map_test.go

Created July 27, 2014 09:56
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save OneOfOne/9d2f9ea36f8507fd60cd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save OneOfOne/9d2f9ea36f8507fd60cd to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. OneOfOne created this gist Jul 27, 2014.
    139 changes: 139 additions & 0 deletions xxhash_map_test.go
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,139 @@
    package xxhash_map_test

    import (
    "bytes"
    "fmt"
    "testing"

    "github.com/OneOfOne/xxhash"
    )

    const size = 1000

    var (
    shortUmap = make(map[uint64]int, size)
    shortSmap = make(map[string]int, size)
    shortKeys = make([]string, size)

    longUmap = make(map[uint64]int, size)
    longSmap = make(map[string]int, size)
    longKeys = make([]string, size)

    reallyLongUmap = make(map[uint64]int, size)
    reallyLongSmap = make(map[string]int, size)
    reallyLongKeys = make([]string, size)

    buf bytes.Buffer
    )

    func getKey(length, idx int) string {
    buf.Reset()
    for i := 0; i < length; i++ {
    buf.WriteByte('a')
    }
    buf.WriteString(fmt.Sprint(idx))
    return buf.String()
    }

    func init() {
    for i := 0; i < size; i++ {
    key := getKey(10, i)
    shortKeys[i] = key
    shortUmap[xxChecksum(key)] = i
    shortSmap[key] = i

    key = getKey(130, i)

    longKeys[i] = key
    longUmap[xxChecksum(key)] = i
    longSmap[key] = i

    key = getKey(400, i)

    reallyLongKeys[i] = key
    reallyLongUmap[xxChecksum(key)] = i
    reallyLongSmap[key] = i
    }
    }

    func xxChecksum(s string) uint64 { //avoid allocating extra allocations, in my app the key is already []byte{}
    buf.Reset()
    buf.WriteString(s)
    return xxhash.Checksum64(buf.Bytes())
    }

    func BenchmarkShortXxhash(b *testing.B) {
    var cnt uint64
    for i := 0; i < b.N; i++ {
    for _, k := range shortKeys {
    cnt += uint64(shortUmap[xxChecksum(k)])
    }
    }
    _ = cnt
    }

    func BenchmarkShortString(b *testing.B) {
    var cnt uint64
    for i := 0; i < b.N; i++ {
    for _, k := range shortKeys {
    cnt += uint64(shortSmap[k])
    }
    }
    _ = cnt
    }

    func BenchmarkLongXxhash(b *testing.B) {
    var cnt uint64

    for i := 0; i < b.N; i++ {
    for _, k := range longKeys {
    cnt += uint64(longUmap[xxChecksum(k)])
    }
    }
    _ = cnt
    }

    func BenchmarkLongString(b *testing.B) {
    var cnt uint64
    for i := 0; i < b.N; i++ {
    for _, k := range longKeys {
    cnt += uint64(longSmap[k])
    }
    }
    _ = cnt
    }

    func BenchmarkReallyLongXxhash(b *testing.B) {
    var cnt uint64

    for i := 0; i < b.N; i++ {
    for _, k := range reallyLongKeys {
    cnt += uint64(reallyLongUmap[xxChecksum(k)])
    }
    }
    _ = cnt
    }

    func BenchmarkReallyLongString(b *testing.B) {
    var cnt uint64
    for i := 0; i < b.N; i++ {
    for _, k := range reallyLongKeys {
    cnt += uint64(reallyLongSmap[k])
    }
    }
    _ = cnt
    }


    /*
    it evens out if len(key) ~= 120, xxhashis 2.5 faster at 400+.
    ➜ go test -bench=. -benchmem
    ....
    BenchmarkShortXxhash 5000 262097 ns/op 0 B/op 0 allocs/op
    BenchmarkShortString 20000 62676 ns/op 0 B/op 0 allocs/op
    BenchmarkLongXxhash 5000 294506 ns/op 0 B/op 0 allocs/op
    BenchmarkLongString 5000 253967 ns/op 0 B/op 0 allocs/op
    BenchmarkReallyLongXxhash 5000 347273 ns/op 0 B/op 0 allocs/op
    BenchmarkReallyLongString 2000 691856 ns/op 0 B/op 0 allocs/op
    */