intmap

README

intmap

Overview

Package intmap implements a fast integer keyed map. Map data is kept densely packed in order to improve data locality.

Set and Get operations are consistently faster than the builtin map[int]interface{}: Get takes from 25 to 50% less time, depending on CPU architecture and map size. On some CPUs like an AMD FX, there is even an actual drop off point in map size (~16384) where the builtin map gets slightly faster.

Benchmark sample (*Builtin are performed using a regular map[int]interface{}):

BenchmarkIntMapSet-6            28105802                37.53 ns/op
BenchmarkBuiltinMapSet-6        21551445                53.44 ns/op
BenchmarkIntMapGet-6            35170137                33.10 ns/op
BenchmarkBuiltinMapGet-6        26973751                44.79 ns/op
BenchmarkIntMapDelete-6         33600421                32.16 ns/op
BenchmarkBuiltinMapDelete-6     38036679                28.68 ns/op

The delete test is wrong since we end up deleting millions of non-existent keys, which is not a typical use case. Regardless, deletes are slower than with the builtin map.

Internals

The implementation is based on http://java-performance.info/implementing-world-fastest-java-int-to-int-hash-map/.

The stored values can be of any type.

Documentation

Overview

Package intmap implements a fast integer keyed map. Map data is kept densely packed in order to improve data locality.

Set and Get operations are consistently faster than the builtin map[int]interface{}: Get takes from 25 to 50% less time, depending on CPU architecture and map size. On some CPUs like an AMD FX, there is even an actual drop off point in map size (~16384) where the builtin map gets slightly faster.

Benchmark sample (*Builtin are performed using a regular map[int]interface{}):

BenchmarkIntMapSet-6            28105802                37.53 ns/op
BenchmarkBuiltinMapSet-6        21551445                53.44 ns/op
BenchmarkIntMapGet-6            35170137                33.10 ns/op
BenchmarkBuiltinMapGet-6        26973751                44.79 ns/op
BenchmarkIntMapDelete-6         33600421                32.16 ns/op
BenchmarkBuiltinMapDelete-6     38036679                28.68 ns/op

The delete test is wrong since we end up deleting millions of non-existent keys, which is not a typical use case. Regardless, deletes are slower than with the builtin map.

Internals

The implementation is based on http://java-performance.info/implementing-world-fastest-java-int-to-int-hash-map/.

The stored values can be of any type.

Index

• type Iterator
  • func (i *Iterator[V]) HasNext() bool
  • func (i *Iterator[V]) Next() (key int, value V)
• type KeyValue
• type Map
  • func New[V any](capacity int, fillratio float32) *Map[V]
  • func (m *Map[V]) Delete(key int) bool
  • func (m *Map[V]) Get(key int) (v V, ok bool)
  • func (m *Map[V]) Init(capacity int, fillratio float32)
  • func (m *Map[V]) Iterator() *Iterator[V]
  • func (m *Map[V]) Keys() []int
  • func (m *Map[V]) Len() int
  • func (m *Map[V]) Set(key int, value V)

Types

type Iterator

type Iterator[V any] struct {
	// contains filtered or unexported fields
}

Iterator represents an iterator over a map.

func (*Iterator[V]) HasNext

func (i *Iterator[V]) HasNext() bool

HasNext returns true if there are any keys left to read.

func (*Iterator[V]) Next

func (i *Iterator[V]) Next() (key int, value V)

Next returns the next key/value pair. Calling Next several times in a row without calling HasNext in between will yield the same result.

type KeyValue

type KeyValue[V any] struct {
	Key   int
	Value V
}

KeyValue wraps a key-value pair.

type Map

type Map[V any] struct {
	// contains filtered or unexported fields
}

Map is a fast int to interface{} map. Map data is kept densely packed in order to improve data locality.

The primary use case for this implementation is that of small maps (regardless of the size of the key set) with almost no deletions.

A Map can be used directly: the start capacity will be set to 8 entries and the fill ratio 87.5%. If the rough map size is known in advance, it is however preferable to initialize it with New or Init for better performance, especially when initializing a large number of maps.

When the size of a Map grows over the fill ratio, its capacity is doubled. Maps are never shrunk when deleting keys.

func New

func New[V any](capacity int, fillratio float32) *Map[V]

New returns a new Map initialized with the given starting capacity and fill ratio.

See Map.Init for more details about the capacity and fillratio parameters.

func (*Map[V]) Delete

func (m *Map[V]) Delete(key int) bool

Delete deletes the given key and returns true if the key was present in the map.

func (*Map[V]) Get

func (m *Map[V]) Get(key int) (v V, ok bool)

Get returns the value associated with the given key and ok set to true if the key exists. If the keys does not exist, it returns the zero value for the Value type and false.

func (*Map[V]) Init

func (m *Map[V]) Init(capacity int, fillratio float32)

Init initializes the Map with the given initial capacity and fill ratio.

If the Map already contains data, it will be reset.

The capacity is rounded up to the next exponent of two. Values < 2 are rounded up to 2. It must be less than or equal to 0x40000000 for 32 bits ints and 0x4000000000000000 for 64 bits ints.

The fill ratio should be between 0 (0%) and 1 (100%) exclusive. Values out of this range are silently rounded to the lowest or largest possible value. When the size of a Map grows over the fill ratio, its capacity is doubled.

The fill ratio will be rounded as follows:

threshold := int(float32(capacity) * fillratio)
if threshold <= 0 {
    threshold = 1
} else if threshold >= capacity {
    threshold = capacity - 1
}
fillratio_rounded := float32(threshold) / float32(capacity)

i.e. requesting a Map of initial capacity 2 with any fill ratio > 0.5 will result in a real fill ratio of 0.5 due to integer rounding.

func (*Map[V]) Iterator

func (m *Map[V]) Iterator() *Iterator[V]

Iterator returns an iterator over the map's key/value pairs.

for i := m.Iterator(); i.HasNext(); {
	k, v := i.Next()
	fmt.Printf("m[%v] = %v\n", k, v)
}

While iterating over a map, deleting the value of the last key returned by Next is supported as well of changing the value of any existing key. Inserting new keys or deleting any other keys will break the iterator.

func (*Map[V]) Keys

func (m *Map[V]) Keys() []int

Keys returns an unordered slice of the map keys.

func (*Map[V]) Len

func (m *Map[V]) Len() int

Len returns the number if keys set in the map.

func (*Map[V]) Set

func (m *Map[V]) Set(key int, value V)

Set sets or resets the value for the given key.