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: 11

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

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL