bit-optimization

Bit-Level Optimization Patterns

Learnings from optimizing succinct data structure operations.

Comprehensive documentation: See docs/optimizations/ for full technique reference:

• bit-manipulation.md - Popcount, CTZ, PDEP/PEXT
• lookup-tables.md - Byte-level lookup tables
• hierarchical-structures.md - Rank/select indices

Byte-Level Lookup Tables

When to use: Scanning bits one-at-a-time is slow (64 iterations per word). Use 256-entry lookup tables to process 8 bits at once.

Pattern: Two-Level Lookup

// Precompute at compile time
const BYTE_MIN_EXCESS: [i8; 256] = { /* min prefix sum for each byte value */ };
const BYTE_TOTAL_EXCESS: [i8; 256] = { /* total excess (popcount*2 - 8) */ };
const BYTE_FIND_CLOSE: [[u8; 16]; 256] = { /* 2D: byte_value x initial_excess */ };

fn find_close_in_word_fast(word: u64, initial_excess: i32) -> Option<usize> {
    let bytes = word.to_le_bytes();
    let mut excess = initial_excess;

    for (i, &byte_val) in bytes.iter().enumerate() {
        // Level 1: Can the result be in this byte?
        let min_excess_in_byte = BYTE_MIN_EXCESS[byte_val as usize] as i32;
        if excess + min_excess_in_byte <= 0 {
            // Level 2: Find exact position within byte
            if excess <= 16 {
                let match_pos = BYTE_FIND_CLOSE[byte_val as usize][(excess - 1) as usize];
                return Some(i * 8 + match_pos as usize);
            }
            // Fallback for excess > 16: bit-by-bit scan of this byte only
        }
        excess += BYTE_TOTAL_EXCESS[byte_val as usize] as i32;
    }
    None
}

Key Insights

1. Two-level lookup: First check if result is in this byte (fast), then find exact position
2. Compile-time computation: Use const blocks for zero runtime overhead
3. Hierarchical skip: Skip entire bytes/words when result can't be there
4. Fallback for edge cases: Handle out-of-range lookup indices with bit scan