3 ms·

Nobody has been able explain to me what would be lost if we defined data races to yield one of the values that had been written to the memory in the past, inste

Nobody has been able explain to me what would be lost if we defined data races to yield one of the values that had been written to the memory in the past, instead of being undefined. It is not as if any optimizer can see that you are racing and delete the code path that has it.

atq2119 3y ago
"One of the values written to memory" isn't really a thing when memory accesses can tear (e.g. because the values are 16 bytes large and are accessed using 8 byte memory ops). So it's not even necessarily about what would be lost, it's about what can be reasonably defined in the first place. If you restrict yourself to relaxed atomic loads and stores -- i.e., memory accesses that are atomic in the sense that they cannot tear, but don't have much in the way of ordering guarantees -- then you do get "one of the values that had been written to the memory in the past". Aside from memory tearing, one other issue is that you generally want to be able to rematerialize loads (i.e., in the face of register pressure, you may want to turn one load of a value into multiple loads instead of loading it once, then spilling to the stack and reloading from the stack). But when the compiler rematerializes a load, then you don't get "one of the values written to memory". From the perspective of the original program it looks like you get some weird superposition of values.
Gehinnn 3y ago
I'm pretty sure that you have either an undecidable problem or a non deterministic piece of code that sometimes computes some value, other times a different value, depending on how the threads are scheduled. Neither is good.
quelsolaar 3y ago
Let me _try_ to explain it. One reason is that non-atomic writes can be torn. So if you have a value like 0x00000000 and over write it with 0xFFFFFFFF, some hardware may do it as two separate writes. This means that another thread can read the data when its half way written and get 0xFFFF0000. I'm using a 32bit value here to illustrate In reality modern hardware is unlikely to tear it, but in other cases it may. Another issue is that what you are writing may depend on something else. Consider this code: x = 42; p = &x; these two operations are independent, and a compiler, CPU or memory system could chose to execute them in any order. This means that even if the second operation is "atomic" and another thread can only read the before or after value of p, another thread could read p and access it, before 42 is written to x. This is why the p = &x; needs a "release" barrier that guarantees that everything before it is completed before the change to p happens. Atomics are complex due to the way modern computers optimize and this is just a very surface level explanation. Still, I hope this helps.
- kaba0 3y ago
  “Fun” stuff: Rust also doesn’t prevent this for more complicated objects. The ‘Sync’ trait will get applied to any struct that has only ‘Sync’ constituents, but that means that such an object can be observable in inconsistent states (e.g. a strange Date object where year, month and day are all atomic numbers can be 2023-02-31).
bluGill 3y ago
A lot of extra CPU time wasted while caches synchronize even though the other CPU isn't running code that uses it. Most of the time the typical racey code works without locks, making everything not race means tode without a potential race still gets locks. Above I'm treating atomics and mutexs above.
pornel 3y ago
The optimizer assumes that a non-atomic non-volatile value written to memory stays the same, until some code that could modify it is executed. This allows a lot of obvious optimizations, like hoisting needlessly repeated computation out of loops, removal of redundant loads, and optimizations of common subexpressions and arithmetic. If a value in memory could suddenly revert to something else, then if obj.x == 1 { print(obj.x) } could print "2", and such paradoxes can lead to unsafety: if obj.x < array.len { array[obj.x] } Defining that values in memory can't be trusted would mean giving up on a lot of optimizations, and require implementations to emit a lot of mostly-useless copying of values to protect them from being unexpectedly modified.
kaba0 3y ago
This is what Java does, so in a way, data races are safe.

atq2119 3y ago

"One of the values written to memory" isn't really a thing when memory accesses can tear (e.g. because the values are 16 bytes large and are accessed using 8 byte memory ops). So it's not even necessarily about what would be lost, it's about what can be reasonably defined in the first place. If you restrict yourself to relaxed atomic loads and stores -- i.e., memory accesses that are atomic in the sense that they cannot tear, but don't have much in the way of ordering guarantees -- then you do get "one of the values that had been written to the memory in the past". Aside from memory tearing, one other issue is that you generally want to be able to rematerialize loads (i.e., in the face of register pressure, you may want to turn one load of a value into multiple loads instead of loading it once, then spilling to the stack and reloading from the stack). But when the compiler rematerializes a load, then you don't get "one of the values written to memory". From the perspective of the original program it looks like you get some weird superposition of values.

Gehinnn 3y ago

I'm pretty sure that you have either an undecidable problem or a non deterministic piece of code that sometimes computes some value, other times a different value, depending on how the threads are scheduled. Neither is good.

quelsolaar 3y ago

Let me _try_ to explain it. One reason is that non-atomic writes can be torn. So if you have a value like 0x00000000 and over write it with 0xFFFFFFFF, some hardware may do it as two separate writes. This means that another thread can read the data when its half way written and get 0xFFFF0000. I'm using a 32bit value here to illustrate In reality modern hardware is unlikely to tear it, but in other cases it may. Another issue is that what you are writing may depend on something else. Consider this code: x = 42; p = &x; these two operations are independent, and a compiler, CPU or memory system could chose to execute them in any order. This means that even if the second operation is "atomic" and another thread can only read the before or after value of p, another thread could read p and access it, before 42 is written to x. This is why the p = &x; needs a "release" barrier that guarantees that everything before it is completed before the change to p happens. Atomics are complex due to the way modern computers optimize and this is just a very surface level explanation. Still, I hope this helps.

kaba0 3y ago
“Fun” stuff: Rust also doesn’t prevent this for more complicated objects. The ‘Sync’ trait will get applied to any struct that has only ‘Sync’ constituents, but that means that such an object can be observable in inconsistent states (e.g. a strange Date object where year, month and day are all atomic numbers can be 2023-02-31).

bluGill 3y ago

A lot of extra CPU time wasted while caches synchronize even though the other CPU isn't running code that uses it. Most of the time the typical racey code works without locks, making everything not race means tode without a potential race still gets locks. Above I'm treating atomics and mutexs above.

pornel 3y ago

The optimizer assumes that a non-atomic non-volatile value written to memory stays the same, until some code that could modify it is executed. This allows a lot of obvious optimizations, like hoisting needlessly repeated computation out of loops, removal of redundant loads, and optimizations of common subexpressions and arithmetic. If a value in memory could suddenly revert to something else, then if obj.x == 1 { print(obj.x) } could print "2", and such paradoxes can lead to unsafety: if obj.x < array.len { array[obj.x] } Defining that values in memory can't be trusted would mean giving up on a lot of optimizations, and require implementations to emit a lot of mostly-useless copying of values to protect them from being unexpectedly modified.

kaba0 3y ago

This is what Java does, so in a way, data races are safe.