Skip to content

Instantly share code, notes, and snippets.

@egonelbre
Last active Aug 29, 2015
Embed
What would you like to do?
sorted set iterator benchmark
package sortedset
type bucket uint16
const (
bits = 15 // bits per bucket
cbit = 1 << bits // continuation bit
mask = cbit - 1 // bits mask
)
type Set struct {
cur int
count int
data []bucket
}
func New() *Set {
return &Set{}
}
func (s *Set) Add(v int) {
df := v - s.cur
if df <= 0 {
panic("Not in increasing order!")
}
s.cur = v
s.count += 1
// fast detection of numbits
switch {
case df < cbit:
s.data = append(s.data, bucket(df))
case df>>(bits*1) < cbit:
s.data = append(s.data,
bucket(cbit|(df&mask)),
bucket(df>>bits),
)
case df>>(bits*2) < cbit:
s.data = append(s.data,
bucket(cbit|(df&mask)),
bucket(cbit|((df>>(bits*1))&mask)),
bucket(df>>(bits*2)),
)
case df>>(bits*3) < cbit:
s.data = append(s.data,
bucket(cbit|(df&mask)),
bucket(cbit|((df>>(bits*1))&mask)),
bucket(cbit|((df>>(bits*2))&mask)),
bucket(df>>(bits*3)),
)
case df>>(bits*4) < cbit:
s.data = append(s.data,
bucket(cbit|(df&mask)),
bucket(cbit|((df>>(bits*1))&mask)),
bucket(cbit|((df>>(bits*2))&mask)),
bucket(cbit|((df>>(bits*3))&mask)),
bucket(df>>(bits*4)),
)
default:
for ; df >= cbit; df = df >> bits {
s.data = append(s.data, bucket(cbit|(df&mask)))
}
s.data = append(s.data, bucket(df))
}
}
func (s *Set) Len() int {
return s.count
}
func (s *Set) IterChan(buf int) chan int {
vals := make(chan int, buf)
go func() {
j := 0
base := 0
df := 0
k := uint(0)
for _, b := range s.data {
df = df | (int(b&mask) << k)
k += bits
if b < cbit {
base += df
vals <- base
df = 0
k = 0
j += 1
}
}
close(vals)
}()
return vals
}
func (s *Set) IterSlice() []int {
vals := make([]int, s.count)
j := 0
base := 0
df := 0
k := uint(0)
for _, b := range s.data {
df = df | (int(b&mask) << k)
k += bits
if b < cbit {
base += df
vals[j] = base
df = 0
k = 0
j += 1
}
}
return vals
}
func (s *Set) IterCallback(fn func(int)) {
j := 0
base := 0
df := 0
k := uint(0)
for _, b := range s.data {
df = df | (int(b&mask) << k)
k += bits
if b < cbit {
base += df
fn(base)
df = 0
k = 0
j += 1
}
}
}
func (s *Set) IterBlockCallback(blockSize int, fn func([]int)) {
block := make([]int, 0, blockSize)
j := 0
base := 0
df := 0
k := uint(0)
for _, b := range s.data {
df = df | (int(b&mask) << k)
k += bits
if b < cbit {
base += df
block = append(block, base)
df = 0
k = 0
j += 1
if cap(block) == len(block) {
fn(block)
block = block[0:0:blockSize]
}
}
}
if len(block) > 0 {
fn(block)
}
}
package sortedset
import (
"math/rand"
"testing"
)
func newBenchSet(b *testing.B) *Set {
set := New()
base := 0
for i := 0; i < b.N; i += 1 {
base += rand.Intn(15) + 1
set.Add(base)
}
b.ResetTimer()
return set
}
func BenchmarkChanUnbuffered(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterChan(0) {
total += v
}
_ = total
}
func BenchmarkBuffered8(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterChan(8) {
total += v
}
_ = total
}
func BenchmarkBuffered16(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterChan(16) {
total += v
}
_ = total
}
func BenchmarkBuffered32(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterChan(32) {
total += v
}
_ = total
}
func BenchmarkBuffered64(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterChan(64) {
total += v
}
_ = total
}
func BenchmarkSlice(b *testing.B) {
set := newBenchSet(b)
total := 0
for v := range set.IterSlice() {
total += v
}
_ = total
}
func BenchmarkCallback(b *testing.B) {
set := newBenchSet(b)
total := 0
set.IterCallback(func(v int) {
total += v
})
_ = total
}
func BenchmarkBlockCallback8(b *testing.B) {
set := newBenchSet(b)
total := 0
set.IterBlockCallback(8, func(vs []int) {
for v := range vs {
total += v
}
})
_ = total
}
func BenchmarkBlockCallback16(b *testing.B) {
set := newBenchSet(b)
total := 0
set.IterBlockCallback(16, func(vs []int) {
for v := range vs {
total += v
}
})
_ = total
}
func BenchmarkBlockCallback32(b *testing.B) {
set := newBenchSet(b)
total := 0
set.IterBlockCallback(32, func(vs []int) {
for v := range vs {
total += v
}
})
_ = total
}
func BenchmarkBlockCallback64(b *testing.B) {
set := newBenchSet(b)
total := 0
set.IterBlockCallback(64, func(vs []int) {
for v := range vs {
total += v
}
})
_ = total
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment