lfmap

README

lfmap

Generic concurrent lock-free map for Golang.

Key features:

• range iteration over consistent snapshot of map without locking other threads and without copying all data in map to maintain that snapshot.
• Convenient transactions where you can read-write multiple keys, check some conditions and make a change based on your logic. Compared to lfmap, sync.Map allows only CAS operations against single key and that's it.

Usage

See godoc examples.

Benchmarks

goos: linux
goarch: amd64
pkg: github.com/Snawoot/lfmap
cpu: Intel(R) N100
BenchmarkLFMapSet-4              	  165698	     11190 ns/op
BenchmarkSyncMapSet-4            	  857448	      2302 ns/op
BenchmarkLFMapGet-4              	 3221922	       365.1 ns/op
BenchmarkSyncMapGet-4            	 5302554	       189.9 ns/op
BenchmarkLFMapRange1000000-4     	       8	 142530076 ns/op
BenchmarkSyncMapRange1000000-4   	       7	 150277709 ns/op
PASS
ok  	github.com/Snawoot/lfmap	31.614s

So far lfmap is 2-6 times slower than sync.Map, mostly because of underlying immutable ds performance. However, nice transactional properties may make it useful.

Documentation

Overview

Package lfmap provides generic concurrent lock-free map implementation, using immutable map and atomic swaps.

Example

package main

import (
	"fmt"
	"sync"

	"github.com/Snawoot/lfmap"
)

func main() {
	m := lfmap.New[string, int]()
	var wg sync.WaitGroup
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			key := fmt.Sprintf("k%d", i)
			value := i * 100
			m.Set(key, value)
		}(i)
	}
	wg.Wait()

	for k, v := range m.Range {
		fmt.Printf("key = %s, value = %d\n", k, v)
	}
}

Index

• type Map
  • func New[K comparable, V any]() *Map[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Delete(key K)
  • func (m *Map[K, V]) Get(key K) (value V, ok bool)
  • func (m *Map[K, V]) Len(key K) int
  • func (m *Map[K, V]) Range(yield func(key K, value V) bool)
  • func (m *Map[K, V]) Set(key K, value V)
  • func (m *Map[K, V]) Transaction(txn func(t Tx[K, V]))
• type Tx

Examples

• Package
• Map.Transaction

Types

type Map

type Map[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Map is an instance of concurrent map. All Map methods are safe for concurrent use.

func New

func New[K comparable, V any]() *Map[K, V]

New returns a new instance of empty Map.

func (*Map[K, V]) Clear

func (m *Map[K, V]) Clear()

Clear empties map. It's a shortcut for a transaction with just clear operation in it.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K)

Delete updates the map removing specified key. It's a shortcut for a transaction with just delete operation in it.

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (value V, ok bool)

Get returns the value for a given key and a flag indicating whether the key exists. This flag distinguishes a nil value set on a key versus a non-existent key in the map.

func (*Map[K, V]) Len

func (m *Map[K, V]) Len(key K) int

Len returns the number of elements in the map.

func (*Map[K, V]) Range

func (m *Map[K, V]) Range(yield func(key K, value V) bool)

Map iterator suitable for use with range keyword.

func (*Map[K, V]) Set

func (m *Map[K, V]) Set(key K, value V)

Set updates the map setting specified key to the new value. It's a shorcut for a Map.Transaction invoked with function setting only one value.

func (*Map[K, V]) Transaction

func (m *Map[K, V]) Transaction(txn func(t Tx[K, V]))

Transaction executes operations made by txn function, allowing complex interactions with map to be performed atomically and consistently.

txn function can be invoked more than once in case if collision happened during update.

Example

package main

import (
	"fmt"

	"github.com/Snawoot/lfmap"
)

func main() {
	m := lfmap.New[string, int]()

	// Let's do a simple increment to illustrate transactions
	key := "abc"
	m.Transaction(func(t lfmap.Tx[string, int]) {
		ctr, _ := t.Get(key)
		t.Set(key, ctr+1)
	})
	fmt.Println(m.Get(key))
}

type Tx

type Tx[K comparable, V any] interface {
	// Clears the map.
	Clear()

	// Deletes the key.
	Delete(key K)

	// Returns the value for a given key and a flag indicating whether the key
	// exists. This flag distinguishes a nil value set on a key versus a
	// non-existent key in the map.
	Get(key K) (value V, ok bool)

	// Returns the number of elements in the map.
	Len() int

	// Map iterator suitable for use with range keyword.
	Range(yield func(key K, value V) bool)

	// Updates the map setting specified key to the new value.
	Set(key K, value V)
}

Tx is a handle to map state usable from within transactions. It's methods are NOT safe for concurrent use.