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

41–50 of 72 posts

Re: Race Conditions Can Be Useful for Parallelism

#41

Post by shwestrick »

layer8 wrote: post #32

> I’m not talking about data races. Data races are typically bugs, by definition. One notable exception is the Racy Single-Check Idiom: http://javaagile.blogspot.com/2013/05/the-racy-single-check-... It is particularly suitable for lazy initialization in code that is typically (but not necessarily) executed single-threaded, and is famously used in Java’s String.hashCode() implementation.

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.

Re: Race Conditions Can Be Useful for Parallelism

#42

Post by nextaccountic »

mgaunard wrote: post #36
nextaccountic wrote: post #27

Earlier quoted context omitted.

There is if the algorithm contains race conditions that cause non-deterministic output. The submitted article goes above and beyond to guarantee that the code always output the same answer even though it has race conditions. But that's sometimes not possible or, if it's possible, it's too much of a hassle so it's rarely done. For example, this project https://github.com/EmbarkStudios/texture-synthesis generates textu…

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 your FP code (there's a number of gotchas - for example, if any library anywhere in your program uses -ffast-math, it may infect the whole program https://stackoverflow.com/questions/68938175/what-happens-if...)

Re: Race Conditions Can Be Useful for Parallelism

#43

Post by bheadmaster »

kazinator wrote: post #38
shwestrick wrote: post #35

Earlier quoted context omitted.

Whoa, uhh, I mean, that's an extremely unfair and inaccurate characterization.

Sure, and one that one can avoid bringing on oneself by not abusing/twisting/redefining common terminology.

Eh, I personally wouldn't be so hard on someone because of language. Words don't have definite meanings on their own, it's our general agreement that makes them meaningful. And the meaning of words are often overlapping, shades-of-grey kind of deal, with even more subtle differences in individual understanding of them. Language is hard.

Moreover, polite explanations may bring enlightenment, but aggressive scoldings are almost guaranteed stop people from accepting your words, even if they're true, because in order to accept their truth, they have to accept the unpleasant implications of your words.

I think learning should generally be as pleasant as possible. Putting the work in is hard enough as it is.

Re: Race Conditions Can Be Useful for Parallelism

#44

Post by kaba0 »

tialaramex wrote: post #23
tonyarkles wrote: post #11

Earlier quoted context omitted.

> And for associative and commutative functions it doesn’t matter what order they’re executed in the final result is always the same. Not directed at you specifically, but just a reminder for anyone who hasn’t been burned by it yet: floating point addition is not associative. (a+b)+c != a+(b+c). It’s close, but if you’re not careful you can get bad results where the accumulated small errors turn into wrong answers.

Not just floating point maths either. The built-in "integers" in your computer don't behave like the integers taught in school either but that's how we tend to think about them. This is why I argue trapping is the most acceptable choice for arithmetic problems in general purpose languages, if the program tries to add 150 to 150 in an unsigned 8-bit integer, that's a programming error. By all means offer wrapping arit…

It can overflow, but integer math is associative and commutative still, isn’t? It’s just modulo the biggest representable number (if unsigned).

Re: Race Conditions Can Be Useful for Parallelism

#45

Post by kaba0 »

shwestrick wrote: post #41
layer8 wrote: post #32

> I’m not talking about data races. Data races are typically bugs, by definition. One notable exception is the Racy Single-Check Idiom: http://javaagile.blogspot.com/2013/05/the-racy-single-check-... It is particularly suitable for lazy initialization in code that is typically (but not necessarily) executed single-threaded, and is famously used in Java’s String.hashCode() implementation.

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?

Re: Race Conditions Can Be Useful for Parallelism

#46

Post by kazinator »

bheadmaster wrote: post #43
kazinator wrote: post #38

Earlier quoted context omitted.

Sure, and one that one can avoid bringing on oneself by not abusing/twisting/redefining common terminology.

Eh, I personally wouldn't be so hard on someone because of language. Words don't have definite meanings on their own, it's our general agreement that makes them meaningful. And the meaning of words are often overlapping, shades-of-grey kind of deal, with even more subtle differences in individual understanding of them. Language is hard. Moreover, polite explanations may bring enlightenment, but aggressive scoldings a…

> I think learning should generally be as pleasant as possible.

If you want pleasant learning on the Internet, don't "learn by teaching" through blogs that mislead other learners, even if only in terminology use.

People will tear that apart.

Re: Race Conditions Can Be Useful for Parallelism

#47

Post by chrisseaton »

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.

Usually you’re adding locks not to remove the race condition but to make them not a bug.

Re: Race Conditions Can Be Useful for Parallelism

#48

Post by shwestrick »

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?

Perfect. Yes, that's exactly right -- if the language semantics is able to guarantee a set of possible values for a data-racy read, then it doesn't catch fire.

The catch-fire terminology comes from the analogy that, as soon as a data race occurs, the semantics of the program completely explodes, and all guarantees are lost---the program is then allowed to do literally anything. This is sometimes known as "DRF-SC or catch fire": either the program is data-race-free (and therefore its executions are sequentially consistent), or the program has undefined behavior.

Infamously, the C memory model has the catch-fire problem. And therefore, any language which relies on the C memory model can catch-fire. As of today, I believe this includes C/C++, Swift, Rust, and probably a few others.

Re: Race Conditions Can Be Useful for Parallelism

#49

Post by raphlinus »

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…

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 optimization levels.

[1]: https://randomascii.wordpress.com/2012/03/21/intermediate-fl...

[2]: https://kristerw.github.io/2021/11/09/fp-contract/

[3]: https://godbolt.org/z/eTz8o6b3P

Re: Race Conditions Can Be Useful for Parallelism

#50

Post by shwestrick »

hegelstoleit wrote: post #33

If you're just doing BFS why do you care who the parent is? Why not just choose the parent to be the predecessor? I.e if you visit 4 from 1, then 1 is the parent. Why do you need to check a list of potential parents?

When visiting vertices in parallel, there might be multiple potential parents that all attempt to visit the same vertex simultaneously. So, we need a way of picking which parent "wins".
Post reply on HN