6 ms·

Bug in my code from compiler optimization [video]

44 points by MiguelX413 3y ago

hyperman1 3y ago
A simplified recap of the video: He wants code: If x then return y With y an unsafe expression, and x always true if y can be evaluated without invoking undefined behaviour. He wrote it as: return x.then_some(y) This always calculates y, but throws it away if x is false. By calculating y, he accidentaly gives a proof to the compiler that x must be true. The proof is of course invalid, but as y is unsafe, the compiler trusts him nevertheless. So the 'if' gets optimized away.
- salawat 3y ago
  ...That sounds like the compiler writer taking undue liberties, and the programmer assuming the machine is capable of reading intent. Sounds like a great learning experience imo.
  - hyperman1 3y ago
    Not really. An example that explicitly crashes instead of triggering undefined behavior: If n!=0 return 1/n Is well behaved: Division by zero wont happen. z=1/n If n!=0 return z Is not well behaved. It will crash when n=0. What the compiler does is take the existence of z as a proof that n can't be 0, and optimize the if away: z=1/n return z Just like division by 0, undefined behaviour (UB) is not allowed. The difference is: UB might crash or give a nonsensical result. You can't tell beforehand. Different versions of a compiler might make different choices of crash vs nonsense. Until recently, the author calculated nonsense, and threw it away, but that was accidental. It might have crashed too. C had a lot of UB that gets thrown away, until some minor shift in optimizations changes it to a crasher. Compare it to an insanely sharp knife: Powerfull, but the slightest error might take off your fingers, it's very hard to know if something is or is not an error, and errors mostly dont cut if your fingers, until surprise surprise they do. Rust is much better: only unsafe code behaves like C's crazy knife. Only when you use unsafe, the rust guarantees go out of the window, because that's what the programmer explicitly asked.
    - trealira 3y ago
      When you're learning to program, teachers will often tell you "The computer is dumb; it will do exactly what you say, and it can't read your intent." Implicitly, I think most people assume the same of compilers: they're dumb, and will translate an unconditional division as an unconditional division, even when it would crash. Instead, compilers seemingly try to make insights into the intent or true meaning of your code, often inaccurately, and change it using ad-hoc unintuitive rules as justification (those being the rules of undefined behavior, and what assumptions the authors are and aren't allowed to make about your code). I know they aren't actually reading your intent; it's just the result of many, many passes that each make seemingly reasonable assumptions, which together may add up to a set of unreasonable ones. > because that's what the programmer explicitly asked. No, the programmer didn't explicitly ask for their check to be deleted, even with "unsafe" written. There is no request written anywhere. At most, you can say they implied they wanted it by invoking undefined behavior. Probably, though, they just made a mistake, or assumed that behavior was defined when it wasn't (e.g. they may have thought division corresponds to a hardware division instruction, modulo optimizations like right shifting for division by 2, constant folding division by 1, etc.)
      - deleted 3y ago
        [deleted]
      - superjan 3y ago
        For some background on why compilers do this, read this gist by ryg. A big issue is we write 32 bit code that runs on 64 bit architectures. https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
        hyperman1 3y ago
        This is a very interesting read. Thanks.
      - thaumasiotes 3y ago
        > No, the programmer didn't explicitly ask for their check to be deleted, even with "unsafe" written. There is no request written anywhere. At most, you can say they implied they wanted it by invoking undefined behavior. Probably, though, they just made a mistake, or assumed that behavior was defined when it wasn't This is a weird complaint to make here, where the compiler optimization isn't introducing a bug. If the check were left in place, the code would have exactly the same problem that it does without the check. The optimization is exactly what you hope for: something that makes the code faster without affecting its behavior in any way. Why is that bad?
- EdSchouten 3y ago
  In that sense .then_some() is sort of a footgun. Compared to a regular if-statement it invites people to write code in a less efficient (and in this case an incorrect manner). It could just have taken a closure instead. Edit: it turns out there’s also a .then() that does exactly that.
  - IshKebab 3y ago
    Not really. `unsafe` is the footgun.
- perryizgr8 3y ago
  I don't get how changing to if else fixes this. The compiler can still reason that the condition is always going to be true (and if it isn't that is undefined behavior, so f it). And then it will elide the comparison. Same result. The compiler bug here is that for some reason it is not able to apply a valid (lol) optimisation to if else statements. The author should not rely on this. Compiler authors will eventually fix this bug and his game will break again.
  - aw1621107 3y ago
    > I don't get how changing to if else fixes this. The compiler can still reason that the condition is always going to be true No, the compiler can't make that assumption for an if statement. That's because the condition of an if statement is always evaluated first, so the following expression(s) are only conditionally evaluated. There's nothing the compiler can do to reason "backwards" in such a case. then_some effectively flips the order around - the consequent of the "if" statement is evaluated first, and then the condition is evaluated. This reversal of the order makes all the difference. For a more concrete example, consider the following snippets: if (ptr != nullptr) { return *ptr; } else { return nullptr; } This is (probably) safe. The condition is evaluated first, and only if the condition is true is *ptr evaluated. The buggy code, on the other hand, was more like (ptr != nullptr).then_some(*ptr) In this case, the argument *ptr is evaluated first, before the condition. This is sort of equivalent to: result = *ptr if (ptr != nullptr) { return result; } else { return nullptr; } And that is definitely buggy, as it unconditionally dereferences ptr. There isn't really a compiler bug here; it's just language semantics coupled with unsafe.
    - gpderetta 3y ago
      An alternative way to see this is that it is conditional execution while then_some is a form of predication.
      - DannyBee 3y ago
        This is all overly complicated. Then_some just has its arguments eagerly evaluated and then (and if/then) do not
- lifthrasiir 3y ago
  As others pointed out, there also exists `bool::then` that always accepts a closure and doesn't have this issue. In fact both `bool::then` and `bool::then_some` are originated from a single RFC [1], and people unanimously agreed on `bool::then` but not `bool::then_some`, so the latter spun off its own issue [2]. It seems that `bool::then_some` was eventually accepted mainly due to the lack of better alternatives---there were enough people wanting the value form and other pairs of method names were considered better. [1] https://github.com/rust-lang/rfcs/pull/2757 https://github.com/rust-lang/rfcs/pull/2757 [2] https://github.com/rust-lang/rust/issues/64260 https://github.com/rust-lang/rust/issues/64260
deathanatos 3y ago
You can write this in safe-Rust, with a match. There are only 8 variants, and while it's a bit tedious¹, Rust will optimize it to the same code as if you had done a from_raw construction … without the possibility of UB.² ¹(but there has to be a crate for this) ²https://godbolt.org/z/W55W1GxvY https://godbolt.org/z/W55W1GxvY
- hyperman1 3y ago
  I wish this wasn't downvoted as for me its the right answer. unsafe in rust is a blank cheque for the compiler. Doing anything complicated in it is almost guaranteed to have UB somewhere. You decide to disable safety. If possible, write the safe but tedious code. Then measure. Only when you're sure unsafe is worth it should you take out the big cannon. Write a km of comments proving this code needs and deserves unsafe. Writing the tedious code is less time consuming than debugging the mess. I wish the video author documented why he choose unsafe here. Was it measured and worth it in an older version of rust? Or a folly of youth (which is fine, as long as you learn from it, been there done that paid the time debugging my stupidity)
- dannymi 3y ago
  >¹(but there has to be a crate for this) num-traits' FromPrimitive https://docs.rs/num-traits/latest/num_traits/cast/trait.FromPrimitive.html https://docs.rs/num-traits/latest/num_traits/cast/trait.From...
3836293648 3y ago
The big questions is why clippy (standard linter) didn't catch this. It will complain about expensive expressions in a `.then_some()` because it's eager, why not unsafe?
- lifthrasiir 3y ago
  Clippy would only complain about expensive expressions when it can prove that the alternative would be always better than the original (for example, `or_fun_call` [1]). It is not impossible to measure the cost of given expression to suggest that, but that would increase a risk of false positives. The OP has the same challenge---this kind of range analysis can only occur (and currently does occur) much later than Clippy. [1] https://rust-lang.github.io/rust-clippy/master/index.html#/or_fun_call https://rust-lang.github.io/rust-clippy/master/index.html#/o...
- Ygg2 3y ago
  You want miri, not clippy. Clippy is for minor issues in code, miri is for finding UB in Rust.
  - 3836293648 3y ago
    In testing I want miri, but knowing that there already is a very similar lint, I want that expanded
- SpaghettiCthulu 3y ago
  I believe the parent wants the lint to trigger for any unsafe code in the argument to `then_some`. This would not require any real analysis of the expression.
nliang86 3y ago
https://www.videogist.co/videos/insane-bug-in-my-code-from-compiler-optimization-2236 https://www.videogist.co/videos/insane-bug-in-my-code-from-c...
SeanAnderson 3y ago
Note that the Rust docs explicitly discourage using `then_some` in the manner described in this video. https://doc.rust-lang.org/beta/std/primitive.bool.html#method.then_some https://doc.rust-lang.org/beta/std/primitive.bool.html#metho... > Arguments passed to then_some are eagerly evaluated; if you are passing the result of a function call, it is recommended to use then, which is lazily evaluated.

44 points by MiguelX413 3y ago

A simplified recap of the video: He wants code: If x then return y With y an unsafe expression, and x always true if y can be evaluated without invoking undefined behaviour. He wrote it as: return x.then_some(y) This always calculates y, but throws it away if x is false. By calculating y, he accidentaly gives a proof to the compiler that x must be true. The proof is of course invalid, but as y is unsafe, the compiler trusts him nevertheless. So the 'if' gets optimized away.

salawat 3y ago
...That sounds like the compiler writer taking undue liberties, and the programmer assuming the machine is capable of reading intent. Sounds like a great learning experience imo.
- hyperman1 3y ago
  Not really. An example that explicitly crashes instead of triggering undefined behavior: If n!=0 return 1/n Is well behaved: Division by zero wont happen. z=1/n If n!=0 return z Is not well behaved. It will crash when n=0. What the compiler does is take the existence of z as a proof that n can't be 0, and optimize the if away: z=1/n return z Just like division by 0, undefined behaviour (UB) is not allowed. The difference is: UB might crash or give a nonsensical result. You can't tell beforehand. Different versions of a compiler might make different choices of crash vs nonsense. Until recently, the author calculated nonsense, and threw it away, but that was accidental. It might have crashed too. C had a lot of UB that gets thrown away, until some minor shift in optimizations changes it to a crasher. Compare it to an insanely sharp knife: Powerfull, but the slightest error might take off your fingers, it's very hard to know if something is or is not an error, and errors mostly dont cut if your fingers, until surprise surprise they do. Rust is much better: only unsafe code behaves like C's crazy knife. Only when you use unsafe, the rust guarantees go out of the window, because that's what the programmer explicitly asked.
  - trealira 3y ago
    When you're learning to program, teachers will often tell you "The computer is dumb; it will do exactly what you say, and it can't read your intent." Implicitly, I think most people assume the same of compilers: they're dumb, and will translate an unconditional division as an unconditional division, even when it would crash. Instead, compilers seemingly try to make insights into the intent or true meaning of your code, often inaccurately, and change it using ad-hoc unintuitive rules as justification (those being the rules of undefined behavior, and what assumptions the authors are and aren't allowed to make about your code). I know they aren't actually reading your intent; it's just the result of many, many passes that each make seemingly reasonable assumptions, which together may add up to a set of unreasonable ones. > because that's what the programmer explicitly asked. No, the programmer didn't explicitly ask for their check to be deleted, even with "unsafe" written. There is no request written anywhere. At most, you can say they implied they wanted it by invoking undefined behavior. Probably, though, they just made a mistake, or assumed that behavior was defined when it wasn't (e.g. they may have thought division corresponds to a hardware division instruction, modulo optimizations like right shifting for division by 2, constant folding division by 1, etc.)
    - deleted 3y ago
      [deleted]
    - superjan 3y ago
      For some background on why compilers do this, read this gist by ryg. A big issue is we write 32 bit code that runs on 64 bit architectures. https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
      - hyperman1 3y ago
        This is a very interesting read. Thanks.
    - thaumasiotes 3y ago
      > No, the programmer didn't explicitly ask for their check to be deleted, even with "unsafe" written. There is no request written anywhere. At most, you can say they implied they wanted it by invoking undefined behavior. Probably, though, they just made a mistake, or assumed that behavior was defined when it wasn't This is a weird complaint to make here, where the compiler optimization isn't introducing a bug. If the check were left in place, the code would have exactly the same problem that it does without the check. The optimization is exactly what you hope for: something that makes the code faster without affecting its behavior in any way. Why is that bad?
EdSchouten 3y ago
In that sense .then_some() is sort of a footgun. Compared to a regular if-statement it invites people to write code in a less efficient (and in this case an incorrect manner). It could just have taken a closure instead. Edit: it turns out there’s also a .then() that does exactly that.
- IshKebab 3y ago
  Not really. `unsafe` is the footgun.
perryizgr8 3y ago
I don't get how changing to if else fixes this. The compiler can still reason that the condition is always going to be true (and if it isn't that is undefined behavior, so f it). And then it will elide the comparison. Same result. The compiler bug here is that for some reason it is not able to apply a valid (lol) optimisation to if else statements. The author should not rely on this. Compiler authors will eventually fix this bug and his game will break again.
- aw1621107 3y ago
  > I don't get how changing to if else fixes this. The compiler can still reason that the condition is always going to be true No, the compiler can't make that assumption for an if statement. That's because the condition of an if statement is always evaluated first, so the following expression(s) are only conditionally evaluated. There's nothing the compiler can do to reason "backwards" in such a case. then_some effectively flips the order around - the consequent of the "if" statement is evaluated first, and then the condition is evaluated. This reversal of the order makes all the difference. For a more concrete example, consider the following snippets: if (ptr != nullptr) { return *ptr; } else { return nullptr; } This is (probably) safe. The condition is evaluated first, and only if the condition is true is *ptr evaluated. The buggy code, on the other hand, was more like (ptr != nullptr).then_some(*ptr) In this case, the argument *ptr is evaluated first, before the condition. This is sort of equivalent to: result = *ptr if (ptr != nullptr) { return result; } else { return nullptr; } And that is definitely buggy, as it unconditionally dereferences ptr. There isn't really a compiler bug here; it's just language semantics coupled with unsafe.
  - gpderetta 3y ago
    An alternative way to see this is that it is conditional execution while then_some is a form of predication.
    - DannyBee 3y ago
      This is all overly complicated. Then_some just has its arguments eagerly evaluated and then (and if/then) do not
lifthrasiir 3y ago
As others pointed out, there also exists `bool::then` that always accepts a closure and doesn't have this issue. In fact both `bool::then` and `bool::then_some` are originated from a single RFC [1], and people unanimously agreed on `bool::then` but not `bool::then_some`, so the latter spun off its own issue [2]. It seems that `bool::then_some` was eventually accepted mainly due to the lack of better alternatives---there were enough people wanting the value form and other pairs of method names were considered better. [1] https://github.com/rust-lang/rfcs/pull/2757 https://github.com/rust-lang/rfcs/pull/2757 [2] https://github.com/rust-lang/rust/issues/64260 https://github.com/rust-lang/rust/issues/64260

deathanatos 3y ago

You can write this in safe-Rust, with a match. There are only 8 variants, and while it's a bit tedious¹, Rust will optimize it to the same code as if you had done a from_raw construction … without the possibility of UB.² ¹(but there has to be a crate for this) ²https://godbolt.org/z/W55W1GxvY https://godbolt.org/z/W55W1GxvY

hyperman1 3y ago
I wish this wasn't downvoted as for me its the right answer. unsafe in rust is a blank cheque for the compiler. Doing anything complicated in it is almost guaranteed to have UB somewhere. You decide to disable safety. If possible, write the safe but tedious code. Then measure. Only when you're sure unsafe is worth it should you take out the big cannon. Write a km of comments proving this code needs and deserves unsafe. Writing the tedious code is less time consuming than debugging the mess. I wish the video author documented why he choose unsafe here. Was it measured and worth it in an older version of rust? Or a folly of youth (which is fine, as long as you learn from it, been there done that paid the time debugging my stupidity)
dannymi 3y ago
>¹(but there has to be a crate for this) num-traits' FromPrimitive https://docs.rs/num-traits/latest/num_traits/cast/trait.FromPrimitive.html https://docs.rs/num-traits/latest/num_traits/cast/trait.From...

3836293648 3y ago

The big questions is why clippy (standard linter) didn't catch this. It will complain about expensive expressions in a `.then_some()` because it's eager, why not unsafe?

lifthrasiir 3y ago
Clippy would only complain about expensive expressions when it can prove that the alternative would be always better than the original (for example, `or_fun_call` [1]). It is not impossible to measure the cost of given expression to suggest that, but that would increase a risk of false positives. The OP has the same challenge---this kind of range analysis can only occur (and currently does occur) much later than Clippy. [1] https://rust-lang.github.io/rust-clippy/master/index.html#/or_fun_call https://rust-lang.github.io/rust-clippy/master/index.html#/o...
Ygg2 3y ago
You want miri, not clippy. Clippy is for minor issues in code, miri is for finding UB in Rust.
- 3836293648 3y ago
  In testing I want miri, but knowing that there already is a very similar lint, I want that expanded
SpaghettiCthulu 3y ago
I believe the parent wants the lint to trigger for any unsafe code in the argument to `then_some`. This would not require any real analysis of the expression.

nliang86 3y ago

https://www.videogist.co/videos/insane-bug-in-my-code-from-compiler-optimization-2236 https://www.videogist.co/videos/insane-bug-in-my-code-from-c...

SeanAnderson 3y ago

Note that the Rust docs explicitly discourage using `then_some` in the manner described in this video. https://doc.rust-lang.org/beta/std/primitive.bool.html#method.then_some https://doc.rust-lang.org/beta/std/primitive.bool.html#metho... > Arguments passed to then_some are eagerly evaluated; if you are passing the result of a function call, it is recommended to use then, which is lazily evaluated.