skipmap is a high-performance concurrent sorted map based on skip list. Up to 3x ~ 10x faster than sync.Map in the typical pattern.

Overview

Introduction

skipmap is a high-performance concurrent map based on skip list. In typical pattern(one million operations, 90%LOAD 9%STORE 1%DELETE), the skipmap up to 3x ~ 10x faster than the built-in sync.Map.

The main idea behind the skipmap is A Simple Optimistic Skiplist Algorithm.

Different from the sync.Map, the items in the skipmap are always sorted, and the Load and Range operations are wait-free (A goroutine is guaranteed to complete a operation as long as it keeps taking steps, regardless of the activity of other goroutines).

Features

  • Concurrent safe API with high-performance.
  • Wait-free Load and Range operations.
  • Sorted items.

When should you use skipmap

In these situations, skipmap is better

  • Sorted elements is needed.
  • Concurrent calls multiple operations. such as use both Load and Store at the same time.

In these situations, sync.Map is better

  • Only one goroutine access the map for most of the time, such as insert a batch of elements and then use only Load (use built-in map is even better).

QuickStart

See Go doc for more information.

package main

import (
	"fmt"

	"github.com/zhangyunhao116/skipmap"
)

func main() {
	l := skipmap.NewInt()

	for _, v := range []int{10, 12, 15} {
		l.Store(v, v+100)
	}

	v, ok := l.Load(10)
	if ok {
		fmt.Println("skipmap load 10 with value ", v)
	}

	l.Range(func(key int, value interface{}) bool {
		fmt.Println("skipmap range found ", key, value)
		return true
	})

	l.Delete(15)
	fmt.Printf("skipmap contains %d items\r\n", l.Len())
}

Benchmark

Go version: go1.15.6 linux/amd64

CPU: AMD 3700x(8C16T), running at 3.6GHz

OS: ubuntu 18.04

MEMORY: 16G x 2 (3200MHz)

benchmark

$ go test -run=NOTEST -bench=. -benchtime=100000x -benchmem -count=10 -timeout=60m  > x.txt
$ benchstat x.txt
name                                           time/op
Store/skipmap-16                                267ns ± 5%
Store/sync.Map-16                               675ns ± 6%
Load100Hits/skipmap-16                         15.2ns ± 6%
Load100Hits/sync.Map-16                        16.0ns ±11%
Load50Hits/skipmap-16                          15.6ns ± 7%
Load50Hits/sync.Map-16                         14.2ns ±18%
LoadNoHits/skipmap-16                          16.7ns ±21%
LoadNoHits/sync.Map-16                         13.1ns ±18%
50Store50Load/skipmap-16                        151ns ±38%
50Store50Load/sync.Map-16                       568ns ± 2%
30Store70Load/skipmap-16                       95.2ns ±43%
30Store70Load/sync.Map-16                       584ns ± 4%
1Delete9Store90Load/skipmap-16                 46.0ns ±11%
1Delete9Store90Load/sync.Map-16                 505ns ± 4%
1Range9Delete90Store900Load/skipmap-16         52.5ns ± 8%
1Range9Delete90Store900Load/sync.Map-16        1.15µs ±18%
StringStore/skipmap-16                          321ns ± 7%
StringStore/sync.Map-16                         872ns ± 4%
StringLoad50Hits/skipmap-16                    28.6ns ± 6%
StringLoad50Hits/sync.Map-16                   18.7ns ± 8%
String30Store70Load/skipmap-16                  125ns ± 5%
String30Store70Load/sync.Map-16                 746ns ± 6%
String1Delete9Store90Load/skipmap-16           56.9ns ± 8%
String1Delete9Store90Load/sync.Map-16           619ns ± 3%
String1Range9Delete90Store900Load/skipmap-16   64.8ns ±24%
String1Range9Delete90Store900Load/sync.Map-16  1.46µs ±20%

name                                           alloc/op
Store/skipmap-16                                 107B ± 0%
Store/sync.Map-16                                128B ± 0%
Load100Hits/skipmap-16                          0.00B     
Load100Hits/sync.Map-16                         0.00B     
Load50Hits/skipmap-16                           0.00B     
Load50Hits/sync.Map-16                          0.00B     
LoadNoHits/skipmap-16                           0.00B     
LoadNoHits/sync.Map-16                          0.00B     
50Store50Load/skipmap-16                        53.0B ± 0%
50Store50Load/sync.Map-16                       65.2B ± 1%
30Store70Load/skipmap-16                        32.0B ± 0%
30Store70Load/sync.Map-16                       74.4B ± 3%
1Delete9Store90Load/skipmap-16                  9.00B ± 0%
1Delete9Store90Load/sync.Map-16                 55.4B ± 3%
1Range9Delete90Store900Load/skipmap-16          9.00B ± 0%
1Range9Delete90Store900Load/sync.Map-16          286B ± 9%
StringStore/skipmap-16                           138B ± 0%
StringStore/sync.Map-16                          152B ± 0%
StringLoad50Hits/skipmap-16                     3.00B ± 0%
StringLoad50Hits/sync.Map-16                    3.00B ± 0%
String30Store70Load/skipmap-16                  52.0B ± 0%
String30Store70Load/sync.Map-16                 96.6B ±13%
String1Delete9Store90Load/skipmap-16            26.0B ± 0%
String1Delete9Store90Load/sync.Map-16           72.3B ± 1%
String1Range9Delete90Store900Load/skipmap-16    26.0B ± 0%
String1Range9Delete90Store900Load/sync.Map-16    333B ±23%
Issues
  • panic: unaligned 64-bit atomic operation

    panic: unaligned 64-bit atomic operation

    attempting to use skipmap on an arm build (with GOARM=7, GOARCH=arm, go version 1.17.8) gave such panic:

    panic: unaligned 64-bit atomic operation
    
    goroutine 1 [running]:
    runtime/internal/atomic.panicUnaligned()
            /usr/local/go/src/runtime/internal/atomic/unaligned.go:8 +0x24
    runtime/internal/atomic.Load64(0xd3e9cc)
            /usr/local/go/src/runtime/internal/atomic/atomic_arm.s:286 +0x14
    github.com/zhangyunhao116/skipmap.(*StringMap).randomlevel(0xd3e9c0)
            /home/rachel/go/pkg/mod/github.com/zhangyunhao116/[email protected]/types.go:8919 +0x34
    github.com/zhangyunhao116/skipmap.(*StringMap).LoadOrStoreLazy(0xd3e9c0, {0xd21270, 0xf}, 0x541ca8)
            /home/rachel/go/pkg/mod/github.com/zhangyunhao116/[email protected]/types.go:9081 +0x20
    

    skipmap version is v0.7.0 as i'm on go <1.18

    Perhaps we can add some padding around these fields? or maybe rearrange the fields so they are aligned:

    // StringMap represents a map based on skip list.
    type StringMap struct {
    	header       *stringNode
    	length       int64
    	highestLevel int64 // highest level for now
    }
    

    ... and for the nodes

    opened by zllovesuki 2
  • skipmap: LoadOrStore is racy

    skipmap: LoadOrStore is racy

    func (s *Map) LoadOrStore(key T, value interface{}) (actual interface{}, loaded bool) {
    	loadedval, ok := s.Load(key)
    	if !ok {
    		s.Store(key, value)
    		return value, false
    	}
    	return loadedval, true
    }
    

    With the current implementation for LoadOrStore, any racing Load*'s under the same key may erroneously return different values as every racing caller to Store under the implementation of LoadOrStore may override the value stored under the provided key.

    I'd like to discuss this, though I believe a way to remediate this behavior is to modify (*Map).Store(key, value) to accept a boolean update. If update is true, and a value is found under the given key, the value is overridden and returned directly. If update is false, and a value is found under the given key, the existing value under the key is returned directly.

    All of this logic under the update boolean needs to be atomic as well which I am not 100% sure is possible with the current Store implementation. So if this change is to be made, there may be a need to have the following lines which can be found in the Store implementation below be modified to be an atomic compare-and-swap operation instead:

    nodeFound := s.findNode(key, &preds, &succs)
    if nodeFound != nil { // indicating the key is already in the skip-list
    	if !nodeFound.flags.Get(marked) {
    		// We don't need to care about whether or not the node is fully linked,
    		// just replace the value.
    		nodeFound.storeVal(value)
    		return
    	}
    	// If the node is marked, represents some other goroutines is in the process of deleting this node,
    	// we need to add this node in next loop.
    	continue
    }
    

    With the update boolean logic proposed above, LoadOrStore may simply just be a direct call to (*Map).Store(key, value, update) then with update set to false.

    Another improvement I'd like to suggest is, instead of following the same API as sync.Map for LoadOrStore where a value is directly provided, have the value parameter be a func() interface{} such that the signature of LoadOrStore is:

    func (m *Map) LoadOrStore(key T, value func() interface{}) (interface{}, bool)
    

    The reason for this is that the value that is intended to be stored under a provided key might be something that is expensive to compute. Suppose you have multiple goroutines racing on LoadOrStore; each goroutine would unnecessarily need to instantiate the expensive-to-compute value when really only the one goroutine that wins the race to store some value under the provided key needs to instantiate the expensive-to-compute value.

    By changing the function signature to accept a value as a func() interface{} instead, only the one goroutine out of many possibly-racing goroutines that wins the race to store a given value under the key will perform the expensive computation.

    opened by lithdew 2
Owner
ZhangYunHao
ZhangYunHao
A skip list implementation in Go

About This is a library implementing skip lists for the Go programming language (http://golang.org/). Skip lists are a data structure that can be used

Ric (Ryszard) Szopa 236 Jul 9, 2022
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist

Fast Skiplist Implementation This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree o

Maurice Tollmien 210 Jul 21, 2022
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Huan Du 286 Aug 1, 2022
A skip list of arbitrary elements that can be filtered using roaring bitmaps stored in an LRU cache

Skipfilter This package provides a data structure that combines a skiplist with a roaring bitmap cache. This library was created to efficiently filter

Kevin Burns 21 Jun 21, 2022
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

sean 231 Aug 6, 2022
sync.WaitGroup for concurrent use

concwg Description This package provides a version of sync.WaitGroup that allows calling Add and Wait in different goroutines. Motivation sync.WaitGro

Maciek Zając 1 May 20, 2022
A Go library to iterate over potentially nested map keys using the visitor pattern

A Go library to iterate over potentially nested map keys using the visitor pattern

null 3 Mar 15, 2022
A typed implementation of the Go sync.Map using code generation

syncmap A typed implementation of the Go sync.Map using code generation. Install go get -u github.com/a8m/[email protected] Examples: Using CLI $ syncma

Ariel Mashraki 236 Jul 22, 2022
Generic types that are missing from Go, including sets, trees, sorted lists, etc.

go-typ Generic types that are missing from Go, including sets, trees, sorted lists, etc. All code is implemented with 0 dependencies and in pure Go co

null 14 Jul 26, 2022
ZSet is an in-memory Redis like sorted set datastructure

zset Getting Started Installing To start using hash, install Go and run go get: $ go get -u github.com/arriqaaq/zset This will retrieve the library. U

Farhan 5 Jul 19, 2022
Recursively searches a map[string]interface{} structure for another map[string]interface{} structure

msirecurse Recursively searches a map[string]interface{} structure for existence of a map[string]interface{} structure Motivation I wrote this package

Fred Moyer 1 Mar 3, 2022
Cuckoo Filter: Practically Better Than Bloom

Cuckoo Filter Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient

Seif Lotfy 917 Aug 1, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 126 May 10, 2022
High-performance minimalist queue implemented using a stripped-down lock-free ringbuffer, written in Go (golang.org)

This project is no longer maintained - feel free to fork the project! gringo A high-performance minimalist queue implemented using a stripped-down loc

Darren Elwood 127 Jul 18, 2022
A feature complete and high performance multi-group Raft library in Go.

Dragonboat - A Multi-Group Raft library in Go / 中文版 News 2021-01-20 Dragonboat v3.3 has been released, please check CHANGELOG for all changes. 2020-03

lni 4.3k Jul 30, 2022
go-fasttld is a high performance top level domains (TLD) extraction module.

go-fasttld go-fasttld is a high performance top level domains (TLD) extraction module implemented with compressed tries. This module is a port of the

Wu Tingfeng 9 Jul 20, 2022
A faster method to get elements from an interface (Struct or Slice type) for Go.

A faster method to get elements from an interface (Struct or Slice type) for Go.

karminski-牙医 35 May 13, 2022
TBH, there are probably better/faster implementations out there.

Scott's Skiplist TBH, there are probably better/faster implementations out there. See https://github.com/MauriceGit/skiplist-survey I wrote this one b

Scott White 1 Feb 10, 2022
Multi-String Pattern Matching Algorithm Using TrieHashNode

Multi-String Pattern Matching algorithm. This implementation is inspired from Aho-Corasick algorithm Getting Started modelA = mspm.NewModel("mspm_mode

Sujit Shakya 17 Jan 23, 2022