Newbie question about just-in-time compilation

[jondeker]

I'm reading about browsers and javascript and how improvements in speed have been made. I don't know programming but I was just curious about general idea of how things work.



First, here is my understanding of javascript path. Is it correct?

Traditional/default path:
javascript --> bytecode --> virtual machine --> machine code

If javascript engine determines command is frequent then path becomes:
javascript --> compiler --> machine code

This second path compiled code is cached and used every time thereafter. This is faster because next time, javascript has fewer steps to execute since it doesn't have to go through virtual machine.



If all of that is the case, my second question is: why bother with second path? If the goal is to speedup by caching machine code, why not store results from first path and cache those results which are also machine code?

 

[degibson]

I'm reading about browsers and javascript and how improvements in speed have been made. I don't know programming but I was just curious about general idea of how things work.



First, here is my understanding of javascript path. Is it correct?

Traditional/default path:
javascript --> bytecode --> virtual machine --> machine code

If javascript engine determines command is frequent then path becomes:
javascript --> compiler --> machine code

This second path compiled code is cached and used every time thereafter. This is faster because next time, javascript has fewer steps to execute since it doesn't have to go through virtual machine.



If all of that is the case, my second question is: why bother with second path? If the goal is to speedup by caching machine code, why not store results from first path and cache those results which are also machine code?

Let me clarify the flows a little more before I answer:
Flow 1: Source->Bytecode, Bytecode run by VM
Flow 2: Source or Bytecode -> Native, Native run on host

Each translation step need only be done once. Generally, the native binary runs faster than the bytecode version, so if the code runs many times, its valuable to pay the cost of the native compiler (generally much slower than the bytecode compiler) and then reap the benefits of the fast execution.

EDIT: I realized my response didn't answer your question. Here it is again:

... why not store results from first path and cache those results which are also machine code?

It depends on what you mean by 'results'. I assume you mean the machine code part of your first flow. The reason why you don't store this is because the VM doesn't make machine code in the first flow. The VM is capable of executing bytecode directly.

Bytecode is a list of instructions that the VM understands. A simply VM reads these commands one a time, performs one, then moves on to the next. These commands are specific to the VM, in this case, to a JVM. The VM reads bytecodes from a file, then the VM itself performs the operation specified. The bytecode is NOT executed -- it is read, as data, by the VM, which then does different things based on that input data.

Machine code, on the other hand, runs natively on the host. To make correct and fast machine code you typically need a longer compilation step than the generation of bytecode.

 

[dalvaallen19]

Hi,

The Flow is gone like
Source->Bytecode, Bytecode run by VM...Java script run on VM means run anywhere.

Thanks
Dalva Allen

 

[doallen194]

Hi,

The Flow is gone like
Source->Bytecode, Bytecode run by VM...Java script run on VM means run anywhere.

Thanks
Dalva Allen

Hi,

Sorry, but i cant understand what you want to say about VM please say in detail so i understand properly....

 

[degibson]

I highly suspect dalvaallen19 = doallen194.

 

[jondeker]

Flow 1: Source->Bytecode, Bytecode run by VM
Flow 2: Source or Bytecode -> Native, Native run on host


It depends on what you mean by 'results'. I assume you mean the machine code part of your first flow. The reason why you don't store this is because the VM doesn't make machine code in the first flow. The VM is capable of executing bytecode directly.

Hi,
Thank you for response, but I do not understand this.

By 'results' i do mean the output of path1.

Why do you say 'VM doesn't make machine code' ? If you're running javascript on a intel cpu, at some point the VM has to create instructions that the intel cpu can understand, x86 machine code?

So even though a VM does read/execute the bytecode, the VM has to translate and output to x86 cpu for something to happen? So why not cache this VM output?


It feels like my mental picture of the process has some hole in it that i'm not seeing...

 

[Markbnj]

I highly suspect dalvaallen19 = doallen194.

It's being looked into. Thanks, degibson.

 

[degibson]

EDIT: OP is asking about JS, I made my answer kinda Java-specific. Meh.

A little out of order in answering...

Hi,
Thank you for response, but I do not understand this.
... It feels like my mental picture of the process has some hole in it that i'm not seeing...

No problem. This is pretty subtle actually.

By 'results' i do mean the output of path1.
...
So even though a VM does read/execute the bytecode, the VM has to translate and output to x86 cpu for something to happen? So why not cache this VM output?

OK. I think I understand your current perception. The following is what I think you think -- tell me if I'm wrong.

Compiler translates source to bytecode. VM translates bytecode to machine code (e.g., x86), which then runs natively.

That is what happens only with a JIT-based approach. Not all VMs will JIT all code, nor will all VMs JIT at all. What else can they do? See below.

Why do you say 'VM doesn't make machine code' ? If you're running javascript on a intel cpu, at some point the VM has to create instructions that the intel cpu can understand, x86 machine code?

I say 'VM doesn't make machine code' because not all VMs make machine code.

What is bytecode? Bytecode is a sequence of instructions that the VM understands, and most CPUs do not. What are the ways that a program represented in bytecode can be executed?
1. Translate the bytecode to machine code, and run the machine code (this is the JIT approach).
2. Read the bytecode and execute each command on behalf of the bytecode within the VM. (interpretation)

Here's an example of #2. Consider a bytecode language with four symbols:
o - Open file
c - Close file
w - Write file
r - Read file

Clearly these operations cannot be executed directly by a CPU. CPUs operate well below the file abstraction, each operation involves the OS, etc., but these are legal operations for any language, including bytecode.

So consider this string of bytecode:
o "foo.txt" "rw" r buffer 64 w "Hello, world!" 14 c

In human language: Open file foo.txt in rw mode. Read 64 bytes from the front into buffer. Then write "Hello, World!" into the file. Close the file.

Still, this sequence cannot be executed directly by the CPU. But it can be read and executed by a VM, by some code that looks like this:

Pseudocode

forever {
  cmd = readBytecode();
  switch(cmd) {
  case 'o':
    filename = arg1;
    mode = arg2;
    f = open_file( filename, mode );
    break;
  case 'r':
    buf = arg1;
    len = arg2;
    buf = read_file( f, len );
    break;
  case 'w':
    data = arg1;
    len = arg2;
    write_file( f, data, len );
    break;
  case 'c':
    close_file( f );
  }
}

The above code is an interpreting VM. The VM does not execute the bytecode, it reads the bytecode and performs the commands encoded within the bytecode. An interpreter need not generate machine code at all for the target execution, because the interpreter knows how to execute the entire language all by itself.

Notice that there aren't any left-overs from interpretation like there are from JIT-ing. There's no machine code to cache, because no machine code was generated.

When to prefer interpretation to native
Lots of languages are interpreted. Shell scripts, python, Java, lots more. Lots more are compiled to native: C, C++, D, etc. Some can go either way: Java, python, etc.

Java is one of those interesting languages that can go either way (actually, Java's intermediate form, bytecode, can go either way). So, what are the advantages and disadvantages of each?

Pro native
- Native code is faster, once it has been compiled

Con native
- Compilation to native takes a long time, but only needs to be done once

Pro interpreted
- Almost no compilation step

Con interpreted
- Runs quite a bit slower than native

The simplest JVMs only interpret. Thats entirely legal in the Java execution model. They never JIT, because decent JIT compilers are hard to write and are pretty large.

The smartest and fastest JVMs out there usually interpret code on the first run. When they detect they are running the same section of code over and over again, they pause execution and JIT the code to native. That allows the execution to pick up a lot of speed, after the compilation is done.

Because compilation is expensive, JVMs keep a compiled code cache (sometime just called a code cache), so they need not repeat most compilation steps if they execute the same code again. But when running interpreted, there are no 'results' of interpretation that can be safely cached -- there are a set of deltas to the outside world (the output set of the interpretation), but that might change from run to run depending on inputs.

 

[Kirby]

It's being looked into. Thanks, degibson.

Bad english, similar posting style, same last name....

Not sure what the point would be. :hmm:

 

[degibson]

Bad english, similar posting style, same last name....

Not sure what the point would be. :hmm:

I have to admit, I'm curious about the motivation myself.

 

[jondeker]

OK. I think I understand your current perception. The following is what I think you think -- tell me if I'm wrong.

Compiler translates source to bytecode. VM translates bytecode to machine code (e.g., x86), which then runs natively.

That is what happens only with a JIT-based approach

First, thank you for long detailed response.

That is a bit of mix between path1 vs path2, or the purpose of interpreting vs jit. I do think i correctly understand that difference... i hope.

I think what i'm not getting is what exactly is happening in path1, interpreting VM



If we can just speak about interpreting mode/path/method, and forget about jit for the moment.

You gave the example of bytecode, then pseudocode, and i am very confused by this:

An interpreter need not generate machine code at all for the target execution, because the interpreter knows how to execute the entire language all by itself.

Notice that there aren't any left-overs from interpretation like there are from JIT-ing. There's no machine code to cache, because no machine code was generated.

How can the interpreter not generate machine code at all?

In my mind there has to be another step after pseudocode to actually speak with cpu. It has to go from pseudocode you wrote to x86 instructions (AAS, ADC, ADD, AND, AND, CALL, etc).



If i can use an analogy (which i hope doesn't make the problem worse), suppose there are 3 people: chinese speaker (source), japanese speaker (target), interpreter. The chinese speaker says something to interpreter which will be translated for japanese speaker.

Ok, with all that said, the way i'm reading your statement is like the chinese speaker says something in chinese (bytecode), the interpreter mentally translates in head (pseudocode), and the japanese speaker does some action without the interpreter ever having said anything outloud (no japanese translation, no machine code generated).

In order for japanese speaker to understand what to do, he has to hear instructions in japanese. But you're saying that no machine code (japanese language spoken outloud) needs to be generated.

I hope what i'm saying makes sense


And just to follow through with this analogy, cacheing would be like tape recording the japanese translation spoken by interpreter. So next time chinese speaker needs to say same thing, he doesn't need to go through interpreter, he could just playback recording.

 

[Crusty]

An interpreter is written in some/any language and in turn gets executed by whatever that language uses for runtime. Since it's up to the interpreter to parse your input and run the code there is no need for it to generate machine code since it is already being hosted in a running process and executing machine code at some level. So simply put, you just use that process to execute what the 'interpreted language' is telling the computer to do.

I could come up with a simple grammar and write a program using Java that can parse inputs that follow the grammar and then execute what that input is requiring all without knowing anything about machine code.

 

[degibson]

You gave the example of bytecode, then pseudocode, and i am very confused by this:
How can the interpreter not generate machine code at all?

The interpreter is compiled beforehand, and shipped to the customer. I.e., that pseudocode I provided is compiled, by a compiler, to machine code. The interpreter itself does't generate any new code to run arbitrary programs in its target bytecode. It just reads a data file (consisting of bytecode), and then does what the bytecode says needs to be done.

 

[jondeker]

An interpreter is written in some/any language and in turn gets executed by whatever that language uses for runtime. Since it's up to the interpreter to parse your input and run the code there is no need for it to generate machine code since it is already being hosted in a running process and executing machine code at some level. So simply put, you just use that process to execute what the 'interpreted language' is telling the computer to do.

The interpreter is compiled beforehand, and shipped to the customer. I.e., that pseudocode I provided is compiled, by a compiler, to machine code. The interpreter itself does't generate any new code to run arbitrary programs in its target bytecode. It just reads a data file (consisting of bytecode), and then does what the bytecode says needs to be done.

Both these statements to me are saying same point about the step between bytecode and interpreter. But i'm talking about after that, the parts i bolded. The step between interpreter and cpu. There has to be some form of binary code, even if not "new" generated code but rather line-by-line translated binary code.

For example the top 2 rows in this picture:

What's the difference between the data in green box in both rows? In both cases "native machine langauge" is sent to cpu.

Whynot cache the results of first row as you are translating line-by-line? Wouldn't that give you the benefit of quick startup when running first time, and by using cached machine code from first row, each subsequent time same bytecode is called you will get fast execution without having to go through compiler?

 

[Crusty]

In the first row the JVM process is reading the bytecode, analyzing it, and executing what it says to do inside of the JVM process.

In the second row at runtime the JIT compiler is reading the bytecode, analyzing it, and storing the native machine code it generates, then executes that code in its own process space.

 

[degibson]

That picture is very misleading, and the text in the first row is just plain wrong.

The JVM itself consists of executable machine code. When operating in interpreted mode, the JVM does not produce machine code, nor convert bytecode into machine code. Interpretation works as I illustrated above, with the JVM literally performing the instructions on the bytecode by reading them, running the bytecode operation through a big switch() statement, and repeating until all the bytecode is gone.

 

[knights489]

No one seems to be answering the heart of the question OP is asking. The other posters are correct in their statements but they are answering a somewhat slightly different question.

The responses so far have answered the question of the difference between 2 functions: interpreter vs jit compiler. The OP is basically asking why isn't there 1 hybrid function.

The answer is yes it's possible, it's called an incremental compiler (http://en.wikipedia.org/wiki/Incremental_compiler). An interpreter is like translating one line at a time every time, a jit compiler is like translating a block at a time and remembering, an incremental compiler is like translating one line at a time but also remembering.

The problem with using an incremental compiler is performance. You get the worst of both worlds: first run and second runs.

First run performance: interpreter is faster than incremental compiler. Incremental compiler has additional overhead because it has extra work of writing down (compiling) as it goes.

Second run performance: jit compiler is faster than incremental compiler. The big performance gains and the whole point in compiling comes from optimizations (http://en.wikipedia.org/wiki/Compiler_optimization). In second runs, the theoretical cached incremental compiled code will be faster than interpreter because there isn't translation work going on. However those performance gains are small, it is optimizing for cpu architecture you are on that will yield the big jumps.

So in summary you are better off picking one or the other rather than trying to meld the two together. Incremental compiler does have benefits in areas other than performance, but web browsers only care about performance and that's where incremental compiler fails.

Since this topic was asked in relation to web browsers: Firefox tracemonkey will start off interpreting and after it detects 2 runs of same function it will kick in nanojit compiler (https://developer.mozilla.org/en/spidermonkey/internals/tracing_jit). Google V8 is more aggressive and starts with trying to compile directly to native code, and only when it encounters problem will it fall back to interpreter. Internet explorer will pick its nose trying to slow down switch to web apps.