Instantly share code, notes, and snippets.

@aybabtme /int_member_test.go Secret
Last active Aug 29, 2015

Embed
What would you like to do?
package set_test
import (
"math/rand"
"testing"
)
func BenchmarkIntMap_2key(b *testing.B) { benchIntMapMembers(b, 2) }
func BenchmarkIntMap_3key(b *testing.B) { benchIntMapMembers(b, 3) }
func BenchmarkIntMap_4key(b *testing.B) { benchIntMapMembers(b, 4) }
func BenchmarkIntMap_5key(b *testing.B) { benchIntMapMembers(b, 5) }
func BenchmarkIntMap_6key(b *testing.B) { benchIntMapMembers(b, 6) }
func BenchmarkIntMap_7key(b *testing.B) { benchIntMapMembers(b, 7) }
func BenchmarkIntMap_8key(b *testing.B) { benchIntMapMembers(b, 8) }
func BenchmarkIntMap_9key(b *testing.B) { benchIntMapMembers(b, 9) }
func BenchmarkIntMap_10key(b *testing.B) { benchIntMapMembers(b, 10) }
func BenchmarkIntMap_100key(b *testing.B) { benchIntMapMembers(b, 100) }
func BenchmarkIntMap_1000key(b *testing.B) { benchIntMapMembers(b, 1000) }
func BenchmarkIntMap_10000key(b *testing.B) { benchIntMapMembers(b, 10000) }
func BenchmarkIntMap_100000key(b *testing.B) { benchIntMapMembers(b, 100000) }
func BenchmarkIntMap_1000000key(b *testing.B) { benchIntMapMembers(b, 1000000) }
func BenchmarkIntSlice_2key(b *testing.B) { benchIntSliceMembers(b, 2) }
func BenchmarkIntSlice_3key(b *testing.B) { benchIntSliceMembers(b, 3) }
func BenchmarkIntSlice_4key(b *testing.B) { benchIntSliceMembers(b, 4) }
func BenchmarkIntSlice_5key(b *testing.B) { benchIntSliceMembers(b, 5) }
func BenchmarkIntSlice_6key(b *testing.B) { benchIntSliceMembers(b, 6) }
func BenchmarkIntSlice_7key(b *testing.B) { benchIntSliceMembers(b, 7) }
func BenchmarkIntSlice_8key(b *testing.B) { benchIntSliceMembers(b, 8) }
func BenchmarkIntSlice_9key(b *testing.B) { benchIntSliceMembers(b, 9) }
func BenchmarkIntSlice_10key(b *testing.B) { benchIntSliceMembers(b, 10) }
func BenchmarkIntSlice_100key(b *testing.B) { benchIntSliceMembers(b, 100) }
func BenchmarkIntSlice_1000key(b *testing.B) { benchIntSliceMembers(b, 1000) }
func BenchmarkIntSlice_10000key(b *testing.B) { benchIntSliceMembers(b, 10000) }
func BenchmarkIntSlice_100000key(b *testing.B) { benchIntSliceMembers(b, 100000) }
func BenchmarkIntSlice_1000000key(b *testing.B) { benchIntSliceMembers(b, 1000000) }
func BenchmarkIntMapNot_10key(b *testing.B) { benchIntMapNotMembers(b, 10) }
func BenchmarkIntMapNot_1000key(b *testing.B) { benchIntMapNotMembers(b, 1000) }
func BenchmarkIntMapNot_1000000key(b *testing.B) { benchIntMapNotMembers(b, 1000000) }
func BenchmarkIntSliceNot_10key(b *testing.B) { benchIntSliceNotMembers(b, 10) }
func BenchmarkIntSliceNot_10000key(b *testing.B) { benchIntSliceNotMembers(b, 10000) }
func BenchmarkIntSliceNot_1000000key(b *testing.B) { benchIntSliceNotMembers(b, 1000000) }
// Helpers
func benchIntMapMembers(b *testing.B, size int) {
m := makeRandomIntMap(size)
samples := sampleFromIntMap(m, b.N)
var member int
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isIntMapMember(m, member)
}
_ = ok
}
func benchIntMapNotMembers(b *testing.B, size int) {
m := makeRandomIntMap(size)
samples := sampleNotInIntMap(m, b.N)
var member int
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isIntMapMember(m, member)
}
_ = ok
}
func benchIntSliceMembers(b *testing.B, size int) {
s := makeRandomIntSlice(size)
samples := sampleFromIntSlice(s, b.N)
var member int
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isIntSliceMember(s, member)
}
_ = ok
}
func benchIntSliceNotMembers(b *testing.B, size int) {
s := makeRandomIntSlice(size)
samples := sampleNotInIntSlice(s, b.N)
var member int
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isIntSliceMember(s, member)
}
_ = ok
}
// Membership tests
func isIntMapMember(m map[int]bool, key int) bool {
_, ok := m[key]
return ok
}
func isIntSliceMember(s []int, key int) bool {
for _, entry := range s {
if key == entry {
return true
}
}
return false
}
// Maps
func makeRandomIntMap(n int) map[int]bool {
set := make(map[int]bool, n)
var i int
for len(set) != n {
i = rand.Int()
if _, ok := set[i]; !ok {
set[i] = true
}
}
return set
}
func sampleFromIntMap(m map[int]bool, size int) (samples []int) {
var keys []int
for key := range m {
keys = append(keys, key)
}
for i := 0; i < size; i++ {
idx := rand.Intn(len(keys))
samples = append(samples, keys[idx])
}
return
}
func sampleNotInIntMap(m map[int]bool, size int) (samples []int) {
var i int
for len(samples) != size {
i = rand.Int()
if !m[i] {
samples = append(samples, i)
}
}
return
}
// Slices
func makeRandomIntSlice(size int) (uniques []int) {
set := make(map[int]bool, size)
var i int
for len(uniques) != size {
i = rand.Int()
if _, ok := set[i]; !ok {
set[i] = true
uniques = append(uniques, i)
}
}
return
}
func sampleFromIntSlice(s []int, size int) (samples []int) {
for i := 0; i < size; i++ {
idx := rand.Intn(len(s))
samples = append(samples, s[idx])
}
return
}
func sampleNotInIntSlice(s []int, size int) (samples []int) {
set := make(map[int]bool, size)
for _, key := range s {
set[key] = true
}
var i int
for len(samples) != size {
i = rand.Int()
if _, ok := set[i]; !ok {
samples = append(samples, i)
}
}
return
}
package set_test
import (
"math/rand"
"testing"
)
func BenchmarkMap_2key_10bytes(b *testing.B) { benchMapMembers(b, 2, 10) }
func BenchmarkMap_3key_10bytes(b *testing.B) { benchMapMembers(b, 3, 10) }
func BenchmarkMap_4key_10bytes(b *testing.B) { benchMapMembers(b, 4, 10) }
func BenchmarkMap_5key_10bytes(b *testing.B) { benchMapMembers(b, 5, 10) }
func BenchmarkMap_6key_10bytes(b *testing.B) { benchMapMembers(b, 6, 10) }
func BenchmarkMap_7key_10bytes(b *testing.B) { benchMapMembers(b, 7, 10) }
func BenchmarkMap_8key_10bytes(b *testing.B) { benchMapMembers(b, 8, 10) }
func BenchmarkMap_9key_10bytes(b *testing.B) { benchMapMembers(b, 9, 10) }
func BenchmarkMap_10key_10bytes(b *testing.B) { benchMapMembers(b, 10, 10) }
func BenchmarkMap_100key_10bytes(b *testing.B) { benchMapMembers(b, 100, 10) }
func BenchmarkMap_1000key_10bytes(b *testing.B) { benchMapMembers(b, 1000, 10) }
func BenchmarkMap_10000key_10bytes(b *testing.B) { benchMapMembers(b, 10000, 10) }
func BenchmarkMap_100000key_10bytes(b *testing.B) { benchMapMembers(b, 100000, 10) }
func BenchmarkMap_1000000key_10bytes(b *testing.B) { benchMapMembers(b, 1000000, 10) }
func BenchmarkMap_2key_100bytes(b *testing.B) { benchMapMembers(b, 2, 100) }
func BenchmarkMap_3key_100bytes(b *testing.B) { benchMapMembers(b, 3, 100) }
func BenchmarkMap_4key_100bytes(b *testing.B) { benchMapMembers(b, 4, 100) }
func BenchmarkMap_5key_100bytes(b *testing.B) { benchMapMembers(b, 5, 100) }
func BenchmarkMap_6key_100bytes(b *testing.B) { benchMapMembers(b, 6, 100) }
func BenchmarkMap_7key_100bytes(b *testing.B) { benchMapMembers(b, 7, 100) }
func BenchmarkMap_8key_100bytes(b *testing.B) { benchMapMembers(b, 8, 100) }
func BenchmarkMap_9key_100bytes(b *testing.B) { benchMapMembers(b, 9, 100) }
func BenchmarkMap_10key_100bytes(b *testing.B) { benchMapMembers(b, 10, 100) }
func BenchmarkMap_100key_100bytes(b *testing.B) { benchMapMembers(b, 100, 100) }
func BenchmarkMap_1000key_100bytes(b *testing.B) { benchMapMembers(b, 1000, 100) }
func BenchmarkMap_10000key_100bytes(b *testing.B) { benchMapMembers(b, 10000, 100) }
func BenchmarkMap_100000key_100bytes(b *testing.B) { benchMapMembers(b, 100000, 100) }
func BenchmarkMap_1000000key_100bytes(b *testing.B) { benchMapMembers(b, 1000000, 100) }
func BenchmarkSlice_2key_10bytes(b *testing.B) { benchSliceMembers(b, 2, 10) }
func BenchmarkSlice_3key_10bytes(b *testing.B) { benchSliceMembers(b, 3, 10) }
func BenchmarkSlice_4key_10bytes(b *testing.B) { benchSliceMembers(b, 4, 10) }
func BenchmarkSlice_5key_10bytes(b *testing.B) { benchSliceMembers(b, 5, 10) }
func BenchmarkSlice_6key_10bytes(b *testing.B) { benchSliceMembers(b, 6, 10) }
func BenchmarkSlice_7key_10bytes(b *testing.B) { benchSliceMembers(b, 7, 10) }
func BenchmarkSlice_8key_10bytes(b *testing.B) { benchSliceMembers(b, 8, 10) }
func BenchmarkSlice_9key_10bytes(b *testing.B) { benchSliceMembers(b, 9, 10) }
func BenchmarkSlice_10key_10bytes(b *testing.B) { benchSliceMembers(b, 10, 10) }
func BenchmarkSlice_100key_10bytes(b *testing.B) { benchSliceMembers(b, 100, 10) }
func BenchmarkSlice_1000key_10bytes(b *testing.B) { benchSliceMembers(b, 1000, 10) }
func BenchmarkSlice_10000key_10bytes(b *testing.B) { benchSliceMembers(b, 10000, 10) }
func BenchmarkSlice_100000key_10bytes(b *testing.B) { benchSliceMembers(b, 100000, 10) }
func BenchmarkSlice_1000000key_10bytes(b *testing.B) { benchSliceMembers(b, 1000000, 10) }
func BenchmarkSlice_2key_100bytes(b *testing.B) { benchSliceMembers(b, 2, 100) }
func BenchmarkSlice_3key_100bytes(b *testing.B) { benchSliceMembers(b, 3, 100) }
func BenchmarkSlice_4key_100bytes(b *testing.B) { benchSliceMembers(b, 4, 100) }
func BenchmarkSlice_5key_100bytes(b *testing.B) { benchSliceMembers(b, 5, 100) }
func BenchmarkSlice_6key_100bytes(b *testing.B) { benchSliceMembers(b, 6, 100) }
func BenchmarkSlice_7key_100bytes(b *testing.B) { benchSliceMembers(b, 7, 100) }
func BenchmarkSlice_8key_100bytes(b *testing.B) { benchSliceMembers(b, 8, 100) }
func BenchmarkSlice_9key_100bytes(b *testing.B) { benchSliceMembers(b, 9, 100) }
func BenchmarkSlice_10key_100bytes(b *testing.B) { benchSliceMembers(b, 10, 100) }
func BenchmarkSlice_100key_100bytes(b *testing.B) { benchSliceMembers(b, 100, 100) }
func BenchmarkSlice_1000key_100bytes(b *testing.B) { benchSliceMembers(b, 1000, 100) }
func BenchmarkSlice_10000key_100bytes(b *testing.B) { benchSliceMembers(b, 10000, 100) }
func BenchmarkSlice_100000key_100bytes(b *testing.B) { benchSliceMembers(b, 100000, 100) }
func BenchmarkSlice_1000000key_100bytes(b *testing.B) { benchSliceMembers(b, 1000000, 100) }
func BenchmarkMapNot_10key_10bytes(b *testing.B) { benchMapNotMembers(b, 10, 10) }
func BenchmarkMapNot_1000key_10bytes(b *testing.B) { benchMapNotMembers(b, 1000, 10) }
func BenchmarkMapNot_1000000key_10bytes(b *testing.B) { benchMapNotMembers(b, 1000000, 10) }
func BenchmarkSliceNot_10key_10bytes(b *testing.B) { benchSliceNotMembers(b, 10, 10) }
func BenchmarkSliceNot_10000key_10bytes(b *testing.B) { benchSliceNotMembers(b, 10000, 10) }
func BenchmarkSliceNot_1000000key_10bytes(b *testing.B) { benchSliceNotMembers(b, 1000000, 10) }
// Helpers
func benchMapMembers(b *testing.B, size int, keySize int) {
// b.Logf("making rand map, size %d, key sized %d", size, keySize)
m := makeRandomMap(size, keySize)
// b.Logf("taking %d rand sample in map, key sized %d", b.N)
samples := sampleFromMap(m, b.N)
var member string
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isMapMember(m, member)
}
_ = ok
}
func benchMapNotMembers(b *testing.B, size int, keySize int) {
// b.Logf("making rand map, size %d, key sized %d", size, keySize)
m := makeRandomMap(size, keySize)
// b.Logf("taking %d rand sample not in map, key sized %d", b.N, keySize)
samples := sampleNotInMap(m, b.N, keySize)
var member string
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isMapMember(m, member)
}
_ = ok
}
func benchSliceMembers(b *testing.B, size int, keySize int) {
// b.Logf("making rand slice, size %d, key sized %d", size, keySize)
s := makeRandomSlice(size, keySize)
// b.Logf("taking %d rand sample in slice", b.N)
samples := sampleFromSlice(s, b.N)
var member string
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isSliceMember(s, member)
}
_ = ok
}
func benchSliceNotMembers(b *testing.B, size int, keySize int) {
// b.Logf("making rand slice, size %d, key sized %d", size, keySize)
s := makeRandomSlice(size, keySize)
// b.Logf("taking %d rand sample not in slice, key sized %d", b.N, keySize)
samples := sampleNotInSlice(s, b.N, keySize)
var member string
var ok bool
// b.Log("starting")
b.ResetTimer()
for i := 0; i < b.N; i++ {
member = samples[i]
ok = isSliceMember(s, member)
}
_ = ok
}
// Membership tests
func isMapMember(m map[string]bool, key string) bool {
_, ok := m[key]
return ok
}
func isSliceMember(s []string, key string) bool {
for _, entry := range s {
if key == entry {
return true
}
}
return false
}
// Maps
func makeRandomMap(n, valSize int) map[string]bool {
set := make(map[string]bool, n)
var str string
for len(set) != n {
str = makeRandomString(valSize)
if _, ok := set[str]; !ok {
set[str] = true
}
}
return set
}
func sampleFromMap(m map[string]bool, size int) (samples []string) {
var keys []string
for key := range m {
keys = append(keys, key)
}
for i := 0; i < size; i++ {
idx := rand.Intn(len(keys))
samples = append(samples, keys[idx])
}
return
}
func sampleNotInMap(m map[string]bool, size, keySize int) (samples []string) {
var str string
for len(samples) != size {
str = makeRandomString(keySize)
if !m[str] {
samples = append(samples, str)
}
}
return
}
// Slices
func makeRandomSlice(size, strSize int) (uniques []string) {
set := make(map[string]bool, size)
var str string
for len(uniques) != size {
str = makeRandomString(strSize)
if _, ok := set[str]; !ok {
set[str] = true
uniques = append(uniques, str)
}
}
return
}
func sampleFromSlice(s []string, size int) (samples []string) {
for i := 0; i < size; i++ {
idx := rand.Intn(len(s))
samples = append(samples, s[idx])
}
return
}
func sampleNotInSlice(s []string, size, keySize int) (samples []string) {
set := make(map[string]bool, size)
for _, key := range s {
set[key] = true
}
var str string
for len(samples) != size {
str = makeRandomString(keySize)
if _, ok := set[str]; !ok {
samples = append(samples, str)
}
}
return
}
// Strings
func makeRandomString(size int) string {
raw := make([]rune, size)
for i := range raw {
raw[i] = randRune()
}
return string(raw)
}
func randRune() rune {
const runeString = `01234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()`
i := rand.Intn(len(runeString))
return []rune(runeString)[i]
}
@aybabtme

This comment has been minimized.

Owner

aybabtme commented Mar 23, 2014

Int map/slice membership benchmark:

BenchmarkIntMap_2key    100000000           11.3 ns/op
BenchmarkIntMap_3key    100000000           14.0 ns/op
BenchmarkIntMap_4key    100000000           16.0 ns/op
BenchmarkIntMap_5key    100000000           16.4 ns/op
BenchmarkIntMap_6key    100000000           17.4 ns/op
BenchmarkIntMap_7key    100000000           19.4 ns/op
BenchmarkIntMap_8key    100000000           20.5 ns/op
BenchmarkIntMap_9key    50000000            29.9 ns/op
BenchmarkIntMap_10key   50000000            29.9 ns/op
BenchmarkIntMap_20key   50000000            29.8 ns/op
BenchmarkIntMap_30key   50000000            28.5 ns/op
BenchmarkIntMap_40key   50000000            31.6 ns/op
BenchmarkIntMap_50key   50000000            30.7 ns/op
BenchmarkIntMap_100key  50000000            30.6 ns/op
BenchmarkIntMap_1000key 50000000            29.8 ns/op
BenchmarkIntMap_10000key    50000000            32.6 ns/op
BenchmarkIntMap_100000key   50000000            40.4 ns/op
BenchmarkIntMap_1000000key  50000000            74.7 ns/op
BenchmarkIntSlice_2key  200000000            9.02 ns/op
BenchmarkIntSlice_3key  100000000           11.1 ns/op
BenchmarkIntSlice_4key  100000000           12.3 ns/op
BenchmarkIntSlice_5key  100000000           13.2 ns/op
BenchmarkIntSlice_6key  100000000           13.7 ns/op
BenchmarkIntSlice_7key  100000000           14.5 ns/op
BenchmarkIntSlice_8key  100000000           15.1 ns/op
BenchmarkIntSlice_9key  100000000           16.0 ns/op
BenchmarkIntSlice_10key 100000000           16.7 ns/op
BenchmarkIntSlice_20key 100000000           24.6 ns/op
BenchmarkIntSlice_30key 50000000            31.1 ns/op
BenchmarkIntSlice_40key 50000000            35.3 ns/op
BenchmarkIntSlice_50key 50000000            39.5 ns/op
BenchmarkIntSlice_100key    50000000            56.2 ns/op
BenchmarkIntSlice_1000key    5000000           340 ns/op
BenchmarkIntSlice_10000key    500000          3212 ns/op
BenchmarkIntSlice_100000key    50000         31051 ns/op
BenchmarkIntSlice_1000000key        5000        331630 ns/op
BenchmarkIntMapNot_10key    100000000           25.4 ns/op
BenchmarkIntMapNot_1000key  100000000           25.5 ns/op
BenchmarkIntMapNot_1000000key   20000000            80.7 ns/op
BenchmarkIntSliceNot_10key  100000000           18.0 ns/op
BenchmarkIntSliceNot_10000key     500000          6220 ns/op
BenchmarkIntSliceNot_1000000key     5000        718006 ns/op
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment