README
¶
Introduction
From v0.12.0, the skipset requires Go version >= 1.18, if your Go version is lower, use v0.11.0 instead.
skipset is a high-performance, scalable, concurrent-safe set based on skip-list. In the typical pattern(100000 operations, 90%CONTAINS 9%ADD 1%REMOVE, 8C16T), the skipset up to 15x faster than the built-in sync.Map.
The main idea behind the skipset is A Simple Optimistic Skiplist Algorithm.
Different from the sync.Map, the items in the skipset are always sorted, and the Contains and Range operations are wait-free (A goroutine is guaranteed to complete an operation as long as it keeps taking steps, regardless of the activity of other goroutines).
The skipset is a set instead of a map, if you need a high-performance full replacement of sync.Map, see skipmap.
Features
- Scalable, high-performance, concurrent-safe.
- Wait-free Contains and Range operations (wait-free algorithms have stronger guarantees than lock-free).
- Sorted items.
When should you use skipset
In most cases, skipset is better than sync.Map, especially in these situations:
- Concurrent calls multiple operations. Such as use both
RangeandAddat the same time, in this situation, use skipset can obtain very large improvement on performance. - Memory intensive. The skipset save at least 50% memory in the benchmark.
If only one goroutine access the set for the most of the time, such as insert a batch of elements and then use only Contains or Range, use built-in map is better.
QuickStart
See Go doc for more information.
package main
import (
"fmt"
"github.com/zhangyunhao116/skipset"
)
func main() {
l := skipset.NewInt()
for _, v := range []int{10, 12, 15} {
if l.Add(v) {
fmt.Println("skipset add", v)
}
}
if l.Contains(10) {
fmt.Println("skipset contains 10")
}
l.Range(func(value int) bool {
fmt.Println("skipset range found ", value)
return true
})
l.Remove(15)
fmt.Printf("skipset contains %d items\r\n", l.Len())
}
From v0.12.0, you can use generic version APIs.
Note that generic APIs are always slower than typed APIs, but are more suitable for some scenarios such as functional programming.
e.g.
New[int]is ~2x slower thanNewInt, andNewFunc(func(a, b int) bool { return a < b })is 1~2x slower thanNew[int].Performance ranking: NewInt > New[Int] > NewFunc(func(a, b int) bool { return a < b })
package main
import (
"math"
"github.com/zhangyunhao116/skipset"
)
func main() {
x1 := skipset.New[int]()
for _, v := range []int{2, 1, 3} {
x1.Add(v)
}
x1.Range(func(value int) bool {
println(value)
return true
})
x2 := skipset.NewFunc(func(a, b float64) bool {
return a < b || (math.IsNaN(a) && !math.IsNaN(b))
})
for _, v := range []float64{math.NaN(), 3, 1, math.NaN(), 2} {
x2.Add(v)
}
x2.Range(func(value float64) bool {
println(value)
return true
})
}
Benchmark
based on typed APIs.
Go version: go1.16.2 linux/amd64
CPU: AMD 3700x(8C16T), running at 3.6GHz
OS: ubuntu 18.04
MEMORY: 16G x 2 (3200MHz)
name time/op
Int64/Add/skipset-16 86.6ns ±11%
Int64/Add/sync.Map-16 674ns ± 6%
Int64/Contains50Hits/skipset-16 9.85ns ±12%
Int64/Contains50Hits/sync.Map-16 14.7ns ±30%
Int64/30Add70Contains/skipset-16 38.8ns ±18%
Int64/30Add70Contains/sync.Map-16 586ns ± 5%
Int64/1Remove9Add90Contains/skipset-16 24.9ns ±17%
Int64/1Remove9Add90Contains/sync.Map-16 493ns ± 5%
Int64/1Range9Remove90Add900Contains/skipset-16 25.9ns ±16%
Int64/1Range9Remove90Add900Contains/sync.Map-16 1.00µs ±12%
String/Add/skipset-16 130ns ±14%
String/Add/sync.Map-16 878ns ± 4%
String/Contains50Hits/skipset-16 18.3ns ± 9%
String/Contains50Hits/sync.Map-16 19.2ns ±18%
String/30Add70Contains/skipset-16 61.0ns ±15%
String/30Add70Contains/sync.Map-16 756ns ± 7%
String/1Remove9Add90Contains/skipset-16 31.3ns ±13%
String/1Remove9Add90Contains/sync.Map-16 614ns ± 6%
String/1Range9Remove90Add900Contains/skipset-16 36.2ns ±18%
String/1Range9Remove90Add900Contains/sync.Map-16 1.20µs ±17%
name alloc/op
Int64/Add/skipset-16 65.0B ± 0%
Int64/Add/sync.Map-16 128B ± 1%
Int64/Contains50Hits/skipset-16 0.00B
Int64/Contains50Hits/sync.Map-16 0.00B
Int64/30Add70Contains/skipset-16 19.0B ± 0%
Int64/30Add70Contains/sync.Map-16 77.7B ±16%
Int64/1Remove9Add90Contains/skipset-16 5.00B ± 0%
Int64/1Remove9Add90Contains/sync.Map-16 57.5B ± 4%
Int64/1Range9Remove90Add900Contains/skipset-16 5.00B ± 0%
Int64/1Range9Remove90Add900Contains/sync.Map-16 255B ±22%
String/Add/skipset-16 97.0B ± 0%
String/Add/sync.Map-16 152B ± 0%
String/Contains50Hits/skipset-16 15.0B ± 0%
String/Contains50Hits/sync.Map-16 15.0B ± 0%
String/30Add70Contains/skipset-16 40.0B ± 0%
String/30Add70Contains/sync.Map-16 98.2B ±11%
String/1Remove9Add90Contains/skipset-16 23.0B ± 0%
String/1Remove9Add90Contains/sync.Map-16 73.9B ± 4%
String/1Range9Remove90Add900Contains/skipset-16 23.0B ± 0%
String/1Range9Remove90Add900Contains/sync.Map-16 261B ±18%
name allocs/op
Int64/Add/skipset-16 1.00 ± 0%
Int64/Add/sync.Map-16 4.00 ± 0%
Int64/Contains50Hits/skipset-16 0.00
Int64/Contains50Hits/sync.Map-16 0.00
Int64/30Add70Contains/skipset-16 0.00
Int64/30Add70Contains/sync.Map-16 1.00 ± 0%
Int64/1Remove9Add90Contains/skipset-16 0.00
Int64/1Remove9Add90Contains/sync.Map-16 0.00
Int64/1Range9Remove90Add900Contains/skipset-16 0.00
Int64/1Range9Remove90Add900Contains/sync.Map-16 0.00
String/Add/skipset-16 2.00 ± 0%
String/Add/sync.Map-16 5.00 ± 0%
String/Contains50Hits/skipset-16 1.00 ± 0%
String/Contains50Hits/sync.Map-16 1.00 ± 0%
String/30Add70Contains/skipset-16 1.00 ± 0%
String/30Add70Contains/sync.Map-16 2.00 ± 0%
String/1Remove9Add90Contains/skipset-16 1.00 ± 0%
String/1Remove9Add90Contains/sync.Map-16 1.00 ± 0%
String/1Range9Remove90Add900Contains/skipset-16 1.00 ± 0%
String/1Range9Remove90Add900Contains/sync.Map-16 1.00 ± 0%
Documentation
¶
Overview ¶
Package skipset is a high-performance, scalable, concurrent-safe set based on skip-list. In the typical pattern(100000 operations, 90%CONTAINS 9%Add 1%Remove, 8C16T), the skipset up to 15x faster than the built-in sync.Map.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type FuncSet ¶ added in v0.12.0
type FuncSet[T any] struct { // contains filtered or unexported fields }
FuncSet represents a set based on skip list.
func NewFloat32 ¶
NewFloat32 returns an empty skip set in ascending order.
func NewFloat32Desc ¶ added in v0.9.0
NewFloat32Desc returns an empty skip set in descending order.
func NewFloat64 ¶
NewFloat64 returns an empty skip set in ascending order.
func NewFloat64Desc ¶ added in v0.9.0
NewFloat64Desc returns an empty skip set in descending order.
func NewFunc ¶ added in v0.12.0
NewFunc returns an empty skip set in ascending order.
Note that the less function requires a strict weak ordering, see https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings, or undefined behavior will happen.
func (*FuncSet[T]) Add ¶ added in v0.12.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type Int32Set ¶
type Int32Set struct {
// contains filtered or unexported fields
}
Int32Set represents a set based on skip list.
func (*Int32Set) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type Int32SetDesc ¶ added in v0.9.0
type Int32SetDesc struct {
// contains filtered or unexported fields
}
Int32SetDesc represents a set based on skip list.
func NewInt32Desc ¶ added in v0.9.0
func NewInt32Desc() *Int32SetDesc
NewInt32Desc returns an empty skip set in descending order.
func (*Int32SetDesc) Add ¶ added in v0.9.0
func (s *Int32SetDesc) Add(value int32) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*Int32SetDesc) Contains ¶ added in v0.9.0
func (s *Int32SetDesc) Contains(value int32) bool
Contains checks if the value is in the skip set.
func (*Int32SetDesc) Len ¶ added in v0.9.0
func (s *Int32SetDesc) Len() int
Len returns the length of this skip set.
func (*Int32SetDesc) Range ¶ added in v0.9.0
func (s *Int32SetDesc) Range(f func(value int32) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Int32SetDesc) Remove ¶ added in v0.9.0
func (s *Int32SetDesc) Remove(value int32) bool
Remove removes a node from the skip set.
type Int64Set ¶
type Int64Set struct {
// contains filtered or unexported fields
}
Int64Set represents a set based on skip list.
func (*Int64Set) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type Int64SetDesc ¶ added in v0.9.0
type Int64SetDesc struct {
// contains filtered or unexported fields
}
Int64SetDesc represents a set based on skip list.
func NewInt64Desc ¶ added in v0.9.0
func NewInt64Desc() *Int64SetDesc
NewInt64Desc returns an empty skip set in descending order.
func (*Int64SetDesc) Add ¶ added in v0.9.0
func (s *Int64SetDesc) Add(value int64) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*Int64SetDesc) Contains ¶ added in v0.9.0
func (s *Int64SetDesc) Contains(value int64) bool
Contains checks if the value is in the skip set.
func (*Int64SetDesc) Len ¶ added in v0.9.0
func (s *Int64SetDesc) Len() int
Len returns the length of this skip set.
func (*Int64SetDesc) Range ¶ added in v0.9.0
func (s *Int64SetDesc) Range(f func(value int64) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Int64SetDesc) Remove ¶ added in v0.9.0
func (s *Int64SetDesc) Remove(value int64) bool
Remove removes a node from the skip set.
type IntSet ¶
type IntSet struct {
// contains filtered or unexported fields
}
IntSet represents a set based on skip list.
func (*IntSet) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type IntSetDesc ¶ added in v0.9.0
type IntSetDesc struct {
// contains filtered or unexported fields
}
IntSetDesc represents a set based on skip list.
func NewIntDesc ¶ added in v0.9.0
func NewIntDesc() *IntSetDesc
NewIntDesc returns an empty skip set in descending order.
func (*IntSetDesc) Add ¶ added in v0.9.0
func (s *IntSetDesc) Add(value int) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*IntSetDesc) Contains ¶ added in v0.9.0
func (s *IntSetDesc) Contains(value int) bool
Contains checks if the value is in the skip set.
func (*IntSetDesc) Len ¶ added in v0.9.0
func (s *IntSetDesc) Len() int
Len returns the length of this skip set.
func (*IntSetDesc) Range ¶ added in v0.9.0
func (s *IntSetDesc) Range(f func(value int) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*IntSetDesc) Remove ¶ added in v0.9.0
func (s *IntSetDesc) Remove(value int) bool
Remove removes a node from the skip set.
type OrderedSet ¶ added in v0.12.0
type OrderedSet[T ordered] struct {
// contains filtered or unexported fields
}
OrderedSet represents a set based on skip list.
func New ¶ added in v0.12.0
func New[T ordered]() *OrderedSet[T]
New returns an empty skip set in ascending order.
func (*OrderedSet[T]) Add ¶ added in v0.12.0
func (s *OrderedSet[T]) Add(value T) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*OrderedSet[T]) Contains ¶ added in v0.12.0
func (s *OrderedSet[T]) Contains(value T) bool
Contains checks if the value is in the skip set.
func (*OrderedSet[T]) Len ¶ added in v0.12.0
func (s *OrderedSet[T]) Len() int
Len returns the length of this skip set.
func (*OrderedSet[T]) Range ¶ added in v0.12.0
func (s *OrderedSet[T]) Range(f func(value T) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*OrderedSet[T]) Remove ¶ added in v0.12.0
func (s *OrderedSet[T]) Remove(value T) bool
Remove removes a node from the skip set.
type OrderedSetDesc ¶ added in v0.12.0
type OrderedSetDesc[T ordered] struct {
// contains filtered or unexported fields
}
OrderedSetDesc represents a set based on skip list.
func NewDesc ¶ added in v0.12.0
func NewDesc[T ordered]() *OrderedSetDesc[T]
NewDesc returns an empty skip set in descending order.
func (*OrderedSetDesc[T]) Add ¶ added in v0.12.0
func (s *OrderedSetDesc[T]) Add(value T) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*OrderedSetDesc[T]) Contains ¶ added in v0.12.0
func (s *OrderedSetDesc[T]) Contains(value T) bool
Contains checks if the value is in the skip set.
func (*OrderedSetDesc[T]) Len ¶ added in v0.12.0
func (s *OrderedSetDesc[T]) Len() int
Len returns the length of this skip set.
func (*OrderedSetDesc[T]) Range ¶ added in v0.12.0
func (s *OrderedSetDesc[T]) Range(f func(value T) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*OrderedSetDesc[T]) Remove ¶ added in v0.12.0
func (s *OrderedSetDesc[T]) Remove(value T) bool
Remove removes a node from the skip set.
type StringSet ¶
type StringSet struct {
// contains filtered or unexported fields
}
StringSet represents a set based on skip list.
func NewString ¶
func NewString() *StringSet
NewString returns an empty skip set in ascending order.
func (*StringSet) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type StringSetDesc ¶ added in v0.12.0
type StringSetDesc struct {
// contains filtered or unexported fields
}
StringSetDesc represents a set based on skip list.
func NewStringDesc ¶ added in v0.12.0
func NewStringDesc() *StringSetDesc
NewStringDesc returns an empty skip set in descending order.
func (*StringSetDesc) Add ¶ added in v0.12.0
func (s *StringSetDesc) Add(value string) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*StringSetDesc) Contains ¶ added in v0.12.0
func (s *StringSetDesc) Contains(value string) bool
Contains checks if the value is in the skip set.
func (*StringSetDesc) Len ¶ added in v0.12.0
func (s *StringSetDesc) Len() int
Len returns the length of this skip set.
func (*StringSetDesc) Range ¶ added in v0.12.0
func (s *StringSetDesc) Range(f func(value string) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*StringSetDesc) Remove ¶ added in v0.12.0
func (s *StringSetDesc) Remove(value string) bool
Remove removes a node from the skip set.
type Uint32Set ¶
type Uint32Set struct {
// contains filtered or unexported fields
}
Uint32Set represents a set based on skip list.
func NewUint32 ¶
func NewUint32() *Uint32Set
NewUint32 returns an empty skip set in ascending order.
func (*Uint32Set) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type Uint32SetDesc ¶ added in v0.9.0
type Uint32SetDesc struct {
// contains filtered or unexported fields
}
Uint32SetDesc represents a set based on skip list.
func NewUint32Desc ¶ added in v0.9.0
func NewUint32Desc() *Uint32SetDesc
NewUint32Desc returns an empty skip set in descending order.
func (*Uint32SetDesc) Add ¶ added in v0.9.0
func (s *Uint32SetDesc) Add(value uint32) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*Uint32SetDesc) Contains ¶ added in v0.9.0
func (s *Uint32SetDesc) Contains(value uint32) bool
Contains checks if the value is in the skip set.
func (*Uint32SetDesc) Len ¶ added in v0.9.0
func (s *Uint32SetDesc) Len() int
Len returns the length of this skip set.
func (*Uint32SetDesc) Range ¶ added in v0.9.0
func (s *Uint32SetDesc) Range(f func(value uint32) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Uint32SetDesc) Remove ¶ added in v0.9.0
func (s *Uint32SetDesc) Remove(value uint32) bool
Remove removes a node from the skip set.
type Uint64Set ¶
type Uint64Set struct {
// contains filtered or unexported fields
}
Uint64Set represents a set based on skip list.
func NewUint64 ¶
func NewUint64() *Uint64Set
NewUint64 returns an empty skip set in ascending order.
func (*Uint64Set) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type Uint64SetDesc ¶ added in v0.9.0
type Uint64SetDesc struct {
// contains filtered or unexported fields
}
Uint64SetDesc represents a set based on skip list.
func NewUint64Desc ¶ added in v0.9.0
func NewUint64Desc() *Uint64SetDesc
NewUint64Desc returns an empty skip set in descending order.
func (*Uint64SetDesc) Add ¶ added in v0.9.0
func (s *Uint64SetDesc) Add(value uint64) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*Uint64SetDesc) Contains ¶ added in v0.9.0
func (s *Uint64SetDesc) Contains(value uint64) bool
Contains checks if the value is in the skip set.
func (*Uint64SetDesc) Len ¶ added in v0.9.0
func (s *Uint64SetDesc) Len() int
Len returns the length of this skip set.
func (*Uint64SetDesc) Range ¶ added in v0.9.0
func (s *Uint64SetDesc) Range(f func(value uint64) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Uint64SetDesc) Remove ¶ added in v0.9.0
func (s *Uint64SetDesc) Remove(value uint64) bool
Remove removes a node from the skip set.
type UintSet ¶
type UintSet struct {
// contains filtered or unexported fields
}
UintSet represents a set based on skip list.
func (*UintSet) Add ¶ added in v0.8.0
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
type UintSetDesc ¶ added in v0.9.0
type UintSetDesc struct {
// contains filtered or unexported fields
}
UintSetDesc represents a set based on skip list.
func NewUintDesc ¶ added in v0.9.0
func NewUintDesc() *UintSetDesc
NewUintDesc returns an empty skip set in descending order.
func (*UintSetDesc) Add ¶ added in v0.9.0
func (s *UintSetDesc) Add(value uint) bool
Add adds the value into skip set, returns true if this process insert the value into skip set, returns false if this process can't insert this value, because another process has insert the same value.
If the value is in the skip set but not fully linked, this process will wait until it is.
func (*UintSetDesc) Contains ¶ added in v0.9.0
func (s *UintSetDesc) Contains(value uint) bool
Contains checks if the value is in the skip set.
func (*UintSetDesc) Len ¶ added in v0.9.0
func (s *UintSetDesc) Len() int
Len returns the length of this skip set.
func (*UintSetDesc) Range ¶ added in v0.9.0
func (s *UintSetDesc) Range(f func(value uint) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*UintSetDesc) Remove ¶ added in v0.9.0
func (s *UintSetDesc) Remove(value uint) bool
Remove removes a node from the skip set.
Source Files