Will It Optimize?

http://ridiculousfish.com/blog/archives/2010/07/23/will-it-optimize/index.html

by DallaRosa • 15 years ago

132 29 15 years ago

udp• 15 years ago

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

samth2• 15 years ago

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• 15 years ago

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.

samth2• 15 years ago

There are two things here: an optimization, and a semantics guarantee. Obviously, if your language provides the guarantee, then implementing it correctly isn't just an optimization. But the original article claims that the transformation proves that proper tail calling is "just an optimization", which it doesn't prove at all. It's still an important semantic guarantee which increases the expressiveness of a language. This is true regardless of whether it is the only means of expressing iteration in a language.

lukesandberg• 15 years ago

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.

alecco2• 15 years ago

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• 15 years ago

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.

ajross4• 15 years ago

This surprises a lot of programmers. A barrel shifter is a big circuit for an ALU. Smaller than a multiplier obviously, but much larger than a ripple carry adder and somewhat larger even than the fancy pipelined adders used in fast CPUs.

It's the kind of thing that got skimped on in Atom. Lots of stuff runs surprisingly slow on Atom. Another one I find striking is that there are two pipes for ADD/SUB instructions, but ADC/SBB (the carry/borrow variants) are not just single-issue, but apparently unpipelined. Intel lists their throughput at 3 instead of 0.5!

alecco2• 15 years ago

My big mouth. I stand corrected.

Roritharr• 15 years ago

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• 15 years ago

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.

merraksh• 15 years ago

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• 15 years ago

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

rcfox2• 15 years ago

"If no converted case constant expression matches and there is no default label, no part of the switch body is executed."

Section 6.8.4.2, item 5 of http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf (page 134)

thefre• 15 years ago

are you high?

ajross4• 15 years ago

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.

wzdd2• 15 years ago

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.

saucetenuto• 15 years ago

GCC can statically prove that `s` isn't changed at all in the loop body, just accessed. Thus the analysis goes: `strlen()` is pure, and its argument never changes, so its result never changes, so I can hoist it.

ajross4• 15 years ago

The compiler can see the loop, so it can optimize it. Hosting constant expressions out of loops is a long-standing optimization in all compilers. Here, the expression "s" is unchanged* inside the loop, so the compiler can hoist it. If the expression were "s[0]" it could do the same. But can it do it for strlen(s)? It can, if it knows that strlen() has no side effects. So gcc extends C's syntax to add a "pure" attribute to tell the compiler exactly that.

* Pedants will point out all subtleties about C pointer aliasing rules apply here. But for the purpose of explanation, assume that nothing assigning throuh s means "s is constant".

ridiculous_fish2• 15 years ago

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.

Will It Optimize?

Related Stories