sets

Thread-safe, generic set implementations for Go: SimpleSet for standard workloads and ShardSet for high-contention scenarios.

No external dependencies. Choose the right tool for your use case: a single-lock set for most problems, or a sharded set to eliminate lock contention under heavy concurrent load.

---

Design

• Generic: Both implementations work with any comparable type via Go generics.
• Thread-Safe: All operations are protected by synchronization primitives. No caller-level locking required.
• Standard Library Only: Built entirely on sync.RWMutex and sync.Mutex. No external packages.
• Simple API: Add, Has, Remove, and Len cover 99% of real-world use cases.

---

SimpleSet

SimpleSet is a straightforward, thread-safe set backed by a map and a single RWMutex. It's optimal for standard read-heavy or mixed workloads where lock contention is not a bottleneck.

Usage

set := sets.NewSimpleSet[string]()

set.Add("alice")
set.Add("bob")

if set.Has("alice") {
	fmt.Println("alice is in the set")
}

set.Remove("alice")
fmt.Println("size:", set.Len())

// Iterate over items
for key := range set.Iterator() {
	fmt.Println(key)
}

---

ShardSet

ShardSet is a high-performance set for scenarios with heavy concurrent load. It distributes keys across multiple independent shards, each with its own lock, eliminating the global bottleneck of a single mutex.

It automatically rounds the shard count up to the nearest power of 2 and uses bitwise AND for routing — mechanical sympathy that keeps CPU cache happy.

When to Use ShardSet

• Thousands of concurrent goroutines contending for the same set
• Session stores or token caches with high read/write volume
• Permission or blocklist checks under sustained concurrent load

Usage

// Create a sharded set with 64 shards
set := sets.NewStringShardSet(64)

set.Add("user:alice")
set.Add("user:bob")

if set.Has("user:alice") {
	fmt.Println("user exists")
}

set.Remove("user:alice")
fmt.Println("size:", set.Len())

For custom types with custom hashing:

type UserID int64

set := sets.NewShardSet[UserID](64, func(id UserID) uint64 {
	return uint64(id * 2654435761) // Example: FNV-like mixing
})

set.Add(42)
fmt.Println(set.Has(42))

---

API Reference

Both SimpleSet and ShardSet share the same core interface:

• Add(key K) — Insert a key into the set. Idempotent; adding an existing key is a no-op.
• Has(key K) bool — Check if a key exists. O(1) average case.
• Remove(key K) — Delete a key from the set. Safe even if the key doesn't exist.
• Len() int — Return the total number of items.

SimpleSet also provides:

• Size() int — Alias for Len().
• Snapshot() []K — Return a point-in-time copy of all keys.
• Iterator() iter.Seq[K] — Range over items using Go's iterator protocol.

---

Benchmarking

Run benchmarks to compare both implementations under different workloads:

go test -bench=. ./...

Results vary by hardware and contention, but ShardSet typically wins when:

• Shard count matches CPU core count or higher
• Write volume is non-trivial (mixed read/write workloads)
• Goroutine count exceeds core count significantly