[PERFORMANCE QUESTION] Why is DashMap faster with less threads?

[redactedontop]

Heya!

As shown on the graph below, DashMap is a lot faster (throughput; 10 mega operations faster than scc) for 1 thread (scc eventually surpasses it). I'm a complete noob in optimization, and this is a genuine (and hopefully not rude) question: what are the big differences in implementations that make SCC's HashMap slower short-term but scale better?

Thanks,
Alex.

[redactedontop]

Maybe the use of Atomics on SCC?

[wvwwvwwv]

Hi @redactedontop,

DashMap is based on hashbrown, which is very aggressively optimized for single-threaded workloads, whereas SCC focuses more on predictability and scalability.

• The primary use case of SCC is RDBMS, where the predictable latency is of utmost importance (the tail latency is important), no matter what happens.

If one needs good single-threaded performance and latency spikes don't quite matter, then DashMap is the way to go. If good read performance is essential and the cost of frequent heap allocation (per-entry heap allocation) is not a problem, papaya is the best choice.

• SCC is good when highly concurrent access to the hashmap is expected, and predictable latencies are essential.

[wvwwvwwv]

I forgot to answer the main part of the question; its single-threaded performance is not as good as others because I didn't pay much attention to this :-( I'll try to optimize it when I have some time.

[redactedontop]

Hiya!

I'll gladly help you, as I enjoy this project a lot: give me a checklist and some days, and I'll see what I can do ;)

Thanks,
Alex <3
PS: It helps both you (less work), me (highly parallelized chess engine), and users (free performance!!!1!1)

[wvwwvwwv]

@redactedontop awesome! The first step of optimization is usually profiling. On macOS, the profiling tool (Instruments) bundled with XCode is pretty powerful, so once a benchmark scenario is prepared (vanilla conc-map-bench is too short - need a longer one to get meaningful results), it will be possible to figure out where to optimize in the code.
-> No pressure at all!

[redactedontop]

Would it be selfish to ask you for a flamegraph (cargo flamegraph) of a bigger benchmark for me to analyse? I currently cannot make benchmarks (studying + homework + personal projects)...?

[redactedontop]

And do you have discord (quicker answers)?

[wvwwvwwv]

I can do profiling, but not sure when I can - possibly early Mar? / no I don’t do discord.

[wvwwvwwv]

I dug into the issue and figured that thread_local in sdd causes the difference.

• tlv_get_addr.

It's interesting that the cost of tlv_get_addr has never been detected in sdd's benchmark suite. I'll need to spend some time thinking about how to optimize calls to tlv_get_addr.

[wvwwvwwv]

Substituting thread_local! with #[thread_local] helps much, but that's gated behind an unstable feature flag.

[redactedontop]

That's so weird!

…

On Wed, Mar 5, 2025 at 2:22 PM Changgyoo Park ***@***.***> wrote: Substituting thread_local! with #[thread_local] helps much, but that's gated behind an unstable feature flag. — Reply to this email directly, view it on GitHub <#177 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> . You are receiving this because you were mentioned.Message ID: ***@***.***> [image: wvwwvwwv]*wvwwvwwv* left a comment (wvwwvwwv/scalable-concurrent-containers#177) <#177 (comment)> Substituting thread_local! with #[thread_local] helps much, but that's gated behind an unstable feature flag. — Reply to this email directly, view it on GitHub <#177 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[redactedontop]

Maybe https://swatinem.de/blog/slow-thread-local/?

…

On Sat, Mar 8, 2025 at 11:00 PM Niggerian ***@***.***> wrote: That's so weird! On Wed, Mar 5, 2025 at 2:22 PM Changgyoo Park ***@***.***> wrote: > Substituting thread_local! with #[thread_local] helps much, but that's > gated behind an unstable feature flag. > > — > Reply to this email directly, view it on GitHub > <#177 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> > . > You are receiving this because you were mentioned.Message ID: > ***@***.*** > com> > [image: wvwwvwwv]*wvwwvwwv* left a comment > (wvwwvwwv/scalable-concurrent-containers#177) > <#177 (comment)> > > Substituting thread_local! with #[thread_local] helps much, but that's > gated behind an unstable feature flag. > > — > Reply to this email directly, view it on GitHub > <#177 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> > . > You are receiving this because you were mentioned.Message ID: > ***@***.*** > com> >

[redactedontop]

Try one of 2 things: 1. Wrap the thread local initialization with const { } (ex. replace const SOMETHING: _ = _::new() with const SOMETHING: _ = const { _::new() }) when possible 2. Make a nightly-only version of the crate for honestly much faster code (would be my course of action).

…

On Sat, Mar 8, 2025 at 11:01 PM Niggerian ***@***.***> wrote: Maybe https://swatinem.de/blog/slow-thread-local/? On Sat, Mar 8, 2025 at 11:00 PM Niggerian ***@***.***> wrote: > That's so weird! > > On Wed, Mar 5, 2025 at 2:22 PM Changgyoo Park ***@***.***> > wrote: > >> Substituting thread_local! with #[thread_local] helps much, but that's >> gated behind an unstable feature flag. >> >> — >> Reply to this email directly, view it on GitHub >> <#177 (comment)>, >> or unsubscribe >> <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> >> . >> You are receiving this because you were mentioned.Message ID: >> ***@***.*** >> com> >> [image: wvwwvwwv]*wvwwvwwv* left a comment >> (wvwwvwwv/scalable-concurrent-containers#177) >> <#177 (comment)> >> >> Substituting thread_local! with #[thread_local] helps much, but that's >> gated behind an unstable feature flag. >> >> — >> Reply to this email directly, view it on GitHub >> <#177 (comment)>, >> or unsubscribe >> <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> >> . >> You are receiving this because you were mentioned.Message ID: >> ***@***.*** >> com> >> >

[redactedontop]

Also, can you send the complete SVG of both sdd and scc?

…

On Sat, Mar 8, 2025 at 11:05 PM Niggerian ***@***.***> wrote: Try one of 2 things: 1. Wrap the thread local initialization with const { } (ex. replace const SOMETHING: _ = _::new() with const SOMETHING: _ = const { _::new() }) when possible 2. Make a nightly-only version of the crate for honestly much faster code (would be my course of action). On Sat, Mar 8, 2025 at 11:01 PM Niggerian ***@***.***> wrote: > Maybe https://swatinem.de/blog/slow-thread-local/? > > On Sat, Mar 8, 2025 at 11:00 PM Niggerian ***@***.***> > wrote: > >> That's so weird! >> >> On Wed, Mar 5, 2025 at 2:22 PM Changgyoo Park ***@***.***> >> wrote: >> >>> Substituting thread_local! with #[thread_local] helps much, but that's >>> gated behind an unstable feature flag. >>> >>> — >>> Reply to this email directly, view it on GitHub >>> <#177 (comment)>, >>> or unsubscribe >>> <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> >>> . >>> You are receiving this because you were mentioned.Message ID: >>> ***@***.*** >>> com> >>> [image: wvwwvwwv]*wvwwvwwv* left a comment >>> (wvwwvwwv/scalable-concurrent-containers#177) >>> <#177 (comment)> >>> >>> Substituting thread_local! with #[thread_local] helps much, but that's >>> gated behind an unstable feature flag. >>> >>> — >>> Reply to this email directly, view it on GitHub >>> <#177 (comment)>, >>> or unsubscribe >>> <https://github.com/notifications/unsubscribe-auth/BJEGBBS25LAICH47IVS6THT2S4CAZAVCNFSM6AAAAABXHKUKHWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDOMBRGA4DQMZUGE> >>> . >>> You are receiving this because you were mentioned.Message ID: >>> ***@***.*** >>> com> >>> >>

[redactedontop]

Also, what about Atomics instead of sdd? You can prevent ABA in HashMaps with double-checks (checking not just the alue but the others).

[wvwwvwwv]

Thanks, @redactedontop. I substituted the thread-local variable's non-const assignment with a const block -> SDD 3.0.8.

Unfortunately, use-after-free is the problem, not ABA. The delayed memory reclamation prevents use-after-free if the hash map has been resized, and relying on thread-local is currently the optimal way to prevent it.

• If SCC only targets Intel/PPC, we can use HTM.

[redactedontop]

How come? Can't you prevent UAF with Atomics?

[wvwwvwwv]

Not quite possible as far as I know since while a reader is in a loop of { read-pointer - do-something - validate }, anything can happen including deallocating the pointee. EBR/RCU/HTM/hazard-pointers etc prevent this from happening.

[redactedontop]

Then why not use HTM when supported instead of a full thread_local? Also, have you thought about the nightly #[thread_local] version?

[wvwwvwwv]

Simple: there is no decent crate that enables easy use of HTM instructions, and ![thread_local] is still unstable.

[redactedontop]

Fair. Have you thought about making a nightly version of the crate?