README
¶
Go map
author Harald Rudell holds M.Sc.EE and M.Sc.BA&E.
5 years Go, 6 years Java, 8 years Node.js/React
Test of complexity and performance of Go map.
Practical conclusions:
- Assign performance worsens 50% comparing map length 1 to 1M.
- For 1M map, 14M assignments per second is max for this hardware and software combination. This is when one processor core is doing nothing else.
- For 1M map, retrieve is 41 ns for this hardware and software combination
- For the retrieve case, complexity is worse than log n, better than nlogn
Other conclusions:
- A hash-map can theoretically obtain O(1) with high probability, ie. any size map exhibiting the same, constant access latency. Depending on hash table implementation complexity may be O(n), O(n) / O(log n), or O(log n)
- Go authors do not make guarantees of Go map performance. However, sync.Map, a concurrency wrapper around Go map, advertises “amortized-constant-time loads, stores, and deletes.” Amortized means constant time with occasional operations being slower
- Go map is an array of 8-entry buckets with further resolution using linked list. 32/64-bit aes hash is used for processors that support it, memhash otherwise
- hash tables are, on average, the most efficient lookup structure, a space-time trade-off compared to array access
- A common complexity for a map designed for large lengths is O(log32 n) from 32-ary trees, ie a tree with 32 children per node. Such trees are O(log n) but often advertised as “effectively constant” time
- Further study is to compare the Go map to a 32-ary hash-map and a larger-bucket hash-map as well as any concurrent map
Go Facts was published on March 14, 2023, its souce code under ISC license.
© 2023–present Harald Rudell <[email protected]> (https://haraldrudell.github.io/haraldrudell/)
Appendix
Data was generated by the Go Benchmarks in this repository, on Go 1.20.1 on a macOS 13.2.1 Apple MacBook Pro.
| Operation | map Size | latency, ns | operations / s |
|---|---|---|---|
| Assign | 1 | 46.21 ± 6% | 21.65M ± 6% |
| 1k | 46.06 ± 4% | 21.71M ± 4% | |
| 10k | 45.90 ± 2% | 21.79M ± 2% | |
| 100k | 55.40 ± 1% | 18.05M ± 1% | |
| 1M | 69.49 ± 1% | 14.39M ± 1% | |
| Retrieve | 1 | 2.680 ± 2% | 373.1M ± 2% |
| 1k | 6.777 ± 7% | 147.6M ± 7% | |
| 10k | 20.48 ± 1% | 48.82M ± 1% | |
| 100k | 24.93 ± 3% | 40.11M ± 3% | |
| 1M | 40.94 ± 8% | 24.43M ± 7% | |
| Delete | 1 | 10.02 ± 1% | 99.78M ± 1% |
| 1k | 31.00 ± 1% | 32.26M ± 1% | |
| 10k | 33.60 ± 1% | 29.76M ± 1% | |
| 100k | 37.33 ± 1% | 26.79M ± 1% | |
| 1M | 59.03 ± 2% | 16.94M ± 2% | |
| Range | 1 | 28.51 ± 1% | 35.08M ± 1% |
| 1k | 8.928µ ± 1% | 112.0k ± 1% | |
| 10k | 83.42µ ± 0% | 11.99k ± 0% | |
| 100k | 792.2µ ± 1% | 1.262k ± 1% | |
| 1M | 9.070m ± 1% | 110.2 ± 0% |
© 2023–present Harald Rudell <[email protected]> (https://haraldrudell.github.io/haraldrudell/)
Documentation
¶
Index ¶
- Constants
- type GoMapTester
- func (f *GoMapTester) CloneIntMapToSlice(m map[int]int, mapList []map[int]int, remaining int)
- func (f *GoMapTester) GeneratedKeyCount() (count int)
- func (f *GoMapTester) IntKeys(length int, series int) (keys []int)
- func (f *GoMapTester) PopulateIntMap(m map[int]int, length int)
- func (f *GoMapTester) SetSeriesInt(keys []int, series int)
- func (f *GoMapTester) SubBenchmarkList() (sb []SubBenchmark)
- type SubBenchmark
Constants ¶
View Source
const ( TgmRetrieveSeries = 0 // the int key series for retrieve keys TgmAssignSeries = 1 // the int key series for assign keys that are not among retrieve keys )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type GoMapTester ¶
type GoMapTester struct {
// contains filtered or unexported fields
}
func NewGoMapTester ¶
func NewGoMapTester() (goMapTester *GoMapTester)
NewGoMapTester returns an object with sub-benchmarks and helper methods
func (*GoMapTester) CloneIntMapToSlice ¶
CloneIntMapToSlice populates mapList with maps.Clone of m but not more maps than remaining
func (*GoMapTester) GeneratedKeyCount ¶
func (f *GoMapTester) GeneratedKeyCount() (count int)
GeneratedKeyCount return how many keys are available
func (*GoMapTester) IntKeys ¶
func (f *GoMapTester) IntKeys(length int, series int) (keys []int)
IntKeys generate keys in random order
- length is how many keys to return. length keys are returned though keys exist for the largest sub-benchmark, typically 1M
- To avoid slow benchmarks, do not request more than 1M keys. GeneratedKeyCount returns how many keys exist after the first Keys invocation.
- series is key series, read keys are normally 0
- key of different series are never the same. series allows to quickly generating keys that are not present in series 0
- generating 1M keys is 83 ms
- shuffle 1M keys is 10 ms
- setSeries 1M keys: 73 ms
func (*GoMapTester) PopulateIntMap ¶
func (f *GoMapTester) PopulateIntMap(m map[int]int, length int)
PopulateIntMap fills map m with length elements
func (*GoMapTester) SetSeriesInt ¶
func (f *GoMapTester) SetSeriesInt(keys []int, series int)
SetSeriesInt modifies keys to be of series series
- series >= 0, <=9
- setSeries 1M keys: 1 ms
func (*GoMapTester) SubBenchmarkList ¶
func (f *GoMapTester) SubBenchmarkList() (sb []SubBenchmark)
SubbenchmarkList returns an iterable benchmark list for map lengths 1…1M
type SubBenchmark ¶
type SubBenchmark struct {
Name string // Name is the name of the sub-benchmark: "10k"
Length int // Length is the initial number of elements of the map being tested
}
SubBenchmark is used to specify sub-benchmarks for the Go map benchmark
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.