Introduction

If your Go version is older than 1.18, use v0.7.0 instead.

Skipmap is a high-performance, scalable, concurrent-safe map based on the skip-list. In the typical pattern (100000 operations, 90%LOAD 9%STORE 1%DELETE, 8C16T), the skipmap is up to 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 keys in the skipmap are always sorted, and the Load 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

• Scalable, high-performance, concurrent-safe.
• Wait-free Load and Range operations (wait-free algorithms have stronger guarantees than lock-free).
• Sorted items.

When should you use skipmap

In most cases, skipmap is better than sync.Map, especially in these situations:

• Sorted keys are needed.
• Concurrent calls multiple operations. Such as using both Range and Store at the same time, in this situation, using skipmap can greatly improve the performance.

If only one goroutine accesses the map for the most of the time, such to insert a batch of elements and then uses only Load or Range, using built-in map is better.

QuickStart

See Go doc for more information.

package main

import (
	"fmt"

	"github.com/zhangyunhao116/skipmap"
)

func main() {
	// Typed key and generic value.
	m0 := skipmap.NewString[int]()

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

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

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

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

	// Generic key and value.
	m1 := skipmap.New[string, int]()
	for _, v := range []int{11, 13, 16} {
		m1.Store(strconv.Itoa(v), v+100)
	}
	m1.Range(func(key string, value int) bool {
		println("m1 found ", key, value)
		return true
	})

	// Generic key and value with less function.
	m2 := skipmap.NewFunc[int, string](func(a, b int) bool { return a < b })
	for _, v := range []int{15, 17, 19} {
		m2.Store(v, strconv.Itoa(v+200))
	}
	m2.Range(func(key int, value string) bool {
		println("m2 found ", key, value)
		return true
	})
}

Note that the generic APIs are always slower than typed APIs, but are more suitable for some scenarios such as functional programming.

e.g. New[string,int] is ~2x slower than NewString[int], and NewFunc[string,int](func(a, b string) bool { return a < b }) is 1~2x slower than NewString[int].

Performance ranking: NewString[int] > New[string,int] > NewFunc[string,int](func(a, b string) bool { return a < b })

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)

$ go test -run=NOTEST -bench=. -benchtime=100000x -benchmem -count=20 -timeout=60m  > x.txt
$ benchstat x.txt

name                                            time/op
Int64/Store/skipmap-16                           158ns ±12%
Int64/Store/sync.Map-16                          700ns ± 4%
Int64/Load50Hits/skipmap-16                     10.1ns ±14%
Int64/Load50Hits/sync.Map-16                    14.8ns ±23%
Int64/30Store70Load/skipmap-16                  50.6ns ±20%
Int64/30Store70Load/sync.Map-16                  592ns ± 7%
Int64/1Delete9Store90Load/skipmap-16            27.5ns ±13%
Int64/1Delete9Store90Load/sync.Map-16            480ns ± 4%
Int64/1Range9Delete90Store900Load/skipmap-16    34.2ns ±26%
Int64/1Range9Delete90Store900Load/sync.Map-16   1.00µs ±12%
String/Store/skipmap-16                          171ns ±15%
String/Store/sync.Map-16                         873ns ± 4%
String/Load50Hits/skipmap-16                    21.3ns ±38%
String/Load50Hits/sync.Map-16                   19.9ns ±12%
String/30Store70Load/skipmap-16                 75.6ns ±16%
String/30Store70Load/sync.Map-16                 726ns ± 5%
String/1Delete9Store90Load/skipmap-16           34.3ns ±20%
String/1Delete9Store90Load/sync.Map-16           584ns ± 5%
String/1Range9Delete90Store900Load/skipmap-16   41.0ns ±21%
String/1Range9Delete90Store900Load/sync.Map-16  1.17µs ± 8%

name                                            alloc/op
Int64/Store/skipmap-16                            112B ± 0%
Int64/Store/sync.Map-16                           128B ± 0%
Int64/Load50Hits/skipmap-16                      0.00B     
Int64/Load50Hits/sync.Map-16                     0.00B     
Int64/30Store70Load/skipmap-16                   33.0B ± 0%
Int64/30Store70Load/sync.Map-16                  81.2B ±11%
Int64/1Delete9Store90Load/skipmap-16             10.0B ± 0%
Int64/1Delete9Store90Load/sync.Map-16            57.9B ± 5%
Int64/1Range9Delete90Store900Load/skipmap-16     10.0B ± 0%
Int64/1Range9Delete90Store900Load/sync.Map-16     261B ±17%
String/Store/skipmap-16                           144B ± 0%
String/Store/sync.Map-16                          152B ± 0%
String/Load50Hits/skipmap-16                     15.0B ± 0%
String/Load50Hits/sync.Map-16                    15.0B ± 0%
String/30Store70Load/skipmap-16                  54.0B ± 0%
String/30Store70Load/sync.Map-16                 96.9B ±12%
String/1Delete9Store90Load/skipmap-16            27.0B ± 0%
String/1Delete9Store90Load/sync.Map-16           74.2B ± 4%
String/1Range9Delete90Store900Load/skipmap-16    27.0B ± 0%
String/1Range9Delete90Store900Load/sync.Map-16    257B ±10%

name                                            allocs/op
Int64/Store/skipmap-16                            3.00 ± 0%
Int64/Store/sync.Map-16                           4.00 ± 0%
Int64/Load50Hits/skipmap-16                       0.00     
Int64/Load50Hits/sync.Map-16                      0.00     
Int64/30Store70Load/skipmap-16                    0.00     
Int64/30Store70Load/sync.Map-16                   1.00 ± 0%
Int64/1Delete9Store90Load/skipmap-16              0.00     
Int64/1Delete9Store90Load/sync.Map-16             0.00     
Int64/1Range9Delete90Store900Load/skipmap-16      0.00     
Int64/1Range9Delete90Store900Load/sync.Map-16     0.00     
String/Store/skipmap-16                           4.00 ± 0%
String/Store/sync.Map-16                          5.00 ± 0%
String/Load50Hits/skipmap-16                      1.00 ± 0%
String/Load50Hits/sync.Map-16                     1.00 ± 0%
String/30Store70Load/skipmap-16                   1.00 ± 0%
String/30Store70Load/sync.Map-16                  2.00 ± 0%
String/1Delete9Store90Load/skipmap-16             1.00 ± 0%
String/1Delete9Store90Load/sync.Map-16            1.00 ± 0%
String/1Range9Delete90Store900Load/skipmap-16     1.00 ± 0%
String/1Range9Delete90Store900Load/sync.Map-16    1.00 ± 0%