BWSPI — Zero-Hash, 1-Instruction Data Index in Rust

A data structure that replaces hash functions with a single CPU instruction (LZCNT). ~x(mostly win but with few regression) faster than HashMap, lesser the memory, zero rehash spikes.

Comment

Inspiration

I had a simple, stubborn question: why do we need to hash data just to find it?

If you have unsorted data — logs, telemetry, event streams — and you want to check if a value exists, your options are:

  • Linear scan — O(n), brutally slow
  • Sort first — expensive, and you lose insertion order
  • HashMap/HashSet — fast on average, but hashing costs 60+ CPU instructions per lookup, and you get unpredictable O(n) rehash spikes that kill latency guarantees

I wanted a fourth option: something that routes data to where it belongs using what the data already has — its binary structure — instead of computing a hash over it.

Initially, I was inspired by how NASA builds systems: optimality with speed and near-zero resource usage. I'm not there yet with my current knowledge — but I built something that can work alongside Google's top-tier SwissTable hashset, not by being better at everything, but by being fundamentally different.

The core insight: every integer already carries a routing key in its bit-width (the number of binary digits it needs). Extracting that costs exactly 1 CPU instruction — LZCNT on x86, CLZ on ARM. No multiplication, no XOR mixing, no seed. Just one instruction that's been in every CPU since 2013.

What it does

BWSPI (Bit-Width Sparse Pointer Index) — also called the Sarkar Bucket Array — is a zero-hash sparse indexing system for unsorted dynamic data streams.

Instead of hashing:

HashMap:  value → hash(value) → bucket     (60+ CPU instructions)
BWSPI:   value → bit_width(value) → bucket (1 CPU instruction)

The architecture uses two tables:

Table 1 (Data Store)          Table 2 (Bit-Width Index)
┌───────────────────┐         ┌────────────────────────┐
│ [42, 7, 1000, 3]  │◄────────│ bw=2: [idx 3]          │
│  append-only Vec   │         │ bw=3: [idx 1]          │
│  never sorted      │         │ bw=6: [idx 0]          │
│  never moved       │         │ bw=10: [idx 2]         │
└───────────────────┘         └────────────────────────┘

Data goes in, never moves, never gets sorted. The index routes lookups to the right bucket using bit-width, then does a small local scan. On high-entropy data, that bucket holds ~2% of total elements.

Inside each bucket, a lazy LSB radix tree progressively splits when leaves exceed 64 entries — giving sub-linear lookup without any hashing at any level.

How I built it

This was an intense AI-assisted architecture + implementation process:

  1. Architecture design: I went back and forth between GPT 5.5 (xHigh reasoning) and Claude Opus 4.6 (adaptive thinking) — using each to review and challenge the other's suggestions. GPT helped me validate the bit-width routing math and think through edge cases. Opus helped me refine the two-table architecture and catch correctness issues.

  2. Implementation: Written in pure Rust with zero dependencies for the core library. The only external crates are dev-dependencies for benchmarking (Criterion, rand, hashbrown for comparison).

  3. SIMD acceleration: Hand-written AVX2 intrinsics — broadcast the search target, load 4 bucket values, compare in parallel, extract bitmask. With runtime feature detection and scalar fallback.

  4. Benchmarking: Built a custom hardware benchmark suite that measures median-of-7 warm runs, tracks working-set deltas, cache topology, and per-result CPU utilization. Compared against std::HashMap, FxHashMap, AHashMap, SwissTable (hashbrown), and raw linear scan.

  5. LSB Radix Tree: After the initial flat-bucket design, I evolved it into a lazy radix tree that consumes 6 bits per level from the LSB side — giving O(log₆₄ k) lookup within each bit-width bucket instead of linear scan.

Challenges

  • The uniform-width worst case: When all values have the same bit-width (e.g., all 32-bit), everything lands in one bucket. This is the fundamental trade-off vs hashing. I mitigated it with the LSB radix tree, but it's an honest limitation.
  • Architecture vs implementation gap: I could see the architecture clearly, but my low-level systems programming knowledge wasn't deep enough to implement everything optimally on the first try. AI bridged that gap — helping me translate architectural ideas into working Rust code.
  • Drastic pivots: The design changed significantly multiple times as I discovered what actually works vs what sounds good on paper. The code is still cluttered from those pivots.

A note to whoever is reading this

I don't want to waste your time. I know this submission is rough around the edges.

What I'm asking you to appreciate is the architecture, not the implementation. I still have a lot to learn about deep systems programming to implement this at its full potential. AI helped me enormously — not just to write code, but to pressure-test whether my ideas could survive contact with real hardware.

If you find the concept interesting — a world where we route data by its physical binary properties instead of computing hashes — I'm submitting a clean, proper version of the architecture and code by July 25th with proper documentation and writing.

Thank you for reading.

Built With

  • bit-manipulation
  • low-latency-programming
  • lzcnt
  • radix-tree
  • system-programming
  • zero-hash-index
Share this project:

Updates