Before you start reading, i wanna warn you the messages, code, and docs are generated by AI, but the thinking, understanding, and implementation are done by me. so if u don't like AI, please don't read. because i already got backlash from reddit, i don't want the same here. and if moderators find this doesn't belong as a proper post, please just delete it! that's all from my side! thnx

Hi all, I've built a small experimental data structure in Rust and would appreciate feedback from anyone with experience in low-level indexing or collections design.

Repo: GitHub - AriajSarkar/bwspi: Sarkar Bucket Array (SBA) / Bit-Width Sparse Pointer Index (BWSPI) — a zero-hash, single-instruction routed sparse indexing system for unsorted dynamic data streams · GitHub

Core idea:
Instead of hashing, route values into buckets using their bit-width (u64::leading_zeros() → single LZCNT/CLZ instruction). This gives 65 deterministic buckets with no collision, no heap allocation per insert, and O(1) amortized insert.

Benchmark highlights (Criterion, N=1000, high-entropy u64):

• Insert: ~6 ns vs ~31 ns (HashMap)
• Lookup HIT: ~2.66 ns vs ~1.64 ns (SwissTable)
• Heap: ~47% of HashMap at 1M elements

Lookup is slower than SwissTable — this is a deliberate tradeoff for write-heavy, append-only workloads with mixed bit-width data.

Specific things I'd like feedback on:

1. Is this a known structure under a different name? I couldn't find a direct prior art.
2. The AVX2 SIMD path is currently slightly slower than scalar in benchmarks — is this a bucket-size issue or a gather/scatter overhead issue?
3. Any API or safety concerns before I consider publishing to crates.io?

Thanks again in advance.

2 posts - 2 participants

Read full topic