views:

156

answers:

7

I am interested in optimization at runtime by a VM and at compile-time. I have had the idea that optimizations are most efficient and easiest at compile-time.

However, my thought seems to be false in certain circumstances. This is evident in Steve Yeggie's statement quoted by Daniel

[O]ptimization is often easier when performed at runtime by a clever virtual machine - -.

Why is the optimization easier when performed at runtime by a VM than at compile-time?

+4  A: 

Short answer: Because it is easier to identify and analyze at runtime the hotspots - the parts of your program that are using the most time.

Long answer:

If you start running the code in interpreted mode a virtual machine can count how often and how long different parts of the code are used. These parts can be optimized better.

Take nested if-then-else-clauses. Fewer boolean checks need lesser runtime. If you optimize the path for the part, that is executed more often, you can get better overall runtime.

Another point is, that at runtime you can make assumptions, that are impossible at compile-time. The Java-VM for instance inlines in server-mode virtual methods - as long only one class is loaded, that implements these method. That would be unsafe, if done at compile time. The JVM deoptimizes the code again, if another class is loaded, but often this never happens.

Also at runtime is more known about the machine the program runs on. If you have a machine with more registers you could use them. Again, that is not safe if done at compile-time.

One thing to say: optimizing at runtime has also disadvantages. Most important: the time for the optimizations is added to the runtime of the program. Also it is more complicated, because you have to compile parts of the program and executes them. Bugs in the virtual machine are critical. Think about a compiler, that sometimes crash - you can compile again and everything is fine. If a VM crashes sometimes, that means your program is crashing sometimes. Not good.

As a conclusion: You can do every optimization at runtime, that is possible at compile-time ... and some more. You have more information about the program, it's execution-paths and the machine the program is running. But you have to factor in the time needed for running the optimizations. Also it is more complicated to do at runtime and faults are more relevant than at compile-time.

Mnementh
"You can do every optimization at runtime that is possible at compile-time" - I don't believe it. A profile-guided optimizer can rearrange the order of data members in an object, e.g. to improve locality of reference or to move the most-used object to offset 0. That's nigh impossible if you already have actual objects in memory.
MSalters
Modern garbage-collectors rearrange the objects in the memory all the time to reduce fragmentation. To do this, all references/pointers have to be rewritten (or some clever indirection is used). Rearranging data-members doesn't seem so complicated in this context. But I have to admit, that I don't know an example of a VM that does it actually.
Mnementh
It's actually very easy, particularly since a VM that uses mark-sweep garbage collection will traverse the entire object tree on a regular basis. And again, runtime wins, because you see what fields really are accessed together, on a regular basis, versus in one method that's rarely called. (note: I have no idea whether the .Net or Java VMs actually do this, and personally doubt that they do)
kdgregory
@Mnementh: comment about the last sentence: Do you mean that optimization at run-time is more complicated than at compile-time and faults are more relevant at run-time than at compile-time.
Masi
@Masi: Yes, I meant it this way. I edited the sentence and added it explicitly for clarity.
Mnementh
I would like to get my hands dirty. --- Could someone give me an example or a homework about how I can see practically what Mnementh means with the last statement.
Masi
@Masi: Faults are more relevant, because a fault on a compiler doesn't necessarily breaks the compiled program. A fault on a VM is a fault of the program executed on the VM.
Mnementh
I mean to get an concrete example about a fault in some compiler, and to get another example of a fault in a VM.
Masi
+1  A: 

Because at runtime you have extra information: how the machine is performing, your process's memory limits and, probably most importantly, what code is being executed and how often.

Those things allow you to make runtime optimizations that you simply can't make at compile time.

cletus
+2  A: 

Because there's more information available at runtime. For instance exact CPU, operating system and other environment details are known. This information has an effect on how the optimization should be done.

Joonas Pulakka
Yup - compilers in general can't take advantage of SSE3, for instance.
MSalters
+2  A: 

The VM has full code of the program and the compiler often has only partial code because of separate translation of different translation units. The VM therefore has more data for analysis.

sharptooth
+1  A: 

THe VM can gather statistics to optimize, likewise a database does on your usage.

HeDinges
+1  A: 

Continuously keeping statistics and checking invariants are also overhead to execution time of compiled or interpreted fragments. If you can't optimize quick and well enough, don't bother. I don't think it is easier to get any better results doing it run time instead of compile time. I think it is even harder considering the complexity of a good implementation.

Much like the common misconception of sufficiently good optimizing compilers' generating better assembly than humans, sufficiently clever VM may need to be damn too clever to execute faster.

artificialidiot
A: 

Something to recognize is that it isn't the concept of a VM that allows runtime optimizations, it's the fact that many VMs don't throw away the original program meta-data and have built in functionality for reflection. A more appropriate term to use would be a "Runtime library" can do better optimizations than static optimizations alone; this applies to non-VM languages like C.