A high-performance SIMD-vectorized bitmap index implementation in Go for dense small-to-medium collections.
kelindar/bitmap is a Go library implementing a dense bitmap (bitset) with SIMD-vectorized operations. It provides high-performance boolean algebra, bit counting, and iteration for building bitmap indexes and managing dense collections. The library is optimized for zero heap allocations and leverages modern CPU instructions for speed.
Go developers building columnar in-memory stores, database indexing systems, or performance-critical applications requiring dense bitmap operations. It's particularly useful for those implementing bitmap indexes as an alternative to B-trees or hash maps.
Developers choose kelindar/bitmap for its exceptional performance in dense bitmap scenarios, featuring SIMD acceleration, zero allocations, and a simple API. It outperforms sparse-focused alternatives like Roaring Bitmaps for small-to-medium dense datasets and integrates seamlessly into indexing systems.
Simple dense bitmap index in Go with binary operators
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
Uses vectorized instructions for boolean algebra operations, achieving nanosecond-level performance in benchmarks for And, Or, etc., as shown with times like 141.7 ns/op for OR on 100,000 elements.
All critical methods avoid heap allocations entirely, evidenced by benchmark results showing 0 B/op across operations, reducing garbage collector overhead in performance-critical applications.
Provides hardware-accelerated AND, OR, XOR, and ANDNOT, making it ideal for implementing bitmap indexes as demonstrated in the documentation with book filtering examples.
Includes Range() and Filter() methods with minimal overhead, optimized for in-place operations without extra allocations, as benchmarked with Filter() at 93,630 ns/op for 100,000 elements.
Explicitly designed for dense small or medium bitmaps; performance and memory usage degrade for sparse data, and the README admits it's not suitable compared to Roaring Bitmaps for sparse cases.
Offers binary encoding with no-copy slice conversion but lacks advanced features like compression or built-in support for persistent storage, limiting use in scenarios requiring efficient disk I/O.
Relies on SIMD assembly code for optimizations, which can complicate porting to non-x86 platforms or debugging, and may not be available in all deployment environments.