search

ibraheemdev / papaya

A fast and ergonomic concurrent hash-table for read-heavy workloads.
MIT License
347 stars 6 forks source link

Experiment With SIMD Probing #4

Open ibraheemdev opened 3 months ago

ibraheemdev commented 3 months ago

The hash-table uses a metadata table inspired by swisstable, so we should be able to benefit from SIMD probing. The difficulty is that atomic group loads must be aligned, causing us to lose some hash entropy. I ran some benchmarks previously and found a small regression from essentially copy-pasting the x86 SIMD implementation from hashbrown, so maybe there's not really much we can do here.

There's also questions about whether mixed-sized atomic accesses are sound on x86, but we should at least be able to benefit on other platforms.

ibraheemdev commented 3 months ago

Alternatively, if we decide not to use SIMD we might want to consider alternative probing strategy. The current quadratic by-group probing makes less sense if groups are not correlated with SIMD groups.

ibraheemdev commented 3 months ago

9b8add8b40b1c5b8f1b48806a74e07174bb8540b switches to pure quadratic probing. Read performance seems to be consistently lower, especially on large tables. However, I'm noticing some unexpected performance fluctuations when adjusting the load factor, so I'd be interested in more robust benchmarks and an analysis of probe lengths. We're in a somewhat unique situation of having a metadata table but not using SIMD (even at the machine word level).