Comment by mikeash | Hacker News Reader

Comment by mikeash | Hacker News Reader

Parent Full thread

Not at all. The problem is that there are useful, effective optimizations allowed by the language spec which also have unexpected consequences on subtly incorrect code.

Take an oversized shift, for example. The result is undefined, and for good reason. This allows an expression like x << y to be translated directly to a single machine instruction on just about every architecture. If there was a defined result for oversized shifts, then many architectures' instructions would not match it, forcing the compiler to generate inefficient code on those architectures.

For every example of a weird optimization causing problems, you can find an example of that same optimization making code go much faster.

You could say that compilers should value correctness over speed, and I would agree with you, but: all of these optimizations are correct. These are C compilers, and they compile C programs just fine. Where they have trouble is on programs that aren't actually valid C, but are just close. You can argue that they are being technically correct in a bad way, but then if you abandon the standard and decide that you should "correctly" compile a certain class of invalid programs, how do you decide what "correct" means?

Ordinarily, unsigned left shift silently shifts bits off the end.

  0xffffffff <<  0 is 0xffffffff
  0xffffffff <<  1 is 0xfffffffe
  ..
  0xffffffff << 30 is 0xc0000000
  0xffffffff << 31 is 0x80000000

It is defined to ignore overflow. Therefore, I claim that there's enough consistency here that we can extend the pattern to this:

  0xffffffff << 32 is 0x00000000

I claim this really is the mathematically correct answer. It's consistent with the most obvious pattern, and there are no other relevant patterns.

C has chosen to call this undefined behavior instead of returning the correct answer here, and I call that choosing optimization over correctness.

That may be a useful left shift operator, but it's just not C's left shift operator. You can argue the spec is poor, but you cannot argue that the compiler writers are incorrect.

Are you so sure that all architectures that implement a left shift operator work the same way? For example, if you shift left by 'x' they might shift left by 'x modulo 32'

With C, you could still use the shift instruction on that architecture. With your 'correct answer', the compiler would have to output instructions to check the value of x prior to the shift.

Besides which, shifting is just one specific case. C has an easily understandable and documented behavior: overflow is undefined, no matter how you achieve it. We don't have to go into horrific detail about what happens when you overflow with adds, multiplys, shifts and so on.

On some architectures it's the way he wants it (always zero on overflow), on some it's the way you suggest (shift is mod 32), and on some it just generates junk.

Bitshifting is an operation that people generally expect to be extremely fast. Adding a check on every single operation generated by a C compiler just to guarantee identical results upon overflow probably would not go over well.

The Watcom C/C++ compiler used to have a neat shift optimization bug.

If you shifted one way a few bits then shifted back a few bits (As you would in calculating addresses for graphics operations), the optimizer would think you were undoing the operation and do nothing. or interestingly shift n-m bits.

You had to do some dummy operation in between for the code to actually execute. This was true at least up to Watcom 11.

Reply on news.ycombinator.com