FastBit

FastBit is a high-performance data indexing and querying library written in Rust, designed for fast analytics on large datasets. It provides one of the fastest bit vector implementations available in the Rust ecosystem.

Performance

FastBit is designed for raw speed with operation-specific optimizations:

• Blazing Fast Operations: Sub-nanosecond performance for operations like any() on specific bit patterns
• Operation-Specific Word Type Advantages:
  • u64: Up to 10x faster for count_ones, all/any checks, and basic bit operations
  • u8: Faster for iteration over dense bit vectors (up to 2x faster than u64)
  • Word Type Gradient: Performance follows a consistent pattern across u8, u16, u32, and u64
• Efficient Memory Usage: Much more memory-efficient than Vec<bool> while maintaining high performance
• Low-Level Optimizations: Uses raw pointers and unsafe code for maximum performance

Benchmark highlights:

• Count operations on 100,000 bits: ~191ns with u64 vs ~810ns with u8
• All/any checks on 100,000 bits: ~500ns with u64 vs ~5.5μs with u8
• Iteration over full 10,000-bit vector: ~6.9μs with u8, ~8.2μs with u16, ~10.2μs with u32, ~13.7μs with u64
• Iteration over empty 10,000-bit vector: ~2.9μs with u8, ~3.2μs with u16, ~4.4μs with u32, ~6.0μs with u64
• Bit operations (set/reset/test) show consistent performance advantages with larger word types

Features

• Efficient bitmap indexing with multiple word type options (u8, u16, u32, u64, usize)
• Fast query processing with optimized bit operations
• Scalable to large datasets with linear performance scaling
• Easy integration with Rust data pipelines

Installation

Add FastBit to your Cargo.toml:

[dependencies]
fastbit = "0.1"

Or clone the repository:

git clone https://github.com/enterprise-search/fastbit.git
cd fastbit
cargo build --release

Comparison with Alternatives

FastBit offers significant performance advantages over other bit vector libraries:

• Raw Speed: FastBit prioritizes performance through low-level optimizations and unsafe code
• Simplified API: Focused on core bit operations without unnecessary abstractions
• Word Type Performance: Choose the optimal word type based on your use case:
  • For general use and most operations: u64 provides dramatic performance improvements
  • For iteration over dense bit vectors: smaller word types (u8, u16) offer better performance
  • For iteration over sparse bit vectors: larger word types (u64, u32) are more efficient

When compared to alternatives like the bitvec crate, FastBit offers:

• Faster operations through direct memory manipulation
• Lower overhead due to fewer abstractions
• Superior performance for large bit vectors
• Flexibility to optimize for specific bit density patterns

Usage

// For most operations, use u64 as the word type
use fastbit::{BitVec, BitRead, BitWrite};

// Create a bit vector with 128 bits
let mut bv: BitVec<u64> = BitVec::new(128);
bv.set(5);
assert!(bv.test(5));
bv.reset(5);
assert!(!bv.test(5));

// Efficient bulk operations
bv.fill();  // Set all bits to 1
assert!(bv.all());
bv.clear(); // Set all bits to 0
assert!(!bv.any());

// For iteration-heavy workloads with dense bit vectors, consider u8
let mut dense_bv: BitVec<u8> = BitVec::new(128);
dense_bv.fill();  // Fill with 1s for dense bit vector
// Iteration over dense_bv will be faster than with u64

Documentation

• API Reference
• BitFixed Documentation
• Examples

Contributing

Contributions are welcome! Please open issues or submit pull requests.

License

This project is licensed under the MIT License.