tree a2b0eb774d2358b2c31f3cde7dc6cad011ae7459
parent 68c0ad3a689833344fada8acc1f36a06c343caa4
author Michael Anthony Knyszek <mknyszek@google.com> 1711156863 +0000
committer Gopher Robot <gobot@golang.org> 1713475209 +0000

internal/concurrent: add HashTrieMap

This change adds a concurrent hash-trie map implementation to the
standard library in the new internal/concurrent package, intended to
hold concurrent data structures. (The name comes from how Java names
their concurrent data structure library in the standard library.)

This data structure is created specially for the upcoming unique
package. It is built specifically around frequent successful lookups and
comparatively rare insertions and deletions.

A valid question is whether this is worth it over a simple locked map.
Some microbenchmarks in this new package show that yes, this extra
complexity appears to be worth it.

Single-threaded performance for LoadOrStore is comparable to a locked
map for a map with 128k small string elements. The map scales perfectly
up to 24 cores for Loads, which is the maximum available parallelism
on my machine. LoadOrStore operations scale less well. Small maps will
have a high degree of contention, but for the unique library, small maps
are very unlikely to stay small if there are a lot of inserts, since
they have a full GC cycle to grow.

For #62483.

Change-Id: I38e5ac958d19ebdd0c8c02e36720bb3338fe2e35
Reviewed-on: https://go-review.googlesource.com/c/go/+/573956
Reviewed-by: David Chase <drchase@google.com>
Auto-Submit: Michael Knyszek <mknyszek@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>