bitmap
A high-performance SIMD-vectorized bitmap index implementation in Go for dense small-to-medium collections.
What is bitmap?
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.
Overview
Simple dense bitmap index in Go with binary operators
Use Cases
Best For
- Implementing bitmap indexes for columnar in-memory databases
- Building high-performance free-list or allocation bitmaps
- Accelerating boolean operations on dense bit sets with SIMD
- Creating custom filtering systems with in-place bitmap operations
- Developing search engines requiring fast intersection/union of result sets
- Optimizing Go applications that need zero-allocation bit manipulation
Not Ideal For
- Applications dealing with extremely sparse bitmaps (e.g., where less than 1% of bits are set), where sparse-focused libraries like Roaring Bitmaps would be more memory-efficient.
- Projects requiring cross-platform deployment on architectures without SIMD support, as the vectorized optimizations are hardware-specific and may not run on all CPUs.
- Use cases needing built-in bitmap compression or advanced persistence mechanisms, as the library focuses on in-memory performance with only basic binary serialization.
Pros & Cons
Pros
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.
Cons
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.
Frequently Asked Questions
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.