skiplistmap

package module
v0.7.3 Latest Latest
Warning

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

 Go to latest Published: Dec 27, 2021 License: MIT Imports: 18 Imported by: 0

README

Skip List Map in Golang

Skip List Map is a concurrent map. this Map is goroutine safety for reading/updating/deleting, no-require locking and coordination.

status

Go Go Reference

features

  • buckets, elemenet(key/value item) structure is concurrent embeded-linked list. (using list_encabezado)
  • keep key order by hash function.
  • ability to store value ( value of key/vale) and elemet of ket/value item(detail is later)
  • improve performance for sync.Map/ internal map in write heavy environment.

requirement

golang >= 1.17

install

Install this package through go get.

go get "github.com/kazu/skiplistmap"

basic usage

package main 

import (
    "fmt"
)

//create skip list map
sMap := skiplistmap.New()
// create make with configure MaxPerBucket
// sMap := skiplistmap.New(skiplistmap.MaxPefBucket(12))
// sMap := skiplistmap.New(skiplistmap.MaxPefBucket(12))

// Set/Add values
sMap.Set("test1", 1)
sMap.Set("test2", 2)

// get the value for a key, return nil if not found, the ok is found.
inf, ok := sMap.Get("test1")
var value1 int
if ok {
    value1 = inf.(int)
}

ok = sMap.GetByFn(func(v interface{}) {
    value = v.(int)
})


// if directry using key/value item. use SampleItem struct
sMap2 := skiplistmap.New(skiplistmap.MaxPefBucket(12))
item := &skiplistmap.SampleItem{
    K: "test1", 
    V: 1234
}

// store item
ok = sMap2.StoreItem(item)

// get key/value item
item, ok = sMap.LoadItem("test1")
// get next key/value
nItem := sMap.Next()

// traverse all item or key/value 
sMap.RangeItem(func(item MapItem) bool {
  fmt.Printf("key=%+v\n", item.Key())  
})
sMap.Range(func(key, value interface{}) bool {
  fmt.Printf("key=%+v\n", key)  
})



// delete marking. set nil as value.
sMap.Delete("test2")

// delete key/value entry from map. traverse locked for deleting item to acceess concurrent
sMap.Purge("test2")

performance

condition
  • 100000 record. set key/value before benchmark
  • mapWithMutex map[interface{}]interface{} with sync.RWMutex
  • skiplistmap4 this package's item pool mode
  • skiplistmap5 embedded item pool in bucket.
  • hashmap github.com/cornelk/hashmap package
  • cmap github.com/lrita/cmap package
read only
Benchmark_Map/mapWithMutex_w/_0_bucket=__0-16         	15610328	        76.12 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/sync.Map_____w/_0_bucket=__0-16         	25813341	        43.37 ns/op	      63 B/op	       2 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_16-16         	35947046	        38.25 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap4_w/_0_bucket=_32-16         	36800390	        36.61 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_16-16         	46779364	        27.37 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_32-16         	49452940	        27.01 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/skiplistmap5_w/_0_bucket=_64-16         	47740882	        27.45 ns/op	      15 B/op	       1 allocs/op
Benchmark_Map/hashmap______w/_0_bucket=__0-16         	20071834	        63.11 ns/op	      31 B/op	       2 allocs/op
Benchmark_Map/cmap.Cmap____w/_0_bucket=__0-16            1841415	       721.00 ns/op	     935 B/op	       5 allocs/op
read 50%. update 50%
Benchmark_Map/mapWithMutex_w/50_bucket=__0-16         	 2895382	       377.3  ns/op	      16 B/op	       1 allocs/op
Benchmark_Map/sync.Map_____w/50_bucket=__0-16         	 9532836	       137.4  ns/op	     140 B/op	       4 allocs/op
Benchmark_Map/skiplistmap4_w/50_bucket=_16-16         	33024600	        50.80 ns/op	      21 B/op	       2 allocs/op
Benchmark_Map/skiplistmap4_w/50_bucket=_32-16         	33231843	        48.75 ns/op	      21 B/op	       2 allocs/op
Benchmark_Map/skiplistmap5_w/50_bucket=_16-16         	33412243	        38.20 ns/op	      21 B/op	       2 allocs/op
Benchmark_Map/skiplistmap5_w/50_bucket=_32-16         	34377592	        38.60 ns/op	      20 B/op	       2 allocs/op
Benchmark_Map/skiplistmap5_w/50_bucket=_64-16         	32261986	        39.33 ns/op	      20 B/op	       2 allocs/op
Benchmark_Map/hashmap______w/50_bucket=__0-16         	37279302	        66.94 ns/op	      65 B/op	       3 allocs/op
Benchmark_Map/cmap_________w/50_bucket=__0-16            1592382	       733.2  ns/op	    1069 B/op	       7 allocs/op

why faster ?

  • lock free , thread safe concurrent without lock. embedded pool mode is using lock per bucket
  • buckets, items(key/value items) is doubly linked-list. this linked list is embedded type. so faster
  • items is shards per hash key single bytes. items in the same shard is high-locality because in same slice.
  • next/prev pointer of items's linked list is relative pointer. low-cost copy for expand shad slice. (elist_head)

Documentation

Overview

Package skitlistmap ... concurrent akiplist map implementatin Copyright 2201 Kazuhisa TAKEI<xtakei@rytr.jp>. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package skitlistmap ... concurrent akiplist map implementatin Copyright 2201 Kazuhisa TAKEI<xtakei@rytr.jp>. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Copyright 2201 Kazuhisa TAKEI<xtakei@rytr.jp>. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Package loncha/list_head is like a kernel's LIST_HEAD list_head is used by loncha/gen/containers_list

Index

Constants

View Source 
const (
	CntSearchBucket  statKey = 1
	CntLevelBucket   statKey = 2
	CntSearchEntry   statKey = 3
	CntReverseSearch statKey = 4
	CntOfGet         statKey = 5
)
View Source 
const (
	CmdNone poolCmd = iota
	CmdGet
	CmdPut
	CmdClose
)
View Source 
const CntOfPersamepleItemPool = 64

count pool per one samepleItemPool

View Source 
const SampleItemOffsetOf = unsafe.Offsetof(EmptySampleHMapEntry.ListHead)
View Source 
const SampleItemSize = unsafe.Sizeof(*EmptySampleHMapEntry)

Variables

View Source 
var (
	ErrItemInvalidAdd      error = NewError(EIItemInvalidAdd, "dd: item is added. but not found", nil)
	ErrBucketNotFound      error = NewError(EBucketNotFound, "bucket is not found", nil)
	ErrBucketAllocatedFail error = NewError(EBucketAllocatedFail, "cannot allocated level bucket buffer", nil)
	ErrBucketAlreadyExit   error = NewError(EBucketAlreadyExist, "bucket is exist alread", nil)
	ErrBucketInvalidOrder  error = NewError(EBucketInvalidOrder, "bucket is invalid order", nil)
	ErrIdxOverflow         error = NewError(EIndexOverflow, "index overflow for slice", nil)
	EPoolAlreadyDeleted    error = NewError(EIPoolAlreadyDeleted, "itemPool already deleted", nil)
	EPoolExpandFail        error = NewError(EIPooExpandFail, "fail expand itemPool", nil)
)
View Source 
var DebugStats map[statKey]int = map[statKey]int{}
View Source 
var (
	EmptyEntryHMap *entryHMap = nil
)
View Source 
var EmptysamepleItemPool *samepleItemPool = (*samepleItemPool)(unsafe.Pointer(uintptr(0)))
View Source 
var EnableStats bool = false
View Source 
var Failreverse uint64 = 0
View Source 
var IsExtended = false
View Source 
var UseGoroutineInPool bool = false

Functions

func ElementOf added in v0.3.1 

func ElementOf(head unsafe.Pointer, offset uintptr) unsafe.Pointer

func IsDebug added in v0.2.4 

func IsDebug() bool

func IsInfo added in v0.6.1 

func IsInfo() bool

func KeyToHash 

func KeyToHash(key interface{}) (uint64, uint64)

func Log added in v0.1.4 

func Log(l LogLevel, s string, args ...interface{})

func MemHash 

func MemHash(data []byte) uint64

func MemHashString 

func MemHashString(str string) uint64

func NewEntryMap 

func NewEntryMap(key, value interface{}) *entryHMap

func PoolCap added in v0.7.1 

func PoolCap(len int) int

func ResetStats added in v0.1.3 

func ResetStats()

func SetLogIO added in v0.1.4 

func SetLogIO(w io.Writer)

func WithBucket 

func WithBucket(b *bucket) func(*hmapMethod)

Types

type CondOfFinder 

type CondOfFinder func(ehead *entryHMap) bool

func CondOfFind 

func CondOfFind(reverse uint64, l sync.Locker) CondOfFinder

type ErrType added in v0.2.4 

type ErrType uint16
const (
	EIItemInvalidAdd ErrType = 1 << iota
	EBucketNotFound
	EBucketAllocatedFail
	EBucketInvalid
	EBucketInvalidOrder
	EBucketAlreadyExist
	EIndexOverflow
	EIPoolAlreadyDeleted
	EIPooExpandFail
)

type Error added in v0.2.4 

type Error struct {
	Type ErrType
	// contains filtered or unexported fields
}

func NewError added in v0.2.4 

func NewError(t ErrType, m string, e error) *Error

func (*Error) Error added in v0.2.4 

func (e *Error) Error() string

func (*Error) ErrorNum added in v0.2.4 

func (e *Error) ErrorNum() uint16

type HMapEntry 

type HMapEntry interface {
	Offset() uintptr
	PtrMapHead() *MapHead
	PtrListHead() *elist_head.ListHead
	HmapEntryFromListHead(*elist_head.ListHead) HMapEntry
	Next() HMapEntry
	Prev() HMapEntry
}

func NilMapEntry added in v0.6.1 

func NilMapEntry() HMapEntry

type HMethodOpt 

type HMethodOpt func(*hmapMethod)

type LevelHead 

type LevelHead list_head.ListHead

type LogLevel added in v0.1.4 

type LogLevel byte
const (
	LogDebug LogLevel = iota
	LogInfo
	LogWarn
	LogError
	LogFatal
)
const CurrentLogLevel LogLevel = LogInfo

const CurrentLogLevel LogLevel = LogDebug

type Map 

type Map struct {
	ItemFn func() MapItem
	// contains filtered or unexported fields
}

Map ... Skip List Map is an ordered and concurrent map. this Map is gourtine safety for reading/updating/deleting, require locking and coordination. This

func New 

func New(opts ...OptHMap) *Map

func NewHMap 

func NewHMap(opts ...OptHMap) *Map

func (*Map) AddLen added in v0.2.1 

func (h *Map) AddLen(inc int64) int64

func (*Map) BackBucket added in v0.2.4 

func (h *Map) BackBucket() (bCur *bucket)

func (*Map) Delete 

func (h *Map) Delete(key interface{}) bool

Delete ... set nil to the key of MapItem. cannot Get entry

func (*Map) DumpBucket 

func (h *Map) DumpBucket(w io.Writer)

func (*Map) DumpBucketPerLevel 

func (h *Map) DumpBucketPerLevel(w io.Writer)

func (*Map) DumpEntry 

func (h *Map) DumpEntry(w io.Writer)

func (*Map) FindBucket added in v0.5.1 

func (h *Map) FindBucket(reverse uint64) (b *bucket)

func (*Map) First added in v0.5.1 

func (h *Map) First() HMapEntry

func (*Map) Get 

func (h *Map) Get(key interface{}) (value interface{}, ok bool)

Get ... return the value for a key, if not found, ok is false

func (*Map) GetByHash added in v0.3.1 

func (h *Map) GetByHash(hash, conflict uint64) (value interface{}, ok bool)

func (*Map) Last added in v0.5.1 

func (h *Map) Last() HMapEntry

func (*Map) Len added in v0.2.1 

func (h *Map) Len() int

func (*Map) LoadItem 

func (h *Map) LoadItem(key interface{}) (item MapItem, success bool)

LoadItem ... return key/value item with embedded-linked-list. if not found, ok is false

func (*Map) LoadItemByHash added in v0.2.1 

func (h *Map) LoadItemByHash(k uint64, conflict uint64) (item MapItem, success bool)

func (*Map) Options 

func (h *Map) Options(opts ...OptHMap) (previouses []OptHMap)

func (*Map) Purge added in v0.7.2 

func (h *Map) Purge(key interface{}) bool

Purge ... key/value entry from map.

func (*Map) Range added in v0.1.2 

func (h *Map) Range(f func(key, value interface{}) bool)

Range ... calls f sequentially for each key and value present in the map. order is reverse key order

func (*Map) RangeItem added in v0.1.2 

func (h *Map) RangeItem(f func(MapItem) bool)

RangeItem ... calls f sequentially for each key and value present in the map. called ordre is reverse key order

func (*Map) SearchKey 

func (h *Map) SearchKey(k uint64, opts ...searchArg) HMapEntry

func (*Map) Set 

func (h *Map) Set(key, value interface{}) bool

Set ... set the value for a key

func (*Map) StoreItem 

func (h *Map) StoreItem(item MapItem) bool

StoreItem ... set key/value item with embedded-linked-list

func (*Map) TestSet added in v0.5.1 

func (h *Map) TestSet(k, conflict uint64, btable *bucket, item MapItem) bool

TestSet ... _set() for Test

type MapHead 

type MapHead struct {
	elist_head.ListHead
	// contains filtered or unexported fields
}
var EmptyMapHead *MapHead = (*MapHead)(unsafe.Pointer(uintptr(0)))

func (*MapHead) ConflictInHamp 

func (mh *MapHead) ConflictInHamp() uint64

func (*MapHead) FromListHead 

func (c *MapHead) FromListHead(l *elist_head.ListHead) elist_head.List

func (*MapHead) IsDeleted added in v0.3.1 

func (mh *MapHead) IsDeleted() bool

func (*MapHead) IsDummy added in v0.3.1 

func (mh *MapHead) IsDummy() bool

func (*MapHead) IsIgnored added in v0.3.1 

func (mh *MapHead) IsIgnored() bool

func (*MapHead) KeyInHmap 

func (mh *MapHead) KeyInHmap() uint64

func (*MapHead) NextWithNil added in v0.1.3 

func (c *MapHead) NextWithNil() *MapHead

func (*MapHead) Offset 

func (mh *MapHead) Offset() uintptr

func (*MapHead) PrevtWithNil added in v0.1.3 

func (c *MapHead) PrevtWithNil() *MapHead

func (*MapHead) PtrListHead 

func (mh *MapHead) PtrListHead() *elist_head.ListHead

type MapItem 

type MapItem interface {
	Key() interface{}   // require order for HMap
	Value() interface{} // require order for HMap
	SetValue(interface{}) bool
	KeyHash() (uint64, uint64)
	Delete()

	HMapEntry
}
var LastItem MapItem = nil

type OptHMap 

type OptHMap func(*Map) OptHMap

func BucketMode 

func BucketMode(mode SearchMode) OptHMap

func ItemFn 

func ItemFn(fn func() MapItem) OptHMap

func MaxPefBucket 

func MaxPefBucket(max int) OptHMap

func UseEmbeddedPool added in v0.5.1 

func UseEmbeddedPool(enable bool) OptHMap

func UsePool added in v0.3.1 

func UsePool(enable bool) OptHMap

type Pool added in v0.3.1 

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

func (*Pool) Get added in v0.3.1 

func (p *Pool) Get(reverse uint64, fn successFn)

func (*Pool) Put added in v0.3.1 

func (p *Pool) Put(item MapItem)

type SampleItem 

type SampleItem struct {
	K string
	V atomic.Value
	MapHead
}
var EmptySampleHMapEntry *SampleItem = (*SampleItem)(unsafe.Pointer(uintptr(0)))

var EmptySampleHMapEntry SampleItem = SampleItem{}

func NewSampleItem added in v0.6.1 

func NewSampleItem(key string, value interface{}) (item *SampleItem)

func SampleItemFromListHead 

func SampleItemFromListHead(head *elist_head.ListHead) *SampleItem

func (*SampleItem) Delete 

func (s *SampleItem) Delete()

func (*SampleItem) HmapEntryFromListHead 

func (s *SampleItem) HmapEntryFromListHead(lhead *elist_head.ListHead) HMapEntry

func (*SampleItem) Key 

func (s *SampleItem) Key() interface{}

func (*SampleItem) KeyHash added in v0.3.1 

func (s *SampleItem) KeyHash() (uint64, uint64)

func (*SampleItem) Next 

func (s *SampleItem) Next() HMapEntry

func (*SampleItem) Offset 

func (s *SampleItem) Offset() uintptr

func (*SampleItem) Prev 

func (s *SampleItem) Prev() HMapEntry

func (*SampleItem) PtrMapHead 

func (s *SampleItem) PtrMapHead() *MapHead

func (*SampleItem) PtrMapeHead 

func (s *SampleItem) PtrMapeHead() *MapHead

func (*SampleItem) SetValue 

func (s *SampleItem) SetValue(v interface{}) bool

func (*SampleItem) Setup added in v0.2.1 

func (s *SampleItem) Setup()

func (*SampleItem) Value 

func (s *SampleItem) Value() interface{}

type SearchMode 

type SearchMode byte
const (
	LenearSearchForBucket SearchMode = iota
	NestedSearchForBucket
	CombineSearch
	CombineSearch2
	CombineSearch3
	CombineSearch4

	NoItemSearchForBucket = 9  // test mode
	FalsesSearchForBucket = 10 // test mode
)

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.