README
¶
gotomic
Non blocking data structures for Go.
Algorithms
The List type is implemented using A Pragmatic Implementation of Non-Blocking Linked-Lists by Timothy L. Harris.
The Hash type is implemented using Split-Ordered Lists: Lock-Free Extensible Hash Tables by Ori Shalev and Nir Shavit with the List type used as backend.
The Transaction type is implemented using OSTM from Concurrent Programming Without Locks by Keir Fraser and Tim Harris with a few tweaks described in https://github.com/zond/gotomic/blob/master/stm.go.
The Treap type uses Transaction to be non blocking and thread safe, and is based (like all other treaps, I guess) on Randomized Search Trees by Cecilia Aragon and Raimund Seidel, but mostly I just used https://github.com/stathat/treap/blob/master/treap.go for reference.
Performance
On my laptop I created benchmarks for a) regular Go map types, b) Go map types protected by sync.RWMutex, c) the gotomic.Hash, d) the gotomic.Treap type and e) the github.com/stathat/treap.Tree type.
The benchmarks for a) and b) can be found at https://github.com/zond/tools/blob/master/tools_test.go#L83, the benchmark for c) at https://github.com/zond/gotomic/blob/master/hash_test.go#L116 and the benchmark for d) and e) at https://github.com/zond/gotomic/blob/master/hash_test.go#L262.
The TL;DR of it all is that the benchmark sets runtime.GOMAXPROCS to be runtime.NumCPU(), and starts that number of goroutines that just mutates and reads the tested mapping.
Last time I ran these tests I got the following results:
a)
BenchmarkNativeMap 5000000 567 ns/op
b)
BenchmarkMyMapConc 200000 10694 ns/op
BenchmarkMyMap 1000000 1427 ns/op
c)
BenchmarkHash 500000 5146 ns/op
BenchmarkHashConc 500000 10599 ns/op
d)
BenchmarkTreap 50000 71250 ns/op
BenchmarkTreapConc 10000 110843 ns/op
e)
BenchmarkStatHatTreap 1000000 4373 ns/op
Also, there are some third party benchmarks available at https://github.com/zond/gotomic/wiki/Benchmarks.
Conclusion: As expected a) is by far the fastest mapping, and it seems that the naive RWMutex wrapped native map b) is much faster at single thread operation, and on a weak laptop about as efficient in multi thread operation, compared to c).
However, on more multicored systems (and also a few smaller ones, strangely enough) c) is more efficient than b).
When it comes to the treap class, I am afraid my implementation of STM is really REALLY inefficient. Maybe because I tried to be clever, or because I just botched it someplace. It seems to work, but I reckon that an RWMutex-wrapped stathat treap would be preferable in most circumstances.
Usage
See https://github.com/zond/gotomic/blob/master/examples/example.go or https://github.com/zond/gotomic/blob/master/examples/profile.go
Also, see the tests.
Documentation
http://go.pkgdoc.org/github.com/zond/gotomic
Bugs
Hash and List have no known bugs and seem to work well.
The Transaction, Handle and Treap types are alpha. They seem to work, but are too slow and untrustworthy :/
I have not tried it on more than my personal laptop however, so if you want to try and force it to misbehave on a heftier machine than a 4 cpu MacBook Air please do!
Improvements
It would be nice to have a Hash#DeleteIfPresent that atomically deletes matching key/value pairs, but since the implementation is slightly harder than trivial and I see no immediate use case I have been too lazy. Tell me if you need it and I might feel motivated :)
Documentation
¶
Index ¶
- type Clonable
- type Comparable
- type Equalable
- type Handle
- type Hash
- func (self *Hash) Delete(k Hashable) (Thing, bool)
- func (self *Hash) DeleteHC(hashCode uint32, k Hashable) (rval Thing, ok bool)
- func (self *Hash) Describe() string
- func (self *Hash) Each(i HashIterator) bool
- func (self *Hash) Get(k Hashable) (Thing, bool)
- func (self *Hash) GetHC(hashCode uint32, k Hashable) (rval Thing, ok bool)
- func (self *Hash) Put(k Hashable, v Thing) (rval Thing, ok bool)
- func (self *Hash) PutHC(hashCode uint32, k Hashable, v Thing) (rval Thing, ok bool)
- func (self *Hash) PutIfMissing(k Hashable, v Thing) (rval bool)
- func (self *Hash) PutIfPresent(k Hashable, v Thing, expected Equalable) (rval bool)
- func (self *Hash) Size() int
- func (self *Hash) String() string
- func (self *Hash) ToMap() map[Hashable]Thing
- func (self *Hash) Verify() error
- type HashIterator
- type Hashable
- type IntKey
- type List
- func (self List) Describe() string
- func (self *List) Each(i ListIterator) bool
- func (self *List) Inject(c Comparable)
- func (self *List) Pop() (rval Thing, ok bool)
- func (self *List) Push(t Thing)
- func (self *List) Search(c Comparable) Thing
- func (self *List) Size() int
- func (self *List) String() string
- func (self *List) ToSlice() []Thing
- type ListIterator
- type StringKey
- type Thing
- type Transaction
- type Treap
- func (treap *Treap) Delete(k Comparable) (old Thing, ok bool)
- func (treap *Treap) Describe() string
- func (treap *Treap) Each(iter TreapIterator) (err error)
- func (treap *Treap) Get(k Comparable) (v Thing, ok bool)
- func (treap *Treap) Max() (k Comparable, v Thing, ok bool)
- func (treap *Treap) Min() (k Comparable, v Thing, ok bool)
- func (treap *Treap) Next(k Comparable) (key Comparable, value Thing, ok bool)
- func (treap *Treap) Previous(k Comparable) (key Comparable, value Thing, ok bool)
- func (treap *Treap) Put(k Comparable, v Thing) (old Thing, ok bool)
- func (treap *Treap) ToSlice() (keys []Comparable, values []Thing)
- type TreapIterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Clonable ¶
type Clonable interface {
Clone() Clonable
}
Clonable types can be handled by the transaction layer.
type Comparable ¶
Comparable types can be kept sorted in a List.
type Handle ¶
Handle wraps any type of data that is supposed to be handled by the transaction layer.
type Hash ¶
type Hash struct {
// contains filtered or unexported fields
}
Hash is a hash table based on "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Ori Shalev and Nir Shavit <http://www.cs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/SplitOrderedLists.pdf>.
TL;DR: It creates a linked list containing all hashed entries, and an extensible table of 'shortcuts' into said list. To enable future extensions to the shortcut table, the list is ordered in reversed bit order so that new table entries point into finer and finer sections of the potential address space.
To enable growing the table a two dimensional slice of unsafe.Pointers is used, where each consecutive slice is twice the size of the one before. This makes it simple to allocate exponentially more memory for the table with only a single extra indirection.
func (*Hash) DeleteHC ¶
DeleteHC removes the key with hashCode that equals k and returns any value it removed.
Use this when you already have the hash code and don't want to force gotomic to calculate it again.
func (*Hash) Describe ¶
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) GetHC ¶
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 ¶
Put k and v in the Hash and return the overwritten value and whether any value was overwritten.
func (*Hash) PutHC ¶
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 ¶
PutIfMissing will insert v under k if k was missing from the Hash, and return whether it inserted anything.
func (*Hash) PutIfPresent ¶
PutIfMissing will insert v under k if k contains expected in the Hash, and return whether it inserted anything.
type HashIterator ¶
type List ¶
type List struct {
// contains filtered or unexported fields
}
List is a singly linked list based on "A Pragmatic Implementation of Non-Blocking Linked-Lists" by Timothy L. Harris <http://www.timharris.co.uk/papers/2001-disc.pdf>
It is thread safe and non-blocking, and supports ordered elements by using List#inject with values implementing Comparable.
func (*List) Each ¶
func (self *List) Each(i ListIterator) bool
Each will run i on each element.
It returns true if the iteration was interrupted. This is the case when one of the ListIterator calls returned true, indicating the iteration should be stopped.
func (*List) Inject ¶
func (self *List) Inject(c Comparable)
Inject c into the List at the first place where it is <= to all elements before it.
func (*List) Search ¶
func (self *List) Search(c Comparable) Thing
Search return the first element in the list that matches c (c.Compare(element) == 0)
type ListIterator ¶
type Transaction ¶
type Transaction struct {
// contains filtered or unexported fields
}
Transaction is based on "Concurrent Programming Without Locks" by Keir Fraser and Tim Harris <http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf>
It has a few tweaks that I don't believe break it (but I haven't even tried proving it):
1) It has an ever increasing counter for the last transaction to commit.
It uses this counter to fail transactions fast when they try to read a value that another transaction has changed since the first transaction began.
2) It copies the data not only on write opening, but also on read opening.
These changes will make the transactions act more along the lines of "Sandboxing Transactional Memory" by Luke Dalessandro and Michael L. Scott <http://www.cs.rochester.edu/u/scott/papers/2012_TRANSACT_sandboxing.pdf> and will hopefully avoid the need to kill transactions exhibiting invalid behaviour due to inconsistent states.
func NewTransaction ¶
func NewTransaction() *Transaction
func (*Transaction) Abort ¶
func (self *Transaction) Abort()
Abort the transaction unless it is already successful.
Safe to call multiple times.
Unless the transaction is half-committed Abort isn't really necessary, the gc will clean it up properly.
func (*Transaction) Commit ¶
func (self *Transaction) Commit() bool
Commit the transaction. Will return whether the commit was successful or not.
Safe to call multiple times, but only from one thread.
func (*Transaction) Describe ¶
func (self *Transaction) Describe() string
func (*Transaction) Read ¶
func (self *Transaction) Read(h *Handle) (rval Clonable, err error)
Read will return a version of the data in h that is guaranteed to not have been changed since this Transaction started.
Any changes made to the return value will *not* be saved when the Transaction commits.
If another Transaction changes the data in h before this Transaction commits the commit will fail.
func (*Transaction) Write ¶
func (self *Transaction) Write(h *Handle) (rval Clonable, err error)
Write will return a version of the data in h that is guaranteed to not have been changed since this Transaction started.
All changes made to the return value *will* be saved when the Transaction commits.
If another Transaction changes the data in h before this Transaction commits the commit will fail.
type Treap ¶
type Treap struct {
// contains filtered or unexported fields
}
Non-transaction controlled "user space" type
func (*Treap) Each ¶
func (treap *Treap) Each(iter TreapIterator) (err error)
func (*Treap) Next ¶
func (treap *Treap) Next(k Comparable) (key Comparable, value Thing, ok bool)
func (*Treap) Previous ¶
func (treap *Treap) Previous(k Comparable) (key Comparable, value Thing, ok bool)
func (*Treap) ToSlice ¶
func (treap *Treap) ToSlice() (keys []Comparable, values []Thing)
type TreapIterator ¶
type TreapIterator func(k Comparable, v Thing)
Source Files
Directories