gotomic

README

Non blocking hash table for Go, designed to have read performance close to that of go's native map, but without requiring a RWMutex. This should perform better if you have a lot of cores. Copied from http://github.com/zond/gotomic, with a few changes:

• Remove interfaces; strong typing for keys and hash table entries means fewer memory allocations
• Thread-local datastructures that are reused instead of allocating temporary datastructures per request
• Tests are in flux and probably broken

Results

Note: garbage collection is turned off. 16 byte keys and interface values (integers). 2^20 keys.

Look here for the benchmarking code: http://github.com/narula/gomap-bench

BenchmarkGoMapReadConcurrentNoLock-80   300000000                5.07 ns/op
BenchmarkGoMapReadConcurrentLocked-80   10000000               573 ns/op
BenchmarkZgotomicReadConcurrent-80      20000000               119 ns/op
BenchmarkGotomicReadConcurrent-80       100000000               23.8 ns/op

Documentation

Index

• func ReusableEntry() *entry
• func ReusableHashHit() *hashHit
• func ReusableHit() *hit
• type Bucket
• type Equalable
• type Hash
  • func NewHash() *Hash
  • func (self *Hash) Describe() string
  • func (self *Hash) Each(i HashIterator) bool
  • func (self *Hash) Get(k Key) (unsafe.Pointer, bool)
  • func (self *Hash) GetHC(hashCode uint32, k Key, ld *LocalData) (rval unsafe.Pointer, ok bool)
  • func (self *Hash) Put(k Key, v unsafe.Pointer) (rval unsafe.Pointer, ok bool)
  • func (self *Hash) PutHC(hashCode uint32, k Key, v unsafe.Pointer) (rval unsafe.Pointer, ok bool)
  • func (self *Hash) PutIfMissing(k Key, v unsafe.Pointer) (rval bool)
  • func (self *Hash) PutIfPresent(k Key, v unsafe.Pointer, expected Equalable) (rval bool)
  • func (self *Hash) Size() int
  • func (self *Hash) String() string
  • func (self *Hash) ToMap() map[Key]Thing
• type HashIterator
• type Key
  • func MakeKey(x uint64) Key
  • func (k Key) Equals(sk Key) bool
  • func (k Key) HashCode() uint32
• type ListIterator
• type LocalData
  • func InitLocalData() *LocalData
• type Thing

Functions

func ReusableEntry

func ReusableEntry() *entry

func ReusableHashHit

func ReusableHashHit() *hashHit

func ReusableHit

func ReusableHit() *hit

Types

type Bucket

type Bucket struct {
	// contains filtered or unexported fields
}

type Equalable

type Equalable interface {
	Equals(Thing) bool
}

type Hash

type Hash struct {
	// contains filtered or unexported fields
}

func NewHash

func NewHash() *Hash

func (*Hash) Describe

func (self *Hash) Describe() string

Describe returns a multi line description of the contents of the map for those of you interested in debugging it or seeing an example of how split-ordered lists work.

func (*Hash) Each

func (self *Hash) Each(i HashIterator) bool

Each will run i on each key and value.

It returns true if the iteration was interrupted. This is the case when one of the HashIterator calls returned true, indicating the iteration should be stopped.

func (*Hash) Get

func (self *Hash) Get(k Key) (unsafe.Pointer, bool)

Get returns the value at k and whether it was present in the Hash.

func (*Hash) GetHC

func (self *Hash) GetHC(hashCode uint32, k Key, ld *LocalData) (rval unsafe.Pointer, ok bool)

GetHC returns the key with hashCode that equals k. Use this when you already have the hash code and don't want to force gotomic to calculate it again.

func (*Hash) Put

func (self *Hash) Put(k Key, v unsafe.Pointer) (rval unsafe.Pointer, ok bool)

Put k and v in the Hash and return the overwritten value and whether any value was overwritten.

func (*Hash) PutHC

func (self *Hash) PutHC(hashCode uint32, k Key, v unsafe.Pointer) (rval unsafe.Pointer, ok bool)

PutHC will put k and v in the Hash using hashCode and return the overwritten value and whether any value was overwritten. Use this when you already have the hash code and don't want to force gotomic to calculate it again.

func (*Hash) PutIfMissing

func (self *Hash) PutIfMissing(k Key, v unsafe.Pointer) (rval bool)

PutIfMissing will insert v under k if k was missing from the Hash, and return whether it inserted anything.

func (*Hash) PutIfPresent

func (self *Hash) PutIfPresent(k Key, v unsafe.Pointer, expected Equalable) (rval bool)

PutIfMissing will insert v under k if k contains expected in the Hash, and return whether it inserted anything.

func (*Hash) Size

func (self *Hash) Size() int

func (*Hash) String

func (self *Hash) String() string

func (*Hash) ToMap

func (self *Hash) ToMap() map[Key]Thing

ToMap returns a map[Hashable]Thing that is logically identical to the Hash.

type HashIterator

type HashIterator func(k Key, v unsafe.Pointer) bool

type Key

type Key [16]byte

Convenience type for generic byte keys

func MakeKey

func MakeKey(x uint64) Key

func (Key) Equals

func (k Key) Equals(sk Key) bool

func (Key) HashCode

func (k Key) HashCode() uint32

type ListIterator

type ListIterator func(e entry) bool

type LocalData

type LocalData struct {
	// contains filtered or unexported fields
}

func InitLocalData

func InitLocalData() *LocalData

type Thing

type Thing interface{}