15 ms·

A similar thing is that I often come across people who are well-informed but still surprised that compilers will combine two observable operations into one, and

A similar thing is that I often come across people who are well-informed but still surprised that compilers will combine two observable operations into one, and complain that some other thread somehow 'should' be able to observe the intermediate state. But I don't understand how they think they would be able to tell the difference between an interleaving that never happens to happen, and one that will never happen.

historyloop 5y ago
It can be tricky in that fuzzing your program to discover race conditions seems to behave perfectly on one compilation target where these atomics are detected and reified, while you later discover on another platform surprisingly your app crashes 20% of the time. Ideally we test our applications on all hardware, with all configuration permutations etc. etc. In practice we do rely on our compilers translating our intent accurately and sometimes such edge cases matter. Compatibility is a tricky thing. It's kind of like the argument whether adding optional arguments to a function breaks BC. It doesn't break BC if you don't pass those parameters. But if for some reason you were passing extra parameters hoping they'd be ignored (for example as a handler some other place) then adding optional parameters WILL break BC and cause your software's behavior to be undefined.
- gizmo686 5y ago
  It is not about translating intent accurately. What you need is for compilation to be fully specified. Anywhere where there is multiple correct ways to compile something introduces a risk for bugs that only show up with some compilers. If you are a compiler or library writer, one solution is to avoid having useful properties that are not part of the spec. For instance, Go does not guarantee any particular iteration order for hashmaps; so they go out of there way to randomize the iteration order, thereby preventing developers from writing code that depends on a deterministic order. In the case of threading, what you would need to do is essentially have a compiler/runtime that goes out of its way to order and time operation in a random/adversarial manner. I've seen research that looks into doing this in a VM environment; which would be inhibited by the type of compiler optimizations being discussed. And others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order. Ultimately, fuzzing and testing can only give you confidence that what is being tested is mostly correct. It can never give you confidence that what is written is entirely correct. If you want confidence in the latter, you need to invest in some form of static analysis (which could either be built into the language, such as a type system, or be an external analysis tool). Ultimatly, writing even a moderately complicated program (by modern standards) with full confidence in its correctness would involve advancing the state of the art of the field by decades (if not longer). For the most part, the field just doesn't care about programs being fully correct; and accept it as a fact of life that going onto new/untested platforms and configurations will introduce/expose bugs.
  - b3morales 5y ago
    Very interesting. I would love to see tools emerge out of that research. In my experience one of the basic problems with testing/verifying concurrent code is that it is often difficult-to-impossible to perturb a particular part of the system, to exercise different orderings, and thus find corners.
    - seppel 5y ago
      Helgrind does something like this: https://www.valgrind.org/docs/manual/hg-manual.html https://www.valgrind.org/docs/manual/hg-manual.html
      - b3morales 5y ago
        Good to know, thanks!
  - nyanpasu64 5y ago
    > In the case of threading, what you would need to do is essentially have a compiler/runtime that goes out of its way to order and time operation in a random/adversarial manner. > others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order. Loom[1] is somewhat of that. It's a testing system (not a runtime for a full app) which tests multiple permutations of program execution (all possible permutations I think, limited by test case complexity or an optional "maximum thread switch count"), as well as modeling atomic/weak memory effects to some degree. [1]: https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom
  - historyloop 5y ago
    > It is not about translating intent accurately. What you need is for compilation to be fully specified. If you know how complicated the transformation pipeline is on a typical compiler, you'll realize that's pretty much impossible. And that pipeline is specific not only to your code, compiler settings, but also your target machine, and is constantly in flux, update to update. Even if it could be documented, no one would read the documentation.
kccqzy 5y ago
The article has this very nice example here: x.fetch_add(1, std::memory_order_relaxed); y.fetch_add(1, std::memory_order_relaxed); x.fetch_add(1, std::memory_order_relaxed); y.fetch_add(1, std::memory_order_relaxed); Can a different thread observe x and y only incremented once? Before the optimization yes, it's possible. After the optimization, no, it's not possible. The compiler removes a possible observable state in the course of optimization, and that occasionally surprises people.
- chrisseaton 5y ago
  > and that occasionally surprises people But what did they want? They tell me they're not happy with 0% chance of some interleaving they need. Are they happy with 0.000000000001%? I'm not sure I understand the practical difference between that and 0%? Can I tell them it is possible, but rely on the death of the universe happening before they have a right to complain it didn't turn up yet? If they have some hard minimum they require, then what do they expect me to do? Completely abstract from the system scheduler to make it happen? Doesn't seem a reasonable expectation from programmers on compiler writers, and likely wouldn't really be what they wanted even if I made it happen.
  - dataflow 5y ago
    It might be 0.000000000001% but it need not be, right? That's kind of the point. I'm pretty sure I could write you a program where the probability of observing that would be (say) 50% without the optimization, and with the optimization that would go to 0%, defeating the program. Should that be allowed? This is basically a statistical/probabilistic version of another problem: should a compiler be allowed to change the time complexity of an algorithm? If I write linear search, and the compiler proves the list is sorted, should it be allowed to switch to binary search—or vice-versa? Traditionally the answer might be 'yes', but it's not exactly hard to argue an answer of 'no' might also be desirable in a number of situations. Now in this case, it's not the time complexity that's changing, but the statistical properties of the program... and while in some cases it might be negligible (1E-10 or what have you), that's not necessarily the case, at which point a difference in degree really can become a difference in kind.
voidnullnil 5y ago
So what's the motivation for the article? Presumably someone complained that the compiler optimizing atomics broke their code.
- chrisseaton 5y ago
  If they need some interleaving to happen at least n% of the time for their program to work... what am I supposed to do? Because it was never guaranteed to be interleaved at least n% of the time, even when the atomics were not merged. Do they want me to bypass the system scheduler and run threads concurrently with forced interleavings against a statistical distribution? I doubt they want that. So what do they want?
overgard 5y ago
> A similar thing is that I often come across people who are well-informed but still surprised that compilers will combine two observable operations into one Well, think of it this way, if you're not into compilers wouldn't you expect your code to run as written? Especially if you put a breakpoint in there and you can see each step happening sequently. I don't really think people that don't know these things should be viewed as ignorant because the compiler tends to be doing some very unintuitive things. IMO everyone would be better off if somehow the tooling or the compiler could report some of these things in an easy to visualize not-super-verbose way.
- chrisseaton 5y ago
  > Well, think of it this way, if you're not into compilers wouldn't you expect your code to run as written? But the possible and actual interleavings aren't written in the program - so how can I guess what the user needs from what's written?
  - Retric 5y ago
    Consider the reverse. What if the interleaving was undesirable, would you like some way to be informed that it’s impossible so you don’t have to reason about it? When trying to reason about code, finding somethings that looks like a bug but isn’t can result in a lot of wasted effort.
    - chrisseaton 5y ago
      > What if the interleaving was undesirable, would you like some way to be informed that it’s impossible That's like synchronised in Java or any other kind of atomic block or serialising block - that's already a thing.
      - Retric 5y ago
        That information is moving in the wrong direction. I don’t want the programmer to be telling a compiler what to do, I want the compiler to inform the programmer what it did.
lmilcin 5y ago
I think at least regarding concurrency, most developers need to rely on a model that is "good enough". You can't know everything, therefore you need to contend with knowing at least enough that is necessary to do your work. Thinking that atomics will not be optimized by compiler is "good enough" in my opinion for almost, and I really mean almost, everybody. Heck, I interview people and atomics optimization is one of my staple questions (Tell me, what does volatile do in Java, exactly?). I have never heard a thorough answer to that question and yet people do work as developers and do produce working applications. The only real users of these optimizations are atomics primitives developers, and the use it to improve them a tiny bit in some special cases. You can technically contrive a test where you run an update that changes something to 1, then immediately to 2 on each iteration. Then you try to look at it from another core and you would expect that at least once in a blue moon you will see 1. But I just don't see any sanely written application to rely on that kind of behavior.
spacechild1 5y ago
It's because people still confuse std::atomic with volatile. Actually, there is a way to get both behaviors: 'volatile std::atomic'. Personally, I never had a situation where I would've needed that, and I use atomics on a regular basis.

historyloop 5y ago

It can be tricky in that fuzzing your program to discover race conditions seems to behave perfectly on one compilation target where these atomics are detected and reified, while you later discover on another platform surprisingly your app crashes 20% of the time. Ideally we test our applications on all hardware, with all configuration permutations etc. etc. In practice we do rely on our compilers translating our intent accurately and sometimes such edge cases matter. Compatibility is a tricky thing. It's kind of like the argument whether adding optional arguments to a function breaks BC. It doesn't break BC if you don't pass those parameters. But if for some reason you were passing extra parameters hoping they'd be ignored (for example as a handler some other place) then adding optional parameters WILL break BC and cause your software's behavior to be undefined.

gizmo686 5y ago
It is not about translating intent accurately. What you need is for compilation to be fully specified. Anywhere where there is multiple correct ways to compile something introduces a risk for bugs that only show up with some compilers. If you are a compiler or library writer, one solution is to avoid having useful properties that are not part of the spec. For instance, Go does not guarantee any particular iteration order for hashmaps; so they go out of there way to randomize the iteration order, thereby preventing developers from writing code that depends on a deterministic order. In the case of threading, what you would need to do is essentially have a compiler/runtime that goes out of its way to order and time operation in a random/adversarial manner. I've seen research that looks into doing this in a VM environment; which would be inhibited by the type of compiler optimizations being discussed. And others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order. Ultimately, fuzzing and testing can only give you confidence that what is being tested is mostly correct. It can never give you confidence that what is written is entirely correct. If you want confidence in the latter, you need to invest in some form of static analysis (which could either be built into the language, such as a type system, or be an external analysis tool). Ultimatly, writing even a moderately complicated program (by modern standards) with full confidence in its correctness would involve advancing the state of the art of the field by decades (if not longer). For the most part, the field just doesn't care about programs being fully correct; and accept it as a fact of life that going onto new/untested platforms and configurations will introduce/expose bugs.
- b3morales 5y ago
  Very interesting. I would love to see tools emerge out of that research. In my experience one of the basic problems with testing/verifying concurrent code is that it is often difficult-to-impossible to perturb a particular part of the system, to exercise different orderings, and thus find corners.
  - seppel 5y ago
    Helgrind does something like this: https://www.valgrind.org/docs/manual/hg-manual.html https://www.valgrind.org/docs/manual/hg-manual.html
    - b3morales 5y ago
      Good to know, thanks!
- nyanpasu64 5y ago
  > In the case of threading, what you would need to do is essentially have a compiler/runtime that goes out of its way to order and time operation in a random/adversarial manner. > others that modify the compiler itself to replace the concurrency primitives with runtime functions, that can then execute them in a fuzzed order. Loom[1] is somewhat of that. It's a testing system (not a runtime for a full app) which tests multiple permutations of program execution (all possible permutations I think, limited by test case complexity or an optional "maximum thread switch count"), as well as modeling atomic/weak memory effects to some degree. [1]: https://github.com/tokio-rs/loom https://github.com/tokio-rs/loom
- historyloop 5y ago
  > It is not about translating intent accurately. What you need is for compilation to be fully specified. If you know how complicated the transformation pipeline is on a typical compiler, you'll realize that's pretty much impossible. And that pipeline is specific not only to your code, compiler settings, but also your target machine, and is constantly in flux, update to update. Even if it could be documented, no one would read the documentation.

kccqzy 5y ago

The article has this very nice example here: x.fetch_add(1, std::memory_order_relaxed); y.fetch_add(1, std::memory_order_relaxed); x.fetch_add(1, std::memory_order_relaxed); y.fetch_add(1, std::memory_order_relaxed); Can a different thread observe x and y only incremented once? Before the optimization yes, it's possible. After the optimization, no, it's not possible. The compiler removes a possible observable state in the course of optimization, and that occasionally surprises people.

chrisseaton 5y ago
> and that occasionally surprises people But what did they want? They tell me they're not happy with 0% chance of some interleaving they need. Are they happy with 0.000000000001%? I'm not sure I understand the practical difference between that and 0%? Can I tell them it is possible, but rely on the death of the universe happening before they have a right to complain it didn't turn up yet? If they have some hard minimum they require, then what do they expect me to do? Completely abstract from the system scheduler to make it happen? Doesn't seem a reasonable expectation from programmers on compiler writers, and likely wouldn't really be what they wanted even if I made it happen.
- dataflow 5y ago
  It might be 0.000000000001% but it need not be, right? That's kind of the point. I'm pretty sure I could write you a program where the probability of observing that would be (say) 50% without the optimization, and with the optimization that would go to 0%, defeating the program. Should that be allowed? This is basically a statistical/probabilistic version of another problem: should a compiler be allowed to change the time complexity of an algorithm? If I write linear search, and the compiler proves the list is sorted, should it be allowed to switch to binary search—or vice-versa? Traditionally the answer might be 'yes', but it's not exactly hard to argue an answer of 'no' might also be desirable in a number of situations. Now in this case, it's not the time complexity that's changing, but the statistical properties of the program... and while in some cases it might be negligible (1E-10 or what have you), that's not necessarily the case, at which point a difference in degree really can become a difference in kind.

voidnullnil 5y ago

So what's the motivation for the article? Presumably someone complained that the compiler optimizing atomics broke their code.

chrisseaton 5y ago
If they need some interleaving to happen at least n% of the time for their program to work... what am I supposed to do? Because it was never guaranteed to be interleaved at least n% of the time, even when the atomics were not merged. Do they want me to bypass the system scheduler and run threads concurrently with forced interleavings against a statistical distribution? I doubt they want that. So what do they want?

overgard 5y ago

> A similar thing is that I often come across people who are well-informed but still surprised that compilers will combine two observable operations into one Well, think of it this way, if you're not into compilers wouldn't you expect your code to run as written? Especially if you put a breakpoint in there and you can see each step happening sequently. I don't really think people that don't know these things should be viewed as ignorant because the compiler tends to be doing some very unintuitive things. IMO everyone would be better off if somehow the tooling or the compiler could report some of these things in an easy to visualize not-super-verbose way.

chrisseaton 5y ago
> Well, think of it this way, if you're not into compilers wouldn't you expect your code to run as written? But the possible and actual interleavings aren't written in the program - so how can I guess what the user needs from what's written?
- Retric 5y ago
  Consider the reverse. What if the interleaving was undesirable, would you like some way to be informed that it’s impossible so you don’t have to reason about it? When trying to reason about code, finding somethings that looks like a bug but isn’t can result in a lot of wasted effort.
  - chrisseaton 5y ago
    > What if the interleaving was undesirable, would you like some way to be informed that it’s impossible That's like synchronised in Java or any other kind of atomic block or serialising block - that's already a thing.
    - Retric 5y ago
      That information is moving in the wrong direction. I don’t want the programmer to be telling a compiler what to do, I want the compiler to inform the programmer what it did.

lmilcin 5y ago

I think at least regarding concurrency, most developers need to rely on a model that is "good enough". You can't know everything, therefore you need to contend with knowing at least enough that is necessary to do your work. Thinking that atomics will not be optimized by compiler is "good enough" in my opinion for almost, and I really mean almost, everybody. Heck, I interview people and atomics optimization is one of my staple questions (Tell me, what does volatile do in Java, exactly?). I have never heard a thorough answer to that question and yet people do work as developers and do produce working applications. The only real users of these optimizations are atomics primitives developers, and the use it to improve them a tiny bit in some special cases. You can technically contrive a test where you run an update that changes something to 1, then immediately to 2 on each iteration. Then you try to look at it from another core and you would expect that at least once in a blue moon you will see 1. But I just don't see any sanely written application to rely on that kind of behavior.

spacechild1 5y ago

It's because people still confuse std::atomic with volatile. Actually, there is a way to get both behaviors: 'volatile std::atomic'. Personally, I never had a situation where I would've needed that, and I use atomics on a regular basis.