5 ms·

is there any situation where a data race might be useful or accommodatable?

by adtac 6y ago

bflesch 6y ago
Querying multiple backends and responding with the data that has been received first. Not sure if this technique is really in use, but I figure this could be an optimization for dns queries and the like.
- Znafon 6y ago
  This is exactly how the "Happy Eyeballs" algorithm in RFC 8305 works: https://en.wikipedia.org/wiki/Happy_Eyeballs https://en.wikipedia.org/wiki/Happy_Eyeballs
- PudgePacket 6y ago
  Definitely in use, I know at least Google does this internally.
chrisseaton 6y ago
For example, some profilers that count the number of times something is run will update a counter without any synchronisation. This risks lost updates, but since you really just need to know if the counter is very low or very high a few lost updates here or there don't really matter. But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
- jfkebwjsbx 6y ago
  +1, at $DAYJOB we use intentional data races all the time for similar purposes.
- robocat 6y ago
  > a few lost updates here or there don't really matter jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788 https://news.ycombinator.com/item?id=23079788
  - chrisseaton 6y ago
    Well I don't know what to tell you except this is how real production compilers written by experts work in practice. https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e94e838214a1b1274b1/compiler/src/org.graalvm.compiler.truffle.runtime/src/org/graalvm/compiler/truffle/runtime/OptimizedCallTarget.java#L816-L818 https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e9... You can argue this is a bug and they shouldn't write like this, but they don't consider it a bug and they do write like this.
  - yencabulator 6y ago
    Profiling is a tricky edge case though. If gathering the profiling data costs too much, the results are completely useless. Especially relevant is all the quirky side effects like cache pressure. So your choices here tend to be: sometimes wrong, or completely useless.
PeterisP 6y ago
Let's say you have query that returns a bunch of rows from a sharded database by asking every shard and naively combining their responses by simply forwarding all rows as soon as you receive them. That's a data race, the result will vary between executions because the row order will be different depending on how fast the various servers respond, but acknowledging that the order is not-well defined or guaranteed makes this data race accomodatable and even useful, since that gives a performance benefit compared to any solution that needs to ensure a specific order of these rows.
- zozbot234 6y ago
  This is not a "data race" in a formal sense. A data race involves multiple threads accessing a non-atomic data object in ways that might result in an unintended and inconsistent state if the accesses overlap. That's always a bug.
  - jfkebwjsbx 6y ago
    A data race does not necessarily imply a bug, even within your definition (which is only relevant for classical multithreaded applications).
    - steerablesafe 6y ago
      In C++ a data race is UB, so it is most definitely always a bug there.
      - CodesInChaos 6y ago
        The C++ standard's definition of a datarace only applies to ordinary memory access and rules those cases UB. But if you port such code to use relaxed load/store operations it's just as racey, but no longer UB. I'd consider still consider those cases data races, even though they don't meet the C++ standard's definition of them.
        6y ago
Unklejoe 6y ago
One time, I wrote a small network protocol stack to handle some proprietary UDP-based protocol that supported fragmentation. Since the header on each fragment contained the total message size, I was able to pre-allocate the full size of the message upon receipt of the first fragment. Then, as fragments arrived, I would copy their data into their respective areas of the message. Typically, everything would arrive in order, so the message would be copied from beginning to end, piece by piece. However, since this was Ethernet/UDP, it was possible for frames to arrive out of order. This would result in the message being pieced together, with each fragment filling in its hole until all fragments have been received. I guess this is a form of a data race? Or rather, a case where a data race at least wasn't detrimental.
- Liquid_Fire 6y ago
  A data race requires multiple threads to access the same memory at the same time and at least one of them to be writing the data. There is no data race in your example, since the fragments are all written to different parts of memory, unless you had something else reading the message while the individual fragments were still being written.
  - deleted 6y ago
    [deleted]
Measter 6y ago
I have one example where I didn't see a race as an issue. I was transferring data from one thread, to a second thread which would process it after a delay. This transfer was done by locking a mutex, then pushing it onto a queue. The second thread does an unsynchronized fetch of the queue length, and then uses that fetched length as a condition in a loop that does a synchronised dequeue of a single item. In this case, the race condition is not a problem, because the only place that data is removed is in that loop, which is a synchronised access. So the worse case for a race here is that the length that's been read is less than the actual length, which is not a problem because that new data will just be handled the next time round.
- StillBored 6y ago
  Well for the readers (not saying you have a bug), what you describe can fail on any processor that doesn't implement TSO. Due to the fact that the write of your "queue length" may be visible before the queued item is fully visible. Meaning you read garbage from the newly queued item. Worse, even on a TSO architecture, unless you have a way to explicitly guarantee a compiler fence or there is an explicit data dependency the compiler is likely free to hoist the code which updates the queue length ahead of the code doing the queue update. Again meaning the unsyncronized thread reads that there is a new queue item before that queue item is visible to the reader. How critical this ends up being to the program is heavily dependent on the queue data structure and how its being manipulated. But in a simple copy/linked list type situation referencing garbage data is quite likely. A lot of traditional comp sci programs are plenty happy to teach about data synchronization primitives but completely fail to mention that most general API (posix/etc) primitives also have read/write fences implied. Those fences are as important on any processor made in the last two decades as the atomic operations themselves. As generally the implementations also provide both architectural memory barriers as well as compiler level fencing to assure the compiler isn't reordering the primitive with the code it is intended to protect. Going further, many architectures provide unfenced atomics. So, if you decide to code your own atomic_inc/swap/etc you have to also understand the memory model of the target machine before you have actually created something equivalent to what is taught in your average comp-sci department.
  - 6y ago
abtinf 6y ago
Any system where the only useful data is whatever was last written. In certain kinds of signals intelligence software, the primary concern is access to the current frame of data. You don’t want to miss an RF peak that lasts just a few nanoseconds. It can be preferable to have half the the frame overwritten mid-processing every few million iterations than to slow down each iteration and force a lower overall refresh rate.
CodesInChaos 6y ago
Data races on normal memory access are undefined behaviour in many languages (e.g. C, C++, Rust), so I assume that you mean races using atomic loads with relaxed ordering. One practical example of using those is Hogwild, which is an implementation of stochastic gradient descent which skips synchronization on individual parameter updates, assuming that it'll converge even if some writes are lost or some reads are stale. https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approach-to-parallelizing-stochastic-gradient-descent https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approa...
threatofrain 6y ago
IMO most front end JS apps have to deal with data races over the wire with multiple API calls, so it’s more like a natural condition of driving.

is there any situation where a data race might be useful or accommodatable?

by adtac 6y ago

is there any situation where a data race might be useful or accommodatable?

Querying multiple backends and responding with the data that has been received first. Not sure if this technique is really in use, but I figure this could be an optimization for dns queries and the like.

Znafon 6y ago
This is exactly how the "Happy Eyeballs" algorithm in RFC 8305 works: https://en.wikipedia.org/wiki/Happy_Eyeballs https://en.wikipedia.org/wiki/Happy_Eyeballs
PudgePacket 6y ago
Definitely in use, I know at least Google does this internally.

chrisseaton 6y ago

For example, some profilers that count the number of times something is run will update a counter without any synchronisation. This risks lost updates, but since you really just need to know if the counter is very low or very high a few lost updates here or there don't really matter. But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.

jfkebwjsbx 6y ago
+1, at $DAYJOB we use intentional data races all the time for similar purposes.
robocat 6y ago
> a few lost updates here or there don't really matter jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788 https://news.ycombinator.com/item?id=23079788
- chrisseaton 6y ago
  Well I don't know what to tell you except this is how real production compilers written by experts work in practice. https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e94e838214a1b1274b1/compiler/src/org.graalvm.compiler.truffle.runtime/src/org/graalvm/compiler/truffle/runtime/OptimizedCallTarget.java#L816-L818 https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e9... You can argue this is a bug and they shouldn't write like this, but they don't consider it a bug and they do write like this.
- yencabulator 6y ago
  Profiling is a tricky edge case though. If gathering the profiling data costs too much, the results are completely useless. Especially relevant is all the quirky side effects like cache pressure. So your choices here tend to be: sometimes wrong, or completely useless.

PeterisP 6y ago

Let's say you have query that returns a bunch of rows from a sharded database by asking every shard and naively combining their responses by simply forwarding all rows as soon as you receive them. That's a data race, the result will vary between executions because the row order will be different depending on how fast the various servers respond, but acknowledging that the order is not-well defined or guaranteed makes this data race accomodatable and even useful, since that gives a performance benefit compared to any solution that needs to ensure a specific order of these rows.

zozbot234 6y ago
This is not a "data race" in a formal sense. A data race involves multiple threads accessing a non-atomic data object in ways that might result in an unintended and inconsistent state if the accesses overlap. That's always a bug.
- jfkebwjsbx 6y ago
  A data race does not necessarily imply a bug, even within your definition (which is only relevant for classical multithreaded applications).
  - steerablesafe 6y ago
    In C++ a data race is UB, so it is most definitely always a bug there.
    - CodesInChaos 6y ago
      The C++ standard's definition of a datarace only applies to ordinary memory access and rules those cases UB. But if you port such code to use relaxed load/store operations it's just as racey, but no longer UB. I'd consider still consider those cases data races, even though they don't meet the C++ standard's definition of them.
      - 6y ago

Unklejoe 6y ago

One time, I wrote a small network protocol stack to handle some proprietary UDP-based protocol that supported fragmentation. Since the header on each fragment contained the total message size, I was able to pre-allocate the full size of the message upon receipt of the first fragment. Then, as fragments arrived, I would copy their data into their respective areas of the message. Typically, everything would arrive in order, so the message would be copied from beginning to end, piece by piece. However, since this was Ethernet/UDP, it was possible for frames to arrive out of order. This would result in the message being pieced together, with each fragment filling in its hole until all fragments have been received. I guess this is a form of a data race? Or rather, a case where a data race at least wasn't detrimental.

Liquid_Fire 6y ago
A data race requires multiple threads to access the same memory at the same time and at least one of them to be writing the data. There is no data race in your example, since the fragments are all written to different parts of memory, unless you had something else reading the message while the individual fragments were still being written.
- deleted 6y ago
  [deleted]

Measter 6y ago

I have one example where I didn't see a race as an issue. I was transferring data from one thread, to a second thread which would process it after a delay. This transfer was done by locking a mutex, then pushing it onto a queue. The second thread does an unsynchronized fetch of the queue length, and then uses that fetched length as a condition in a loop that does a synchronised dequeue of a single item. In this case, the race condition is not a problem, because the only place that data is removed is in that loop, which is a synchronised access. So the worse case for a race here is that the length that's been read is less than the actual length, which is not a problem because that new data will just be handled the next time round.

StillBored 6y ago
Well for the readers (not saying you have a bug), what you describe can fail on any processor that doesn't implement TSO. Due to the fact that the write of your "queue length" may be visible before the queued item is fully visible. Meaning you read garbage from the newly queued item. Worse, even on a TSO architecture, unless you have a way to explicitly guarantee a compiler fence or there is an explicit data dependency the compiler is likely free to hoist the code which updates the queue length ahead of the code doing the queue update. Again meaning the unsyncronized thread reads that there is a new queue item before that queue item is visible to the reader. How critical this ends up being to the program is heavily dependent on the queue data structure and how its being manipulated. But in a simple copy/linked list type situation referencing garbage data is quite likely. A lot of traditional comp sci programs are plenty happy to teach about data synchronization primitives but completely fail to mention that most general API (posix/etc) primitives also have read/write fences implied. Those fences are as important on any processor made in the last two decades as the atomic operations themselves. As generally the implementations also provide both architectural memory barriers as well as compiler level fencing to assure the compiler isn't reordering the primitive with the code it is intended to protect. Going further, many architectures provide unfenced atomics. So, if you decide to code your own atomic_inc/swap/etc you have to also understand the memory model of the target machine before you have actually created something equivalent to what is taught in your average comp-sci department.
- 6y ago

abtinf 6y ago

Any system where the only useful data is whatever was last written. In certain kinds of signals intelligence software, the primary concern is access to the current frame of data. You don’t want to miss an RF peak that lasts just a few nanoseconds. It can be preferable to have half the the frame overwritten mid-processing every few million iterations than to slow down each iteration and force a lower overall refresh rate.

CodesInChaos 6y ago

Data races on normal memory access are undefined behaviour in many languages (e.g. C, C++, Rust), so I assume that you mean races using atomic loads with relaxed ordering. One practical example of using those is Hogwild, which is an implementation of stochastic gradient descent which skips synchronization on individual parameter updates, assuming that it'll converge even if some writes are lost or some reads are stale. https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approach-to-parallelizing-stochastic-gradient-descent https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approa...

threatofrain 6y ago

IMO most front end JS apps have to deal with data races over the wire with multiple API calls, so it’s more like a natural condition of driving.