types

This repository contains production-ready reusable types implemented in Go.

Each type in this repository is expected to be:

• covered by unit tests
• covered by benchmarks
• checked under the race detector when concurrency matters
• designed for predictable behavior in production code

Implemented

• result: a Rust-inspired Result[T] type built around Go's error
• lru_cache: two production-ready generic LRU cache implementations
• btree: a generic in-memory B-tree (sorted map) with free-list and custom comparator

Planned

• option
• either
• validated

B-tree

btree.BTree[K, V] is a generic in-memory B-tree (sorted map) with a configurable degree and a custom comparator. Nodes are pooled in a free-list for allocation reuse, and all slices inside nodes are pre-sized to their maximum capacity so no slice growth occurs during inserts.

API

type BTree[K comparable, V any] struct { ... }

func New[K comparable, V any](degree int, less func(K, K) bool) *BTree[K, V]
func NewOrdered[K cmp.Ordered, V any](degree int) *BTree[K, V]

func (t *BTree[K, V]) Put(key K, value V) (V, bool)   // returns old value if replaced
func (t *BTree[K, V]) Get(key K) (V, bool)
func (t *BTree[K, V]) Delete(key K) (V, bool)          // returns deleted value
func (t *BTree[K, V]) Has(key K) bool
func (t *BTree[K, V]) Len() int
func (t *BTree[K, V]) Min() (K, V, bool)
func (t *BTree[K, V]) Max() (K, V, bool)
func (t *BTree[K, V]) Range(lo, hi K, fn func(K, V) bool)  // iterate [lo, hi]
func (t *BTree[K, V]) All(fn func(K, V) bool)               // iterate all in order
func (t *BTree[K, V]) Clear()

Complexity

Operation	Complexity
Get	O(log_t n)
Put	O(log_t n)
Delete	O(log_t n)
Min/Max	O(log_t n)
Range	O(log_t n + k) where k = results in range
Len	O(1)
Clear	O(1)

Why B-tree over balanced BST

• Cache locality: each node holds multiple keys, reducing pointer chasing
• Fewer allocations: one node = dozens of entries, so far fewer heap objects than a BST with one entry per node
• Shallower tree: height is O(log_t n) instead of O(log_2 n)
• Simpler balancing: splits and merges are local, no rotations needed

Use cases

• Time-series index: store events keyed by timestamp, iterate in order, get oldest/newest in O(log n)
• Range queries: find all entries between two keys efficiently
• Sorted map with eviction: use Min() to find and evict the oldest/smallest entry
• Custom ordering: struct keys with composite comparators (region + ID, priority + timestamp)

Example

package main

import (
    "fmt"
    "types/btree"
)

func main() {
    // Built-in ordered types (int, string, ...)
    tree := btree.NewOrdered[int, string](32)
    tree.Put(3, "c")
    tree.Put(1, "a")
    tree.Put(2, "b")

    tree.All(func(k int, v string) bool {
        fmt.Println(k, v)
        return true
    })
    // Output: 1 a  2 b  3 c

    // Custom comparator for struct keys
    type Key struct{ Region string; ID int }
    routes := btree.New[Key, string](8, func(a, b Key) bool {
        if a.Region != b.Region { return a.Region < b.Region }
        return a.ID < b.ID
    })
    routes.Put(Key{"us", 2}, "us-2")
    routes.Put(Key{"eu", 1}, "eu-1")
}

B-tree test status

• go test ./btree: passed
• go test -race ./btree: passed
• unit tests: 17
• benchmark functions: 9

B-tree microbenchmarks

Measured on 2026-06-12 with go1.26, darwin/arm64, Apple M5.

Benchmark	ns/op	B/op	allocs/op
BenchmarkGetHit	34.71	0	0
BenchmarkGetMiss	33.78	0	0
BenchmarkPutNew	54.87	52	0
BenchmarkPutExisting	6.849	0	0
BenchmarkDelete	9340	0	0
BenchmarkMin	1.628	0	0
BenchmarkAll	13213	0	0
BenchmarkRange	7083	0	0
BenchmarkMixedWorkload	58.64	0	0

Interpretation:

• Get, Put (existing), Delete, Min, iteration, and mixed workloads are all allocation-free in steady state
• PutNew shows amortized bytes per operation from node creation during growth, but the free-list ensures nodes are reused once the tree reaches steady size
• Delete benchmark deletes 256 keys per iteration; per-key cost is ~36 ns with 0 allocs

Result

Result[T] is designed to feel familiar if you use Rust, while still integrating cleanly with Go's (T, error) style.

Because Go does not support methods that introduce new type parameters, type-changing combinators such as Map, And, and AndThen are exposed as package functions.

Go style vs Result style

Go style is still the default for simple code:

value, err := parseUserIDGo(input)
if err != nil {
	return err
}

Result[T] becomes useful when you want composable chains:

value, err := strconv.Atoi(input)
r := result.From(value, err).MapErr(func(err error) error {
	return fmt.Errorf("parse: %w", err)
})

out := result.AndThen(r, func(v int) result.Result[int] {
	if v <= 0 {
		return result.Err[int](errors.New("user id must be positive"))
	}
	return result.Ok(v)
})

The repository keeps both styles available, and From is the bridge from (T, error) to Result[T].

package main

import (
	"errors"
	"fmt"

	"types/result"
)

func parsePositive(v int) result.Result[int] {
	if v < 0 {
		return result.Err[int](errors.New("value must be positive"))
	}

	return result.Ok(v)
}

func main() {
	r := result.AndThen(parsePositive(21), func(v int) result.Result[string] {
		return result.Ok(fmt.Sprintf("value=%d", v*2))
	})

	fmt.Println(r.Unwrap())
}

Result test status

• go test ./result: passed
• go test -race ./result: passed
• unit tests: 14
• benchmark functions: 8

Result benchmarks

Measured on 2026-06-12 with go1.26, darwin/arm64, Apple M5.

Benchmark	ns/op	B/op	allocs/op
BenchmarkOkUnwrap	1.595	0	0
BenchmarkErrUnwrapOr	1.606	0	0
BenchmarkFrom	1.603	0	0
BenchmarkMapOk	3.687	0	0
BenchmarkAndThenOk	6.185	0	0
BenchmarkAndThenErr	6.185	0	0
BenchmarkMapErr	23.91	32	2
BenchmarkInspectNoop	1.545	0	0

Err results are validated once at construction (Err, From, MapErr), so per-call validity checks stay reflection-free on every hot path.

The main fast-path operations of result stay allocation-free. The only measured allocation in the current suite is MapErr, where the benchmark intentionally creates a new wrapped error value on every iteration.

LRU Cache

The lru_cache package provides two generic implementations behind one common Cache[K, V] interface:

• Strict[K, V]: exact global LRU with one mutex
• Sharded[K, V]: approximate global LRU with multiple shard-local mutexes for higher parallel throughput

API

type Cache[K comparable, V any] interface {
	Get(key K) (V, bool)
	Peek(key K) (V, bool)
	Put(key K, value V)
	Delete(key K) bool
	Len() int
	Cap() int
	Clear()
}

func NewStrict[K comparable, V any](capacity int) *Strict[K, V]
func NewSharded[K comparable, V any](capacity int, opts ...Option[K, V]) *Sharded[K, V]

func WithShards[K comparable, V any](n int) Option[K, V]
func WithHasher[K comparable, V any](fn func(K) uint64) Option[K, V]

Data structure and algorithm

Both implementations use the classic O(1) LRU design:

• map[K]*node for constant-time key lookup
• an intrusive doubly linked list for recency order
• the list head stores the most recently used entry
• the list tail stores the least recently used entry and is evicted first

That gives these complexity guarantees:

Operation	Strict	Sharded
Get	O(1)	O(1)
Peek	O(1)	O(1)
Put	O(1)	O(1)
Delete	O(1)	O(1)
Len	O(1)	O(shards)
Clear	O(1)	O(shards)

Strict vs Sharded

Strict is better when you want exact eviction order across the whole cache.

• one lock protects the whole structure
• every Get updates recency globally
• eviction is the true global least recently used entry
• lower implementation complexity and easier reasoning

Sharded is better when you expect heavy concurrent access.

• the cache is split into multiple shards
• each shard has its own map + doubly linked list + mutex
• recency and eviction are strict inside a shard, not across the whole cache
• lower lock contention under multi-goroutine load

Built-in hashing support

Sharded hashes any comparable key type by default using hash/maphash.Comparable with a per-cache random seed, which also makes shard distribution resistant to hash flooding. WithHasher(...) remains available to control how keys distribute across shards or to shave a few nanoseconds with a key-specific hash.

Semantics that matter in production

• Get updates recency
• Peek does not update recency
• updating an existing key also refreshes recency
• Strict is globally exact LRU
• Sharded trades global exactness for parallelism
• both implementations are safe for concurrent use

Example

package main

import "types/lru_cache"

func buildCache(highContention bool) lru_cache.Cache[string, int] {
	if highContention {
		return lru_cache.NewSharded[string, int](50_000, lru_cache.WithShards[string, int](32))
	}

	return lru_cache.NewStrict[string, int](50_000)
}

func main() {
	cache := buildCache(true)
	cache.Put("user:42", 1)
	_, _ = cache.Get("user:42")
	_, _ = cache.Peek("user:42")
}

LRU test status

• go test ./lru_cache: passed
• go test -race ./lru_cache: passed
• unit tests: 8
• benchmark functions: 14
• tests are split into strict_test.go and sharded_test.go
• table-driven tests are used for the main operation matrix where that style fits naturally

LRU microbenchmarks

Measured on 2026-06-12 with go1.26, darwin/arm64, Apple M5.

Benchmark	ns/op	B/op	allocs/op
BenchmarkStrictGetHit	6.912	0	0
BenchmarkStrictGetMiss	5.164	0	0
BenchmarkStrictPutExisting	10.80	0	0
BenchmarkStrictPutNew	97.49	1	0
BenchmarkStrictPutEvict	36.11	0	0
BenchmarkStrictParallelReadHeavy	148.6	0	0
BenchmarkStrictParallelLargeChurn	121.7	0	0
BenchmarkShardedGetHit	11.38	0	0
BenchmarkShardedGetMiss	8.268	0	0
BenchmarkShardedPutExisting	16.18	0	0
BenchmarkShardedPutNew	108.3	2	0
BenchmarkShardedPutEvict	43.66	0	0
BenchmarkShardedParallelReadHeavy	37.02	0	0
BenchmarkShardedParallelLargeChurn	25.29	0	0

Interpretation:

• on single-cache hot paths, Strict is slightly faster because it avoids shard selection and hashing overhead
• under parallel mixed load, Sharded is much faster because lock contention is spread across shards
• both implementations stay allocation-free on Get, Peek, Delete, and updates to existing keys
• eviction reuses the evicted list node, so a cache at capacity allocates nothing on Put; only growth toward capacity allocates list nodes (amortized in PutNew)

Large parallel load

This is the heavier contention-oriented benchmark:

• benchmark: Benchmark(Strict|Sharded)ParallelLargeChurn
• cache capacity: 16_384
• working set: 131_072
• workload: mixed Get/Put
• duration: 3s

Benchmark	CPU setting	ns/op	B/op	allocs/op
ShardedParallelLargeChurn	1	42.51	0	0
ShardedParallelLargeChurn	4	19.35	0	0
ShardedParallelLargeChurn	10	27.20	0	0
StrictParallelLargeChurn	1	35.40	0	0
StrictParallelLargeChurn	4	125.7	0	0
StrictParallelLargeChurn	10	122.3	0	0

These numbers show the expected trade-off clearly:

• at 1 CPU, Strict wins because there is no contention and it has the shorter path
• at 4 and 10 CPUs, Sharded wins by a large margin because it avoids a single global lock

Commands used for verification

go test ./...
go test -race ./lru_cache ./result
go test ./result -bench . -benchmem -count=1
go test ./lru_cache -bench . -benchmem -count=1
go test ./lru_cache -run '^$' -bench 'Benchmark(Strict|Sharded)ParallelLargeChurn$' -benchmem -benchtime=3s -cpu=1,4,10 -count=1