Race Conditions Can Be Useful for Parallelism • Hacker News Board

Re: Race Conditions Can Be Useful for Parallelism

#31

Post by chrisseaton » Sun, Oct 02, 2022, 2:41 PM UTC

ajross wrote: post #26

chrisseaton wrote: post #15

Earlier quoted context omitted.

> That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems) There are plenty of examples of entirely deterministic parallel models. Fork-join for one.

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.

Re: Race Conditions Can Be Useful for Parallelism

#32

Post by layer8 » Sun, Oct 02, 2022, 2:47 PM UTC

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

Re: Race Conditions Can Be Useful for Parallelism

#33

Post by hegelstoleit » Sun, Oct 02, 2022, 2:50 PM UTC

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?

Re: Race Conditions Can Be Useful for Parallelism

#34

Post by remram » Sun, Oct 02, 2022, 3:00 PM UTC

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…

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.

Re: Race Conditions Can Be Useful for Parallelism

#35

Post by shwestrick » Sun, Oct 02, 2022, 3:09 PM UTC

kazinator wrote: post #24

shwestrick wrote: post #17

Earlier quoted context omitted.

Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctness, which is exactly what we're doing here.

If we put on a cynical hat, your page reads like "I've never heard of lock-free algorithms based on atomic operations. I therefore must have just invented it and I get to name it: how about beneficial use of race conditions?"

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

Re: Race Conditions Can Be Useful for Parallelism

#36

Post by mgaunard » Sun, Oct 02, 2022, 3:10 PM UTC

nextaccountic wrote: post #27

mgaunard wrote: post #16

Earlier quoted context omitted.

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

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.

Re: Race Conditions Can Be Useful for Parallelism

#37

Post by mgaunard » Sun, Oct 02, 2022, 3:11 PM UTC

touisteur wrote: post #21

mgaunard wrote: post #16

Earlier quoted context omitted.

There is nothing wrong with testing for equality so long as your computation is exact or correctly-rounded.

Yes, I know. For purely sequential code that's the actual use (though sometimes, golden tests are generated through matlab or python, in double precision and then every divergence becomes a game of whack a mole. And don't start me on x87-80 bits extended precision suddenly compiled to SSE, so actual ieee754... We have integrated some of the FP static and dynamic analysis tools in our CI/CD pipeline for new code but u…

There are simple tools that tell you how many of your floating-point digits are just propagated rounding errors.

Re: Race Conditions Can Be Useful for Parallelism

#38

Post by kazinator » Sun, Oct 02, 2022, 3:13 PM UTC

shwestrick wrote: post #35

kazinator wrote: post #24

Earlier quoted context omitted.

If we put on a cynical hat, your page reads like "I've never heard of lock-free algorithms based on atomic operations. I therefore must have just invented it and I get to name it: how about beneficial use of race conditions?"

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.

Re: Race Conditions Can Be Useful for Parallelism

#39

Post by shwestrick » Sun, Oct 02, 2022, 3:13 PM UTC

bheadmaster wrote: post #28

shwestrick wrote: post #17

Earlier quoted context omitted.

Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctness, which is exactly what we're doing here.

I've personally only heard the term "race condition" used to refer to bugs that have their source in non-deterministic execution of programs. In most cases, they refer to a specific sequence of events that the programmer did not foresaw, which lead to incorrect computation. Using the term "race condition" in context of correct programs would make it cover exactly the same universe of programs as the term "non-determi…

Ah I see. That's a fair point!

When talking about this kind of stuff to people who are unfamiliar with, say, lock-freedom, I've found that "non-determinism" is too vague --- people start thinking about things like randomness, or user interaction, etc. In contrast, the term "race condition" seems to hit the nail on the head.

But certainly, "race condition" also carries with it a bit of baggage ;)

Re: Race Conditions Can Be Useful for Parallelism

#40

Post by mgaunard » Sun, Oct 02, 2022, 3:23 PM UTC

nextaccountic wrote: post #29

chrisseaton wrote: post #20

Earlier quoted context omitted.

I think some people have gotten the mistaken idea that floating point arithmetic is inherently somehow non-deterministic. It is of course entirely deterministic, and if you do the same FP operations in the same order you will get the same result.

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 so that they may be parallelized.

What does affect the result of floating-point operations is when rounding happens and at what precision. If we're talking about C, the compiler is allowed to run intermediate operations with higher precision than that mandated by its type. This is merely so that it can use x87 which is 96-bit long by default and only round when it spills to memory and needs to store a 64-bit or 32-bit value. Compilers have flags to disable that behaviour, and it doesn't apply when the SSE unit instead of x87 is used. Using SSE for floating-point doesn't necessarily mean it's using SIMD, most of the instructions have scalar variants.

Another example is FMA, which might be substituted for any multiply+add operations.

In practice if your code breaks with this it just means it was incorrect in the first place.