For 2-3 weeks now,I have been trying to implement a high performance concurrent ordered map called Masstree in Rust (the original is written in C++ and has some practical use too as much as I am aware). I need some advice for the following problems. I have been lurking for a month on this forum so I know that there are some very experienced regulars here :'D

My first problem is that, I am not sure about what the standard crates/techniques I should use/know about if I am working on a very complex concurrent data structure (like a trie of B+trees in this case)? I used miri with the strict provenance flag to catch bad memory access patterns, leaks and potential UB's. I have stress tests and benches. I tried loom and shuttle (have basic tests working, but struggle to model complex scenarios). What else could I be using to test the soundness and stability of my implementation? I tried using perf and cargo-flamegraph to find the bottlenecks, but I can't get them to work properly.

I currently have some very rare transient test failures in concurrent stress tests and for write ops I am outperforming other data structures in under 8 threads, but going above that leads to some very complex and subtle issues (like leaf split storms, excessive CAS retry contentions etc). For example, at 16 threads, fastest write is 40ms but slowest is 5 seconds (120x variance). I am trying to fix them by adding logs and checking where the logical flow is going wrong. But this is becoming too hard and unmaintainable.

I will appreciate any suggestions on a more sustainable design/development workflow. I want to implement it seriously and I sort of feel optimistic about it becoming a crate that others might find useful, especially after some unusually impressive benchmark results (I need some advice here too to make them more fair and rigorous, and to ensure that I am not misinterpreting things here). Here is the repo , if someone is interested but needs to take a look at the code to suggest what the proper tools may be in this case.

1 post - 1 participant

Read full topic