Home

State of the art C compiler optimization tricks

A survey about state of the art C compiler optimization tricks, Felix von Leitner, Linux Kongress 2009.

The introduction and the conclusion is quite well put:

  • Optimizing == important.
  • But often: Readable code == more important

  • Learn what your compiler does

    Then let the compiler do it.

  • If you do an optimization, test it on real world data.
  • If it’s not drastically faster but makes the code less readable: undo it.

That's certainly something that I agree with 110%. And really, that's why a good compilers course is so important, even if the vast majority of students never write a compiler outside of class.

By Leon P Smith at 2009-11-06 19:29 | Implementation | Teaching & Learning | other blogs | 134788 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

And why all software

And why all software engineering/design courses should teach about profilers, and mandate their use.

By Ehud Lamm at Fri, 2009-11-06 19:52 | login or register to post comments

There have been "teaching &

There have been "teaching & learning" style academic papers that have advocated showing students how parsers and interpreters translate to machine code in the past, visually. What I think is missing is the ability for the student to see how something like a BURS graph optimizer transforms a tree and then yields faster execution code. It also makes you realize how hard the compiler must work to understand you to tune something for you.

This idea is sort of like how CMU teaches grade school algebra to kids.

By Z-Bo at Fri, 2009-11-06 23:48 | login or register to post comments

Also pays to recheck what the hardware is doing over time

Last time I worked on the nether end of a native compiler (targeting x86), when it came time to see what constants it was worth not-multiplying by (i.e., converting to shifts and adds), it turned out to be precious few (*). The amount of compute-ahead that some chips will perform (i.e., if you can avoiding doing anything data-dependent in your code) is astonishing, too.

So, just for example, you might be better off in some cases doing "complicated arithmetic" instead of "cheap table lookups".

(*) The exact multiply delay was almost certainly dependent on other factors, but it's relatively much faster than in the past.

By dr2chase at Fri, 2009-11-06 20:26 | login or register to post comments

And really, that's why a

And really, that's why a good compilers course is so important, even if the vast majority of students never write a compiler outside of class.

Or, another take we've had: teach students about compilers they would be writing. Most won't work for Sun to make the next Java. I don't think low-level optimizations are super important to most of them (though they should understand it a little). There's a myth that language design is hard: while true in the general case, as soon as you're in a specialized domain, there might be 'good enough'. Lex/Yacc-style tools were big steps here, and the community has rediscovered it a bit with Ruby DSLs. So, for example, teach students about source-to-source translators: let LLVM or JavaScript do the rest of the work.

In the beginning of our course, students wrote a quick Greasemonkey script to interpret webpages a little differently. Then, after going over parsing, they implemented one of google's little languages (unit conversion). Closer to the end (though as a worse example), they added classes, type checking, and FRP to the not-really-evolving JavaScript language through simple source-to-source translators.

Why not present compilers in a way students would more likely use them? It's less effective for students who will move on to language/compiler design, but they wouldn't be getting much out of such a class anyways.

As for the article itself -- it's interesting how it balances on the fence of architectural differences. E.g., when you tune, you tune for a particular architecture. I actually misread the article title before reading it: I've been looking for good books on modern static and dynamic language implementation.

edit: cleared up the list of examples. For this year's version (I'm not involved, but much is still in place since our changes): cs164. Unfortunately, there is no undergrad PL course, just a compilers one, which makes it a little random.

By lmeyerov at Fri, 2009-11-06 20:33 | login or register to post comments

Und dann ...?

Then, after going over parsing, they implemented one of google's little languages (unit conversion) and then, near the end (though as a worse example).

I was very interested by the examples you were giving, but then I ran into the period! Is it possible that you some words out?

By L Spice at Fri, 2009-11-06 23:44 | login or register to post comments

Fixed and added more

Fixed and added more context. I'm not the best storyteller :)

By lmeyerov at Sat, 2009-11-07 01:18 | login or register to post comments

Nah! Given a choice... skip the compiler course!

If the choice is a course on benchmarking and profiling vs a course on compilers.... teach/learn benchmarking / profiling.

And if you think there is not enough to be taught in such a course... well, you obviously need one yourself!

By John Carter at Sun, 2009-11-08 22:52 | login or register to post comments

There is no such course in

There is no such course in any major program I know about.

Closest would be Computer Systems course at CMU, based on Bryant's textbook.

By Z-Bo at Mon, 2009-11-09 14:11 | login or register to post comments

Depends

To be honest, it very much depends on the quality of the compilers course. I've taken two, at different institutions, and they were at the opposite extremes of quality.

By Leon P Smith at Mon, 2009-11-09 15:32 | login or register to post comments

Tail recursion example is wrong

The author gives a non-tail-recursive version of factorial and says that msvc doesn't turn it into a loop. I've seen msvc turn tail recursive functions into loops. I use that feature pretty heavily when writing algorithmic code because the compiler is also smart enough to warn if a tail recursive call will result in an infinite loop, which you don't get if you write complex for/while iterations.


long fact(long x) {
if (x<=0) return 1;
return x*fact(x-1);
}

It is interesting that gcc turns this into a loop, although it isn't tail recursive.

By Srikumar Subramanian at Mon, 2009-11-09 00:54 | login or register to post comments

Integer multiplications and additions are associative

GCC uses the associative property to transform the operation.

From tree-tailcall.c:

In addition to the standard tail recursion elimination, we handle the most
trivial cases of making the call tail recursive by creating accumulators.
For example the following function

int sum (int n)
{
if (n > 0)
return n + sum (n - 1);
else
return 0;
}

is transformed into

int sum (int n)
{
int acc = 0;

while (n > 0)
acc += n--;

return acc;
}

By bashyal at Mon, 2009-11-09 03:11 | login or register to post comments

This is really COOL

I don't comment too often, but just wanted to offer kudos.

In general, I'd love more straight ahead papers/book that really explain current practice/state of the art.

-- Scott

By scottmcl at Sat, 2009-11-14 00:40 | login or register to post comments

The author gives a

The author gives a non-tail-recursive version of factorial and says that msvc doesn't turn it into a loop. I've seen msvc turn tail recursive functions into loops. I use that feature pretty heavily when writing algorithmic code because the compiler is also smart enough to warn if a tail recursive call will result in an infinite loop, which you don't get if you write complex for/while iterations.

long fact(long x) {
if (x return x*fact(x-1);
}

It is interesting that gcc turns this into a loop, although it isn't tail recursive.

[spam signature delete by admin]

By dmayer77 at Sat, 2010-07-10 20:34 | login or register to post comments