README
¶
Introduction
skipset is a high-performance concurrent set based on skip list. In typical pattern(100000 operations, 90%CONTAINS 9%ADD 1%REMOVE), the skipset up to 3x ~ 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).
Features
- Concurrent safe API with high-performance.
- Wait-free Contains and Range operations.
- Sorted items.
When should you use skipset
In these situations, skipset is better
- Sorted elements is needed.
- Concurrent calls multiple operations. such as use both
ContainsandAddat the same time. - Memory intensive. The skipset save at least 50% memory in the benchmark.
In these situations, sync.Map is better
- Only one goroutine access the set for most of the time, such as insert a batch of elements and then use only
Contains(use built-in map is even better).
QuickStart
package main
import (
"fmt"
"github.com/alimy/tryst/collection/skipset"
)
func main() {
l := 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())
}
Benchmark
Go version: go1.16.2 linux/amd64
CPU: AMD 3700x(8C16T), running at 3.6GHz
OS: ubuntu 18.04
MEMORY: 16G x 2 (3200MHz)
$ go test -run=NOTEST -bench=. -benchtime=100000x -benchmem -count=20 -timeout=60m > x.txt
$ benchstat x.txt
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.
Code generated by go run types_gen.go; DO NOT EDIT.
Example ¶
l := 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())
Index ¶
- type Float32Set
- type Float32SetDesc
- type Float64Set
- type Float64SetDesc
- type Int16Set
- type Int16SetDesc
- type Int32Set
- type Int32SetDesc
- type Int64Set
- type Int64SetDesc
- type IntSet
- type IntSetDesc
- type StringSet
- type Uint16Set
- type Uint16SetDesc
- type Uint32Set
- type Uint32SetDesc
- type Uint64Set
- type Uint64SetDesc
- type UintSet
- type UintSetDesc
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Float32Set ¶
type Float32Set struct {
// contains filtered or unexported fields
}
Float32Set represents a set based on skip list in ascending order.
func NewFloat32 ¶
func NewFloat32() *Float32Set
NewFloat32 return an empty float32 skip set in ascending order.
func (*Float32Set) Add ¶
func (s *Float32Set) Add(value float32) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Float32Set) Contains ¶
func (s *Float32Set) Contains(value float32) bool
Contains check if the value is in the skip set.
func (*Float32Set) Range ¶
func (s *Float32Set) Range(f func(value float32) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Float32Set) Remove ¶
func (s *Float32Set) Remove(value float32) bool
Remove a node from the skip set.
type Float32SetDesc ¶
type Float32SetDesc struct {
// contains filtered or unexported fields
}
Float32SetDesc represents a set based on skip list in descending order.
func NewFloat32Desc ¶
func NewFloat32Desc() *Float32SetDesc
NewFloat32Desc return an empty float32 skip set in descending order.
func (*Float32SetDesc) Add ¶
func (s *Float32SetDesc) Add(value float32) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Float32SetDesc) Contains ¶
func (s *Float32SetDesc) Contains(value float32) bool
Contains check if the value is in the skip set.
func (*Float32SetDesc) Len ¶
func (s *Float32SetDesc) Len() int
Len return the length of this skip set.
func (*Float32SetDesc) Range ¶
func (s *Float32SetDesc) Range(f func(value float32) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Float32SetDesc) Remove ¶
func (s *Float32SetDesc) Remove(value float32) bool
Remove a node from the skip set.
type Float64Set ¶
type Float64Set struct {
// contains filtered or unexported fields
}
Float64Set represents a set based on skip list in ascending order.
func NewFloat64 ¶
func NewFloat64() *Float64Set
NewFloat64 return an empty float64 skip set in ascending order.
func (*Float64Set) Add ¶
func (s *Float64Set) Add(value float64) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Float64Set) Contains ¶
func (s *Float64Set) Contains(value float64) bool
Contains check if the value is in the skip set.
func (*Float64Set) Range ¶
func (s *Float64Set) Range(f func(value float64) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Float64Set) Remove ¶
func (s *Float64Set) Remove(value float64) bool
Remove a node from the skip set.
type Float64SetDesc ¶
type Float64SetDesc struct {
// contains filtered or unexported fields
}
Float64SetDesc represents a set based on skip list in descending order.
func NewFloat64Desc ¶
func NewFloat64Desc() *Float64SetDesc
NewFloat64Desc return an empty float64 skip set in descending order.
func (*Float64SetDesc) Add ¶
func (s *Float64SetDesc) Add(value float64) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Float64SetDesc) Contains ¶
func (s *Float64SetDesc) Contains(value float64) bool
Contains check if the value is in the skip set.
func (*Float64SetDesc) Len ¶
func (s *Float64SetDesc) Len() int
Len return the length of this skip set.
func (*Float64SetDesc) Range ¶
func (s *Float64SetDesc) Range(f func(value float64) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Float64SetDesc) Remove ¶
func (s *Float64SetDesc) Remove(value float64) bool
Remove a node from the skip set.
type Int16Set ¶
type Int16Set struct {
// contains filtered or unexported fields
}
Int16Set represents a set based on skip list in ascending order.
func NewInt16 ¶
func NewInt16() *Int16Set
NewInt16 return an empty int16 skip set in ascending order.
func (*Int16Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 Int16SetDesc ¶
type Int16SetDesc struct {
// contains filtered or unexported fields
}
Int16SetDesc represents a set based on skip list in descending order.
func NewInt16Desc ¶
func NewInt16Desc() *Int16SetDesc
NewInt16Desc return an empty int16 skip set in descending order.
func (*Int16SetDesc) Add ¶
func (s *Int16SetDesc) Add(value int16) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Int16SetDesc) Contains ¶
func (s *Int16SetDesc) Contains(value int16) bool
Contains check if the value is in the skip set.
func (*Int16SetDesc) Range ¶
func (s *Int16SetDesc) Range(f func(value int16) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Int16SetDesc) Remove ¶
func (s *Int16SetDesc) Remove(value int16) bool
Remove a node from the skip set.
type Int32Set ¶
type Int32Set struct {
// contains filtered or unexported fields
}
Int32Set represents a set based on skip list in ascending order.
func NewInt32 ¶
func NewInt32() *Int32Set
NewInt32 return an empty int32 skip set in ascending order.
func (*Int32Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type Int32SetDesc struct {
// contains filtered or unexported fields
}
Int32SetDesc represents a set based on skip list in descending order.
func NewInt32Desc ¶
func NewInt32Desc() *Int32SetDesc
NewInt32Desc return an empty int32 skip set in descending order.
func (*Int32SetDesc) Add ¶
func (s *Int32SetDesc) Add(value int32) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *Int32SetDesc) Contains(value int32) bool
Contains check if the value is in the skip set.
func (*Int32SetDesc) Range ¶
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 ¶
func (s *Int32SetDesc) Remove(value int32) bool
Remove a node from the skip set.
type Int64Set ¶
type Int64Set struct {
// contains filtered or unexported fields
}
Int64Set represents a set based on skip list in ascending order.
func NewInt64 ¶
func NewInt64() *Int64Set
NewInt64 return an empty int64 skip set in ascending order.
func (*Int64Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type Int64SetDesc struct {
// contains filtered or unexported fields
}
Int64SetDesc represents a set based on skip list in descending order.
func NewInt64Desc ¶
func NewInt64Desc() *Int64SetDesc
NewInt64Desc return an empty int64 skip set in descending order.
func (*Int64SetDesc) Add ¶
func (s *Int64SetDesc) Add(value int64) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *Int64SetDesc) Contains(value int64) bool
Contains check if the value is in the skip set.
func (*Int64SetDesc) Range ¶
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 ¶
func (s *Int64SetDesc) Remove(value int64) bool
Remove a node from the skip set.
type IntSet ¶
type IntSet struct {
// contains filtered or unexported fields
}
IntSet represents a set based on skip list in ascending order.
func (*IntSet) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type IntSetDesc struct {
// contains filtered or unexported fields
}
IntSetDesc represents a set based on skip list in descending order.
func NewIntDesc ¶
func NewIntDesc() *IntSetDesc
NewIntDesc return an empty int skip set in descending order.
func (*IntSetDesc) Add ¶
func (s *IntSetDesc) Add(value int) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *IntSetDesc) Contains(value int) bool
Contains check if the value is in the skip set.
func (*IntSetDesc) Range ¶
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 ¶
func (s *IntSetDesc) Remove(value int) bool
Remove 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 (*StringSet) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 Uint16Set ¶
type Uint16Set struct {
// contains filtered or unexported fields
}
Uint16Set represents a set based on skip list in ascending order.
func NewUint16 ¶
func NewUint16() *Uint16Set
NewUint16 return an empty uint16 skip set in ascending order.
func (*Uint16Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 Uint16SetDesc ¶
type Uint16SetDesc struct {
// contains filtered or unexported fields
}
Uint16SetDesc represents a set based on skip list in descending order.
func NewUint16Desc ¶
func NewUint16Desc() *Uint16SetDesc
NewUint16Desc return an empty uint16 skip set in descending order.
func (*Uint16SetDesc) Add ¶
func (s *Uint16SetDesc) Add(value uint16) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 (*Uint16SetDesc) Contains ¶
func (s *Uint16SetDesc) Contains(value uint16) bool
Contains check if the value is in the skip set.
func (*Uint16SetDesc) Len ¶
func (s *Uint16SetDesc) Len() int
Len return the length of this skip set.
func (*Uint16SetDesc) Range ¶
func (s *Uint16SetDesc) Range(f func(value uint16) bool)
Range calls f sequentially for each value present in the skip set. If f returns false, range stops the iteration.
func (*Uint16SetDesc) Remove ¶
func (s *Uint16SetDesc) Remove(value uint16) bool
Remove a node from the skip set.
type Uint32Set ¶
type Uint32Set struct {
// contains filtered or unexported fields
}
Uint32Set represents a set based on skip list in ascending order.
func NewUint32 ¶
func NewUint32() *Uint32Set
NewUint32 return an empty uint32 skip set in ascending order.
func (*Uint32Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type Uint32SetDesc struct {
// contains filtered or unexported fields
}
Uint32SetDesc represents a set based on skip list in descending order.
func NewUint32Desc ¶
func NewUint32Desc() *Uint32SetDesc
NewUint32Desc return an empty uint32 skip set in descending order.
func (*Uint32SetDesc) Add ¶
func (s *Uint32SetDesc) Add(value uint32) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *Uint32SetDesc) Contains(value uint32) bool
Contains check if the value is in the skip set.
func (*Uint32SetDesc) Len ¶
func (s *Uint32SetDesc) Len() int
Len return the length of this skip set.
func (*Uint32SetDesc) Range ¶
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 ¶
func (s *Uint32SetDesc) Remove(value uint32) bool
Remove a node from the skip set.
type Uint64Set ¶
type Uint64Set struct {
// contains filtered or unexported fields
}
Uint64Set represents a set based on skip list in ascending order.
func NewUint64 ¶
func NewUint64() *Uint64Set
NewUint64 return an empty uint64 skip set in ascending order.
func (*Uint64Set) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type Uint64SetDesc struct {
// contains filtered or unexported fields
}
Uint64SetDesc represents a set based on skip list in descending order.
func NewUint64Desc ¶
func NewUint64Desc() *Uint64SetDesc
NewUint64Desc return an empty uint64 skip set in descending order.
func (*Uint64SetDesc) Add ¶
func (s *Uint64SetDesc) Add(value uint64) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *Uint64SetDesc) Contains(value uint64) bool
Contains check if the value is in the skip set.
func (*Uint64SetDesc) Len ¶
func (s *Uint64SetDesc) Len() int
Len return the length of this skip set.
func (*Uint64SetDesc) Range ¶
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 ¶
func (s *Uint64SetDesc) Remove(value uint64) bool
Remove a node from the skip set.
type UintSet ¶
type UintSet struct {
// contains filtered or unexported fields
}
UintSet represents a set based on skip list in ascending order.
func (*UintSet) Add ¶
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
type UintSetDesc struct {
// contains filtered or unexported fields
}
UintSetDesc represents a set based on skip list in descending order.
func NewUintDesc ¶
func NewUintDesc() *UintSetDesc
NewUintDesc return an empty uint skip set in descending order.
func (*UintSetDesc) Add ¶
func (s *UintSetDesc) Add(value uint) bool
Add add the value into skip set, return true if this process insert the value into skip set, return 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 ¶
func (s *UintSetDesc) Contains(value uint) bool
Contains check if the value is in the skip set.
func (*UintSetDesc) Range ¶
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 ¶
func (s *UintSetDesc) Remove(value uint) bool
Remove a node from the skip set.
Source Files