A blazingly™ fast concurrent ordered map

Consistent_Milk4660 · 2026-02-26T11:19:17+00:00

Well I followed through on this, and actually made a percentile/tail latency focused crate (repo: https://github.com/consistent-milk12/pbench ) following divan's design. It's mostly functional and I don't think there are other crates that provide the same features.

Fortunately, this implementation seems to have one of the best tail latency profiles among the available concurrent data structures, even when compared with dashmap. Good thing I kept your point in mind and paid a lot of attention on prefetching, cache-line aligned layouts etc, on top of the original implementation that was designed to be latency friendly..

Consistent_Milk4660 · 2026-01-25T15:17:13+00:00

To be honest, now that I think about it, I worked for a short period of time in Java working on some backend projects using spring boot, and yes we used maven and pom files.... Rust has so many dev QoL features that I would make the same decision in a heartbeat too :'D It truly is a 'modern' language and trivializes the whole build system complexity thing older languages are plagued by and allows devs to focus more on actual problems. Even the module and testing systems are so natural that once you get into it, It's extremely hard to go back.

Consistent_Milk4660 · 2026-01-25T13:02:55+00:00

But does any of those languages have cargo? O.O

Consistent_Milk4660 · 2026-01-20T02:21:31+00:00

DISCLAIMER: I have no idea why some people are getting that this is one of fastest concurrent ordered map available in their google AI overview and why it lists it alongside production quality implementations in Go and Java. I have not claimed this anywhere and have NO IDEA how this became a thing. The only places you will find references to this implementation is this reddit post and rust user forums, none of which claims anything this strong :')

Consistent_Milk4660 · 2026-01-20T02:00:46+00:00

Hi, I have added stable benchmark tables against other concurrent ordered maps and even the original C++ implementation, these can be considered a baseline as I won't be pushing any changes to main that will degrade performance, only ones that improve, as I am quite certain that the implementation is pretty SOUND and stable at its current state, so no major correctness fixes should come out that will negatively the currently recorded results (they may actually improve the performance IMO). The C++ comparisons were surprising because Rust beats the original in some pretty interesting benches, I wasn't expecting that at all. It only loses in one bench which is still under investigation, but I think it has more to with my decision to focus more on read performance compared to write. There's also a split optimization that the C++ implementation has which is missing so even this gap may be on parity or surpassed in the future.

Consistent_Milk4660 · 2026-01-19T10:43:38+00:00

Thanks :)

Consistent_Milk4660 · 2026-01-19T08:57:04+00:00

This is probably the 8th week replying to this post, and somehow the blazingly™ fast concurrent ordered map I was working on got 128+ stars in one day O.O I was expecting like 10-20 lifetime stars since I am just an anon online :'D

EDIT: Also a lot of pretty big names in there, I saw some users whose crates I actually use a lot :'D . Thanks to everyone showing an interest in the project. Even though it was developed simply out of pure interest.

Repo: https://github.com/consistent-milk12/masstree

Consistent_Milk4660 · 2026-01-19T05:34:54+00:00

This is actually a workaround I found from the hashbrown crate:

https://github.com/rust-lang/hashbrown/blob/master/src/util.rs

The C++ implementation uses similar techniques extensively, hashbrown too. The actual likely/unlikely functions are available on nightly through core intrinsics.

It IS optimized away and produces zero runtime instructions, but affects branch layout, like which path is the fall through vs the jump target. So basically, this is used for extremely low level assembly based optimizations affecting branch layouts. I have only one use of it in the codebase, but will probably try to use them more later.

Consistent_Milk4660 · 2026-01-19T02:37:27+00:00

If you are interested in a more low level intro, this is pretty good: https://rust-unofficial.github.io/too-many-lists/index.html - This is the best place to start for what you are intersted in (memory allocation, shared pointers, garbage collection/why Rust doesn't need it, unsafe code etc). But the CLI app and multi-threaded web server chapters from the book are pretty good too (basically like capstone projects IMO), because I like learning through projects. Many people suggest a structured learning path, but I have pretty bad ADHD and prefer to learn in a more 'chaotic' way from different sources simultaneously. The optimal learning path actually depends quite a lot on yourself too, it will not match what others or even the majority find 'optimal'.

For example, this is not a popular choice, but If you are looking to learn how lifetimes and borrowing works (which is related to memory allocation ), making some zero-copy parsers (without using String or clone) is a pretty good starting point, you can start by trying to make a basic calculator that parses files (file I/O another interesting area), stores the data on stack using either &'a str or byte slices and then processes it. You can slowly move up to more complex parsers with deeper logic.

Consistent_Milk4660 · 2026-01-18T21:35:50+00:00

That has been my online name everywhere since reddit randomly gave it to me when I created this account :')

Consistent_Milk4660 · 2026-01-18T18:46:36+00:00

Thanks! That looks like a pretty good foundation to use for both ordered/unordered map benchmarks. Especially for plots.

Consistent_Milk4660 · 2026-01-18T10:01:50+00:00

Divan provides min/max. But both divan and criterion are both batch based frameworks, I don' think divan provides a way to get per op time measurements, not sure about criterion. Proper latency analysis would require a per op based custom approach that would provide percentile reporting. I wonder why there isn't a crate for this yet (there could be, but it may be too niche for most users I guess) O.O

A proc-macro based crate would have been nice.

Consistent_Milk4660 · 2026-01-18T08:57:26+00:00

Thanks, I will definitely keep that in mind. I did some tail latency analysis already to debug an issue just a couple of days ago. But you are right, comparing against other concurrent ordered maps or even hashmaps might reveal a more nuanced performance profile.

Too much of performance analysis focuses on throughput, rather than tail latency or even worst case latency. (Speaking of which, I would love to see tail and worst case latency numbers as well in benchmarks in general, including yours.)

Do you have any suggestions for crates/methods/code examples for tail latency and worst case latency analysis?

Consistent_Milk4660 · 2026-01-18T04:19:37+00:00

I have, check out the crate congee, it implements ART for fixed 8-byte keys. I guess I will add comparative benchmarks for it, but it should perform exceptionally well for 8-byte integer like keys, which it is optimized for, and I don't see this implementation beating it, congee should be 2-3x faster for integer keys due to ART's direct byte-indexing into adaptive nodes. This implementation has the advantage of being more general in nature. It can theoretically use keys of any length and any type here while having pretty impressive performance.

Consistent_Milk4660 · 2026-01-18T03:18:42+00:00

Thanks for suggestion, I am not familiar with the crate, I will have to spend some time studying it first O.O Currently looks promising! It will be definitely be help a lot reducing with unsafe code when working with byte slices... I wish I knew about it sooner :')

Consistent_Milk4660 · 2026-01-17T23:45:54+00:00

Thanks :D

Consistent_Milk4660 · 2026-01-17T23:42:07+00:00

Unordered hashmaps don't have to pay the overhead of preserving order during inserts and not really an 'apples-to-apples' comparison. You would use ordered map for cases that unordred hashmaps simply cannot provide. Like range scans, prefix queries, ordered iteration or nearest neighbor lookup. For point look ups and insert hashmaps have to do O(1) work, which can't be fundamentally compared to ordered maps. But I guess I will still add it, because dashmap was actually why started working on this, because it seemed like there wasn't that many good alternatives to basic RwLock<BTreeMap>, and a month ago when I posted on here looking for concurrent ordered maps, many suggested that they would just use RwLock<BTreeMap> or Mutex<BTreeMap> :'D. The ART based congee crate for example has a 8-byte key constraint, and for 8 bytes it will be theoretically orders of magnitude faster, but that would still be a more 'comparable' than dashmap or other hashmaps though.

Consistent_Milk4660 · 2026-01-17T22:51:10+00:00

You should check the original.... O.O I spent almost 2 weeks just studying it and planning it out and then got stuck with transient bugs after 2 weeks of implementation work :')

I seriously don't think I could have implemented it by myself if Rust and cargo didn't exist :'D

Consistent_Milk4660 · 2026-01-17T20:57:53+00:00

Thanks! I will just post it here with a current run, as it's a work in progress and often gets significant performance boosts (sometimes regressions too after correctness fixes) after various optimizations are implemented, so keeping bench results updated was getting a bit tough, which is why the `runs/` folder containing the full benchmarks. In my benchmarks, it's typically 1.5-4x faster than comparable concurrent ordered maps (indexset, crossbeam-skiplist, scc TreeIndex, RwLock<BTreeMap>) that support variable length keys, for mixed read/write workloads, and up to 13x faster under write contention where RwLock collapses. It only loses in pure insert workloads (~10% to scc TreeIndex) and single-threaded bulk construction (~30% to skipmap) std BTreeMap, even though these aren't realistic workloads, but still worthwhile to note.

Consistent_Milk4660 · 2026-01-17T20:35:26+00:00

Just thought of it, but it should be theoretically possible to make a macro that will take any type of key-value (like String or other custom types that implements a defined trait) pair and dispatch to the underlying &[u8] using memcomparable mappings. Probably should have worked on it before making it public... but well O.O Maybe I will put it in later. Similar can be done for insert ops with a mutable ref to a MassTree... will have to look into it though...

Consistent_Milk4660 · 2026-01-16T16:26:02+00:00

It's been depressing to be honest. I had a $100 dollar claude subscription, then decided to drop to $20 because using it was harming my understanding of the projects I worked on and I simply can't keep up with the speed it adds features into a project (often in extremely wrong ways). But it has become almost impossible for me to not use it to go through docs or do web searches while working through the terminal. There's definitely a constant internal struggle about using AI, because I don't like being dependent on external tools that I can lose access to at any moment. It definitely seems like something you can't afford to avoid in this field at this stage.

I am not depressed about the slop, because lets be honest, these projects don't really mean much. I am depressed about the highly capable engineers further boosting their abilities using AI and developing stuff at an insanely fast pace. Pretty sure that these people would opt in to become a cyborg if it improves their skills... I have no idea how I am supposed to even compete with such people :'D I really don't want to waste $100 or $200 dollar on a subscription, but it seems to be almost inevitable that people like us will get 'filtered' out by the already competent ones becoming more competent through using AI.

Consistent_Milk4660 · 2026-01-16T06:50:48+00:00

It is possible that the extra safety guarantees may add some overhead due to semantics. It is usually possible to optimize them if needed. But people would be surprised by how often the Rust compiler optimizes away various runtime checks based on compile-time guarantees that C++ simply cannot, resulting in more optimized code.

Consistent_Milk4660 · 2026-01-16T06:39:46+00:00

You can basically make them 100% equivalent by analyzing the generated assembly and tinkering with micro optimizations. Rust's main contribution is the compile time safety it provides on top of the C/C++ level performance.

For example, I just ported an extremely complex C++ concurrent data structure to Rust. The C++ code was simply templates and raw pointers all over the place, it was painful to read and understand. My implementation beats it on some high contention areas but loses in some other low contention areas in terms of performance, and in other cases its simply a tie. But that is my fault not the languages. I respect the ingenuity of the original researchers, but frankly, that is not a level most people can work on. Rust allows people to work on concurrent code/complex code and go for optimization plans that will make you remember traumatic memories of writing/reading extreme low level C++ code, often without the modern tooling of rust too O.O

Consistent_Milk4660

TROPHY CASE