7 ms·
Why does unsafe multithreaded std:unordered_map crash more than std:map?
- PessimalDecimal 3y agoWhat would be a good way to test the author's hunch? Just instrument std::unordered_map and trace an execution until a crash occurs?
- tedunangst 3y agoShip v1. Collect crash reports. Switch collections. Ship v1.1. Collect crash reports. Compare.
- saagarjha 3y agoShip v1.2. Apologize to your users.
- xuhu 3y agoFrom 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 ?
- tedunangst 3y agoRehashing the table affects every element. Rebalancing the tree only affects a few elements, and probably not one being concurrently accessed.
- btilly 3y agoLet'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.
- kazinator 3y agoWhy does running red lights crash more than driving the wrong way down a one-way street? Discuss among yourselves ...
- deleted 3y ago[deleted]
- mathiasgredal 3y agoAnyone 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.
- uluyol 3y agoJust a minor point: while tsan is extremely helpful, it is not guaranteed to catch all data races.
- jenadine 3y agoMatches 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.
- moregrist 3y agoUnfortunately 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.
- moregrist 3y agoI’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.
- aidenn0 3y agoIt'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.
- pinum 3y ago"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.
- yalok 3y agoWhy 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...
- xyst 3y agoyet another reason to switch to rust
- ridiculous_fish 3y agoA 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.collections.hashtable https://learn.microsoft.com/en-us/dotnet/api/system.collecti...
- leosanchez 3y agoIs it same for Dictionary? .People hardly use Hashtable these day
- codeflo 3y agoNo, 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.collections.generic.dictionary-2?view=net-7.0#thread-safety https://learn.microsoft.com/en-us/dotnet/api/system.collecti... Maybe that guarantee was too strong and prevented a more efficient implementation.
- abacate 3y agoYou can easily write a concurrent hash table in C++ or Rust. I fail to understand your point.
- ridiculous_fish 3y agoHow? I honestly don't know how to do it in C++ or Rust, without using exotic techniques like hazard pointers.
- foota 3y ago
- hindsightbias 3y agoThis article needs a mutex.
- Racing0461 3y agoAs soon as i saw microsoft.com, i knew this was gonna be a raymond chen article.
- dmurray 3y agoWell 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.
- kryptiskt 3y agoStephen Toub's posts about performance improvements in .NET disproves that assertion: https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/ https://devblogs.microsoft.com/dotnet/performance-improvemen... (Warning: link goes very long blog post)
- codeflo 3y agoGiven 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.
- bruce343434 3y agoI 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?
- iamds 3y agoIf 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!
- Traubenfuchs 3y agoCrashed 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?
- Majromax 3y ago> 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.