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.NewWithFill(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: 13th Gen Intel(R) Core(TM) i7-13700K
BenchmarkStore/intmap-24 144682518 8.203 ns/op 0 B/op 0 allocs/op
BenchmarkStore/sync-24 47746893 24.78 ns/op 0 B/op 0 allocs/op
BenchmarkStore/stdmap-24 65009140 17.73 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/intmap-0%-24 40558078 28.98 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/sync-0%-24 36516896 31.53 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/stdmap-0%-24 76847426 15.57 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/intmap-10%-24 40846196 28.31 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/sync-10%-24 37622625 31.21 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/stdmap-10%-24 69917145 16.90 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/intmap-50%-24 52405636 21.62 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/sync-50%-24 44567251 25.75 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/stdmap-50%-24 50478930 23.68 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/intmap-90%-24 140594277 8.486 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/sync-90%-24 83630574 14.40 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/stdmap-90%-24 69522844 17.17 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/intmap-100%-24 189147504 6.271 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/sync-100%-24 88044195 13.58 ns/op 0 B/op 0 allocs/op
BenchmarkLoad/stdmap-100%-24 78736231 15.12 ns/op 0 B/op 0 allocs/op
Documentation
¶
Index ¶
- type Map
- func (m *Map) Capacity() int
- func (m *Map) Clear()
- 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, val uint32) bool)
- func (m *Map) RangeEach(fn func(key, val uint32))
- func (m *Map) RangeErr(fn func(key, val uint32) error) error
- func (m *Map) Store(key, val uint32)
- type 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)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map struct {
// contains filtered or unexported fields
}
Map is a contiguous hash table with interleaved key/value slots.
func NewWithFill ¶ added in v1.5.0
New allocates a map sized for at least `size` entries.
func (*Map) Capacity ¶ added in v1.4.1
Capacity returns the maximum number of entries before resize.
func (*Map) Clear ¶ added in v1.4.0
func (m *Map) Clear()
Clear removes all key/value pairs from the map.
func (*Map) Load ¶
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) RangeEach ¶ added in v1.3.0
RangeEach visits every key/value pair without early‑exit capability.
type Sync ¶ added in v1.1.0
type Sync struct {
// contains filtered or unexported fields
}
Sync is a thread-safe, map-like data-structure for int64s
func NewSync ¶ added in v1.1.0
NewSync returns a thread-safe map initialized with n spaces and uses the stated fillFactor. The map will grow as needed.
func NewSyncWithFill ¶ added in v1.5.0
NewSyncWithFill returns a thread-safe map initialized with n spaces and uses the stated fillFactor. The map will grow as needed.
func (*Sync) Load ¶ added in v1.1.0
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 ¶ added in v1.1.0
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.
Source Files