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 ?
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.
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.
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.
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.
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.
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)
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.
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...
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.
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]
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.
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.
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?
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).
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://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.
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.
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 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.
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.
.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.
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).
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.
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.
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.
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.
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.
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!
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.
73 comments
[ 2.6 ms ] story [ 140 ms ] threadMaybe it's beacause std::map tree nodes don't get reallocated while unordered_map hash buckets do ?
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.
That said, it’s can be really helpful when you suspect a race condition.
Tsan is also not static analysis.
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)
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.
Seems reasonable to me. It's an interesting question even if any given answer is only valid under narrow conditions.
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...
It isn't an official Microsoft publication.
https://xkcd.com/1053/
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...
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.
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...
Maybe that guarantee was too strong and prevented a more efficient implementation.
Typically you need hazard pointers or similar deferred reclamation tricks.
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)
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.
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.
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.
There's std::shared_mutex, which allows multiple readers and a writer.
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.
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.
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/
edit: note this is not just a map datastructure. As far as I understand, left_right can wrap any data structure.
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.
A similar case to what the parent describes is RCU or crossbeam's epoch-based reclaim.
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.