intmap

README

Uint32-to-Uint32 Map

This repository contains an implementation of uint32-to-uint32 map which is ~20-50% faster than Go standard map for the same types (see benchmarks below). The code was based of Brent Pedersen's intintmap and the main logic remains intact, with some bug fixes and improvements of the API itself. The map is backed by a single array which interleaves keys and values to improve data locality.

Usage

// Create a new map with capacity of 1024 (resizeable) and 90% desired fill rate
m := intmap.New(1024, 0.90)

// Store a few key/value pairs
m.Store(1, 100)
m.Store(2, 200)

// Load them
v, ok := m.Load(1)
v, ok := m.Load(2)

// Delete keys
m.Delete(1)
m.Delete(2)

Benchmarks

Looking at the benchmarks agains the standard Go map, this map should perform roughly 20-50% better depending on the conditions.

cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkStore/intmap-8                 14422464                81.09 ns/op            0 B/op          0 allocs/op
BenchmarkStore/sync-8                   10812642                93.62 ns/op            0 B/op          0 allocs/op
BenchmarkStore/stdmap-8                 10179489               114.8 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/intmap-0%-8               10622955               108.6 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/sync-0%-8                  9956158               115.7 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/stdmap-0%-8               10334260               108.4 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/intmap-10%-8              10721809               105.1 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/sync-10%-8                 9463400               111.8 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/stdmap-10%-8              10433720               110.7 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/intmap-50%-8              12272485                88.29 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/sync-50%-8                11352820                91.41 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/stdmap-50%-8              10265517               111.1 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/intmap-90%-8              15370150                66.75 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/sync-90%-8                17687307                69.72 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/stdmap-90%-8              10236068               112.2 ns/op             0 B/op          0 allocs/op
BenchmarkLoad/intmap-100%-8             20562958                58.48 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/sync-100%-8               18913777                62.92 ns/op            0 B/op          0 allocs/op
BenchmarkLoad/stdmap-100%-8              9638715               109.7 ns/op             0 B/op          0 allocs/op

Documentation

Index

• type Map
  • func New(size int, fillFactor float64) *Map
  • func (m *Map) Clone() *Map
  • func (m *Map) Count() int
  • func (m *Map) Delete(key uint32)
  • func (m *Map) Load(key uint32) (uint32, bool)
  • func (m *Map) Range(fn func(key, value uint32) bool)
  • func (m *Map) RangeEach(fn func(key, value uint32))
  • func (m *Map) RangeErr(fn func(key, value uint32) error) error
  • func (m *Map) Store(key, val uint32)
• type Sync
  • func NewSync(size int, fillFactor float64) *Sync
  • func (m *Sync) Count() (count int)
  • func (m *Sync) Delete(key uint32)
  • func (m *Sync) Load(key uint32) (value uint32, ok bool)
  • func (m *Sync) LoadOrStore(key uint32, fn func() uint32) (value uint32, loaded bool)
  • func (m *Sync) Range(f func(key, value uint32) bool)
  • func (m *Sync) Store(key, val uint32)

Types

type Map

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

Map is a map-like data-structure for int64s

func New

func New(size int, fillFactor float64) *Map

New returns a map initialized with n spaces and uses the stated fillFactor. The map will grow as needed.

func (*Map) Clone

func (m *Map) Clone() *Map

Clone returns a copy of the map.

func (*Map) Count

func (m *Map) Count() int

Count returns number of key/value pairs in the map.

func (*Map) Delete

func (m *Map) Delete(key uint32)

Delete deletes the value for a key.

func (*Map) Load

func (m *Map) Load(key uint32) (uint32, bool)

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 (*Map) Range

func (m *Map) Range(fn func(key, value uint32) bool)

Range calls f sequentially for each key and value present in the map. If fn returns false, range stops the iteration.

func (*Map) RangeEach

func (m *Map) RangeEach(fn func(key, value uint32))

RangeEach calls f sequentially for each key and value present in the map.

func (*Map) RangeErr

func (m *Map) RangeErr(fn func(key, value uint32) error) error

RangeErr calls f sequentially for each key and value present in the map. If fn returns error, range stops the iteration.

func (*Map) Store

func (m *Map) Store(key, val uint32)

Store sets the value for a key.

type Sync

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

Sync is a thread-safe, map-like data-structure for int64s

func NewSync

func NewSync(size int, fillFactor float64) *Sync

NewSync returns a thread-safe map initialized with n spaces and uses the stated fillFactor. The map will grow as needed.

func (*Sync) Count

func (m *Sync) Count() (count int)

Count returns number of key/value pairs in the map.

func (*Sync) Delete

func (m *Sync) Delete(key uint32)

Delete deletes the value for a key.

func (*Sync) Load

func (m *Sync) Load(key uint32) (value uint32, ok bool)

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 (*Sync) LoadOrStore

func (m *Sync) LoadOrStore(key uint32, fn func() uint32) (value uint32, loaded bool)

LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value returned by the handler. The loaded result is true if the value was loaded, false if stored.

func (*Sync) Range

func (m *Sync) Range(f func(key, value uint32) bool)

Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

func (*Sync) Store

func (m *Sync) Store(key, val uint32)

Store sets the value for a key.