cmap

package module
v0.0.0-...-ccaef76 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 25, 2017 License: Apache-2.0 Imports: 3 Imported by: 10

README

cmap GoDoc Build Status Coverage

CMap (concurrent-map) is a sharded map implementation to support fast concurrent access.

Install

go get github.com/OneOfOne/cmap

Features

  • Full concurrent access (except for Update).
  • Supports Get, Set, SetIfNotExists, Swap, Update, Delete, DeleteAndGet (Pop).
  • ForEach / Iter supports modifing the map during the iteration like map and sync.Map.
  • stringcmap.CMap gives a specialized version to support map[string]interface{}.
  • stringcmap.MapWithJSON implements json.Unmarshaler with a custom value unmarshaler.

Typed CMap (using genx)

  • CMap fully supports generating typed versions, for example stringcmap is generated by running go:generate genx -pkg github.com/OneOfOne/cmap -v -n stringcmap -t KT=string,VT=interface{} -fld HashFn -fn DefaultKeyHasher -s "cm.HashFn=hashers.Fnv32" -m -o ./stringcmap/cmap_string_iface.go
How to generate your own?
	➤ go get -u github.com/OneOfOne/genx/cmd/genx # get or update genx
	➤ genx -pkg github.com/OneOfOne/cmap -v -m -t KT=pkg.SomeType,VT=interface{} -name newPackageName -o ./cmap_something.go
	# example:
	➤ genx -pkg github.com/OneOfOne/cmap -v -m -t KT=uint64,VT=func() -name cbmap -o ./cmap_cbmap.go

FAQ

Why?
  • A simple sync.RWMutex wrapped map is much slower as the concurrency increase.
  • Provides several helper functions, Swap(), Update, DeleteAndGet.
Why not sync.Map?
  • sync.Map is great, I absolute love it if all you need is pure Load/Store, however you can't safely update values in it.

Usage

import (
	"github.com/OneOfOne/cmap"
)

func main() {
	cm := cmap.New() // or cmap.NewString()
	// cm := cmap.NewSize(1 << 8) // the size must always be a power of 2
	cm.Set("key", "value")
	ok := cm.Has("key") == true
	if v, ok := cm.Get("key").(string); ok {
		// do something with v
	}
	cm.Update("key", func(old interface{}) interface{} {
		v, _ := old.(uint64)
		return v + 1
	})
}

Benchmark

➤ go version; go test -tags streamrail -short -bench=. -benchmem -count 5 ./ ./stringcmap/ | benchstat /dev/stdin
go version devel +ff90f4af66 2017-08-19 12:56:24 +0000 linux/amd64

name               time/op
# pkg:github.com/OneOfOne/cmap goos:linux goarch:amd64
CMap/2048-8        85.3ns ± 2%
CMap/4096-8        86.5ns ± 1%
CMap/8192-8        95.0ns ±16%

# simple map[interface{}]interface{} wrapped with a sync.RWMutex
MutexMap-8          486ns ± 9%

# sync.Map
SyncMap-8           511ns ±28%

# pkg:github.com/OneOfOne/cmap/stringcmap goos:linux goarch:amd64
StringCMap/2048-8  38.3ns ± 3%
StringCMap/4096-8  37.9ns ± 5%
StringCMap/8192-8  38.5ns ±17%

Streamrail/2048-8  47.2ns ± 1%
Streamrail/4096-8  46.6ns ± 1%
Streamrail/8192-8  46.7ns ± 2%

name               alloc/op
# pkg:github.com/OneOfOne/cmap goos:linux goarch:amd64
CMap/2048-8         48.0B ± 0%
CMap/4096-8         48.0B ± 0%
CMap/8192-8         48.0B ± 0%

MutexMap-8          35.0B ± 0%

SyncMap-8           63.4B ± 7%

# pkg:github.com/OneOfOne/cmap/stringcmap goos:linux goarch:amd64

# specialized version of CMap, using map[string]interface{} internally
StringCMap/2048-8   16.0B ± 0%
StringCMap/4096-8   16.0B ± 0%
StringCMap/8192-8   16.0B ± 0%

# github.com/streamrail/concurrent-map
Streamrail/2048-8   16.0B ± 0%
Streamrail/4096-8   16.0B ± 0%
Streamrail/8192-8   16.0B ± 0%

name               allocs/op
# pkg:github.com/OneOfOne/cmap goos:linux goarch:amd64
CMap/2048-8          3.00 ± 0%
CMap/4096-8          3.00 ± 0%
CMap/8192-8          3.00 ± 0%

MutexMap-8           2.00 ± 0%

SyncMap-8            3.00 ± 0%

# pkg:github.com/OneOfOne/cmap/stringcmap goos:linux goarch:amd64
StringCMap/2048-8    1.00 ± 0%
StringCMap/4096-8    1.00 ± 0%
StringCMap/8192-8    1.00 ± 0%

Streamrail/2048-8    1.00 ± 0%
Streamrail/4096-8    1.00 ± 0%
Streamrail/8192-8    1.00 ± 0%

License

Apache v2.0 (see LICENSE file).

Copyright 2016-2017 Ahmed <OneOfOne> W.

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

Documentation

Index

Constants

View Source 
const DefaultShardCount = 1 << 8

DefaultShardCount is the default number of shards to use when New() or NewFromJSON() are called. The default is 256.

Variables

This section is empty.

Functions

This section is empty.

Types

type CMap 

type CMap struct {
	// contains filtered or unexported fields
}

CMap is a concurrent safe sharded map to scale on multiple cores.

func New 

func New() *CMap

New is an alias for NewSize(DefaultShardCount)

func NewSize 

func NewSize(shardCount int) *CMap

NewSize returns a CMap with the specific shardSize, note that for performance reasons, shardCount must be a power of 2. Higher shardCount will improve concurrency but will consume more memory.

func (*CMap) Delete 

func (cm *CMap) Delete(key interface{})

Delete is the equivalent of `delete(map, key)`.

func (*CMap) DeleteAndGet 

func (cm *CMap) DeleteAndGet(key interface{}) interface{}

DeleteAndGet is the equivalent of `oldVal := map[key]; delete(map, key)`.

func (*CMap) ForEach 

func (cm *CMap) ForEach(fn func(key interface{}, val interface{}) bool) bool

ForEach loops over all the key/values in the map. You can break early by returning false. It **is** safe to modify the map while using this iterator, however it uses more memory and is slightly slower.

func (*CMap) ForEachLocked 

func (cm *CMap) ForEachLocked(fn func(key interface{}, val interface{}) bool) bool

ForEachLocked loops over all the key/values in the map. You can break early by returning false. It is **NOT* safe to modify the map while using this iterator.

func (*CMap) Get 

func (cm *CMap) Get(key interface{}) (val interface{})

Get is the equivalent of `val := map[key]`.

func (*CMap) GetOK 

func (cm *CMap) GetOK(key interface{}) (val interface{}, ok bool)

GetOK is the equivalent of `val, ok := map[key]`.

func (*CMap) Has 

func (cm *CMap) Has(key interface{}) bool

Has is the equivalent of `_, ok := map[key]`.

func (*CMap) Iter 

func (cm *CMap) Iter(ctx context.Context, buffer int) <-chan *KV

Iter returns a channel to be used in for range. Use `context.WithCancel` if you intend to break early or goroutines will leak. It **is** safe to modify the map while using this iterator, however it uses more memory and is slightly slower.

func (*CMap) IterLocked 

func (cm *CMap) IterLocked(ctx context.Context, buffer int) <-chan *KV

IterLocked returns a channel to be used in for range. Use `context.WithCancel` if you intend to break early or goroutines will leak and map access will deadlock. It is **NOT* safe to modify the map while using this iterator.

func (*CMap) Keys 

func (cm *CMap) Keys() []interface{}

Keys returns a slice of all the keys of the map.

func (*CMap) Len 

func (cm *CMap) Len() int

Len returns the length of the map.

func (*CMap) NumShards 

func (cm *CMap) NumShards() int

NumShards returns the number of shards in the map.

func (*CMap) Set 

func (cm *CMap) Set(key interface{}, val interface{})

Set is the equivalent of `map[key] = val`.

func (*CMap) SetIfNotExists 

func (cm *CMap) SetIfNotExists(key interface{}, val interface{}) (set bool)

SetIfNotExists will only assign val to key if it wasn't already set. Use `Update` if you need more logic.

func (*CMap) ShardDistribution 

func (cm *CMap) ShardDistribution() []float64

ShardDistribution returns the distribution of data amoung all shards. Useful for debugging the efficiency of a hash.

func (*CMap) ShardForKey 

func (cm *CMap) ShardForKey(key interface{}) *LMap

ShardForKey returns the LMap that may hold the specific key.

func (*CMap) Swap 

func (cm *CMap) Swap(key interface{}, val interface{}) interface{}

Swap is the equivalent of `oldVal, map[key] = map[key], newVal`.

func (*CMap) Update 

func (cm *CMap) Update(key interface{}, fn func(oldval interface{}) (newval interface{}))

Update calls `fn` with the key's old value (or nil) and assign the returned value to the key. The shard containing the key will be locked, it is NOT safe to call other cmap funcs inside `fn`.

type KV 

type KV struct {
	Key   interface{}
	Value interface{}
}

KV holds the key/value returned when Iter is called.

type LMap 

type LMap struct {
	// contains filtered or unexported fields
}

LMap is a simple sync.RWMutex locked map. Used by CMap internally for sharding.

func NewLMap 

func NewLMap() *LMap

NewLMap returns a new LMap with the cap set to 0.

func NewLMapSize 

func NewLMapSize(cap int) *LMap

NewLMapSize is the equivalent of `m := make(map[interface{}]interface{}, cap)`

func (*LMap) Delete 

func (lm *LMap) Delete(key interface{})

Delete is the equivalent of `delete(map, key)`.

func (*LMap) DeleteAndGet 

func (lm *LMap) DeleteAndGet(key interface{}) (v interface{})

DeleteAndGet is the equivalent of `oldVal := map[key]; delete(map, key)`.

func (*LMap) ForEach 

func (lm *LMap) ForEach(keys []interface{}, fn func(key interface{}, val interface{}) bool) bool

ForEach loops over all the key/values in the map. You can break early by returning an error . It **is** safe to modify the map while using this iterator, however it uses more memory and is slightly slower.

func (*LMap) ForEachLocked 

func (lm *LMap) ForEachLocked(fn func(key interface{}, val interface{}) bool) bool

ForEachLocked loops over all the key/values in the map. You can break early by returning false It is **NOT* safe to modify the map while using this iterator.

func (*LMap) Get 

func (lm *LMap) Get(key interface{}) (v interface{})

Get is the equivalent of `val := map[key]`.

func (*LMap) GetOK 

func (lm *LMap) GetOK(key interface{}) (v interface{}, ok bool)

GetOK is the equivalent of `val, ok := map[key]`.

func (*LMap) Has 

func (lm *LMap) Has(key interface{}) (ok bool)

Has is the equivalent of `_, ok := map[key]`.

func (*LMap) Keys 

func (lm *LMap) Keys(buf []interface{}) []interface{}

Keys appends all the keys in the map to buf and returns buf. buf may be nil.

func (*LMap) Len 

func (lm *LMap) Len() (ln int)

Len returns the length of the map.

func (*LMap) Set 

func (lm *LMap) Set(key interface{}, v interface{})

Set is the equivalent of `map[key] = val`.

func (*LMap) SetIfNotExists 

func (lm *LMap) SetIfNotExists(key interface{}, val interface{}) (set bool)

SetIfNotExists will only assign val to key if it wasn't already set. Use `Update` if you need more logic.

func (*LMap) Swap 

func (lm *LMap) Swap(key interface{}, newV interface{}) (oldV interface{})

Swap is the equivalent of `oldVal, map[key] = map[key], newVal`.

func (*LMap) Update 

func (lm *LMap) Update(key interface{}, fn func(oldVal interface{}) (newVal interface{}))

Update calls `fn` with the key's old value (or nil) and assigns the returned value to the key. The shard containing the key will be locked, it is NOT safe to call other cmap funcs inside `fn`.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.