Why does unsafe multithreaded std:unordered_map crash more than std:map? | Hacker News Reader

Why does unsafe multithreaded std:unordered_map crash more than std:map?

devblogs.microsoft.com

92 pointsluu69 comments

A fascinating design decision of Hashtable in .NET is its support for multiple readers AND a single writer.

In C++ or Rust, we get multiple readers OR a single writer. Shared ref or exclusive mut, pick one. But in .NET we have AND not OR: one writer AND multiple readers, all concurrent.

This works because .NET's GC can tolerate the race. A writer may trigger a table rehash, and a reader will read either the old or new table. If the reader loads the old table, it won't be deallocated until it's done: the GC will keep it alive.

Any cool uses of this one writer AND multiple readers?

https://learn.microsoft.com/en-us/dotnet/api/system.collecti...

I'm surprised nobody mentioned the Rust crate left_right[1].

It's also a map that supports multiple readers AND a writer.

It does this by maintaining two maps, one used by the writer and one used by the readers and atomically swap the two when useful, the cool part is that reads are wait-free but the cost is at least double memory usage and slow writes (twice the work).

[1]: https://docs.rs/left-right/latest/left_right/

Nice! As far as I understand, it uses RCU-like epochs, except that the reclaimed memory is immediately used for the new version of the data, bounding the memory usage at the cost of having the writer block. The oplog seems quite an additional complication, but I guess it makes sense for costly updates. The simplest solution is to just copy the last version over the stale version.

edit: note this is not just a map datastructure. As far as I understand, left_right can wrap any data structure.

Reminds me of the shadow paging used in LMDB, which is effectively the same but at the page level rather than the whole tree and allows each reader their own context to read from, rather than a shared reader context.

The author of left_right has a really great YouTube channel on Rust programming: https://youtube.com/@jonhoo

How about many readers and zero writers? :)

For my text editor, I went with an immutable balanced tree. I was surprised by how easily I was about to implement all operations I needed with reasonable runtime complexity (log N mostly, operations like "give me a copy with element at position i removed"): https://github.com/alefore/edge/blob/master/src/language/con...

I use this throughout my editor. For example, I load a file into a sequence of lines represented here: https://github.com/alefore/edge/blob/8fdf7f76ffa167497a7e9e9...

I found that the good performance, relatively straightforward implementation and very strong thread safety (making the data immutable means a whole class of problems just disappears) works very well.

.NET Hashtable is roughly the same lousy bucketed hash table from C++ std::unordered_map. So, the hash table trick gets you to one of N linked lists (the buckets), and then you walk that linked list you found to see if a matching element is in the list.

Writing sometimes needs to "re-bucket" everything and during that process it's mayhem if you were stupid enough to be simultaneously looking something up (but in .NET this will be prevented†) but before and afterwards even write operations "just" add or remove elements to linked lists, which you're correct in a GC language it's not crucial to care that some reader may look at an element which you have meanwhile removed [in C++ that would be a use-after-free]

> Enumerating through a collection is intrinsically not a thread safe procedure. Even when a collection is synchronized, other threads can still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection during the entire enumeration or catch the exceptions resulting from changes made by other threads.

So, you know, congratulations you played silly games and you have won yourself a stupid prize.

This has basically the same "cool uses" as with an RwLock, AFAIU the readers aren't actually allowed to look at the hash table while it is being rehashed, they're silently held by the implementation.

You could do the "Reclaim data only once nobody is looking" in a non-GC language with any of the other concurrent reclamation techniques such as RCU or Hazard Pointers and in many cases you'd be fine with a reference counting approach (not always which is why these other techniques exist).

Edited To Add: † Huh. Maybe under GC they get away with doing all the work and then just pivoting to the new hashtable after rebucketing with a single writer? So then readers just get obsolete data for a while and it's the poor GC which has to cope with the mess.

Is it same for Dictionary? .People hardly use Hashtable these day

No, the documentation for Dictionary doesn’t make this guarantee, it’s explicit that readers are only allowed as long as the collection isn’t modified: https://learn.microsoft.com/en-us/dotnet/api/system.collecti...

Maybe that guarantee was too strong and prevented a more efficient implementation.

Rust has this as well but makes you explicitly state it using a wrapper type called refcell (internal vs external borrow checking, I think are the terms).

They're faster than mutexes, which themselves also internal borrow check, but also have the logic mechanic.

This allows you to make any type work similarly but eschew the overhead in cases where it's not needed.

No, RefCell relaxes the rules from requiring the borrowcheck rules be provably always followed at compile time to requiring the borrowcheck rules be actually followed in the codepaths actually run at runtime. You still can't have a mutation concurrently with a reader.

Sort of, refcell still enforces that shared and mutable borrows cannot coexist.

A similar case to what the parent describes is RCU or crossbeam's epoch-based reclaim.

You can easily write a concurrent hash table in C++ or Rust. I fail to understand your point.

How? I honestly don't know how to do it in C++ or Rust, without using exotic techniques like hazard pointers.

https://docs.rs/arc-swap/latest/arc_swap/ Is a basic rcu mechanism that doesn’t have the exotic requirements of urcu (but probably not as efficient). If you make the interior nodes of your data structure Arc (assuming they are large or expensive enough to warrant it), then updating is relatively fast. Of course you also want to be careful here to batch as many changes at once if you’re doing this at all frequently.

But ultimately I don’t recall anything special about the runtime semantics the first time I came across this technique which if I recall correctly came from the brilliant folk at Azul Systems for their JVM. You just need a way to atomically adjust certain nodes. And if I recall correctly Azul’s supported N concurrent writers that were all wait free (ie every thread participated in forward progress)

To be fair, RCU is about as exotic as hazard pointers. Then again, there is plenty of documentation for both and once you are familiar with them they lose a lot of their mystique.

You’re thinking of the kernel and urcu implementations. The RCU implementation that I linked here isn’t exotic at all. It creates a duplicate structure and atomically swaps pointers. If the swap fails because another update occurred, it tries creating a new duplicate structure running your RCU closure and swapping again. Forward progress is eventually made although it scales poorly if you have a lot of concurrent updaters.

So not quite as performant but in terms of having a writer and lots of concurrent readers, it achieves that requirement. And it’s data structure agnostic and you only need to pay this cost if you really have concurrency.

Well, my point is that hazard pointers are not really that exotic either :D.

This seems to be an implementation built on RCU, iiuc: https://github.com/urcu/userspace-rcu/blob/master/src/rculfh...

This looks rough: it spawns background "worker threads" for tasks like lazy resizing; and even with that it still sometimes takes locks (see resize_mutex).

If you search for "concurrent hash table <language>" or "concurrent map <language>" (being <language> Rust or C++) you get a number of open source libraries written using different techniques. I consider "exotic" a matter of opinion.

An atomic reference count seems sufficient, but I could be wrong.

It is actually quite tricky to lock-free swap a concurrently-accessed reference counted pointer. The reference count is not associated with the pointer, but with the pointee, so a 2CAS is not enough.

Typically you need hazard pointers or similar deferred reclamation tricks.

https://lib.rs/crates/dashmap

First time seeing dashmap, but a cursory inspection shows it works via sharded locks:

    pub struct DashMap<K, V, S = RandomState> {
        shift: usize,
        shards: Box<[RwLock<HashMap<K, V, S>>]>,
        hasher: S,
    }

so an array of RwLocks.

That's quite different than what .NET offers, which is multiple readers and a single writer with NO locks outside of the allocator/GC.

I'm not shilling for .NET (I've never written a .NET app) but it does have a really cool hash table.

> Shared ref or exclusive mut

There's std::shared_mutex, which allows multiple readers and a writer.

That's exactly the scenario your parent is describing. You can have (multiple) readers or a single writer. You cannot have both.

The analogous Rust type is std::sync::RwLock<T> (but as with Mutex, RwLock is a wrapper, so it is actually protecting something inside it, not just providing the raw mutex type).

If you've been using std::shared_mutex assuming you can have both then, I guess it's good luck that you didn't cause a deadlock of some sort, but at least this API unlike most C++ APIs isn't just "LOL, if you use this wrong it's Undefined Behaviour, all bets are off, goodbye" in the respect that matters to you.

Oh I see, sorry I misunderstood that. Yes indeed the readers won't be able read while the writer is writing.

From the article: std::map inserts are O(log n) while std::unordered_map inserts are O(1) and rehashes are O(n). Concurrent rehashes have a high chance of crashing, but I don't see how it follows that overall unordered_map crashes more than std::map.

Maybe it's beacause std::map tree nodes don't get reallocated while unordered_map hash buckets do ?

Let's walk through it in more detail.

Suppose you have two threads doing writes at a rate of r per second. Suppose that it takes time t to do an operation. Suppose that concurrent operations have a probability p of crashing. What rate do crashes happen at?

Well, the one thread spends time t * r per second in the operation. The other spends the same. So you spend time (r * t)^2 per second with concurrent accesses, and crashes happen at a rate p * (r * t)^2.

Now let's look at the normal case for a hash insert. t is small and constant in the size of the collection. p is proportional to 1/n. And therefore collisions happen at a rate of O((r * t)^2 / n).

Now let's think about the red-black tree. Exact numbers are calculated. While the writing part is at most O(log(n)). But on average you spend time O(log(n)) finding where to write, and only write O(1) nodes. Think half the time you only write once, 1/4 of the time you write once, rebalance once. 1/8 of the time you write once and rebalance twice. The result is complicated to analyze, but it works out as worse than the regular hash operation by a constant factor. So crashes happen at a rate O((r * t)^2 / n) with worse constants.

Now let's look at the resize operation. This works very differently. The first thread encounters resize every n operations, for a rate r/n. A resize takes time O(t * n). If any write comes in during that resize, the other thread will also do a resize, and they will crash. So the odds that we crash is the time of the operation, times the rate at which writes come, which is O(r * t * n). Multiplying this by the rate we get a probability of O(r/n * r * t * n) = O(r^2 * t).

The previous equation was smaller by a factor of t/n. But remember, t is a very small time (operations are fast) and n tends to be reasonably large (the size of the collection). The result is that race conditions happen dramatically more often for resizes of hashes than any other operation.

Rehashing the table affects every element. Rebalancing the tree only affects a few elements, and probably not one being concurrently accessed.

As soon as i saw microsoft.com, i knew this was gonna be a raymond chen article.

Well yeah, I assume that devblogs.microsoft.com hosts hundreds of blogs by Microsoft® Expert Valued Partners® for .NET® 365® selling all kinds of shitware, but they also host exactly one writer with interesting technical content.

Stephen Toub's posts about performance improvements in .NET disproves that assertion: https://devblogs.microsoft.com/dotnet/performance-improvemen... (Warning: link goes very long blog post)

Crashed a lot... more? You tell me crashing was expected default behaviour to a point where the suitability of implementation details was decided by how much one would crash?

> You tell me crashing was expected default behaviour to a point where the suitability of implementation details was decided by how much one would crash?

No, and Chen emphasizes this point repeatedly in his blog post. The customer knew the crashing was bad, but it wondered why switching to the unordered map caused the frequency to increase.

For threading-related problems, an increase in the crash frequency can be a good thing, since it makes the problem somewhat easier to reproduce and debug.

I wonder why he felt the need to reiterate the obvious here twice, about concurrent read/write being the true culprit. I mean, it's already obvious from the title that this is just an intellectual pursuit to satisfy some curiosity. Is it really that weird or unconventional of a question?

If you read his old blog posts from about 10 years ago he didn't reiterate anything. If you then read the comments on those posts you'll understand why he now does!

What would be a good way to test the author's hunch? Just instrument std::unordered_map and trace an execution until a crash occurs?

Ship v1. Collect crash reports. Switch collections. Ship v1.1. Collect crash reports. Compare.

Ship v1.2. Apologize to your users.

This article needs a mutex.

when you're done with the read lock, may i please acquire it?

Mom says it's my turn on the read lock

Why does running red lights crash more than driving the wrong way down a one-way street? Discuss among yourselves ...

Anyone making multithreaded code in c++ should be using thread sanitizer. Whether or not a specific datastruture crashes more in multithreaded code will not matter, since tsan will issue a warning on all unsafe accesses.

Unfortunately tsan is a pretty big performance hit (5x-15x with 5x-10x increase in memory) and has a non-zero false positive rate. So it’s not a “use almost always during development thing” like the address sanitizer is.

That said, it’s can be really helpful when you suspect a race condition.

In my experience, it has a near-zero false positive rate though.

After enough YOE you can perform tsan-like static analysis just by reading the code.

Given how many times I've seen people on the C++ standards committee make a concurrency mistake, I don't believe you. Thread safety is extraordinarily difficult to reason about by looking at code once you've moved beyond very basic designs.

Tsan is also not static analysis.

YOE = years of experience

Maybe if you work on a tiny codebase.

Thread sanitizer doesn't understand fences. It seems relacy is the only one that does.

If anyone knows how to make relacy run a somewhat fair scheduler please let me know - it told me a server thread that waited for work never made any progress, but it also never gave a client thread any cycles to submit work so that wasn't very informative.

(edit: just occurred to me I can probably fake it adequately by having a yield that makes the current thread start playing the role of the other service, coroutine style)

Just a minor point: while tsan is extremely helpful, it is not guaranteed to catch all data races.

Matches my experience. It does sometimes warn about race in 3rd party library (that are actual race usually, even though there might not be issues in practice) but then you can add suppression when fixing upstream is not an option.

Tsan doesn’t understand mach semaphores unfortunately.

I’m stunned that this article exists and was published by Microsoft. Unsafe access to either is clearly undefined behavior. Discussing which one is more or less undefined is like discussing whether it’s safer to run with scissors or a knife: it doesn’t really matter because you’re going to cut yourself badly and possibly in life-changing ways.

Please protect your STL data structures with a mutex. Please keep your thread communications sane. There’s no reason to think through why one is more prone to explosion than another; any conclusions you draw are at best only relevant to your current compiler and STL implementation, and maybe only during some phases of the moon.

"The customer understood that their code was broken either way. They just were curious why unordered_map seems to demonstrate the problem more clearly."

Seems reasonable to me. It's an interesting question even if any given answer is only valid under narrow conditions.

Raymond Chen has been at Microsoft since 92 on the shell team and has worked on OS/2, Windows 95, DirectX and others but is more well known for his 2003 blog "The Old New Thing" which does nerdy deep dives into the internals of Windows / Microsoft-verse and the various ways customers abuse it.

Have you ever wondered what’s up with the CF_SYLK and CF_DIF clipboard formats? [0]

Or why did the message on the Start menu change from Start to Ship It! for one build? [1]

Or how about filling in some gaps in the story of Space Cadet Pinball on 64-bit Windows [2]

[0] https://devblogs.microsoft.com/oldnewthing/20200226-00/?p=10...

[1] https://devblogs.microsoft.com/oldnewthing/20200505-00/?p=10...

[2] https://devblogs.microsoft.com/oldnewthing/20220106-00/?p=10...

Why stunned? The author reiterates 2 times that neither maps should be used in unsafe way.

Look at this from the point of code analysis - if "a bit more thread-safe" map is used - you have less chances to detect the problem in local testing & and may be surprised in prod. And, you may be even more surprised when switching to unordered map.

Usually, any big app has a huge tail of very rare crashes that nobody has time to fix, ever. Those rare crashes are indistinguishable from some system/hardware related faults (system OOM, system trying to kill an app, battery dying, bit flipping due to radiation/faulty silicon). And that's the point - if you are planning to change map to unordered map - look at the crashes list around map invocations and try to understand, if any of them are due to multithreading and not system/hw...

Clearly the author should have stated a third time not to violate thread safety, to prevent the article from being misinterpreted.

The counterargument to the IMHO highly destructive attitude of "learned ignorance" that you're espousing is easily summed up in one sentence: "If you don't break anything, you'll never learn how to fix anything."

Asking and answering "why" is an important educational process. I've met other developers like you, and quite frankly they've always been mediocre to abysmal in their work, especially when debugging, because they've almost completely lost the ability to reason and hypothesise.

From my experience there is a real issue of C and C++ developers treating undefined behavior as an error. Yet you can't reason around undefined behavior, you can't catch it at runtime and there are more ways how UB is meaningfully different than an error or bug in the program logic. I can see how such a post could inadvertently reinforce such a mindset. No clue if the person you are responding to had that in mind.

The article isn't an endorsement of using thread unsafe structures without protection in a multithreaded context. It's simply analyzing why the bug was less prevalent with one data structure vs. another. It's an interesting question.

It's like discussing if you have a better chance surviving against a Tiger or a Lion when armed with a machete. I'm not jumping into the arena with either one, but it can still make for good conversation.

This is essentially a personal blog of a long-term Microsoft employee on all sorts of interesting technical topics.

It isn't an official Microsoft publication.

One of today's lucky 10,000! Raymond Chen is a gem. His blog has many good features, I'll let you discover then for yourself.

https://xkcd.com/1053/

yet another reason to switch to rust

Given that “crash” in C++ has a 99% chance to mean “security issue”, and given that I have seen people “pragmatically” go with a solution that “crashes less” in the wild, I’m convinced that nothing good comes out of this line of reasoning.

Reply on news.ycombinator.com