Will It Optimize?

[udp]

Previous submission and discussion: http://news.ycombinator.com/item?id=1540567

[Roritharr]

I remember learning about compiler optimization at university. Sadly all my colleagues knew(and were taught) was Java and the Sun JVM we used at the time didn't even do most of the stuff we learned, not even the tail-recursion optimization, therefor the opinion of most of the students was that the professor should stop babbling about things that have no application in real life.

This was the one time i was on the side of academia...

[iam]

Thankfully since then the HotSpot JVM has become one of the most advanced VMs in terms of JIT optimization, doing things that are so wild and crazy that other JITs can only dream of.

[ajross]

Quibbles: the strlen() example is poorly explained. It doesn't hoist it because it's "built-in", it hoists it because strlen() is marked "pure" (i.e. without side effects) in the declaration. Any function can get that attribute.

[ridiculous_fish]

Actually I think this is a glibc/BSD difference. You're right that any pure function would be hoisted in the same way, but in fact strlen() is not marked pure in my OS X header (which looks to be the same as in FreeBSD). Compiling with -fno-builtin defeats the optimization, which shows that it is due to strlen being built-in on those platforms.

On my Linux machine, on the other hand, strlen() is marked pure, and there the optimization persists even with -fno-builtin.

[wzdd]

There must be more to it than that. For example, if something in the loop body writes to s, then the result of "strlen" could change and the optimisation will be wrong.

So, it must know a bit about what strlen() does, mustn't it -- otherwise it wouldn't know that it has to ensure that \0 isn't written to s inside the loop body.

[alecco]

Oh, I remember getting upset last time with this "test". For example:

  3. Multiplication by 2 to addition - integer
  Will GCC transform an integer multiplication by 2 to addition?

The statement (not function) x * 2 is shift x left 1 bit on almost all compilers. Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput. Meh.

[DarkShikari]

Shift has a lot less dependencies than ADD/LEA and has better reciprocal throughput.

Nope. Usually it's the reverse: Atom, for example, can only do one shift per cycle, but it can dual-issue adds.

[samth]

The comment about tail calls is wrong -- it's not an optimization, it's a guarantee about semantics of your program. Not optimizing tail calls is like making array dereference run in linear time instead of constant: it changes the programs you can write.

[barrkel]

Irrespective of how it changes the semantics of (mostly functional) languages that rely on it for iteration, tail calling is also an optimization in languages that don't need to rely on it for this, and it is not wrong to describe it as such.

[lukesandberg]

In a language that requires TCO then you are right, it's not about optimization it's about correctness. In a language (like c) that has no such semantics it is 'just' an optimization. In scheme however it is a correctness issue.

[merraksh]

I have a little doubt about number 6. A switch() without a "default:" label has undefined behavior if x is negative or above 5, while nothing would happen in the cascading if's. Wouldn't a correct optimization of that be

  void function(int x) {
    switch (x) {
      case 0: f0(); break;
      case 1: f1(); break;
      case 2: f2(); break;
      case 3: f3(); break;
      case 4: f4(); break;
      case 5: f5(); break;
      default:
    }
  }

[dchest]

Why does it have undefined behavior? Switch statement with no match and without the default case has defined behavior: the switch statement does nothing.

[thefre]

are you high?