Hacker News Reader

Comment by mpweiher | Hacker News Reader

Seems to be a problem of language-lawyers coding compiler optimizations. Stop doing that. See also "Doctor, it hurst when I move my arm this way".

View on HN

People writing compiler optimizations are necessarily language lawyers. Their job is to make the code run as fast as possible given the semantics of the language.

Given the reasons that people use C, what do you think makes for a better sales pitch -- "our compiler produces the fastest code" or "our compiler produces the safest code"? This is simply the compiler market optimizing for what it's customers want.

Well the existence of CompCert seems to indicate that there is at least some demand for a compiler with a greater emphasis on correctness than speed. It doesn't fix the issue of undefined behaviour of course since that is part of the language standard itself.

http://compcert.inria.fr/compcert-C.html

CompCert is a research project. Its unqualified existence does not prove that any demand exist for anything. You might as well say that there is some demand for aspect-oriented programming because so much research is being done on the topic (substitute the topic of your choice if my having picked this one offends you).

It so happens that this particular research project found a few industrial users eager to try it out and study the feasibility of deploying it, but it wasn't necessary for the research project to exist.

In a way, the problem is that C dates too much from a time before language lawyers. I can't think of a modern language that is as underspecified as C, because we know better now. If were to be written again today, it would be much better specified (see: Go). I don't even mean this as a criticism of anybody in particular, it was a different time.

"Fixing" C would be creating a new dialect, unfortunately. (Personally, I just consider C a last resort, and I've found that works pretty well.)

The problem is deciding what kind of optimizations are 'resonable'. In one context, assuming x+1 is greater than x will avoid some wasteful code in your loops. In another context, it could destroy your program's logic. If you restrict yourself to guaranteed-safe optimizations, you miss out on most of the potential gains.

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