gotomic

package module
v0.0.0-...-c442ca1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 12, 2016 License: BSD-2-Clause-Views Imports: 8 Imported by: 21

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

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 

type Comparable interface {
	Compare(Thing) int
}

Comparable types can be kept sorted in a List.

type Equalable 

type Equalable interface {
	Equals(Thing) bool
}

type Handle 

type Handle struct {
	/*
	 Will point to a version.
	*/
	Pointer unsafe.Pointer
}

Handle wraps any type of data that is supposed to be handled by the transaction layer.

func NewHandle 

func NewHandle(c Clonable) *Handle

NewHandle will wrap a Clonable value to enable its use in the transaction layer.

func (*Handle) Current 

func (self *Handle) Current() Clonable

Current returns the current content of this Handle, disregarding any transactional state.

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 NewHash 

func NewHash() *Hash

func (*Hash) Delete 

func (self *Hash) Delete(k Hashable) (Thing, bool)

Delete removes k from the Hash and returns any value it removed.

func (*Hash) DeleteHC 

func (self *Hash) DeleteHC(hashCode uint32, k Hashable) (rval Thing, ok bool)

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 

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 Hashable) (Thing, 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 Hashable) (rval Thing, 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 Hashable, v Thing) (rval Thing, 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 Hashable, v Thing) (rval Thing, 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 Hashable, v Thing) (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 Hashable, v Thing, 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[Hashable]Thing

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

func (*Hash) Verify 

func (self *Hash) Verify() error

Verify the integrity of the Hash. Used mostly in my own tests but go ahead and call it if you fear corruption.

type HashIterator 

type HashIterator func(k Hashable, v Thing) bool

type Hashable 

type Hashable interface {
	Equalable
	HashCode() uint32
}

Hashable types can be in a Hash.

type IntKey 

type IntKey int

Convenience type to simplify using ints as keys in a Hash

func (IntKey) Equals 

func (self IntKey) Equals(t Thing) bool

func (IntKey) HashCode 

func (self IntKey) HashCode() uint32

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 NewList 

func NewList() *List

func (List) Describe 

func (self List) Describe() string

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

func (self *List) Pop() (rval Thing, ok bool)

Pop removes and returns the top of the List.

func (*List) Push 

func (self *List) Push(t Thing)

Push adds t to the top of the List.

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)

func (*List) Size 

func (self *List) Size() int

func (*List) String 

func (self *List) String() string

func (*List) ToSlice 

func (self *List) ToSlice() []Thing

ToSlice returns a []Thing that is logically identical to the List.

type ListIterator 

type ListIterator func(t Thing) bool

type StringKey 

type StringKey string

Convenience type to simplify using strings as keys in a Hash

func (StringKey) Equals 

func (self StringKey) Equals(t Thing) bool

func (StringKey) HashCode 

func (self StringKey) HashCode() uint32

type Thing 

type Thing interface{}

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 NewTreap 

func NewTreap() *Treap

func (*Treap) Delete 

func (treap *Treap) Delete(k Comparable) (old Thing, ok bool)

func (*Treap) Describe 

func (treap *Treap) Describe() string

func (*Treap) Each 

func (treap *Treap) Each(iter TreapIterator) (err error)

func (*Treap) Get 

func (treap *Treap) Get(k Comparable) (v Thing, ok bool)

func (*Treap) Max 

func (treap *Treap) Max() (k Comparable, v Thing, ok bool)

func (*Treap) Min 

func (treap *Treap) Min() (k Comparable, v Thing, ok bool)

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

func (treap *Treap) Put(k Comparable, v Thing) (old 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

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.