go-datastructures is a collection of performant and threadsafe data structures for Go.
The project addresses the need for specialized data structures optimized for specific use cases where standard Go collections fall short. It provides implementations tuned for performance characteristics that matter in practice: interval trees for multidimensional range queries, bit arrays for membership testing without hashing overhead, futures for broadcasting events to multiple listeners, and queues that never block on send and grow dynamically. The augmented tree uses red-black balancing to maintain O(log n) operations for insertions, deletions, and queries in single dimensions. Bit arrays offer two variants—regular and sparse—trading insertion speed for space efficiency, and include operations for detecting intersection between arrays. The queue implementations avoid the blocking semantics and panic behavior of Go channels, instead returning errors only when pushing to a disposed queue.
Developers should consider this collection when building systems that require specific algorithmic properties. The augmented tree suits applications needing collision detection across dimensional ranges. The Fibonacci heap implementation is valuable for graph algorithms like Dijkstra or Prim's where decrease-key operations are frequent, though the large constant factors mean it may underperform simpler heap variants in practice. The MPMC ring buffer addresses goroutine synchronization and graceful shutdown patterns using only compare-and-swap operations. The futures package solves a genuine limitation of Go channels—the inability to broadcast a single message to multiple listeners. Projects with performance-critical paths or those requiring threadsafe concurrent access without locks will benefit most from these structures.
The project maintains a focused scope on core data structures with clear algorithmic properties documented in the README. Development activity shows ongoing refinement, with the priority queue explicitly noted as targeted for improvement via Fibonacci heap integration and the project including benchmarks to validate performance claims. The codebase demonstrates attention to threadsafety through careful use of synchronization primitives like CAS operations rather than mutex-based locking.
