synx

README

Synx

Synx is enhanced version of standard sync package.

Spinlock

TODO

Once

$ go version
go version go1.17.1 linux/amd64
$ go test -race -bench=. ./...
goos: linux
goarch: amd64
pkg: github.com/moeryomenko/synx
cpu: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx
BenchmarkOnce-8         	19812547	       61.74 ns/op
BenchmarkCustomOnce-8   	23804229	       50.94 ns/op
PASS
ok  	github.com/moeryomenko/synx	2.571s

Documentation

Index

• Variables
• func JumpConsistentHash(n int64, hashkey uint64) int64
• func MultiProbingHash(key string) [4]uint64
• type Item
• type Map
  • func New(size int) *Map
  • func (m *Map) Del(key string)
  • func (m *Map) Get(key string) (val interface{}, err error)
  • func (m *Map) Reset()
  • func (m *Map) Set(key string, val interface{}) error
  • func (m *Map) SyncDel(key string)
  • func (m *Map) SyncGet(key string) (val interface{}, err error)
  • func (m *Map) SyncSet(key string, val interface{}) error
• type Once
  • func (o *Once) Do(f func())
• type Spinlock
  • func (l *Spinlock) Lock()
  • func (l *Spinlock) TryLock() bool
  • func (l *Spinlock) Unlock()

Variables

var (
	ErrMapFull  = errors.New("map is full")
	ErrNotFound = errors.New("key not found")
)

Functions

func JumpConsistentHash

func JumpConsistentHash(n int64, hashkey uint64) int64

JumpConsistentHash returns index of map entry.

Conceptually, it is a hash algorithm that can be expressed in about 5 lines of code. In comparison to the algorithm of Karger et al., jump consistent hash requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets and of evenly dividing the workload when the number of buckets changes.

Reference:

John Lamping, Eric Veach, 2014, A Fast, Minimal Memory, Consistent Hash Algorithm, Google https://arxiv.org/pdf/1406.2294v1.pdf

func MultiProbingHash

func MultiProbingHash(key string) [4]uint64

MultiProbingHash returns a number of hashes from a given key. It must return at least one hash. Returning more than one allows for performance improvements via multi-probing.

Ben Appleton, Michael O’Reilly, 2015, Multi-probe consistent hashing, Google http://arxiv.org/pdf/1505.00062.pdf

Types

type Item

type Item struct {
	Key string
	Val interface{}

	Distance int // How far item is from its best position.
}

Item represents an entry in the RHMap.

type Map

type Map struct {
	// Items are the slots of the hashmap for items.
	Items []Item

	// Number of keys in the Map.
	Count int
	// contains filtered or unexported fields
}

Map is a hashmap that uses the robinhood algorithm.

A general purpose hash table, using the Robin Hood hashing algorithm.

Conceptually, it is a hash table using linear probing on lookup with a particular displacement strategy on inserts. The central idea of the Robin Hood hashing algorithm is to reduce the variance of the probe sequence length (PSL).

Reference:

Pedro Celis, 1986, Robin Hood Hashing, University of Waterloo https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf

func New

func New(size int) *Map

New returns a new robinhood hashmap.

func (*Map) Del

func (m *Map) Del(key string)

func (*Map) Get

func (m *Map) Get(key string) (val interface{}, err error)

func (*Map) Reset

func (m *Map) Reset()

Reset clears Map, where already allocated memory will be reused.

func (*Map) Set

func (m *Map) Set(key string, val interface{}) error

func (*Map) SyncDel

func (m *Map) SyncDel(key string)

func (*Map) SyncGet

func (m *Map) SyncGet(key string) (val interface{}, err error)

func (*Map) SyncSet

func (m *Map) SyncSet(key string, val interface{}) error

type Once

type Once struct {
	// contains filtered or unexported fields
}

Once is an object that will perform exactly one action.

func (*Once) Do

func (o *Once) Do(f func())

Do calls the function f if and only if Do is being called for the first time for this instance of Once. In other words, given

var once Once

if once.Do(f) is called multiple times, only the first call will invoke f, even if f has a different value in each invocation. A new instance of Once is required for each function to execute.

Do is intended for initialization that must be run exactly once. Since f is niladic, it may be necessary to use a function literal to capture the arguments to a function to be invoked by Do:

config.once.Do(func() { config.init(filename) })

Because no call to Do returns until the one call to f returns, if f causes Do to be called, it will deadlock.

If f panics, Do considers it to have returned; future calls of Do return without calling f.

type Spinlock

type Spinlock struct {
	// contains filtered or unexported fields
}

Spinlock is a spinlock-based implementation of lock.

func (*Spinlock) Lock

func (l *Spinlock) Lock()

Lock waits until the locker with be released (if it is not) and then acquire it.

func (*Spinlock) TryLock

func (l *Spinlock) TryLock() bool

TryLock performs a non-blocking attempt to acquire the locker and returns true if successful.

func (*Spinlock) Unlock

func (l *Spinlock) Unlock()

Unlock relases the locker.