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

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%
Comments
  • 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

  • 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.

  • LoadOrStore: lazy generate level

    LoadOrStore: lazy generate level

    The key problem is that LoadOrStore uses an outdated highest level to search the skip list, if the new generated level(says newLevel) is bigger than the outdated highest level(says oldLevel), all slots in the slices preds[newLevel-oldLevel:newLevel] are nil, the function will panic.

    The solution is that if the newLevel has updated the highest level, we could just continue the loop, and find a new path. At this time, the latest highest level used by the findNode is always bigger than or equal to the newLevel, the function won't panic.

    name                            old time/op  new time/op  delta
    LoadOrStoreExist-16             4.43ns ±11%  1.06ns ±21%  -76.05%  (p=0.000 n=10+10)
    LoadOrStoreLazyExist-16         4.61ns ± 6%  1.16ns ± 0%  -74.90%  (p=0.000 n=9+7)
    LoadOrStoreExistSingle-16       37.5ns ± 6%  10.3ns ± 0%  -72.61%  (p=0.000 n=9+9)
    LoadOrStoreLazyExistSingle-16   38.3ns ±11%  10.6ns ± 0%  -72.43%  (p=0.000 n=10+10)
    LoadOrStoreRandom-16             209ns ±14%   206ns ±14%     ~     (p=0.684 n=10+10)
    LoadOrStoreLazyRandom-16         215ns ± 8%   207ns ± 9%     ~     (p=0.139 n=10+10)
    LoadOrStoreRandomSingle-16      1.05µs ± 1%  1.04µs ± 4%     ~     (p=0.535 n=9+10)
    LoadOrStoreLazyRandomSingle-16  1.07µs ± 1%  1.06µs ± 3%   -1.09%  (p=0.029 n=8+9)
    
  • Performance review

    Performance review

    I ran some benchmarks and got the following results. SkipMap appears to have the least performance. Am I not setting up the tests properly? Code is below the specs.


    goos: windows
    goarch: amd64
    pkg: source/core
    cpu: Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
    
    BenchmarkHaxMapReadsOnly
    BenchmarkHaxMapReadsOnly-8                170182              6550 ns/op
                   0 B/op          0 allocs/op
    BenchmarkHaxMapReadsWithWrites
    BenchmarkHaxMapReadsWithWrites-8          172702              6914 ns/op
                 751 B/op         93 allocs/op
    BenchmarkSkipMapReadsOnly
    BenchmarkSkipMapReadsOnly-8                33459             32374 ns/op
                   0 B/op          0 allocs/op
    BenchmarkSkipMapReadsWithWrites
    BenchmarkSkipMapReadsWithWrites-8          21088             58494 ns/op
                 152 B/op         19 allocs/op
    BenchmarkGoSyncMapReadsOnly
    BenchmarkGoSyncMapReadsOnly-8              70982             17184 ns/op
                   0 B/op          0 allocs/op
    BenchmarkGoSyncMapReadsWithWrites
    BenchmarkGoSyncMapReadsWithWrites-8        58191             22223 ns/op
                4809 B/op        446 allocs/op
    BenchmarkCornelkMapReadsOnly
    BenchmarkCornelkMapReadsOnly-8            192178              6747 ns/op
                   0 B/op          0 allocs/op
    BenchmarkCornelkMapReadsWithWrites
    BenchmarkCornelkMapReadsWithWrites-8      154560              8351 ns/op
                1004 B/op        125 allocs/op
    PASS
    

    package main
    
    import (
    	"github.com/alphadose/haxmap"
    	"github.com/cornelk/hashmap"
    	"github.com/zhangyunhao116/skipmap"
    	"sync"
    	"sync/atomic"
    	"testing"
    )
    
    const (
    	epochs  uintptr = 1 << 12
    	mapSize         = 256
    )
    
    func setupHaxMap() *haxmap.HashMap[uintptr, uintptr] {
    	m := haxmap.New[uintptr, uintptr](mapSize)
    	for i := uintptr(0); i < epochs; i++ {
    		m.Set(i, i)
    	}
    	return m
    }
    
    func setupGoSyncMap() *sync.Map {
    	m := &sync.Map{}
    	for i := uintptr(0); i < epochs; i++ {
    		m.Store(i, i)
    	}
    	return m
    }
    
    func setupCornelkMap(b *testing.B) *hashmap.Map[uintptr, uintptr] {
    	m := hashmap.NewSized[uintptr, uintptr](mapSize)
    	for i := uintptr(0); i < epochs; i++ {
    		m.Set(i, i)
    	}
    	return m
    }
    
    type anyskipmap[T any] interface {
    	Store(key T, value any)
    	Load(key T) (any, bool)
    	Delete(key T) bool
    	LoadAndDelete(key T) (any, bool)
    	LoadOrStore(key T, value any) (any, bool)
    	LoadOrStoreLazy(key T, f func() any) (any, bool)
    	Range(f func(key T, value any) bool)
    	Len() int
    }
    
    func setupSkipMap() *skipmap.OrderedMap[uintptr, uintptr] {
    	m := skipmap.New[uintptr, uintptr]()
    	//hashmap.NewSized[uintptr, uintptr](mapSize)
    	for i := uintptr(0); i < epochs; i++ {
    		m.Store(i, i)
    	}
    	return m
    }
    
    func BenchmarkHaxMapReadsOnly(b *testing.B) {
    	m := setupHaxMap()
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		for pb.Next() {
    			for i := uintptr(0); i < epochs; i++ {
    				j, _ := m.Get(i)
    				if j != i {
    					b.Fail()
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkHaxMapReadsWithWrites(b *testing.B) {
    	m := setupHaxMap()
    	var writer uintptr
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		// use 1 thread as writer
    		if atomic.CompareAndSwapUintptr(&writer, 0, 1) {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					m.Set(i, i)
    				}
    			}
    		} else {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					j, _ := m.Get(i)
    					if j != i {
    						b.Fail()
    					}
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkSkipMapReadsOnly(b *testing.B) {
    	m := setupSkipMap()
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		for pb.Next() {
    			for i := uintptr(0); i < epochs; i++ {
    				j, _ := m.Load(i)
    				if j != i {
    					b.Fail()
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkSkipMapReadsWithWrites(b *testing.B) {
    	m := setupSkipMap()
    	var writer uintptr
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		// use 1 thread as writer
    		if atomic.CompareAndSwapUintptr(&writer, 0, 1) {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					m.Store(i, i)
    				}
    			}
    		} else {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					j, _ := m.Load(i)
    					if j != i {
    						b.Fail()
    					}
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkGoSyncMapReadsOnly(b *testing.B) {
    	m := setupGoSyncMap()
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		for pb.Next() {
    			for i := uintptr(0); i < epochs; i++ {
    				j, _ := m.Load(i)
    				if j != i {
    					b.Fail()
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkGoSyncMapReadsWithWrites(b *testing.B) {
    	m := setupGoSyncMap()
    	var writer uintptr
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		// use 1 thread as writer
    		if atomic.CompareAndSwapUintptr(&writer, 0, 1) {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					m.Store(i, i)
    				}
    			}
    		} else {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					j, _ := m.Load(i)
    					if j != i {
    						b.Fail()
    					}
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkCornelkMapReadsOnly(b *testing.B) {
    	m := setupCornelkMap(b)
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		for pb.Next() {
    			for i := uintptr(0); i < epochs; i++ {
    				j, _ := m.Get(i)
    				if j != i {
    					b.Fail()
    				}
    			}
    		}
    	})
    }
    
    func BenchmarkCornelkMapReadsWithWrites(b *testing.B) {
    	m := setupCornelkMap(b)
    	var writer uintptr
    	b.ReportAllocs()
    	b.ResetTimer()
    	b.RunParallel(func(pb *testing.PB) {
    		// use 1 thread as writer
    		if atomic.CompareAndSwapUintptr(&writer, 0, 1) {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					m.Set(i, i)
    				}
    			}
    		} else {
    			for pb.Next() {
    				for i := uintptr(0); i < epochs; i++ {
    					j, _ := m.Get(i)
    					if j != i {
    						b.Fail()
    					}
    				}
    			}
    		}
    	})
    }
    
  • Documentation for preds and succs

    Documentation for preds and succs

    https://github.com/zhangyunhao116/skipmap/blob/fd4ece9e59b79b85915c4e3c7de744be1ec18898/skipmap.tpl#L63 In this comment, it said preds[i].key > key >= succs[i].key.

    But in the paper, it's image which implies the relation is preds[i].key < key <= succs[i].key

    Am I understand correctly? I check the findNode and findNodeDelete. The code corresponds to the code in the paper.

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

Sep 21, 2022
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist
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

Dec 30, 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

Dec 4, 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

Aug 4, 2022
A fast, threadsafe skip list in Go
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

Dec 2, 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

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

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/syncmap@master Examples: Using CLI $ syncma

Dec 26, 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

Dec 4, 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

Oct 13, 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

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

Jan 4, 2023
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

Nov 20, 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

Oct 24, 2022
A feature complete and high performance multi-group Raft library in Go.
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

Jan 5, 2023
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

Dec 21, 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.

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

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

Dec 9, 2022