4 ms·

Moar please. I'm loving these counterintuitive C optimization gotchas lately[1]. They are like little brain teasers. 1. https://news.ycombinator.com/item?id=28

• 0xcde4c3db 5y ago
  About a year ago there was something of a "joke isEven() implementation discourse" on Twitter, which eventually evolved a sort of informal optimizer abuse contest. For example: https://twitter.com/zeuxcg/status/1291872698453258241 https://twitter.com/zeuxcg/status/1291872698453258241 https://twitter.com/jckarter/status/1428071485827022849 https://twitter.com/jckarter/status/1428071485827022849
  • aw1621107 5y ago
    OK, those are horrifying and fascinating, and they basically break my brain. Is there a explanation somewhere of why the first one "works"? The second one I think is the compiler assuming the default case will never be hit since it'll result in infinite recursion, which is UB under C++, so it's basically assuming 0<=x<=3 and optimizing from there. Is that correct? The first one I'm less certain about. The only thing I can think of is that the compiler deduces an upper limit of INT_MAX - 1 to avoid signed overflow, and then somehow figuring out the true/false pattern from there? Still a bit of a gap in my understanding there.
    • barsonme 5y ago
      My guess: since overflowing int is UB, and the only value of n that stops the recursion is zero, the compiler assumes that n must be zero and checks accordingly. That doesn’t explain why it uses test dil, 1 instead of test dil, dil or cmp 0 or whatever.
      • eMSF 5y ago
        The compiler cannot assume that much, because the argument is a signed integer (negative integers will not overflow and do have well-defined behaviour).
        • davemp 5y ago
          The rabbit hole goes deeper than that: https://gcc.godbolt.org/z/Tc1MTa6nj https://gcc.godbolt.org/z/Tc1MTa6nj
          • rocqua 5y ago
            That is a well defined function. And indeed implements isEven. Because unsigned int has defined overflow semantics. Essentially, it will eventually overflow and hit the correct base-case for 0.
    • davemp 5y ago
      Optimizers have to keep the same input/output pairs unless there is undefined behavior. In the second function the truth table looks like: in | out ---------- 0b000 | 1 0b001 | 0 0b010 | 1 0b011 | 0 0b100 | don't care . . . MAX | don't care The compiler just chooses the most efficient way it knows to get the filled out entries correct which happens to be: in | ~in[0] ---------- 0b000 | 1 0b001 | 0 0b010 | 1 0b011 | 0 0b100 | 1 . . . MAX | 1 It would have been just as valid to do: in | in[2] or ~in[0] ---------- 0b000 | 1 0b001 | 0 0b010 | 1 0b011 | 0 0b100 | 1 0b101 | 1 . . . MAX | 1 The first function's table looks like: in | out ---------- 0b000 | 1 0b001 | don't care 0b010 | don't care . . . MAX | don't care And the compiler still likes the even check in this case, which makes sense.
      • notriddle 5y ago
        The first function (the `n == 0 || !isEven(n+1)` recursive function) has defined behavior for negative numbers. That's probably why it compiled to an even number check.
        • davemp 5y ago
          Hmm you're right that there's definitely more to the first function than coincidence. I dug a bit deeper and surprisingly when n is unsigned the function is still well defined and correct. [0] AFAIK clang will usually just treat a signed overflow as an unsigned overflow when optimizing as it simplifies things. So my bet would be that clang is just casting n to unsigned and performing some inductive reasoning similar to the proof I wrote below. Pretty impressive on the behalf of clang. [1] [0]: I did the proof below for anyone interested: int isEven(unsigned int n) { return n == 0 || !isEven(n + 1); } # assumptions MAX + 1 --> 0 # from the C standard MAX is odd # true for most machines # base case isEven(0) --> True # trivial short circuit # base case isEven(MAX): ==> return MAX == 0 || !isEven(MAX+1) # MAX is not zero ==> return False || !isEven(MAX+1) # MAX + 1 rolls over ==> return False || !isEven(0) ==> return False || !True ==> return False || False ==> return False ==> isEven(MAX) --> False # recursive steps isEven(n) where 0 < n < MAX ==> return n == 0 || !isEven(n + 1) # n cannot be zero ==> return False || !isEven(n + 1) # False || anything is tautological ==> return !isEven(n + 1) which will turn into an inverter chain of length MAX - n until you reach isEven(MAX) - an odd length inverter chain is the same as a single inversion - an even length inverter chain is the identity (can be proven by induction trivially) isEven(n) where 0 < n < MAX and n is even ==> return !isEven(n + 1) # MAX - n is odd, when n is even; replace with single inversion before isEven(MAX) ==> return !isEven(MAX) ==> !(False) --> True isEven(n) where 0 < n < MAX and n is odd ==> return !isEven(n + 1) # MAX - n is even, when n is odd; replace with identity of isEven(MAX) ==> return isEven(MAX) ==> False --> False All cases of n are accounted for so the function is correct (and equivalent to return n & 1 == 0). [1]: Yup clang just recognizes this optimization: https://gcc.godbolt.org/z/Tc1MTa6nj https://gcc.godbolt.org/z/Tc1MTa6nj
• archi42 5y ago
  It's all fun and games until you write (or review) C/C++ test cases for a compiler or disassembler ;-) It never stopped to amaze me how good the compiler was to figure out that I actually wrote very complicated "return 0".