1

Martinus gives a good example of a code where compiler optimizes the code at run-time by calculating out multiplication:

Martinus code

int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
    x += x + x + x + x + x;
}
System.out.println(x);

His code after Constant Folding -compiler's optimization at compile-time (Thanks to Abelenky for pointing that out)

int x = 0;
for (int i = 0; i < 100000000000; ++i) {
    x += x + x + x + x + x;
}
System.out.println(x);

This optimization technique seems to be a trivial in my opinion. I guess that it may one of the techniques Sun started to keep trivial recently.

I am interested in two types of optimizations made by compilers:

  1. optimizations which were omitted in today's compilers as trivial such as in Java's compiler at run-time
  2. optimizations which are used by the majority of today's compilers

Please, put each optimization technique to a separate answer.

Which techniques have compilers used in 90s (1) and today (2)?

Community
  • 1
  • 1
Léo Léopold Hertz 준영
  • 134,464
  • 179
  • 445
  • 697
  • Good links about the topic: http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773, http://stackoverflow.com/questions/375913/what-can-i-use-to-profile-c-code-in-linux/378024#378024 and http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773. – Léo Léopold Hertz 준영 Jun 26 '09 at 21:25

4 Answers4

4

Just buy the latest edition of the Dragon Book.

Pod
  • 3,938
  • 2
  • 37
  • 45
1

The optimization shown in your example, of collapsing 100*1000*1000*1000 => 100000000000 is NOT a run-time optimization. It happens at compile-time. (and I wouldn't even call it an optimization)

I don't know of any optimizations that happen at run-time, unless you count VM engines that have JIT (just-in-time) compiling.

Optimizations that happen at compile-time are wide ranging, and frequently not simple to explain. But they can include in-lining small functions, re-arranging instructions for cache-locality, re-arranging instructions for better pipelining or hyperthreading, and many, many other techniques.

EDIT: Some F*ER edited my post... and then down-voted it. My original post clearly indicated that collapsing multiplication happens at COMPILE TIME, not RUN TIME, as the poster suggested. Then I mentioned I don't really consider collapsing constants to be much of an optimization. The pre-processor even does it.

Masi: if you want to answer the question, then answer the question. Do NOT edit other people's answers to put in words they never wrote.

abelenky
  • 63,815
  • 23
  • 109
  • 159
  • 2
    100*1000*1000*1000 => 100000000000 That is very much an optimization. It's called constant folding. – Pod Jun 26 '09 at 16:25
  • If you wouldn't call that an optimization, then you're wrong. – mqp Jun 26 '09 at 16:27
1

How about loop unrolling?:

for (i = 0; i < 100; i++)
    g ();

To:

for (i = 0; i < 100; i += 2)
{
    g ();
    g ();
}

From http://www.compileroptimizations.com/. They have many more - too many for an answer per technique.

Check out Trace Trees for a cool interpreter/just-in-time optimization.

Corbin March
  • 25,526
  • 6
  • 73
  • 100
0

Compiler books should provide a pretty good resource.

If this is obvious, please ignore it, but you're asking about low-level optimizations, the only ones that compilers can do. In non-toy programs, high-level optimizations are far more productive, but only the programmer can do them.

Community
  • 1
  • 1
Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
  • Your answer suggests me that compilers cannot do high-level optimizations. Is that right? – Léo Léopold Hertz 준영 Jun 26 '09 at 20:43
  • Right (I mean maybe there is a little bit they can do) but to do high-level optimizations effectively you need something that identifies high-cost call instructions, and that allows you to see the reason for what is being done, so you can see if there is a more direct way to do it. Only the programmer can see the reason. The link above shows a pretty good example. – Mike Dunlavey Jun 26 '09 at 21:00
  • I accept this answer, since I did not know about high-level optimizations explicitly. – Léo Léopold Hertz 준영 Jun 26 '09 at 21:22