Efficient immutable data types.
frozen is a Go 1.19+ library of immutable, persistent data structures built on hashed array tries (HAT). All mutation operations return a new value that shares structure with the original; no existing value is ever modified. The library uses Go generics throughout.
go get github.com/arr-ai/frozen
An immutable set backed by a hashed array trie.
Key operations: With, Without, Has, Union, Intersection, Difference, SymmetricDifference, Where, Reduce, Reduce2, IsSubsetOf.
Package-level functions: Powerset[T], SetMap[T, U], SetGroupBy[T, K], SetAs[U, T].
import "github.com/arr-ai/frozen"
s := frozen.NewSet(1, 2, 3)
s2 := s.With(4).Without(2) // {1, 3, 4}
fmt.Println(s2.Has(3)) // true
fmt.Println(s2.Count()) // 3
evens := s2.Where(func(n int) bool { return n%2 == 0 }) // {4}
u := s.Union(frozen.NewSet(3, 4, 5)) // {1, 2, 3, 4, 5}
d := s.Difference(frozen.NewSet(2, 3)) // {1}
sum, _ := s.Reduce2(func(a, b int) int { return a + b }) // 6An immutable key-value map backed by a hashed array trie.
Key operations: With, Without, Get, MustGet, GetElse, Has, Keys, Values, Where, Merge, Update, Project.
Package-level functions: MapMap[K, V, U], NewMapFromKeys, NewMapFromGoMap, MapToGoMap.
m := frozen.NewMap(frozen.KV("a", 1), frozen.KV("b", 2))
m2 := m.With("c", 3).Without("a") // (b: 2, c: 3)
if v, ok := m2.Get("b"); ok {
fmt.Println(v) // 2
}
doubled := frozen.MapMap(m, func(k string, v int) int { return v * 2 })
merged := m.Merge(m2, func(k string, a, b int) int { return a + b })A specialised immutable set for integer types, using 64-bit bitmap compression to pack values into cells. More memory-efficient than Set[int] for dense integer ranges.
The integer constraint covers ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr.
Key operations: With, Without, Has, Union, Intersection, Where, Map, IsSubsetOf.
s := frozen.NewIntSet(1, 2, 3, 100, 101)
fmt.Println(s.Has(100)) // true
fmt.Println(s.Count()) // 5
u := s.Union(frozen.NewIntSet(3, 4)) // {1, 2, 3, 4, 100, 101}A constraint interface that types must satisfy to be usable as custom map keys or set elements with value-based equality:
type Key[T any] interface {
value.Equaler[T] // Equal(T) bool
hash.Hashable // Hash(seed uintptr) uintptr
}Set[T] and Map[K, V] themselves implement Key, so they can be nested.
Builders accumulate elements incrementally and are more efficient than repeated With calls when constructing large collections.
// SetBuilder
b := frozen.NewSetBuilder[string](16)
b.Add("x")
b.Add("y")
s := b.Finish() // immutable Set[string]; builder is reset
// MapBuilder
mb := frozen.NewMapBuilder[string, int](16)
mb.Put("a", 1)
mb.Put("b", 2)
m := mb.Finish() // immutable Map[string, int]Finish() returns the immutable result and resets the builder for reuse.
A Set interface for deferred evaluation with memoization. Operations such as Union, Intersection, Difference, Where, and Powerset are composed lazily and only evaluated when elements are accessed. Useful for constructing large set expressions without paying the full construction cost up front.
Relational algebra built on frozen.Map and frozen.Set:
type Tuple = frozen.Map[string, any]
type Relation = frozen.Set[Tuple]Provided operations: New, Join, CartesianProduct, Project, Nest, Unnest.
r := rel.New(
[]string{"name", "age"},
[]any{"alice", 30},
[]any{"bob", 25},
)
names := rel.Project(r, "name")v1.8.0 introduces two optimizations to the HAMT internals:
-
Recursive XOR hash (h0): Every node caches the XOR of its elements' hashes. Set operations that discover mismatched h0 values reject entire subtrees without traversal, turning O(n) comparisons into O(1).
-
Allocation reduction: Hash function caching moved from
sync.Mapto direct function pointers; spine operations batched to reduce intermediate allocations.
Two independently constructed sets with identical elements — the fairest apples-to-apples comparison (no pointer shortcuts).
h0 early rejection: When sets have different content, Equal on 1M-element sets drops from ~25 us to ~50 ns — over 500x faster — because the h0 hash mismatch is detected at the root without any traversal.
Trade-off: Single-element Has is ~20-60% slower due to h0 bookkeeping overhead. The bulk-operation gains more than compensate in typical workloads.
The EqHash[T] interface replaces per-operation function resolution with cached
concrete implementations. Map operations now use H128-native key hashing instead
of double seeded calls. Key improvements (Apple M4 Max, Go 1.25, darwin/arm64):
- Map Merge 1M: 39ms → 18ms (53% faster)
- Map Insert 1M: 1032ns → 700ns (32% faster)
- Set Equal (all variants): 42ns → 26ns (38% faster)
- Set Intersection/Difference (Same/Equal): ~38% faster
- Overall geomean: 19% faster
Full benchstat comparison (before vs after EqHash)
│ before │ after │
│ sec/op │ sec/op vs base │
InsertFrozenMap0-16 42.74n ± ∞ 41.84n ± ∞ ~ (p=0.100)
InsertFrozenMap1k-16 260.7n ± ∞ 263.9n ± ∞ ~ (p=0.400)
InsertFrozenMap1M-16 1032.0n ± ∞ 700.0n ± ∞ ~ (p=0.100)
MergeFrozenMap10-16 630.1n ± ∞ 474.5n ± ∞ ~ (p=0.100)
MergeFrozenMap100-16 6.344µ ± ∞ 4.619µ ± ∞ ~ (p=0.100)
MergeFrozenMap1k-16 81.56µ ± ∞ 52.26µ ± ∞ ~ (p=0.100)
MergeFrozenMap100k-16 9.708m ± ∞ 5.811m ± ∞ ~ (p=0.100)
MergeFrozenMap1M-16 38.97m ± ∞ 18.35m ± ∞ ~ (p=0.100)
SetOps/Equal/1ki/Same-16 43.16n ± ∞ 26.62n ± ∞ ~ (p=0.100)
SetOps/Equal/1Mi/Equal-16 42.18n ± ∞ 26.43n ± ∞ ~ (p=0.100)
SetOps/Intersection/1ki/Same-16 43.62n ± ∞ 27.46n ± ∞ ~ (p=0.100)
SetOps/Intersection/1Mi/Same-16 43.08n ± ∞ 26.82n ± ∞ ~ (p=0.100)
SetOps/Difference/1ki/Same-16 42.91n ± ∞ 26.56n ± ∞ ~ (p=0.100)
SetOps/Difference/1Mi/Same-16 42.30n ± ∞ 26.64n ± ∞ ~ (p=0.100)
geomean 11.73µ 6.533µ -18.67%
Full benchstat comparison (v1.7.0 vs v1.8.0)
Benchmarks on Apple M4 Max, Go 1.23, darwin/arm64. Each row is the median of 6 runs. "Same" = identical pointer, "Equal" = independently built with same elements, "Half" = 50% overlap, "Disjoint" = no overlap.
│ v1.7.0 │ v1.8.0 │
│ sec/op │ sec/op vs base │
SetOps/Equal/1ki/Same 24.46µ ± 7% 11.16µ ± 39% -54.37% (p=0.002)
SetOps/Equal/1ki/Equal 26.027µ ±104% 6.905µ ± 1% -73.47% (p=0.002)
SetOps/Equal/1ki/Half 94.74n ±234% 41.38n ± 56% -56.32% (p=0.002)
SetOps/Equal/1ki/Disjoint 101.50n ± 4% 53.96n ± 6% -46.84% (p=0.002)
SetOps/Equal/1Mi/Same 11.282m ± 88% 6.443m ± 21% -42.90% (p=0.002)
SetOps/Equal/1Mi/Equal 24.060m ± 8% 5.238m ± 21% -78.23% (p=0.002)
SetOps/Equal/1Mi/Half 32035.50n ± 25% 51.16n ± 10% -99.84% (p=0.002)
SetOps/Equal/1Mi/Disjoint 24611.00n ± 22% 46.48n ± 12% -99.81% (p=0.002)
SetOps/Intersection/1ki/Same 69.66µ ± 11% 34.59µ ± 6% -50.34% (p=0.002)
SetOps/Intersection/1ki/Equal 68.20µ ± 8% 34.56µ ± 4% -49.33% (p=0.002)
SetOps/Intersection/1ki/Half 48.33µ ± 1% 45.75µ ± 28% -5.32% (p=0.002)
SetOps/Intersection/1ki/Disjoint 34.84µ ± 2% 25.27µ ± 6% -27.48% (p=0.002)
SetOps/Intersection/1Mi/Same 30.51m ± 18% 21.48m ± 14% -29.60% (p=0.002)
SetOps/Intersection/1Mi/Equal 43.28m ± 19% 23.68m ± 17% -45.29% (p=0.002)
SetOps/Intersection/1Mi/Half 37.91m ± 10% 18.81m ± 19% -50.37% (p=0.002)
SetOps/Intersection/1Mi/Disjoint 27.347m ± 12% 8.694m ± 87% -68.21% (p=0.002)
SetOps/Difference/1ki/Same 81.38µ ± 26% 19.01µ ± 7% -76.64% (p=0.002)
SetOps/Difference/1ki/Equal 67.11µ ± 18% 19.17µ ± 3% -71.43% (p=0.002)
SetOps/Difference/1ki/Half 58.90µ ± 4% 34.58µ ± 19% -41.29% (p=0.002)
SetOps/Difference/1ki/Disjoint 37.50µ ± 9% 37.07µ ± 7% ~ (p=0.937)
SetOps/Difference/1Mi/Same 118.701m ± 13% 8.861m ± 17% -92.54% (p=0.002)
SetOps/Difference/1Mi/Equal 154.07m ± 14% 10.77m ± 18% -93.01% (p=0.002)
SetOps/Difference/1Mi/Half 156.68m ± 15% 15.01m ± 8% -90.42% (p=0.002)
SetOps/Difference/1Mi/Disjoint 109.13m ± 18% 11.78m ± 25% -89.21% (p=0.002)
SetOps/SubsetOf/1ki/Same 42.39µ ± 10% 12.34µ ± 10% -70.89% (p=0.002)
SetOps/SubsetOf/1ki/Equal 40.50µ ± 2% 13.27µ ± 4% -67.24% (p=0.002)
SetOps/SubsetOf/1ki/Half 144.1n ± 2% 150.5n ± 24% +4.51% (p=0.009)
SetOps/SubsetOf/1ki/Disjoint 143.8n ± 3% 165.7n ± 21% +15.19% (p=0.002)
SetOps/SubsetOf/1Mi/Same 20.894m ± 18% 9.031m ± 13% -56.77% (p=0.002)
SetOps/SubsetOf/1Mi/Equal 26.378m ± 19% 9.771m ± 31% -62.96% (p=0.002)
SetOps/SubsetOf/1Mi/Half 30.88µ ± 36% 32.31µ ± 7% ~ (p=0.485)
SetOps/SubsetOf/1Mi/Disjoint 27.86µ ± 8% 27.40µ ± 21% ~ (p=0.240)
SetOps/Has/1ki/Hit 41.00n ± 5% 65.93n ± 2% +60.82% (p=0.002)
SetOps/Has/1ki/Miss 39.31n ± 1% 63.00n ± 1% +60.28% (p=0.002)
SetOps/Has/1Mi/Hit 204.8n ± 3% 244.8n ± 10% +19.51% (p=0.002)
SetOps/Has/1Mi/Miss 139.3n ± 7% 210.9n ± 19% +51.35% (p=0.002)
geomean 110.9µ 38.15µ -65.61%
Legacy insertion benchmarks (pre-generics)
These benchmarks were recorded before the generics rewrite. Relative ordering remains indicative but absolute numbers will differ on current hardware and Go versions.
| Benchmark | Type |
|---|---|
| MapInt | map[int]int |
| MapInterface | map[any]any |
| FrozenMap | frozen.Map |
| FrozenNode | frozen.node |
| SetInt | set = map[int]struct{} |
| SetInterface | set = map[any]struct{} |
| FrozenSet | frozen.Set |
$ go test -run ^$ -cpuprofile cpu.prof -memprofile mem.prof -benchmem -bench ^BenchmarkInsert .
goos: linux
goarch: amd64
pkg: github.com/arr-ai/frozen
BenchmarkInsertMapInt0-24 8532830 175 ns/op 72 B/op 0 allocs/op
BenchmarkInsertMapInt1k-24 10379329 164 ns/op 60 B/op 0 allocs/op
BenchmarkInsertMapInt1M-24 6760242 185 ns/op 78 B/op 0 allocs/op
BenchmarkInsertMapInterface0-24 3579843 348 ns/op 152 B/op 2 allocs/op
BenchmarkInsertMapInterface1k-24 3675631 365 ns/op 148 B/op 2 allocs/op
BenchmarkInsertMapInterface1M-24 6517272 354 ns/op 115 B/op 2 allocs/op
BenchmarkInsertFrozenMap0-24 5443401 225 ns/op 240 B/op 6 allocs/op
BenchmarkInsertFrozenMap1k-24 2553954 446 ns/op 635 B/op 10 allocs/op
BenchmarkInsertFrozenMap1M-24 1263691 960 ns/op 954 B/op 13 allocs/op
BenchmarkInsertFrozenNode0-24 8220901 141 ns/op 144 B/op 4 allocs/op
BenchmarkInsertFrozenNode1k-24 3294789 388 ns/op 539 B/op 8 allocs/op
BenchmarkInsertFrozenNode1M-24 1316443 871 ns/op 858 B/op 11 allocs/op
BenchmarkInsertSetInt0-24 12816358 155 ns/op 29 B/op 0 allocs/op
BenchmarkInsertSetInt1k-24 12738687 155 ns/op 29 B/op 0 allocs/op
BenchmarkInsertSetInt1M-24 7613054 171 ns/op 39 B/op 0 allocs/op
BenchmarkInsertSetInterface0-24 5121948 302 ns/op 58 B/op 1 allocs/op
BenchmarkInsertSetInterface1k-24 5051988 303 ns/op 58 B/op 1 allocs/op
BenchmarkInsertSetInterface1M-24 3172472 329 ns/op 62 B/op 1 allocs/op
BenchmarkInsertFrozenSet0-24 5400745 236 ns/op 296 B/op 6 allocs/op
BenchmarkInsertFrozenSet1k-24 2460313 512 ns/op 787 B/op 11 allocs/op
BenchmarkInsertFrozenSet1M-24 1132215 1046 ns/op 1106 B/op 14 allocs/op
PASS
ok github.com/arr-ai/frozen 65.909s