Finally something that I think is a worthwhile contribution from me to the Rust ecosystem :'D Almost 2 months of work porting this almost insane data structure from a research grade C++ implementation... but it seems to be worth it based on the current performance under high contention, where the std RwLock<BTreeMap> seems to fall behind significantly, so it may be of use for some actual projects. I am actually considering rewriting it in nightly because some of the unstable features would make the implementation much easier and maintainable. I will highly appreciate any feedback.
A high-performance concurrent ordered map for Rust. It stores keys as &[u8] and supports variable-length keys by building a trie of B+trees, based on the Masstree paper.
Keeping this post short, because I know it's a really niche and complex data structure that not many people will be interested in. Please check links below, I tried to keep an iterative divan benchmark record throughout the development, which you will be able to find in the repo inside the runs/ folder. It does win in almost all realistic workload against similar data structures compared with (which is highly suspicious and I am not sure what else I can do to make the benches more fair and rigorous O.O).
Disclaimer: Yes, a $20 claude subscription was used during development to write the large amount of tests and docs for the codebase :'D Sorry! I checked most of them, but some of the docs may still be stale, especially for the WIDTH 24 variant, which I wouldn't recommend using anyway.
Also, if anyone has time, please consider contributing by adding some more benchmarks. Please note that it is theoretically impossible for any complex concurrent data structure to compete with std's RwLock<BTreeMap> in PURE read cases, these data structures are optimized to perform under contention (concurrent read + write).
For example, here's a comparison between them, if you properly batch them, BTreeMap works well when there is no write contention. But if you even add 5% writers and increase contention, Rw:Lock<BTreeMap> starts to scale negatively with higher threads. Maybe someone will be able to provide a pattern to show otherwise:
β 02_point_get_zipf_64B β β β β β
β ββ masstree15 β β β β β
β β ββ 1 10.1 ms β 13.22 ms β 10.83 ms β 11.03 ms β 200 β 200
β β β 4.945 Mitem/s β 3.779 Mitem/s β 4.612 Mitem/s β 4.53 Mitem/s β β
β β ββ 2 11 ms β 14.16 ms β 11.51 ms β 11.74 ms β 200 β 200
β β β 9.09 Mitem/s β 7.057 Mitem/s β 8.685 Mitem/s β 8.517 Mitem/s β β
β β ββ 3 11.46 ms β 16.47 ms β 11.93 ms β 12.37 ms β 200 β 200
β β β 13.07 Mitem/s β 9.103 Mitem/s β 12.56 Mitem/s β 12.12 Mitem/s β β
β β ββ 4 11.61 ms β 16.77 ms β 11.84 ms β 12.48 ms β 200 β 200
β β β 17.22 Mitem/s β 11.92 Mitem/s β 16.88 Mitem/s β 16.01 Mitem/s β β
β β ββ 5 11.77 ms β 16.25 ms β 12.23 ms β 12.96 ms β 200 β 200
β β β 21.23 Mitem/s β 15.37 Mitem/s β 20.42 Mitem/s β 19.28 Mitem/s β β
β β β°β 6 11.94 ms β 16.16 ms β 12.2 ms β 12.87 ms β 200 β 200
β β 25.11 Mitem/s β 18.55 Mitem/s β 24.57 Mitem/s β 23.3 Mitem/s β β
β ββ parking_rwlock_btreemap β β β β β
β β ββ 1 9.136 ms β 14.92 ms β 9.469 ms β 10.04 ms β 200 β 200
β β β 5.472 Mitem/s β 3.35 Mitem/s β 5.28 Mitem/s β 4.975 Mitem/s β β
β β ββ 2 10.07 ms β 15.25 ms β 11.93 ms β 12.47 ms β 200 β 200
β β β 9.92 Mitem/s β 6.555 Mitem/s β 8.376 Mitem/s β 8.015 Mitem/s β β
β β ββ 3 10.51 ms β 16.94 ms β 12.7 ms β 13.1 ms β 200 β 200
β β β 14.27 Mitem/s β 8.851 Mitem/s β 11.8 Mitem/s β 11.44 Mitem/s β β
β β ββ 4 13.37 ms β 17.82 ms β 13.62 ms β 14.19 ms β 200 β 200
β β β 14.95 Mitem/s β 11.21 Mitem/s β 14.67 Mitem/s β 14.09 Mitem/s β β
β β ββ 5 14.78 ms β 18.5 ms β 15.57 ms β 15.96 ms β 200 β 200
β β β 16.9 Mitem/s β 13.51 Mitem/s β 16.04 Mitem/s β 15.65 Mitem/s β β
β β β°β 6 16.1 ms β 20.05 ms β 16.47 ms β 17.05 ms β 200 β 200
β β 18.63 Mitem/s β 14.95 Mitem/s β 18.21 Mitem/s β 17.58 Mitem/s β β
β ββ parking_rwlock_btreemap_batched β β β β β
β β ββ 1 9.028 ms β 15.3 ms β 9.565 ms β 10.54 ms β 200 β 200
β β β 5.538 Mitem/s β 3.267 Mitem/s β 5.226 Mitem/s β 4.741 Mitem/s β β
β β ββ 2 9.186 ms β 14.73 ms β 9.782 ms β 10.25 ms β 200 β 200
β β β 10.88 Mitem/s β 6.787 Mitem/s β 10.22 Mitem/s β 9.755 Mitem/s β β
β β ββ 3 9.431 ms β 14.52 ms β 9.906 ms β 10.3 ms β 200 β 200
β β β 15.9 Mitem/s β 10.32 Mitem/s β 15.14 Mitem/s β 14.55 Mitem/s β β
β β ββ 4 9.616 ms β 15.18 ms β 10 ms β 10.89 ms β 200 β 200
β β β 20.79 Mitem/s β 13.17 Mitem/s β 19.98 Mitem/s β 18.35 Mitem/s β β
β β ββ 5 9.708 ms β 15.07 ms β 10.09 ms β 10.73 ms β 200 β 200
β β β 25.75 Mitem/s β 16.58 Mitem/s β 24.75 Mitem/s β 23.29 Mitem/s β β
β β β°β 6 9.833 ms β 15.56 ms β 10.31 ms β 11.33 ms β 200 β 200
β β 30.5 Mitem/s β 19.27 Mitem/s β 29.09 Mitem/s β 26.45 Mitem/s β β
β ββ std_rwlock_btreemap β β β β β
β β ββ 1 9.051 ms β 13.67 ms β 9.332 ms β 9.582 ms β 200 β 200
β β β 5.524 Mitem/s β 3.655 Mitem/s β 5.357 Mitem/s β 5.218 Mitem/s β β
β β ββ 2 9.91 ms β 16.97 ms β 11.85 ms β 12.1 ms β 200 β 200
β β β 10.09 Mitem/s β 5.891 Mitem/s β 8.435 Mitem/s β 8.263 Mitem/s β β
β β ββ 3 11.31 ms β 18.32 ms β 12.74 ms β 12.92 ms β 200 β 200
β β β 13.25 Mitem/s β 8.184 Mitem/s β 11.76 Mitem/s β 11.6 Mitem/s β β
β β ββ 4 13.26 ms β 17.81 ms β 13.54 ms β 14.02 ms β 200 β 200
β β β 15.07 Mitem/s β 11.22 Mitem/s β 14.76 Mitem/s β 14.25 Mitem/s β β
β β ββ 5 13.44 ms β 18.26 ms β 14.65 ms β 15.23 ms β 200 β 200
β β β 18.6 Mitem/s β 13.69 Mitem/s β 17.05 Mitem/s β 16.41 Mitem/s β β
β β β°β 6 15.99 ms β 19.61 ms β 16.23 ms β 16.75 ms β 200 β 200
β β 18.75 Mitem/s β 15.29 Mitem/s β 18.48 Mitem/s β 17.9 Mitem/s β β
β β°β std_rwlock_btreemap_batched β β β β β
β ββ 1 9.245 ms β 12.93 ms β 9.584 ms β 9.845 ms β 200 β 200
β β 5.407 Mitem/s β 3.864 Mitem/s β 5.216 Mitem/s β 5.078 Mitem/s β β
β ββ 2 9.38 ms β 13.87 ms β 9.847 ms β 10.28 ms β 200 β 200
β β 10.66 Mitem/s β 7.209 Mitem/s β 10.15 Mitem/s β 9.721 Mitem/s β β
β ββ 3 9.559 ms β 13.25 ms β 10.1 ms β 10.38 ms β 200 β 200
β β 15.69 Mitem/s β 11.31 Mitem/s β 14.83 Mitem/s β 14.44 Mitem/s β β
β ββ 4 9.748 ms β 14.74 ms β 10.19 ms β 10.93 ms β 200 β 200
β β 20.51 Mitem/s β 13.56 Mitem/s β 19.62 Mitem/s β 18.29 Mitem/s β β
β ββ 5 9.981 ms β 17.08 ms β 10.37 ms β 11.12 ms β 200 β 200
β β 25.04 Mitem/s β 14.63 Mitem/s β 24.09 Mitem/s β 22.46 Mitem/s β β
β β°β 6 10.13 ms β 15.24 ms β 10.45 ms β 11.29 ms β 200 β 200
β 29.6 Mitem/s β 19.67 Mitem/s β 28.69 Mitem/s β 26.55 Mitem/s β β
ββ 03b_mixed_zipf_hotset_95_5_64B β β β β β
β ββ masstree15 β β β β β
β β ββ 1 3.884 ms β 7.671 ms β 4.062 ms β 4.409 ms β 200 β 200
β β β 12.87 Mitem/s β 6.517 Mitem/s β 12.3 Mitem/s β 11.33 Mitem/s β β
β β ββ 2 4.349 ms β 7.803 ms β 5.264 ms β 5.519 ms β 200 β 200
β β β 22.99 Mitem/s β 12.81 Mitem/s β 18.99 Mitem/s β 18.11 Mitem/s β β
β β ββ 3 4.698 ms β 9.504 ms β 6.172 ms β 6.891 ms β 200 β 200
β β β 31.92 Mitem/s β 15.78 Mitem/s β 24.3 Mitem/s β 21.76 Mitem/s β β
β β ββ 4 5.7 ms β 9.433 ms β 8.306 ms β 7.556 ms β 200 β 200
β β β 35.08 Mitem/s β 21.2 Mitem/s β 24.07 Mitem/s β 26.46 Mitem/s β β
β β ββ 5 6.227 ms β 10.1 ms β 7.921 ms β 7.885 ms β 200 β 200
β β β 40.14 Mitem/s β 24.75 Mitem/s β 31.56 Mitem/s β 31.7 Mitem/s β β
β β β°β 6 6.618 ms β 11.5 ms β 7.842 ms β 7.989 ms β 200 β 200
β β 45.33 Mitem/s β 26.06 Mitem/s β 38.25 Mitem/s β 37.54 Mitem/s β β
β ββ parking_rwlock_btreemap β β β β β
β β ββ 1 4.328 ms β 8.271 ms β 4.43 ms β 4.802 ms β 200 β 200
β β β 11.55 Mitem/s β 6.045 Mitem/s β 11.28 Mitem/s β 10.41 Mitem/s β β
β β ββ 2 6.492 ms β 13.85 ms β 10.85 ms β 11.12 ms β 200 β 200
β β β 15.4 Mitem/s β 7.218 Mitem/s β 9.208 Mitem/s β 8.988 Mitem/s β β
β β ββ 3 8.62 ms β 16.1 ms β 13.48 ms β 13.55 ms β 200 β 200
β β β 17.4 Mitem/s β 9.311 Mitem/s β 11.12 Mitem/s β 11.06 Mitem/s β β
β β ββ 4 16.08 ms β 22.4 ms β 17.17 ms β 17.43 ms β 200 β 200
β β β 12.43 Mitem/s β 8.928 Mitem/s β 11.64 Mitem/s β 11.46 Mitem/s β β
β β ββ 5 19.65 ms β 26.99 ms β 22.74 ms β 22.77 ms β 200 β 200
β β β 12.71 Mitem/s β 9.261 Mitem/s β 10.98 Mitem/s β 10.97 Mitem/s β β
β β β°β 6 24.23 ms β 30.68 ms β 28.07 ms β 27.52 ms β 200 β 200
β β 12.37 Mitem/s β 9.777 Mitem/s β 10.68 Mitem/s β 10.89 Mitem/s β β
β ββ parking_rwlock_btreemap_batched_reads β β β β β
β β ββ 1 4.278 ms β 6.527 ms β 4.363 ms β 4.503 ms β 200 β 200
β β β 11.68 Mitem/s β 7.659 Mitem/s β 11.45 Mitem/s β 11.1 Mitem/s β β
β β ββ 2 10.82 ms β 18.07 ms β 13.11 ms β 13.47 ms β 200 β 200
β β β 9.237 Mitem/s β 5.531 Mitem/s β 7.623 Mitem/s β 7.422 Mitem/s β β
β β ββ 3 19.41 ms β 29.09 ms β 21.95 ms β 22.23 ms β 200 β 200
β β β 7.724 Mitem/s β 5.155 Mitem/s β 6.833 Mitem/s β 6.745 Mitem/s β β
β β ββ 4 28.44 ms β 41.08 ms β 32.72 ms β 33.18 ms β 200 β 200
β β β 7.03 Mitem/s β 4.867 Mitem/s β 6.111 Mitem/s β 6.026 Mitem/s β β
β β ββ 5 36.19 ms β 54.42 ms β 43.69 ms β 43.87 ms β 200 β 200
β β β 6.906 Mitem/s β 4.593 Mitem/s β 5.721 Mitem/s β 5.697 Mitem/s β β
β β β°β 6 45.3 ms β 67.74 ms β 49.97 ms β 50.95 ms β 200 β 200
β β 6.621 Mitem/s β 4.428 Mitem/s β 6.002 Mitem/s β 5.887 Mitem/s β β
β ββ std_rwlock_btreemap β β β β β
β β ββ 1 4.354 ms β 9.043 ms β 4.507 ms β 4.613 ms β 200 β 200
β β β 11.48 Mitem/s β 5.529 Mitem/s β 11.09 Mitem/s β 10.83 Mitem/s β β
β β ββ 2 9.921 ms β 21.73 ms β 17.18 ms β 16.38 ms β 200 β 200
β β β 10.07 Mitem/s β 4.6 Mitem/s β 5.817 Mitem/s β 6.101 Mitem/s β β
β β ββ 3 15.52 ms β 27.17 ms β 20.99 ms β 21.61 ms β 200 β 200
β β β 9.658 Mitem/s β 5.519 Mitem/s β 7.143 Mitem/s β 6.939 Mitem/s β β
β β ββ 4 22.67 ms β 39.43 ms β 30.5 ms β 30.58 ms β 200 β 200
β β β 8.82 Mitem/s β 5.071 Mitem/s β 6.555 Mitem/s β 6.54 Mitem/s β β
β β ββ 5 30.77 ms β 47.94 ms β 37.77 ms β 37.92 ms β 200 β 200
β β β 8.122 Mitem/s β 5.213 Mitem/s β 6.617 Mitem/s β 6.591 Mitem/s β β
β β β°β 6 33.43 ms β 57.91 ms β 44.37 ms β 44.77 ms β 200 β 200
β β 8.973 Mitem/s β 5.18 Mitem/s β 6.76 Mitem/s β 6.699 Mitem/s β β
β β°β std_rwlock_btreemap_batched_reads β β β β β
β ββ 1 4.254 ms β 6.354 ms β 4.312 ms β 4.401 ms β 200 β 200
β β 11.75 Mitem/s β 7.868 Mitem/s β 11.59 Mitem/s β 11.36 Mitem/s β β
β ββ 2 12.04 ms β 19.87 ms β 15.38 ms β 15.05 ms β 200 β 200
β β 8.303 Mitem/s β 5.032 Mitem/s β 6.497 Mitem/s β 6.641 Mitem/s β β
β ββ 3 16.85 ms β 27.77 ms β 23.07 ms β 23.26 ms β 200 β 200
β β 8.901 Mitem/s β 5.399 Mitem/s β 6.5 Mitem/s β 6.447 Mitem/s β β
β ββ 4 22.45 ms β 36.7 ms β 30.43 ms β 30.56 ms β 200 β 200
β β 8.905 Mitem/s β 5.448 Mitem/s β 6.572 Mitem/s β 6.542 Mitem/s β β
β ββ 5 28.37 ms β 48.25 ms β 38.46 ms β 38.57 ms β 200 β 200
β β 8.81 Mitem/s β 5.18 Mitem/s β 6.5 Mitem/s β 6.481 Mitem/s β β
β β°β 6 35.44 ms β 58.99 ms β 46.56 ms β 46.84 ms β 200 β 200
β 8.462 Mitem/s β 5.084 Mitem/s β 6.442 Mitem/s β 6.403 Mitem/s β β
I really wasn't expecting this repo to get 108 stars this fast (!?). But thank you to everyone for the interest, I guess the complexity original implementation is well known among people working with data structures :'D
A RwLock<BTreeMap> requires an atomic write for any read operation (to acquire the read lock), so any concurrent map that avoids it can theoretically be faster.
I guess I should have made it clear that I was talking about concurrent ordered maps. I have only seen papaya (which is an unordered hashmap) beat RwLock, this implementation also uses papaya's memory reclamation crate. But as far as I know, no concurrent ordered maps are capable of beating RwLock for pure read cases.
Someone has brought to my attention that google's stupid AI overview lists this as one of the fastest concurrent ordered map available, I have not claimed this anywhere :')
Almost done with the project, the core API is there and most of the basic stuff + some specialized things one would expect from a Rust data structure. I would appreciate anyone taking a look and contributing or suggesting how/where SIMD can be leveraged. The most likely candidate probably is the suffix comparison algorithm for long keys. But to be honest, I have very little idea about this topic.
The implementation is already unusually fast, and beats the original C++ implementation in most of the benches, which makes me a bit suspicious. I couldn't break it with the stress tests I could think of, but It still needs further validation and testing.
As it somehow got an unexpected number of stars all of a sudden (close to 200 O.O), it could be an interesting first repo to contribute to if you are looking for contributing to open source projects Some areas that you can consider:
Running the benchmarks on a 16 or 32 physical core machine if you have access to it. My PC unfortunately only has 6 cores. I have noticed some performance degradation and bad scaling issues for 7 to 12 threads (SMT/Hyperthreading) and for greater than 12 threads (oversubscription)
Test cases and more rigorous benchmarks.
SIMD (Already described above)
loom and shuttle tests (this would probably be harder to work on)
Don't be ashamed of using AI to write code! A lot of users on here are rude and insulting about it but they will fade away if they reject this technology.
I am not ashamed, it's just that it often generates subtle inaccurate stuff in docs and tests that are very easy to miss when rechecking O.O The sorry was for the stuff that I missed.
If AI has been used to write the code, I think it's at least fair to give a visible warning, preferably at the top of the README.
I don't want to start a debate here, since I've already explained that more often than I should, but the reason of the warning is that LLMs are not an appropriate tool for writing code (even less for testing it), so it's a significant risk. I think it's good practice to make that visible to potential users. If it was used only for the documentation, though, it's not as problematic.
I agree, because I actually tried to write some parts of it in some of the older commits, and you will be able to see them if you search :'D , which looked alright at first but led to lots of transient bugs. When there was AI generated core logic, there was also an AI-Assist disclaimer in the README, but most of the AI generated code had to be removed apart from some boilerplate and copy pasted same module with some minor modifications for different variants of the same code. But I am working on fully rewriting the docs and tests too. The project itself is complex enough, that it should be quite obvious that it wasn't AI generated/vibecoded O.O
I can't claim that the implementation is completely sound though, even if the full project was hand written without any external tools, because it's an extremely complex concurrent data structure and I wouldn't be surprised if it takes months or years before I find some edge case that hasn't been addressed yet.
It will be funny when all the mayor companies like Microsoft, Google, OpenAI, SpaceX will print such warnings on their products
I agree that AI assistance should be labeled -- but more in a way to honor their contribution, similar to when your mom helped you by a homework task.
The final responsible for the quality of a product is by the human authors, and it makes no difference if there was AI assistance, or if it might have been created mostly by AI. Soon we will have no software products created fully without AI support -- companies trying to avoid AI will go bankrupt, and people trying to avoid using AI will lose their jobs fast. And AI support can be seen even as a quality indicator, if used correctly.
But at least I agree in one point: What is now often called "AI slop" can be a real pain when it is publicized, e.g. all the four sec videos on YouTube without AI indicator, and most importantly fake videos.
I agree, but I guess this an unpopular opinion in the rust community :'D but I am pretty sure that the expert engineers currently active in the industry are heavily using AI, even if they don't admit it directly. I understand the ideological position of being against it, but it's not a pragmatic position to take in such a competitive industry. You won't be able to keep up with your peers who have actual domain knowledge and are heavily using AI to speed up their work. The people making slop projects are not the problem, they are mostly just beginners. Senior devs on the other hand... they can literally do the work of several junior devs when they properly get accustomed to it. If you can't stop those in the top of the industry from using AI, it doesn't make much sense to discourage others O.O
EDIT: Also, I really don't have enough spare income to invest heavily in AI anyway, unlike the top companies and their engineers :'D
Look, I am quite ideologically against it myself and it's an interesting paper.
The study was done in early 2025, when agentic coding wasn't even a thing... O.O And I don't see a point in your bet either, literally all top companies are heavily invested in AI, and their employees are given access to cutting edge models with basically unlimited amount of resources.
Also, It unfortunately proves my point... Experienced devs will always go with using AI, and perceive it as something productive, because it makes their work easier, instead of making them pessimistic about AI. The models used were claude 3.5 and 3.7... these can't really be compared to current frontier models that excel in agentic coding. Be prepared to be thoroughly disappointed when/if they update this study this year.
Core Result
When developers are allowed to use AI tools, they take 19% longer to complete issuesβa significant slowdown that goes against developer beliefs and expert forecasts. This gap between perception and reality is striking: developers expected AI to speed them up by 24%, and even after experiencing the slowdown, they still believed AI had sped them up by 20%.
Below, we show the raw average developer forecasted times, and the observed implementation timesβwe can clearly see that developers take substantially longer when they are allowed to use AI tools.
I think the reason that some "expert software developers" fail to use AI is the same why they often fail to lead a team of developers, e.g. delegating (simpler) sub-tasks to team members. Many AI experts and companies like Microsoft already admits that they use AI internally a lot -- the job marked confirms this, and internal AI use might explain the currently fast progress in AI development itself. Some might hesitate to admit the use of AI yet. Note, the software industry has only very few experts and project leaders -- the majority of software devs are doing quite trivial plumbing work, which an AI can already do fine.
I guess I'm wasting my time arguing here, but I can't help but reply to this:
You know why this is? Because they are mandating it:
Sure lets them publish big numbers for AI adoption, but they stop standing for people wanting to use it at that point. At most, the number of employees who still refuse to use it has meaning now.
I mean, I agree with your points and want less AI adoption myself, so I don't see what you are trying to argue here :'D My $20 claude subscription is basically because I am afraid of falling behind other devs and have an up to date working knowledge of how to use this tool if needed :'D
This forced use of AI is pretty dystopian, I read that they have some pretty big rust projects planned, considering how buggy windows 11 has been based on recent reports, those repos would be quite interesting to go though :'D
Please, again: this isn't the place for a debate on AI; there are already other threads about it, and it's definitely not my intention to derail this one (sorry about that @consistent-milk12).
I think the fact the topic is constantly debated (even here) should be enough to suggest general transparency about using an LLM to write the code of an open-source project, which others might decide to depend on. Particularly with a language like Rust that's chosen for its safety.
Anyway, the OP had already replied, so the point for this project was moot.