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.
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 The bucket array is fully dynamic — starts at 0 slots and only grows to fit the highest bit-width present in the data (8-bit data → 9 slots, 32-bit → 33 slots, never 65 unless you actually have full u64-range values). No collision, no heap allocation per insert, O(1) amortized insert.
What is this for? If you have u64s using the full range, it seems like the buckets will be absolutely gigantic?
Certainly if you have a uniform distribution of values, half of them will be in one bucket (the largest, thanks to the pie series), making this pretty similar to just not having bucketing at all?
It seems like the comparison shouldn't be against a HashMap, but against Vec.
Thanks both, and i should clarify something missing from my original post. (i'm gonna try to edit if option available)
the bucket array is fully dynamic(i'm not 100% sure, because the code is right now AI gen. i've to read line by line), it starts at 0 slots and only grows to fit the highest bit-width actually present in the data.
8 bit values -> 9 slots,
32 bit values -> 33 slots
never 65 unless you actually have u64 range values, my original post said "65 buckets" which was wrong, sorry for the confusion.
@scottmcm -
the uniform full-range u64 case is a genuine worst case and it's documented as such in the trade-offs.
the Vec comparison is fair for that case and i'll add it to the benchmarks.
but for the intended workload "non-uniform", mixed bit-width data like counters, ID's, indices, the distribution is naturally spread and the 98% search reduction benchmark reflects that.
@giocri - & 63 produces a uniform distribution but the bucket assignment is meaningless, it's a cheap hash. With LZCNT, bucket k strictly contains values in [2^(k-1), 2^k-1],
that bound is what enables range queries and sorted iteration as future operations. The goal wasn't uniformity, it was semantic partitioning at zero cost.
TBH, statements like this just trip my meaningless slop filter. What makes this particular thing so special? LZCNT would also be "semantic" (under whatever meaning you're assigning to that word) in the sense that it'd be bucketed by how aligned it is, for example. Why is this a container and not just a trivial u64-only hasher?
It's not only that if you have "full-range u64" that it's bad. It's literally any uniform subset of the integers where this hash function makes no sense. (You mention "random ids" for example, but those are uniform absent other information. Entity ids in bevy tend to even be contiguous, for example, where this LZCNT-based lookup would be particularly terrible.)
This is only a good hash function if the values have a Geometric distribution - Wikipedia but I can't think of a single time when I've wanted a hashset-like thing where the keys had that distribution. Do you have a concrete example?
If you don't know what it does, I don't know why I'd ever use your crate vs just getting my own AI to make the same thing. What value are you providing? What's your special expertise that makes this crate valuable? See previous conversations like
Sorry for the "not 100% sure" reply, i specified "because the code is right now AI gen", i know the concept and design,
i just don't know every line of the generated implementation yet.
i'm a CS student exploring whether LZCNT could replace hashing in a specific narrow case.
the target isn't HashMap. the tradeoff is: Vec -> O(1) insert, O(n) lookup, HashMap -> O(1) lookup, but rehash spikes, 2x memory, no duplicates, BWSPI -> O(1) insert no rehash, O(k) lookup where k << n, O(1) instant miss if bit-width bucket doesn't exist - faster than HashMap on miss, half the memory, native duplicates,
on your "geometric distribution" question - the concrete case i have is telemetry counters.
event occurrence counts are naturally geometric:
most events fire rarely -
small values, low bit-widths,
few fire thousands of times.
buckets stay small, k stays low.
you're right the niche is narrow,
"Better than linear scan for insert-heavy, duplicate-heavy workloads on geometrically distributed data" is the honest claim.
iterating on 0...x ends up having up to 50% of it's data in a single unsorted bucket
iterating on x...y query will have up to 100% of it's data in a single unsorted bucket
buckets really don't seem to help much with ordering at the very least
your average lookup cost for a list of n elements ranges from a single instance of O(n/65) to a wide set of O(n) depending on how the list is distributed.
for lists heavily clustered around 0 you are likely to have O(n/2)
Looking beyond the contradiction, it may have been more helpful to have a discussion about the ideas behind this design, rather than presenting the implementation and asking for review.
I find great joy in reading (and sometimes contributing to) discussions about designs for solving a problem. But when someone brings code for review, stating they don't know the code any better than me (a first time reader), then it's difficult to have a productive discussion around it.
@giocri@scottmcm
the formal Big-O point, O(n/65) and O(n) are the same class, constants drop.
the O(k) where k << n claim requires stating the distribution assumption explicitly,
which i didn't do clearly enough. that's a real correction and i'll fix the framing.
the practical constant still matters in real workloads, 1.9% bucket occupancy on high-entropy data means 98.1% fewer comparisons, but i understand that's not how complexity is formally expressed.
i rushed this with AI because i wanted to know if the idea makes real impact before spending weeks implementing from scratch. the numbers shocked me so i posted early. that was a mistake. i can't cleanly defend every line right now and that's on me, not the concept.
i'm going to implement this fully by hand(including some refinements), then repost properly. before that i'm sharing the concept with my professor along with both your replies, curious what his take is, because in my research i haven't found this same approach done before.
also topic aside, this forum/site is far far better than reddit to actually discuss things rather than just... , the quality - 67.6/32.4(pls dont ask me how i got this num)!
that's fair, bit_width is technically a hash function, the "zero-hash" framing isn't precise.
the real distinction i was trying to make is that bit_width is a semantically meaningful, deterministic routing function, bucket k strictly contains values in [2^(k-1), 2^k-1], unlike a pseudo-random hash designed for uniform distribution.
but structurally, yes, it's a hash table with bit_width as the hash function.
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
, the quality - 67.6/32.4(pls dont ask me how i got this num)!