13 ms·

atomic loop elided

194 points by ainar-g 10y ago

LeanderK 10y ago
can somebody comment on what's happening there? I don't know go and i can't put the pieces together right now. Also aren't optimising-transformations not checked (verified) for correctness? If not, how can the authors be confident in the optimisations? Simple tests? Or is it a bug?
- iand 10y ago
  It's a bug.
- chrisseaton 10y ago
  I think how to verify real compiler optimisations is still an open research question. Does any other compiler do it formally? I'm not sure it's reasonable to expect Go to do it.
  - chimeracoder 10y ago
    In the general case, it's definitely not solved. Java and C/C++ (gcc) are known to have had compiler optimizations introduce bugs. (I assume the same is true about clang and other compilers; I just happen to remember about these ones).
    - pjmlp 10y ago
      For a recent Java one with Hotspot JIT, there is this FOSDEM 2017 talk. "....Escape Analysis and Intrinsics, two commonly used HotSpot optimization techniques. I'll show how a combination of these two features can optimize away IndexOutOfBoundsExceptions in some corner cases where they are required by the standard..." https://fosdem.org/2017/schedule/event/optimizing_error/ https://fosdem.org/2017/schedule/event/optimizing_error/
- yalue 10y ago
  Variable writes that look like they have no side effects may actually be intended for another thread to read (but hopefully most reasonable programs don't do this without some good explanation). However, many concurrency models say that this method of inter-thread communication is Okay to optimize out, because most threading libraries (including Go's) make no guarantees about the order in which threads are scheduled. Therefore, removing the "writing" thread entirely is equivalent to it never being scheduled. However, this is not the case for atomic operations (which are generally specifically intended for communication via shared variables). This optimization of removing the writing thread entirely isn't allowed if atomic operations are used, because those actually do come with a guarantee that other threads will get to see the update in finite time. Go was incorrectly "optimizing" the atomic operations out entirely. It's a fairly subtle bug, actually, but still likely a big deal for the few programs communicating via shared variables.
  - masklinn 10y ago
    > However, this is not the case for atomic operations (which are generally specifically intended for communication via shared variables). This optimization of removing the writing thread entirely isn't allowed if atomic operations are used, because those actually do come with a guarantee that other threads will get to see the update in finite time. That sounds more like volatile than atomic. At its core, atomic just means that observer may see either pre-update or post-update state but won't see intermediate states.
    - yalue 10y ago
      I agree that this sounds more like "volatile", but it still makes sense that programmers should be able to rely on atomic operations for inter-thread communication. According to the comments on the bug report, this behavior is inspired by C++'s <atomic> library, which guarantees cross-thread visibility.
      - deleted 10y ago
        [deleted]
      - 10y ago
- xgbi 10y ago
  It seems that they unified the assembler used in the go compiler to use intrinsics for amd64. In doing so, they must have botched something, because now some atomic operations (IE. operations that shouldn't be interruptible by another thread) are completely optimized away. This is quite a big issue because any multi-threaded program will use these (they are the only way to do lock-free code).
  - ghthor 10y ago
    This isn't correct, if it was this would be a much bigger issue. I'd be quite surprised if this affects any code in the wild. This bug is related to the compiler deciding to optimize the loop. All modifications of variables in the loop are being batched till the loop exits, but it never exits therefore none of the modifications ever happen. In most cases this would be fine as the side-effects of modifying the variables in the loop wouldn't need to visible anywhere else until the loop exited. If you remove the loop and just modify the atomic variable once, the modification is eventually happens and is seen by the second go routine.
- frede 10y ago
  One point of view is that the removal of the atomic increment is justified because the programmer cannot rely on the execution of the go routine that contains the increment. If you add an explicit call to the scheduler the problem is fixed. However, the justification is a bit of a stretch and it looks like it will be changed back to old behavior by the go developers.
the8472 10y ago
It is strange, the atomic package[0] exposes various low-level atomic functions but none of them seem to take ordering arguments and the docs don't mention a default order either. Atomicity and ordering constraints are orthogonal, so you can have an atomic add but relaxed ordering, which allows the compiler to do lots of optimizations on those adds, presumably to the point where they are optimized out completely. If this is the cause it seems like pretty bad API design to not expose the flags on low-level library functions. Even high level languages like java expose them[2] [0] https://golang.org/pkg/sync/atomic/ https://golang.org/pkg/sync/atomic/ [1] http://en.cppreference.com/w/cpp/atomic/memory_order http://en.cppreference.com/w/cpp/atomic/memory_order [2] http://download.java.net/java/jdk9/docs/api/java/lang/invoke/VarHandle.AccessMode.html http://download.java.net/java/jdk9/docs/api/java/lang/invoke...
- fmstephe 10y ago
  There is no official ordering provided by the atomic package. An atomic package isn't very useful without ordering semantics. And ordering actually _is_ provided, it's just not part of the documentation. The background is that the Go team were initially reluctant to even make the atomic package public. It's mostly there to support the runtime and the sync package which needs fiddly low level concurrency things. But, it exists and it is public. Some people on the Go team regret this (I believe). Giving clear and precise semantics to the atomic package was delayed because, it's a lot of difficult work and you only get to do it once. There was discussion around trying to find a clear and simple semantics. In the mean time the atomic package actually had ordering, because you would have a hard time writing runtime or the sync package without this. Also the race detector assumes some kind of ordering for operations in the atomic package. It was confirmed by Dmitry Vyukov that the race detector assumed C/C++11 acquire/release semantics for atomic operations. After some discussion it was decided that C/C++11 semantics should be adopted. But the documentation has not been updated to reflect this. Updating the documentation doesn't appear to planned right now. Which is a shame. https://github.com/golang/go/issues/5045 https://github.com/golang/go/issues/5045 Above I have sort of put words into the mouths of the Go team (or some members of it). It's not my intention and bad mouth anyone, and I think everyone was making decisions for good reasons. Whether I agree or not :) With respect to adding ordering arguments, Go most likely won't get those for a very long time.
londons_explore 10y ago
What is the overflow behaviour here? Surely in the case of this example code, the compiler sees an overflow is going to occur, leading the variable back to zero. By removing all the code, the compiler has simply combined all the additions into a single addition which overflows back to the initial value. Seems working as intended to me.
- Dylan16807 10y ago
  Surely? Based on what? As far as I can see there's a very good chance it will do the same thing even if you use a saturating add.
- mook 10y ago
  As far as I can tell it's just as broken if you change the Add to a Store (at least, doing that and breaking in the main routine when it's > 1 still times out on play.golang.org). That just turned into a (terrible) spinlock and has no overflow issues. On mobile, so I can't test with a real toolchain. https://play.golang.org/p/DlWBh1Via4 https://play.golang.org/p/DlWBh1Via4
vessenes 10y ago
This is interesting, actually. As the language is specified, it's not wrong to just ignore that add completely -- the variable isn't used inside the goroutine, and you're not guaranteed a goroutine will run at any particular time. So, code executed right after that routine is spawned will be hitting the 'old' value anyway; hence Dvyukov's comments that this is arguably to spec, or within spec. Think if you actually wrote this code; you'd have some weird behavior if the compiler did what you 'expect' - a couple outputs of low integers then some high ones as the goroutine gets scheduled in. So it's almost certainly just 'wrong' to write something like this, under most (all?) circumstances. Because sync.Wait() isn't used, there's no guarantee the goroutine will execute at all before program halt. That said, I bet there's some related more reasonable scenario where you could argue the compiler should at least do the adding. I'm not sure why atomic.Add* should get special treatment though, and it looks like the fix is to remove some escape-analysis type code, so I'm curious how this will get fixed.
- fmstephe 10y ago
  Unfortunately this miscompilation probably is within spec, given that the atomic package has no documented ordering. But it's coming. https://github.com/golang/go/issues/5045 https://github.com/golang/go/issues/5045
  - gpderetta 10y ago
    This is issue is not related to ordering, but to visibility (i.e., when is a memory side effect globally visible). Many concurrent memory models (C++ at least, java very likely) allow coalescing stores to atomic variables as long as there is no other interleaving side effect; this is normally a desirable optimization. As described by dvyukov, the go compiler seems to be aggressively coalescing all stores till the end of the loop (which never happens). Store coalescing is desirable, but it is hard to specify completely, for example the C++ standard has non normative wording stating that stores should be visible in a reasonable amount of time exactly to prevent this sort of issues.
    - twic 10y ago
akkartik 10y ago
Quote of the day: "Language implementation[s] become useless when they take formal properties to the extreme." (https://github.com/golang/go/issues/19182#issuecomment-281076863 https://github.com/golang/go/issues/19182#issuecomment-28107...)
richard_todd 10y ago
What's funny to me is: if you don't do the add in a loop, go1.8 generates the add code: go func() { atomic.AddUint64(&a, uint64(1)) // no loop }() To me, it's the unpredictability of how compilers will choose to apply these extreme optimizations that is most frustrating. Reasoning from the spec ("the goroutine might not be scheduled anyway") isn't very satisfying when the compiler clearly doesn't follow logic like this. The implementers reason from the spec and then glue together a mishmash of targeted optimizations--presumably the ones they think will be most helpful. I suppose many modern modes of programming with composable abstractions result in lots of dead code, and it's a net win for the compiler to aggressively try to get rid of it. With simpler languages like C or Go, though, I might prefer a rule like: "I wouldn't have written the code if I didn't want any instructions generated from it."
- 0xCMP 10y ago
  Luckily go does provide ways to see the compiler's decisions. I'm not sure if it goes far enough here though
YZF 10y ago
As many of the comments point out it look like this isn't a compiler bug. The example code makes assumptions about the goroutine execution order without using the facilities (e.g. channels) that guarantee the right ordering. The use of atomic doesn't seem to be relevant. The example code is what I call "works by chance" which I would contrast with code that "works by design". I think some people are trying to argue that a language should prevent developers from writing code that "works by chance" but I don't think that's actually possible. It's the equivalent of saying I want to be able to type anything I want into my editor and have it compile into doing what I think it should do... A "works by design" code here would be adding channel synchronization points between the two goroutines such that the desired execution order is guaranteed. It's also IMO not reasonable to expect a new compiler to produce identical results to an old compiler. E.g. if the compiler does a better job your code may run faster (or slower) which may break something if you've assumed that something takes so long to run (e.g. some hard coded timeout in some other component). At least the 1.8 compiler behaviour is deterministic. So code written assuming some particular value of a would either work or fail consistently. Previously you could construct some code that fails randomly.

194 points by ainar-g 10y ago

can somebody comment on what's happening there? I don't know go and i can't put the pieces together right now. Also aren't optimising-transformations not checked (verified) for correctness? If not, how can the authors be confident in the optimisations? Simple tests? Or is it a bug?

iand 10y ago
It's a bug.
chrisseaton 10y ago
I think how to verify real compiler optimisations is still an open research question. Does any other compiler do it formally? I'm not sure it's reasonable to expect Go to do it.
- chimeracoder 10y ago
  In the general case, it's definitely not solved. Java and C/C++ (gcc) are known to have had compiler optimizations introduce bugs. (I assume the same is true about clang and other compilers; I just happen to remember about these ones).
  - pjmlp 10y ago
    For a recent Java one with Hotspot JIT, there is this FOSDEM 2017 talk. "....Escape Analysis and Intrinsics, two commonly used HotSpot optimization techniques. I'll show how a combination of these two features can optimize away IndexOutOfBoundsExceptions in some corner cases where they are required by the standard..." https://fosdem.org/2017/schedule/event/optimizing_error/ https://fosdem.org/2017/schedule/event/optimizing_error/
yalue 10y ago
Variable writes that look like they have no side effects may actually be intended for another thread to read (but hopefully most reasonable programs don't do this without some good explanation). However, many concurrency models say that this method of inter-thread communication is Okay to optimize out, because most threading libraries (including Go's) make no guarantees about the order in which threads are scheduled. Therefore, removing the "writing" thread entirely is equivalent to it never being scheduled. However, this is not the case for atomic operations (which are generally specifically intended for communication via shared variables). This optimization of removing the writing thread entirely isn't allowed if atomic operations are used, because those actually do come with a guarantee that other threads will get to see the update in finite time. Go was incorrectly "optimizing" the atomic operations out entirely. It's a fairly subtle bug, actually, but still likely a big deal for the few programs communicating via shared variables.
- masklinn 10y ago
  > However, this is not the case for atomic operations (which are generally specifically intended for communication via shared variables). This optimization of removing the writing thread entirely isn't allowed if atomic operations are used, because those actually do come with a guarantee that other threads will get to see the update in finite time. That sounds more like volatile than atomic. At its core, atomic just means that observer may see either pre-update or post-update state but won't see intermediate states.
  - yalue 10y ago
    I agree that this sounds more like "volatile", but it still makes sense that programmers should be able to rely on atomic operations for inter-thread communication. According to the comments on the bug report, this behavior is inspired by C++'s <atomic> library, which guarantees cross-thread visibility.
    - deleted 10y ago
      [deleted]
    - 10y ago
xgbi 10y ago
It seems that they unified the assembler used in the go compiler to use intrinsics for amd64. In doing so, they must have botched something, because now some atomic operations (IE. operations that shouldn't be interruptible by another thread) are completely optimized away. This is quite a big issue because any multi-threaded program will use these (they are the only way to do lock-free code).
- ghthor 10y ago
  This isn't correct, if it was this would be a much bigger issue. I'd be quite surprised if this affects any code in the wild. This bug is related to the compiler deciding to optimize the loop. All modifications of variables in the loop are being batched till the loop exits, but it never exits therefore none of the modifications ever happen. In most cases this would be fine as the side-effects of modifying the variables in the loop wouldn't need to visible anywhere else until the loop exited. If you remove the loop and just modify the atomic variable once, the modification is eventually happens and is seen by the second go routine.
frede 10y ago
One point of view is that the removal of the atomic increment is justified because the programmer cannot rely on the execution of the go routine that contains the increment. If you add an explicit call to the scheduler the problem is fixed. However, the justification is a bit of a stretch and it looks like it will be changed back to old behavior by the go developers.

the8472 10y ago

It is strange, the atomic package[0] exposes various low-level atomic functions but none of them seem to take ordering arguments and the docs don't mention a default order either. Atomicity and ordering constraints are orthogonal, so you can have an atomic add but relaxed ordering, which allows the compiler to do lots of optimizations on those adds, presumably to the point where they are optimized out completely. If this is the cause it seems like pretty bad API design to not expose the flags on low-level library functions. Even high level languages like java expose them[2] [0] https://golang.org/pkg/sync/atomic/ https://golang.org/pkg/sync/atomic/ [1] http://en.cppreference.com/w/cpp/atomic/memory_order http://en.cppreference.com/w/cpp/atomic/memory_order [2] http://download.java.net/java/jdk9/docs/api/java/lang/invoke/VarHandle.AccessMode.html http://download.java.net/java/jdk9/docs/api/java/lang/invoke...

fmstephe 10y ago
There is no official ordering provided by the atomic package. An atomic package isn't very useful without ordering semantics. And ordering actually _is_ provided, it's just not part of the documentation. The background is that the Go team were initially reluctant to even make the atomic package public. It's mostly there to support the runtime and the sync package which needs fiddly low level concurrency things. But, it exists and it is public. Some people on the Go team regret this (I believe). Giving clear and precise semantics to the atomic package was delayed because, it's a lot of difficult work and you only get to do it once. There was discussion around trying to find a clear and simple semantics. In the mean time the atomic package actually had ordering, because you would have a hard time writing runtime or the sync package without this. Also the race detector assumes some kind of ordering for operations in the atomic package. It was confirmed by Dmitry Vyukov that the race detector assumed C/C++11 acquire/release semantics for atomic operations. After some discussion it was decided that C/C++11 semantics should be adopted. But the documentation has not been updated to reflect this. Updating the documentation doesn't appear to planned right now. Which is a shame. https://github.com/golang/go/issues/5045 https://github.com/golang/go/issues/5045 Above I have sort of put words into the mouths of the Go team (or some members of it). It's not my intention and bad mouth anyone, and I think everyone was making decisions for good reasons. Whether I agree or not :) With respect to adding ordering arguments, Go most likely won't get those for a very long time.

londons_explore 10y ago

What is the overflow behaviour here? Surely in the case of this example code, the compiler sees an overflow is going to occur, leading the variable back to zero. By removing all the code, the compiler has simply combined all the additions into a single addition which overflows back to the initial value. Seems working as intended to me.

Dylan16807 10y ago
Surely? Based on what? As far as I can see there's a very good chance it will do the same thing even if you use a saturating add.
mook 10y ago
As far as I can tell it's just as broken if you change the Add to a Store (at least, doing that and breaking in the main routine when it's > 1 still times out on play.golang.org). That just turned into a (terrible) spinlock and has no overflow issues. On mobile, so I can't test with a real toolchain. https://play.golang.org/p/DlWBh1Via4 https://play.golang.org/p/DlWBh1Via4

vessenes 10y ago

This is interesting, actually. As the language is specified, it's not wrong to just ignore that add completely -- the variable isn't used inside the goroutine, and you're not guaranteed a goroutine will run at any particular time. So, code executed right after that routine is spawned will be hitting the 'old' value anyway; hence Dvyukov's comments that this is arguably to spec, or within spec. Think if you actually wrote this code; you'd have some weird behavior if the compiler did what you 'expect' - a couple outputs of low integers then some high ones as the goroutine gets scheduled in. So it's almost certainly just 'wrong' to write something like this, under most (all?) circumstances. Because sync.Wait() isn't used, there's no guarantee the goroutine will execute at all before program halt. That said, I bet there's some related more reasonable scenario where you could argue the compiler should at least do the adding. I'm not sure why atomic.Add* should get special treatment though, and it looks like the fix is to remove some escape-analysis type code, so I'm curious how this will get fixed.

fmstephe 10y ago
Unfortunately this miscompilation probably is within spec, given that the atomic package has no documented ordering. But it's coming. https://github.com/golang/go/issues/5045 https://github.com/golang/go/issues/5045
- gpderetta 10y ago
  This is issue is not related to ordering, but to visibility (i.e., when is a memory side effect globally visible). Many concurrent memory models (C++ at least, java very likely) allow coalescing stores to atomic variables as long as there is no other interleaving side effect; this is normally a desirable optimization. As described by dvyukov, the go compiler seems to be aggressively coalescing all stores till the end of the loop (which never happens). Store coalescing is desirable, but it is hard to specify completely, for example the C++ standard has non normative wording stating that stores should be visible in a reasonable amount of time exactly to prevent this sort of issues.
  - twic 10y ago

akkartik 10y ago

Quote of the day: "Language implementation[s] become useless when they take formal properties to the extreme." (https://github.com/golang/go/issues/19182#issuecomment-281076863 https://github.com/golang/go/issues/19182#issuecomment-28107...)

richard_todd 10y ago

What's funny to me is: if you don't do the add in a loop, go1.8 generates the add code: go func() { atomic.AddUint64(&a, uint64(1)) // no loop }() To me, it's the unpredictability of how compilers will choose to apply these extreme optimizations that is most frustrating. Reasoning from the spec ("the goroutine might not be scheduled anyway") isn't very satisfying when the compiler clearly doesn't follow logic like this. The implementers reason from the spec and then glue together a mishmash of targeted optimizations--presumably the ones they think will be most helpful. I suppose many modern modes of programming with composable abstractions result in lots of dead code, and it's a net win for the compiler to aggressively try to get rid of it. With simpler languages like C or Go, though, I might prefer a rule like: "I wouldn't have written the code if I didn't want any instructions generated from it."

0xCMP 10y ago
Luckily go does provide ways to see the compiler's decisions. I'm not sure if it goes far enough here though

YZF 10y ago

As many of the comments point out it look like this isn't a compiler bug. The example code makes assumptions about the goroutine execution order without using the facilities (e.g. channels) that guarantee the right ordering. The use of atomic doesn't seem to be relevant. The example code is what I call "works by chance" which I would contrast with code that "works by design". I think some people are trying to argue that a language should prevent developers from writing code that "works by chance" but I don't think that's actually possible. It's the equivalent of saying I want to be able to type anything I want into my editor and have it compile into doing what I think it should do... A "works by design" code here would be adding channel synchronization points between the two goroutines such that the desired execution order is guaranteed. It's also IMO not reasonable to expect a new compiler to produce identical results to an old compiler. E.g. if the compiler does a better job your code may run faster (or slower) which may break something if you've assumed that something takes so long to run (e.g. some hard coded timeout in some other component). At least the 1.8 compiler behaviour is deterministic. So code written assuming some particular value of a would either work or fail consistently. Previously you could construct some code that fails randomly.