How can race conditions be useful?

Question

One of the answers to the question of what race conditions are mentioned low-level algorithms deliberately using race condition. How can race conditions be beneficial?

EDIT: Concurrency and queues are a good example of deliberately not caring about ordering of things, as long as nothing is lost. Any ideas on how "really hairy low-level algorithms do this on purpose"?

Costanzo

At the time of asking, didn't have enough reputation to comment the mentioned answer. Commented now. Maybe the author will notice. – Costanzo

I think his point is not that the race condition is useful, but rather that it isn't catastrophic. – Forgiving

Googling "intentional race condition" gives some links that seem to be relevant. – Petrifaction

@EvgenyKluev, I used every synonym imaginable, but not intentional. This is good. – Costanzo

I've never seen anything like this implemented, but I wonder if a PRNG couldn't use an intentional race condition to inject some hardware randomness. – Weevil

Answer 1

Not all races are equally bad.

The worst kind of race that you can get is reading of partial results. This is what Herb Sutter referred to as 'seeing pink elephants': your program is able to observe an intermediate state that violates all invariants.

The typical example here are concurrent non-atomic writes. If one thread reads from a variable that is concurrently written by another thread, the reader might obtain complete garbage. Not only can you not tell whether the reader will see the old value or the new value, it might actually see a value that was never written by anyone. These kinds of data races need to be avoided at all costs, as it's pretty much impossible to reason about the observed values in any way. C++ for example sends you straight to undefined-behavior-land in this case.

A less critical kind of race is when all data accesses are atomic, so you know that readers will only ever observe fully written values, but the order is unspecified. So you don't know whether the value that you read is actually the newest or whether two values that you read together were actually in memory at the same time. It is often useful to accept this for performance reasons. A prominent example here are distributed applications: Synchronizing data over the network is particularly slow, so it is often accepted that certain nodes may have an outdated view of the world but are still able to perform work based on that state. Think of a search engine cache: It's better to give a fast result based on yesterday's cache than to give a slow result or no result at all.

Similar examples occur in non-distributed environments. Consider a lock-free queue: You usually don't care about the exact order in which items end up in the queue. All producers 'race' to inserting items to the back of the queue and similarly all consumers 'race' to consume the front item of the queue. However, as long as you can guarantee that no items are accidentally lost or corrupted, this reduced level of control is acceptable.

Krusche

Answer 2

One such case (at least it can be thought of as a race condition, although it might be arguable if the term hold here), is when the threads are competing for finding some solution in multiple ways, and the first to get there can end the entire algorithm. see for e.g. - http://parasail-programming-language.blogspot.co.il/2010/06/intentional-race-condition-in-parasail.html

Analgesia

I don't think the phrase "race condition" applies to this one. Reaching a conclusion from two paths does not create a conflict scenario but a condition or decision scenario. That said, thanks for introducing this blog. Interesting read. – Striptease

@Xephon, I tend to agree, but the writer obviously doesn't so it's worth the discussion. – Analgesia

@Xephon: The term "race condition" applies even in cases where program behavior would be unaffected by "who won" in the absence of optimizations. For example, something like x=foo->field1; ... y=x; while something else might be writing foo->field1 could break if a compiler, thinking nothing could change foo->field1, replaces the former code with x=foo->field1; ... y=foo->field1;. – Niccolite