set comparison

set.go

package main

import (
	"bytes"
	"flag"
	"fmt"
	"log"
	"runtime"
	"sync"

	"github.com/cznic/b"
	"github.com/datastream/btree"
	"github.com/petar/GoLLRB/llrb"
)

func main() {
	var (
		kind = flag.String("kind", "map", "map, btree, llrb, cznic")
		n    = flag.Int("n", 10000, "how many values to store")
	)
	flag.Parse()
	log.SetFlags(0)

	var s set
	switch *kind {
	case "map":
		s = newMapSet()
	case "btree":
		s = newBtreeSet()
	case "llrb":
		s = newLLRBSet()
	case "cznic":
		s = newCznicSet()
	default:
		log.Fatalf("%q: invalid kind", *kind)
	}

	for i := 0; i < *n; i++ {
		s.add(fmt.Sprintf("%9d", i))
	}

	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	log.Print(m.Alloc)
}

type set interface {
	add(value string)
	has(value string) bool
	del(value string)
}

type mapSet struct {
	sync.RWMutex
	m map[string]struct{}
}

func newMapSet() *mapSet {
	return &mapSet{
		m: map[string]struct{}{},
	}
}

func (s *mapSet) add(value string) {
	s.Lock()
	defer s.Unlock()
	s.m[value] = struct{}{}
}

func (s *mapSet) has(value string) bool {
	s.RLock()
	defer s.RUnlock()
	_, ok := s.m[value]
	return ok
}

func (s *mapSet) del(value string) {
	s.Lock()
	defer s.Unlock()
	delete(s.m, value)
}

type btreeSet struct {
	sync.RWMutex
	*btree.Btree
}

func newBtreeSet() *btreeSet {
	return &btreeSet{
		Btree: btree.NewBtree(),
	}
}

func (s *btreeSet) add(value string) {
	s.Lock()
	defer s.Unlock()
	s.Btree.Insert([]byte(value), []byte{})
}

func (s *btreeSet) has(value string) bool {
	s.RLock()
	defer s.RUnlock()
	_, err := s.Btree.Search([]byte(value))
	return err == nil
}

func (s *btreeSet) del(value string) {
	s.Lock()
	defer s.Unlock()
	s.Btree.Delete([]byte(value))
}

type llrbSet struct {
	sync.RWMutex
	*llrb.LLRB
}

type llrbString string

func (s llrbString) Less(than llrb.Item) bool {
	return bytes.Compare([]byte(s), []byte(than.(llrbString))) < 0
}

func newLLRBSet() *llrbSet {
	return &llrbSet{
		LLRB: llrb.New(),
	}
}

func (s *llrbSet) add(value string) {
	s.Lock()
	defer s.Unlock()
	s.LLRB.ReplaceOrInsert(llrbString(value))
}

func (s *llrbSet) has(value string) bool {
	s.RLock()
	defer s.RUnlock()
	return s.LLRB.Has(llrbString(value))
}

func (s *llrbSet) del(value string) {
	s.Lock()
	defer s.Unlock()
	s.LLRB.Delete(llrbString(value))
}

type cznicSet struct {
	sync.RWMutex
	*b.Tree
}

func newCznicSet() *cznicSet {
	return &cznicSet{
		Tree: b.TreeNew(func(a, b interface{}) int {
			return bytes.Compare([]byte(a.(string)), []byte(b.(string)))
		}),
	}
}

func (s *cznicSet) add(value string) {
	s.Lock()
	defer s.Unlock()
	s.Tree.Set(value, nil)
}

func (s *cznicSet) has(value string) bool {
	s.RLock()
	defer s.RUnlock()
	_, ok := s.Tree.Get(value)
	return ok
}

func (s *cznicSet) del(value string) {
	s.Lock()
	defer s.Unlock()
	s.Tree.Delete(value)
}

# for n in 100 1000 10000 ; echo n=$n ; for kind in map btree llrb cznic ; echo $kind  ; ./set -n=$n -kind=$kind ; end ; echo ; end
n=100
map
184560
btree
477464
llrb
155488
cznic
141680

n=1000
map
195112
btree
2411720
llrb
281576
cznic
303592

n=10000
map
594616
btree
35363848
llrb
1553624
cznic
1579480