An implementation of ordered map in Go. An ordered map preserves the original insertion order when iterating.
It's implemented by wrapping a map and a
doubly linked list.
The interface is intentionally kept the same with sync.Map to be used
interchangeably (except with added generics support).
This package comes with benchmark test to test against
builtin map and sync.Map:
$ go test -bench .
goos: linux
goarch: amd64
pkg: go.yhsif.com/orderedmap
cpu: 12th Gen Intel(R) Core(TM) i5-1235U
BenchmarkMap/DeleteEmpty/builtin-12 1000000000 1.067 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/sync-12 1000000000 1.089 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/ordered-12 10550479 107.1 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/builtin-12 934932499 1.165 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/sync-12 1000000000 1.144 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/ordered-12 20735286 56.56 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store1/builtin-12 157484062 7.507 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store1/sync-12 4521426 268.2 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store1/ordered-12 9733495 122.5 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Store2/builtin-12 151412253 7.859 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store2/sync-12 4417717 264.8 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store2/ordered-12 10051618 121.7 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Update1/builtin-12 161776555 7.772 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Update1/sync-12 4492196 301.7 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Update1/ordered-12 7688208 147.1 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Load1/builtin-12 436247556 2.537 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/sync-12 425829909 4.240 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/ordered-12 17000335 64.42 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/builtin-12 130940556 8.450 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/sync-12 602772472 3.151 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/ordered-12 15910669 71.54 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreStore/builtin-12 67150718 15.16 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreStore/sync-12 7958462 187.2 ns/op 360 B/op 8 allocs/op
BenchmarkLoadOrStoreStore/ordered-12 6706869 184.9 ns/op 416 B/op 5 allocs/op
BenchmarkLoadOrStoreLoad/builtin-12 470602132 2.529 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreLoad/sync-12 75306667 21.58 ns/op 32 B/op 2 allocs/op
BenchmarkLoadOrStoreLoad/ordered-12 8332143 136.6 ns/op 0 B/op 0 allocs/op
BenchmarkStoreThenDelete/builtin-12 55998295 21.19 ns/op 0 B/op 0 allocs/op
BenchmarkStoreThenDelete/sync-12 1961560 670.6 ns/op 346 B/op 8 allocs/op
BenchmarkStoreThenDelete/ordered-12 3997981 293.8 ns/op 78 B/op 1 allocs/op
BenchmarkRange/10/builtin-12 12832806 85.99 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/sync-12 73554632 26.04 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/ordered-12 1466373 756.6 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/builtin-12 1762689 667.0 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/sync-12 7852339 264.1 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/ordered-12 152163 6690 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/builtin-12 118522 8893 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/sync-12 682383 2591 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/ordered-12 16834 64454 ns/op 0 B/op 0 allocs/op
PASS
ok go.yhsif.com/orderedmap 64.694s
Note that for the benchmark tests,
sync and ordered are parallel benchmarks while builtin are sequential.