Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'd like to see (good) examples of optimizations performed by compilers (static and JIT). Why?

  • To learn what we don't have to optimize ourselves (often leading to better code)
  • To be amazed
share|improve this question
    
I have a problem with the premise. I don't mind the compiler doing a good job of streamlining code, but personally I don't want a compiler trying to be smarter than me. I want it to do what it's told. It's job is to generate assembly language so that I don't have to. If I want to write stupid code, I don't want it to try and fix it for me. Often, I have a reason for writing it the way I do, and it don't want it rearranged. So maybe optimization is a fine option, but I fail to see the real value of it. –  Mike Dunlavey Dec 26 '10 at 21:42
add comment

closed as too broad by MichaelT, gnat, GlenH7, Bart van Ingen Schenau, Dan Pichelman Nov 18 '13 at 22:25

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

Someone once tried to examine optimizers in C code. They ran this code through various C compilers with different levels of optimization:

 main() {
      long i;
      double x;

      for( i=0; i<100000; i++) {
           x = sin(.3)
      }

      printf("%ld\n", i);
 }

With gcc, the code took about 20 seconds (that was in the age of the 486). With gcc -O, it took so little time, they couldn't measure it anymore. What had happened?

First the compiler noticed that x wasn't used anywhere, so it removed that:

 main() {
      long i;

      for( i=0; i<100000; i++) {
           sin(.3)
      }

      printf("%ld\n", i);
 }

sin() is a function without side effects, so we don't need to call it if no one cares for the result:

 main() {
      long i;

      for( i=0; i<100000; i++) {
      }

      printf("%ld\n", i);
 }

The loop is empty, so we can remove that, too:

 main() {
      long i = 100000;
      printf("%ld\n", i);
 }

A classical example of removing unused code.

share|improve this answer
    
Did it determine by itself that sin has no side effects or is that hardcoded somewhere? –  Bart van Heukelom Sep 30 '10 at 12:36
    
That's pretty impressive that it completely removed the loop and assigned i equal to the final value. –  tcrosley Sep 30 '10 at 13:34
    
@Bart: I think that's a special attribute in the header files. But if it has the source code, it should be able to figure that out by itself. –  Aaron Digulla Sep 30 '10 at 14:11
    
I wonder how useful this is. Does real code actually contain dead sections like that which can be removed? –  Winston Ewert Oct 1 '10 at 16:19
1  
@Winston: Usually, code I write doesn't have explicitly dead sections. However, optimizers do a lot of rearrangement of code, and can create issues that weren't in the original code, and so it can be worth checking for things that humans wouldn't do. We judge the optimizer on the time it takes and the output, not on each intermediate step. –  David Thornley Oct 1 '10 at 17:57
show 3 more comments

When I wrote the compiler for my implementation of ECMAScript I noticed that I could not perform recursion to a depth that was greater than 3000 calls. To me this was unacceptable so after a bit of experimentation I came up with the idea of replacing the return value with the arguments that were passed recursively. With this in place recursion became a viable option when writing code for my implementation.

public IDynamic Call(IDynamic thisObject, Args args)
{
    var engine = Engine.Instance.Value; // Thread Local
    var lexicalEnviroment = Scope.NewDeclarativeEnviroment();
    var thisBinding = thisObject ?? engine.GlobalEnviroment.GlobalObject;
    var newContext = new ExecutionContext(lexicalEnviroment, thisBinding);
    var result = default(IDynamic);
    var currentArgs = args;

    engine.EnterContext(newContext);
    do
    {
        result = Function.Value(newContext, currentArgs);
        currentArgs = result as Args;
    } while (currentArgs != null);
    engine.LeaveContext();

    return result;
}

NOTE

I don't believe that you would ever see this technique used in a professional context. Given the current code a strong relationship is implied (run-time -> compiler) and there really shouldn't be. I would expect any proper compiler would perform tail-call optimizations on the code itself.

Here is a proper example of tail-call optimization:

F#

let rec inner value input state =
    let r = p input state
    if r.IsEmpty then 
        value, state, input 
    else 
        inner (value @ [r.Head.Value]) r.Head.Input r.Head.State

Reflected CIL as C#

internal static Tuple<FSharpList<a>, b, LazyList<c>> inner@242<a, b, c>(FSharpFunc<LazyList<c>, FSharpFunc<b, FSharpList<Result<a, b, c>>>> p, FSharpList<a> value, LazyList<c> input, b state)
{
    while (true)
    {
        FSharpList<Result<a, b, c>> r = FSharpFunc<LazyList<c>, b>.InvokeFast<FSharpList<Result<a, b, c>>>(p, input, state);
        if (r.get_TailOrNull() == null)
        {
            return new Tuple<FSharpList<a>, b, LazyList<c>>(value, state, input);
        }
        state = r.Head.state;
        input = r.Head.input;
        value = Operators.op_Append<a>(value, FSharpList<a>.Cons(r.Head.value, FSharpList<a>.get_Empty()));
        p = p;
    }
}

Notice how the compiler is simply reusing the same stack frame in a while loop. This is very similar to what I implemented but without the unnecessary friendliness between the compiler and the run-time.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.