A set implementation based on lockfree skiplist.
- The complexity of all operations included Add, Remove, Contains are log(n).
- Thread-safe and Lock-free.
- Support Multi-producer and Multi-consumer.
go test bench=. -args -n=1000000
n represents the amount of data.
goos: darwin
goarch: amd64
pkg: LockFreeSkipList
BenchmarkRandomAdd-8 1 2025239990 ns/op
BenchmarkRandomRemove-8 1 2042296246 ns/op
BenchmarkRandomAddAndRemoveAndContains-8 1 1308625407 ns/op
PASS
ok LockFreeSkipList 7.319s
The above data was tested on my 2013 macbook-pro with Intel Core i7 4 cores 2.3 GHz.
See benchmark.
func NewLockFreeSkipList(comp func(value1 interface{}, value2 interface{}) bool)(sl *LockFreeSkipList)
func (sl *LockFreeSkipList) Add(value interface{})(success bool)
func (sl *LockFreeSkipList) Remove(value interface{})(success bool)
func (sl *LockFreeSkipList) Contains(value interface{})(contains bool)
func (sl *LockFreeSkipList) GetSize(value interface{})(size int32)[1]A Pragmatic Implementation of Non-BlockingLinked-Lists. Timothy L.Harris
[2]M. Herlihy, Y. Lev, and N. Shavit. A lock-free concurrent skiplist with wait-free search. Unpublished Manuscript, Sun Microsystems Laborato- ries, Burlington, Massachusetts, 2007
[3]The Art of Multiprocessor Programming. Maurice Herlihy Nir Shavit