[Project] compact-dict: Experimenting with cache-local linear probing. Seeking code review on unsafe and soundness.

code review
1

Hi everyone,

I've recently released compact-dict, a hash map implementation that focuses on memory contiguity and cache-line efficiency. This is my first time sharing a library here, and I'm looking for some feedback from the community, especially regarding my use of unsafe and the overall design.

Repo: GitHub - gustawdaniel/compact-dict: An experimental, highly customizable, open-addressing dictionary in Rust. · GitHub

The Goal: I wanted to explore how a "brutalist" approach - using a strictly continuous memory layout and linear probing - compares to more complex designs like hashbrown (SwissTables). My hypothesis is that for specific small-to-medium workloads, the CPU's prefetcher efficiency can outweigh the benefits of SIMD-based metadata scanning.

Key Design Choices:

  • Continuous Layout: No separate chaining; all data lives in a single allocation.
  • Linear Probing: Chosen for its simplicity and extreme cache locality.
  • No Deletion (Yet): Currently, it's an append-only/static dictionary to keep the lookup path as clean as possible.

What I'm specifically looking for:

  1. Unsafe Soundness: I've used std::ptr and raw memory manipulation to minimize overhead. I'd love to know if I'm violating any aliasing rules or Stacked Borrows / Tree Borrows invariants.
  2. The "Rust Way": Since this is one of my first deep dives into systems-level Rust, I'm sure there are places where my API isn't as idiomatic as it could be.
  3. Miri: I've done some testing, but if anyone is willing to run it through more rigorous Miri checks or loom, I'd be very grateful.

I'm prepared for a thorough roast! My goal is to learn how to write more robust, high-performance unsafe Rust.

Thanks in advance for your time and insights!

2 Likes