README
¶
Sharded RWLocked Map, using go generics
Introduction
In some scenarios sync.Map could allocate large space for dirty-read copies, or even heavily use locks (when getting missing values, that should be rechecked in map with lock). In such scenarios go internal map with rw-mutex, divided to several shards could perform much better, with cost of memory for additional locks storage. But this amount could be much less, than sync.map uses.
Interface incompatibility
LoadOrStoremethod changed toLoadOrCreate, with callback that generates value. Could be used to avoid unnecessary creating huge values, in case if key already exists.
Usage Example
package main
import (
"fmt"
"github.com/WinnerSoftLab/go-generics-tools/smap"
)
func main() {
m := smap.NewIntegerComparable[int, int](8, 128)
m.Store(123, 456)
value, ok := m.Load(123)
fmt.Printf("%d, %t", value, ok)
}
A bit more examples could be found in tests.
Benchmark
Benchmark
Benchmark performed on Lenovo Ideapad laptop with AMD Ryzen 7 4700U, Linux Mint 20.3 with 5.13.0 kernel
BenchmarkIntegerSMap_ConcurrentGet-8 82540485 12.95 ns/op 0 B/op 0 allocs/op
BenchmarkSyncMap_ConcurrentGet-8 73431339 18.35 ns/op 0 B/op 0 allocs/op
BenchmarkLockMap_ConcurrentGet-8 19327282 54.03 ns/op 0 B/op 0 allocs/op
BenchmarkIntegerShardedMap_ConcurrentSet-8 25605380 42.33 ns/op 0 B/op 0 allocs/op
BenchmarkSyncMap_ConcurrentSet-8 2138496 536.1 ns/op 36 B/op 3 allocs/op
BenchmarkLockMap_ConcurrentSet-8 3827476 302.9 ns/op 0 B/op 0 allocs/op
BenchmarkIntegerShardedMap_ConcurrentGetSet5-8 3377473 357.1 ns/op 0 B/op 0 allocs/op
BenchmarkSyncMap_ConcurrentGetSet5-8 323318 3540 ns/op 266 B/op 3 allocs/op
BenchmarkLockMap_ConcurrentGetSet5-8 204633 6176 ns/op 0 B/op 0 allocs/op
BenchmarkIntegerShardedMap_ConcurrentGetSet50-8 18236305 65.03 ns/op 0 B/op 0 allocs/op
BenchmarkSyncMap_ConcurrentGetSet50-8 18337423 56.55 ns/op 32 B/op 2 allocs/op
BenchmarkLockMap_ConcurrentGetSet50-8 2697315 431.2 ns/op 0 B/op 0 allocs/op
BenchmarkIntegerShardedMap_ConcurrentGetSet1-8 1003506 1076 ns/op 0 B/op 0 allocs/op
BenchmarkSyncMap_ConcurrentGetSet1-8 32668 44423 ns/op 3508 B/op 5 allocs/op
BenchmarkLockMap_ConcurrentGetSet1-8 78486 16019 ns/op 0 B/op 0 allocs/op
Sharded Lock map is approximately equal to sync.Map on 50% read + 50% concurrent writes, and is much faster on 5% writes+95% reads, and 1% writes+99% reads. Also sharded map allocated about 40x less memory in 5% writes+95% reads scenario, than sync.Map does.
Compatibility
Minimal Golang version is 1.18. Generics are used.
Installation
To install package, run:
go get github.com/WinnerSoftLab/go-generics-tools/smap
License
The smap package is licensed under the MIT license. Please see the LICENSE file for details.
Documentation
¶
Index ¶
- func HeuristicOptimalDistribution(expectedItemsCount int) (int, int)
- func HeuristicOptimalShardsCount() int
- type Generic
- func (sm Generic[K, V]) Delete(key K)
- func (sm Generic[K, V]) DeleteWhere(predicate func(K, V) bool)
- func (sm Generic[K, V]) DeleteWhereKeys(predicate func(K) bool)
- func (sm Generic[K, V]) Len() int
- func (sm Generic[K, V]) Load(key K) (V, bool)
- func (sm Generic[K, V]) LoadAndDelete(key K) (V, bool)
- func (sm Generic[K, V]) LoadOrCreate(key K, generator func() V) (V, bool)
- func (sm Generic[K, V]) LockShard(id int)
- func (sm Generic[K, V]) RLockShard(id int)
- func (sm Generic[K, V]) RUnlockShard(id int)
- func (sm Generic[K, V]) Range(cb func(K, V) bool)
- func (sm Generic[K, V]) RangeKeys(cb func(K) bool)
- func (sm Generic[K, V]) ShardID(key K) int
- func (sm Generic[K, V]) ShardsCount() int
- func (sm Generic[K, V]) Store(key K, value V)
- func (sm Generic[K, V]) UnblockedGet(key K) (V, bool)
- func (sm Generic[K, V]) UnblockedSet(key K, value V)
- func (sm Generic[K, V]) UnblockedShardRange(shardID int, cb func(key K, value V) bool)
- func (sm Generic[K, V]) UnlockShard(id int)
- type GenericComparable
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func HeuristicOptimalDistribution ¶
HeuristicOptimalDistribution returns shards count, and shard size for given map size. Use with caution, It's point for change, and could be changed in the future.
func HeuristicOptimalShardsCount ¶
func HeuristicOptimalShardsCount() int
HeuristicOptimalShardsCount returns shards count. Use with caution, It's point for change, and could be changed in the future.
Types ¶
type Generic ¶
type Generic[K comparable, V any] struct { // contains filtered or unexported fields }
Generic stores data in N shards, with rw mutex for each.
func NewGeneric ¶
func NewGeneric[K comparable, V any](shardsCount, defaultSize int, shardDetector func(key K) int) Generic[K, V]
NewGeneric creates generic RWLocked Sharded map. shardDetector should be idempotent function.
func NewInteger ¶
func NewInteger[K constraints.Integer, V any](shardsCount, defaultSize int) Generic[K, V]
NewInteger creates sharded rwlock maps with shard detection based on key division to shards count modulo.
func (Generic[K, V]) Delete ¶
func (sm Generic[K, V]) Delete(key K)
Delete deletes the value for a key.
func (Generic[K, V]) DeleteWhere ¶ added in v1.1.1
DeleteWhere deletes values according to predicate.
func (Generic[K, V]) DeleteWhereKeys ¶ added in v1.1.1
DeleteWhereKeys deletes values according to predicate.
func (Generic[K, V]) Load ¶
Load returns the value stored in the map for a key, or nil if no value is present. The ok result indicates whether value was found in the map.
func (Generic[K, V]) LoadAndDelete ¶
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.
func (Generic[K, V]) LoadOrCreate ¶
LoadOrCreate returns the existing value for the key if present. Otherwise, it calls generator func, stores and returns the generator's result. Generator will not be called if key present. The loaded result is true if the value was loaded, false if stored.
func (Generic[K, V]) LockShard ¶
LockShard locks shard with given id. Could be useful with Unblocked* functions. Other calls to sm could be locked. Use with caution, only when benchmark shows significant performance changes.
func (Generic[K, V]) RLockShard ¶
RLockShard locks for read shard with given id. Could be useful with Unblocked* functions. Other calls to sm could be rlocked. Use with caution, only when benchmark shows significant performance changes.
func (Generic[K, V]) RUnlockShard ¶
RUnlockShard unlocks for read shard with given id.
func (Generic[K, V]) Range ¶
Range calls cb sequentially for each key and value present in the map. If cb returns false, range stops the iteration.
Range performs like sync.Range: does not correspond to any consistent snapshot of the Map's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently (including by cb), Range may reflect any mapping for that key from any point during the Range call. Range does not block other methods on the receiver; even cb itself may call any method on sm.
Range may be O(N) with the number of elements in the map even if f returns false after a constant number of calls.
func (Generic[K, V]) RangeKeys ¶ added in v1.1.2
RangeKeys works similar like Range, but iterates by keys only.
func (Generic[K, V]) ShardsCount ¶
ShardsCount returns shards count, given on initialisation.
func (Generic[K, V]) Store ¶
func (sm Generic[K, V]) Store(key K, value V)
Store sets the value for a key.
func (Generic[K, V]) UnblockedGet ¶
UnblockedGet returns value, without locks. Use with caution, only when lock or rlock were taken for shard.
func (Generic[K, V]) UnblockedSet ¶
func (sm Generic[K, V]) UnblockedSet(key K, value V)
UnblockedSet sets value, without locks. Use with caution, only when lock were taken for shard.
func (Generic[K, V]) UnblockedShardRange ¶
UnblockedShardRange calls cb sequentially for each key and value present in the maps shard. Use with caution, only when lock or rlock were taken for shard.
func (Generic[K, V]) UnlockShard ¶
UnlockShard unlocks shard with given id.
type GenericComparable ¶
type GenericComparable[K comparable, V comparable] struct { Generic[K, V] }
GenericComparable stores data in N shards, with rw mutex for each. Additional CompareAndSwap method added for comparable values.
func NewGenericComparable ¶
func NewGenericComparable[K comparable, V comparable](shardsCount, defaultSize int, shardDetector func(key K) int) GenericComparable[K, V]
NewGenericComparable creates generic RWLocked Sharded map for comparable values. shardDetector should be idempotent function.
func NewIntegerComparable ¶
func NewIntegerComparable[K constraints.Integer, V comparable](shardsCount, defaultSize int) GenericComparable[K, V]
NewIntegerComparable creates sharded rwlock maps with comparable values.
func (GenericComparable[K, V]) CompareAndSwap ¶
func (sm GenericComparable[K, V]) CompareAndSwap(key K, old, new V) (V, bool)
CompareAndSwap executes the compare-and-swap operation for the Key & Value pair. If and only if key exists, and value for key equals old, value will be changed to new. Otherwise, returns current value. The ok result indicates whether value was changed to new in the map.
Source Files