sorted set iterator benchmark

set.go

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

set_test.go

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
}