Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Race Conditions Can Be Useful for Parallelism

shwestrick.github.io

Post reply on HN
Print view View original

51–60 of 72 posts

Re: Race Conditions Can Be Useful for Parallelism

#51

Post by moonchild »

kaba0 wrote: post #45
shwestrick wrote: post #41

Earlier quoted context omitted.

That's a nice example. It seems that data races in Java don't "catch fire"; is that correct? The catch-fire problem is pretty bad for languages like C/C++, which have undefined behavior for data races, and in this sense data races are "bugs by definition" in those languages.

Java’s primitives and references are guaranteed to be “tear-free”, which guarantees no “out-of-thin-air” values. So a field set to 1 and being written by several threads to 2 and 3 can only ever be observed as 1,2 or 3, no other value. Is that what you mean under not catching fire?

> Java’s primitives and references are guaranteed to be “tear-free”, which guarantees no “out-of-thin-air” values

Tear-free does not imply no out-of-thin-air. But, afaik, the java memory model protects from both tearing and oota.

Re: Race Conditions Can Be Useful for Parallelism

#52

Post by mgaunard »

nextaccountic wrote: post #42
mgaunard wrote: post #36

Earlier quoted context omitted.

I gave conditions upon which testing for equality is correct. Of course if the result is non-deterministic it doesn't satisfy those conditions.

Unfortunately it may be quite hard to certify that your program qualifies, specially if it's a high performance program that can't be single threaded. An innocuous-looking commit can completely undermine this property. Doubly so if you must guarantee determinism across multiple platforms! IEEE 754-2008 helps but it defines cross-platform determinism for just a subset of operations. Compilers can also sometimes botch…

Achieving exact or correctly-rounded results is much more work than that.

You can look at the crlibm papers for example.

Re: Race Conditions Can Be Useful for Parallelism

#53

Post by mgaunard »

raphlinus wrote: post #49
mgaunard wrote: post #40

Earlier quoted context omitted.

Typical technobabble from someone who doesn't really understand floating-point. Floating-point is not associative. Reordering operations yields different results, so no compiler will do so, unless you specifically disable standards conformance. The use of SIMD, which is just a type of instruction-level parallelism, has no effect on the result of floating-point operations, unless of course you reorder your operations…

The actual rules are very complicated. C allows greater precision for intermediate results but compilers are sometimes careful to stick to IEEE rounding. [1] contains a good general overview, and [2] talks about FMA in particular. And in [3] I've set up a Godbolt example to play with. By default -O3 gives you FMA, but -O or -O3 with -ffp-contract=off don't. So you absolutely can get different results depending on opt…

The rule is very simple, I'm not seeing anything in what you say suggesting that it isn't?

Re: Race Conditions Can Be Useful for Parallelism

#54

Post by squeaky-clean »

bheadmaster wrote: post #3

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demo…

> This article needs additional citations for verification. (July 2010).

The definition you quote has no linked citation on Wikipedia. Usually a good sign that you should not treat those statements as definitive. A good Wikipedia article should not state any "facts" without a direct means of verification. Otherwise it's considered "original research" and against the wiki policy for a high quality article.

https://en.m.wikipedia.org/wiki/Wikipedia:No_original_resear...

Re: Race Conditions Can Be Useful for Parallelism

#55

Post by kaba0 »

mgaunard wrote: post #40
nextaccountic wrote: post #29

Earlier quoted context omitted.

You get the same result if you run on the same architecture and with the same instructions (or if you run on machines that implement IEEE 754-2008 [*], which was the first standard that guaranteed cross-platform determinism for a subset of floating point operations, which means, no SIMD!! =/), and you don't have non-determinism introduced by thread interleaving and race conditions (unless you very carefully account f…

Typical technobabble from someone who doesn't really understand floating-point. Floating-point is not associative. Reordering operations yields different results, so no compiler will do so, unless you specifically disable standards conformance. The use of SIMD, which is just a type of instruction-level parallelism, has no effect on the result of floating-point operations, unless of course you reorder your operations…

You do realize programming languages don’t necessarily manipulate the architectures native floating point operations, but are free to define any semantics they want? You know, like it could have number types that work like in math, e.g. symbolic math tools does exactly that.

Also, that kind of language is absolutely not warranted.

Re: Race Conditions Can Be Useful for Parallelism

#56

Post by bheadmaster »

squeaky-clean wrote: post #54
bheadmaster wrote: post #3

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demo…

> This article needs additional citations for verification. (July 2010). The definition you quote has no linked citation on Wikipedia. Usually a good sign that you should not treat those statements as definitive. A good Wikipedia article should not state any "facts" without a direct means of verification. Otherwise it's considered "original research" and against the wiki policy for a high quality article. https://en.…

I used Wikipedia in order to have some kind of reference, but I was fairly sure of the meaning beforehand.

Searching the internet for "race condition definition" and taking the top few results brings several definitions that all agree in spirit with the Wikipedia one (see below).

If you know of any more reliable source that doesn't agree with Wikipedia on the definition of "race condition", please post it here. This is a honest request - I am always grateful to those who correct my mistakes (in good faith).

    wordnik [0]:  A flaw in a system or process whereby the output or result is unexpectedly and critically dependent on the sequence or timing of other events.

    techtarget [1]: A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly.

    techterms [2]: A race condition occurs when a software program depends on the timing of one or more processes to function correctly.

    javatpoint [3]: When the output of the system or program depends on the sequence or timing of other uncontrolled events, this condition is called Race Condition.

    technopedia [4]: A race condition is a behavior which occurs in software applications or electronic systems, such as logic systems, where the output is dependent on the timing or sequence of other uncontrollable events.
[0] https://www.wordnik.com/words/race%20condition

[1] https://www.techtarget.com/searchstorage/definition/race-con...

[2] https://techterms.com/definition/race_condition

[3] https://www.javatpoint.com/what-is-race-condition

[4] https://www.techopedia.com/definition/10313/race-condition

Re: Race Conditions Can Be Useful for Parallelism

#57

Post by bheadmaster »

chrisseaton wrote: post #6
bheadmaster wrote: post #3

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demo…

I don't know where Wikipedia got this 'substantive behaviour' requirement from, but for example it explicitly isn't part of the definition in the industry's definitive reference for parallelism - Padua. > A race condition occurs in a parallel program execution when two or more threads access a common resource, e.g., a variable in shared memory, and the order of the accesses depends on the timing, i.e., the progress o…

Hey, I've just downloaded PADUA (http://dx.doi.org/10.1145/2633685), and skimming through it, I can't find a single mention of the phrase "race condition".

Is this the paper you're referring to? If not, could you please provide a reference to which PADUA you're referring to? I'd really like to read more on the subject, especially if the source is, as you claim, an industry reference.

Re: Race Conditions Can Be Useful for Parallelism

#58

Post by asveikau »

remram wrote: post #34
chrisseaton wrote: post #6

Earlier quoted context omitted.

I don't know where Wikipedia got this 'substantive behaviour' requirement from, but for example it explicitly isn't part of the definition in the industry's definitive reference for parallelism - Padua. > A race condition occurs in a parallel program execution when two or more threads access a common resource, e.g., a variable in shared memory, and the order of the accesses depends on the timing, i.e., the progress o…

By this definition, every access to a shared resource is a race condition, e.g. even when properly acquiring a lock. It is common knowledge that you introduce locks to remove race conditions so I would say something is definitely missing from the definition.

I think "remove" the race condition is the wrong word. It should be "resolve" the race conditions.

The race exists because there are multiple accesses. This is resolved when there is a protocol for deciding who proceeds and who waits for the other.

Re: Race Conditions Can Be Useful for Parallelism

#59

Post by smallnamespace »

chrisseaton wrote: post #31
ajross wrote: post #26

Earlier quoted context omitted.

I think you missed the point. Let me expand. I mean, yes, what you say is true, but it just amounts to saying "synchronization is a solvable problem". At their core, ALL synchronization paradigms (spin polling, interrupt masking, OS-managed process suspend, hardware memory barriers, weird lockless tricks like Dekker's algorithm, you name it) can be understood to be ways of enforcing "para-determinism" on environments…

If you can't observe the non-determinism, then is it really non-determinism? Your processor executes a single thread of instructions also in a non-deterministic order, based on complex internal state. We'd never say it was non-deterministic, as you can't detect it.

It's visible from the perspective of the software engineer who molds non-deterministic abstractions into predictable interactions for the user.

Re: Race Conditions Can Be Useful for Parallelism

#60

Post by chrisseaton »

bheadmaster wrote: post #57
chrisseaton wrote: post #6

Earlier quoted context omitted.

I don't know where Wikipedia got this 'substantive behaviour' requirement from, but for example it explicitly isn't part of the definition in the industry's definitive reference for parallelism - Padua. > A race condition occurs in a parallel program execution when two or more threads access a common resource, e.g., a variable in shared memory, and the order of the accesses depends on the timing, i.e., the progress o…

Hey, I've just downloaded PADUA ( http://dx.doi.org/10.1145/2633685 ), and skimming through it, I can't find a single mention of the phrase "race condition". Is this the paper you're referring to? If not, could you please provide a reference to which PADUA you're referring to? I'd really like to read more on the subject, especially if the source is, as you claim, an industry reference.

David Padua, https://link.springer.com/referencework/10.1007/978-0-387-09....
Post reply on HN