Seven kinds of virtual machine interpreters. In search of the fastest

All problems in the field of Computer Science can be solved by introducing an additional level of indirection. Except for one: too many levels of indirection.
But for all the problems of computer science, it’s possible to solve all problems.

Software interpreters are known for their low speed. In this article I will tell you how to speed them up.
I have long wanted to elaborate on the creation of interpreters. Just the same promised, including himself. However, a serious approach required the use of more or less realistic code for examples, as well as performance measurements, confirming (and sometimes refuting) my arguments. But at last I am ready to present to the venerable public results, and even a little more interesting than I intended.
This article will describe seven ways to build a software VM for a single guest system. We will proceed from the slowest to the faster ones, in turn getting rid of various “inefficiencies” in the code, and at the end we will compare their work using the example of one program.
Those who are not afraid of assembler listings, macro-speckled C code, richly fertilized with address arithmetic, goto and even longjmp, as well as programs that use copy-paste in the name of speed or even create pieces of themselves, please under cat.


Interpreters are a class of programs that analyze text written in some input language for one phrase (expression, statement, instruction, other semantic unit) at a time and immediately perform the actions prescribed by this phrase. In this way, they differ, for example, from translators in which the phases of parsing the input language and the execution of actions are separated in time.
This definition is quite general, and many programs fall under it, including implementing virtual machines (VMs). The latter can be divided into two classes : language and system.

It should be warned that most of the ideas that I will talk about were found quite a long time [3, 4]. Moreover, a similar comparison of the speed of various types of interpreters (for a very primitive VM) has already been made [2]. There are even Russian-language books of the Soviet time [1] on this topic.

1. I allow myself to limit myself to Intel® 64 host architecture. Measurements will be made for only one machine. I urge all readers to clearly understand that the details of the architecture and micro-architecture (such as the organization of the transition predictor) directly affect the speed of the programs, in particular the interpreters. Moreover, it may turn out that algorithm A, which runs faster than algorithm B on architecture Z, will lose to him on system Y.
')
2. Code examples were made with the expectation of inter-system portability. They must be handled correctly by the currently popular versions of the GCC and ICC compilers on POSIX systems. I will point out a few “non-portable” places separately.

3. The story is focused on interpreters created for the needs of simulation of central processing units. The specificity of this subject area affects the structure of the solution. For example, further attention is drawn to the non-triviality of the decoding phase of the input machine language, whereas in the works I know, this problem is considered trivial (solved by the identity operator).

4. In this article, nothing will be said about the analysis of grammar, that is, about that part of the interpretation necessary for building interpreters of high-level languages. In the book of Terrence Parr [5], the creator of ANTLR - a powerful framework for creating lexers, parsers and generators, this issue is revealed in detail and in detail.

So, first, the description of what we will model is the specification of the virtual machine.

The architecture of the investigated VM

The full code of the examples, as well as the Makefile for the build and the script for performance testing are published here: github.com/grigory-rechistov/interpreters-comparison .
Further I will quote some pieces of code from there and refer the reader to specific file names and functions.

For the purposes of this article, I wanted to use a VM, simple enough to have time to write and debug several options for its implementation in a reasonable time, but difficult enough so that it manifests various effects inherent in real projects, and that it can be performed though would be a minimally useful program, and not just a boring pseudo-random flow of instructions.
In general, this VM is inspired by the Fort language. Compared to it, it is greatly simplified and has only those instructions that were necessary to illustrate the ideas described in the article. The most important, in my opinion, its omissions (simplifications) compared with the normal Fort - the lack of a procedural mechanism and a dictionary.
I want to note that all the examples described below can be directly adapted not only for stack but also register VMs.

1. The word width is 32 bits. All operands and instructions are signed or unsigned 32-bit integers.
2. Three processor states: Running — active execution of instructions; Halted - stop after the execution of Halt, corresponds to the normal completion of the program; Break - stop after any abnormal, unsupported, or non-standard state instruction, indicates an error in the program. In other words, the VM starts working in the Running state. She finishes her work in the Halted state, if no unexpected events occurred during the work and the execution reached the Halt instruction. If there was a division by zero, going beyond the code, overflowing or emptying the stack, or something else that I didn’t want to support during implementation, it stops in Break mode.
3. All registers are implicit, and there are only two of them. PC is a pointer to the current command. SP is a pointer to the top of the stack. At the beginning of the PC = 0, SP = -1.
4. A stack of parameters with 32 unsigned whole words. SP points to the current member, or is -1 if the stack is empty.
5. Program memory with a capacity of 512 words, available only for reading. When going beyond the boundaries [0; 511] the processor stops in the Break state.
6. Instructions can have zero or one explicit operand (imm). In the first case, they have a length of one word, in the second - two.
7. Description of all machine instructions. Operation codes, as well as other elements of the VM architecture, are described in the common.h file.
   
   Description of instruction set

   Break = 0x0000 - put the processor in the Break state. Since the uninitialized program memory is filled with zeros, any random transition "past the code" leads to a halt.
   Nop = 0x0001 - an empty command that does not change the stack and SP.
   Halt = 0x0002 - put the processor in the Halted state.
   Push = 0x0003 imm - put the imm constant at the top of the stack.
   Print = 0x0004 - remove the value from the top of the stack and print it in decimal form.
   JNE = 0x0005 imm - remove the value from the top of the stack, and if it is not zero, add imm to PC. The imm is interpreted as a signed number.
   Swap = 0x0006 - swap the top of the stack and the next element below.
   Dup = 0x0007 - put a copy of the topmost item on the top of the stack.
   JE = 0x0008 imm - remove the value from the top of the stack, and if it is zero, add imm to PC. The imm is interpreted as a signed number.
   Inc = 0x0009 - add one to the top of the stack.
   Add = 0x000a - add the top two stack elements. Remove them from the stack and put the result as the top.
   Sub = 0x000b - subtract from the top of the stack following it. Remove them from the stack and place the result on top.
   Mul = 0x000c - multiply the top two stack elements. Remove them from the stack and put the result as the top.
   Rand = 0x000d - place a random number on the top of the stack.
   Dec = 0x000e - subtract one from the top of the stack.
   Drop = 0x000f - remove the number from the top of the stack and “throw it away”.
   Over = 0x0010 - place on the top of the stack a copy of the item that is the second in the stack after the top.
   Mod = 0x0011 - divide the top stack element to the next one. Remove them from the stack and place the remainder of the division at the top.
   Jump = 0x0012 imm - add imm to PC. The imm is interpreted as a signed number.
   
   Arithmetic operations that lead to overflow (except division by zero) do not cause a transition to the Break state and are not signaled in any way.
   I note that all instructions, including those that control execution (ie, Jump, JE, JNE), unconditionally promote the PC to its length at the end of the execution. This should be taken into account when calculating the transition address offset. Those. the jump is counted from the beginning of the instruction, following for the current one.
   
   
   
8. Execution of any instruction not explicitly defined in the architecture is equivalent to execution of Break.
9. For debugging needs, the processor contains a 64-bit register of steps, increasing by one after each executed VM instruction. Programs allow you to set a limit on the number of steps after which the simulation is interrupted. By default, it is LLONG_MAX.
10. After completion of the simulation program displays the status of the processor and the stack on the screen.

Benchmark

To compare the performance needed a program written for this VM. It had to be long enough, with a non-trivial flow of control, not to use excessive input-output, i.e. be computationally complex. And at the same time be simple enough that such a scattered person like me could debug it in machine codes even without a normally working simulator. The result is what I called Primes.
Primes displays all prime numbers contained in the interval from 2 to 100,000. Its code for the VM is contained in the Primes [] array, which was declared the same in all examples.

In my launches, it ran from half to three minutes. Its algorithm is approximately (corrected for the stack architecture) corresponds to the program contained in the file native.c.

Optimization Note

One misleading benchmark can help achieve what is impossible to get through years of good engineering work.
A misleading benchmark can be done.
dilbert.com/strip/2009-03-02

I want to once again emphasize one very important point in optimizing application performance: no one can be trusted . Especially if someone says something like: “use algorithm X instead of your Y, because it is always faster”. It is impossible to trust hardware prospectuses to manufacturers of equipment, articles of creators of compilers, promises of authors of libraries. You can not believe your instinct - in matters of finding bottlenecks in performance, it still lies like. You can only believe the results of measurements and profiling, and then not always.

Nevertheless, you can believe me. Indeed, the Primes program, which I use to compare performance, is ridiculously naive: not only does it hardly create any significant load on all processor subsystems, so the algorithm used in it is not optimal! In fact, for large N there is no need to check the divisibility of N by N-1; it suffices to check the dividers from 2 to √N. She doesn't even use all the available instructions that I wrote so carefully!
Yes, and VM, which is already there, a little worth it. Resource volumes are tiny, even 8-bit microcontrollers are often more complicated. Without mechanisms for calling procedures and handling exceptions, you won't get far. Perhaps in the next semester, I will force students to expand it to a sanctioned monstrous size, hehehe!

But do not forget that all this material serves only an illustrative purpose. If the simulator were realistically complex, and the benchmark program were real sizes, then few would want to read them.

The optimization note applies to all subsequent material in this article. On another generation of host processors with a different version of the compiler, it may well turn out that the slowest code of this article will overtake all other options. I myself was surprised to receive the graphics - some results did not meet my expectations; Moreover, different compilers took the lead of different participants. But I am again running ahead.

Switchable

The first interpreter construction scheme is the most popular - the switched interpreter (the switched.c file). Its code naturally expresses the base cycle "read the operation code - recognize - execute - repeat". Since this is the first scheme to be analyzed, let us consider how all the phases of this cycle are expressed in code VM; in the future we will pay attention only to the differences (no one wants to read hundreds of lines of similar code).

The fetch () function reads the “raw code” of the operation located at PC. Since the interpreter models the system VM, it is necessary to be ready for the PC to go beyond memory; fetch_checked () is responsible for checking.



The decode () function should complete what started in fetch () —to fully define the characteristics of the command. In our case, this is its length (1 or 2) and the value of the literal operand for those instructions that have it. In addition, according to the adopted agreements, all unknown opcodes are considered equivalent to Break. All this becomes clear as a result of the work of a single switch statement.
The peculiarity of the processing of "long" instructions with the operand: they require additional reading of the instruction memory at PC + 1, which also needs to be checked to go beyond the boundaries.


For more realistic architectures, the decoding procedure in a software VM is somewhat more complicated : you have to search through the prefix tree, that is, go through a series of nested switches. But I think that the general idea was successful.

Finally, execution — by the operation code obtained from decode (), we move on to the service procedure (service routine) —a block of code responsible for the semantics of a specific guest instruction. Another switch, in all its glory length.


Hereinafter, BAIL_ON_ERROR is used to intercept possible exceptions that occurred during the execution of individual commands:

 #define BAIL_ON_ERROR () if (cpu.state! = Cpu_Running) break;

Unfortunately, this is C, and using normal try-catch will not work (but wait, near the end of the article there will be something similar to it).
An observant reader may wonder why two switches are used: in decode () and in main (), because they are called one by one and controlled by the same value, that is, they can be combined. The need for such a separation will become clear in the next section, where we will get rid of the need to constantly call decode ().

Pre-decoding (pre-decoding)

The first thing to get rid of is decoding at each step of the simulation (file predecoded.c). In fact, the contents of the program do not change in the course of work, or change very infrequently: when loading new applications or dynamic libraries, occasionally by the application itself (JIT program that adds its own pieces). In our VM there is generally no possibility to change the program during execution, and this should be used.



Since the memory of the programs of this VM is only 512 words, we have the opportunity to decode it all at once and save the result in an array indexed by the value of PC. In real VMs with 2 ³² – 2⁶⁴ byte guest memory, this trick wouldn’t work. It would be necessary to use an a la cache structure with displacement, which in a limited amount of host memory would keep the working set of matches “PC → decode_t”. In this case, it would be necessary to make new entries in the cache of decoded instructions during simulation. However, in this case there would be a gain in speed. When re-executing recently executed instructions, they would not have to be re-decoded.

Well, let's call predecode_program () before execution:


Two comments.
1. Pre-decoding leads to the fact that at the stage of command execution the Fetch phase is not executed. In this case, there is a risk of incorrect simulation of architectural effects associated with it, such as triggering hardware breakpoints. This problem is solved by carefully tracking the entered cache.
2. Unlike system VMs, in language VMs, which usually have a very simple command structure, the fetch and decode phases are trivial. Therefore, for them, such caching is not applicable.

How much getting rid of decoding accelerated the simulation? Let me keep the intrigue until the end of the article, where all variants of interpreters will be compared. In the meantime, let's try to understand how to further speed up our interpreter.
As I already wrote, intuition in this case is a bad assistant. Let's turn to impartial tools: we use Intel® VTune Amplifier XE 2015 Update 4 to carry out “General Exploration” for predecoded. In the overview report, the problematic, from the point of view of the analyzer, aspects of the program are highlighted in red:



"Bad speculation" ??? What is such a speculator? Unclear. “Branch Mispredict” is already clearer. Some kind of conditional or indirect transition in our program constantly causes an error of the predictor of transitions. At this event, instead of doing useful work, the processor is forced to empty the pipeline and begin executing another instruction. In this case, there is a simple one in a couple of tens of cycles.
But why in such a simple program such a problem? Begin to go down below. I click on “Branch Mispredict”, it opens the Bottom-up view, which shows the main suspect - main ().



NDA, it did not become clearer. Let's try to search for the program line. We click on main (), a view of the program source opens (previously collected with symbolic information). Open both views - Source and Assembly, and carefully look at the columns "Branch Mispredict". Frankly, I did not immediately manage to find what I needed, even though I knew where and what to look for.



In this screenshot, blue highlights the lines of the source code and the corresponding machine code. Wow - our main switch and the corresponding command “jmpq 0x400f20 (,% rdx, 8)” have one hundred percent (1.000) incorrect predictions! How so? The reason is the limitations of the equipment for predicting such transitions.

The branch target predictor tries to predict where the transition will occur in the current jmp version, based on a limited set of historical data, such as the address of the instruction itself and the history of transitions from it. In our case, the transition history is the history of the execution of guest commands inside the VM. However, for Primes, it is completely chaotic - after push, both one more push and over can go, after over can go over, sub, swap; the number of iterations of the inner loop is large and changes all the time, etc.


The penalty of incorrectly predicting the address of the transition is the more likely the greater the number of instructions available in the VM - for this reason I abandoned the idea of ​​using the BF machine as an experimental one: only 8 instructions could turn out to be insufficient.

Threaded

“SEDDRESSES are an important element of the Ardrit civilization from the planet Enteropia. See SEPULARS.
I followed this advice and read:
"SEPULCARIES - devices for seperation".
I searched "Sepulenie"; it said:
“SEPARATION is the occupation of the ardrites from the planet Enteropia. See SOPULTS.

Stanislav Lem. “The Star Diaries of Ion Tikhy. Journey fourteenth. "

With the cause of poor performance figured out. Let's start to eliminate it. Need to help predictor transitions. In this case, of course, it would be nice to know how it works, in detail. For lack (or unwillingness to contact) the details, we use general considerations. Recall that the predictor uses the address of the instruction itself to associate the transition history with it. That would be able to "smudge" a single jmp in several places; Each of them will have its own local history, which, hopefully, will be less chaotic to make adequate predictions.
This is what I tried to do in the threaded.c and threaded-cached.c files (an option that also includes pre-decoding).
The essence of the solution: after the execution of the current service procedure, do not return to the common point (switch), but go straight to the service procedure of the next instruction.
The bad news number 1 - to go on the label will have to use the operator goto. Yes, yes, I know, goto is bad, oh, I myself wrote about it. For the sake of speed - all serious. In the VM code, this will be hidden in the DISPATCH macro:


The bad news is number 2: you will have to use a non-standard (absent in C standard) extension of the GCC language — the operator for taking the address of the && label:

This nonstandard operator is supported by GCC and ICC compilers for the C language (but as far as I know, not for C ++).
As a result, the main "loop" (which in fact does not do any iteration) of the interpreter looks like this:


The simulation begins with the first DISPATCH and then occurs as a leapfrog between service procedures. The number of host instructions for indirect transitions in the code has grown, and each of them now has an associated history for a couple of guest instructions. The probability of an unsuccessful prediction decreases in this case (in [4] it is stated that from 100% to 50%).

This technique has the name of the sewn code , in English - threaded code; Note that the modern term “thread - flow” appeared much later and is not related to the topic in question.
This optimization and in our time is used in quite popular projects. I will quote the post Utter_step habrahabr.ru/post/261575 of July 1 of this year:

Vamsi Parasa from the team of optimizing server scripting languages ​​from Intel suggested a patch <...> that translated the switch block responsible for processing Python bytecode to use the computed goto, as already done in Python 3. As Eli Bendersky explained , in such a huge switch -block, as in the bytecode parsing unit in CPython (consisting of more than 2000 (!) lines), this gives an acceleration of about 15-20%. This happens for two reasons: the computed goto, unlike the switch-case, does not perform the boundary checks required for the switch operator according to the C99 standard, and, perhaps more importantly, the CPU can better predict branching in such situations <... >

However, when measuring the interpreter speed obtained from threaded.c with the default compilation flags (threaded-notune program), I got an unexpected result. The speed of the program was 10% –20% lower than switched. Analysis in VTune showed that the cause of the brakes is still the same - 100% Branch Mispredict on one of the indirect transitions within DISPATCH:



However, something is wrong here - for all other DISPATCH there are no statistics at all. Moreover, VTune does not show an assembly code for them. The objdump check by disassembling confirmed the suspicions - there was only one indirect transition in the whole body of main (), associated with the transition to service procedures:

 $ objdump -d threaded-notune |  grep 'jmpq \ s * \ *% rdx'
   4006c8: ff e2 jmpq *% rdx
   400ae7: ff e2 jmpq *% rdx

(The second jmpq at address 400ae7 - from the register_tm_clones function - is irrelevant). What turns out - the GCC compiler as a result of the optimization process helpfully slammed all the DISPATCH into one, in fact having rebuilt the switchable interpreter!

The compiler is a sworn friend

This is where my struggle with the compiler began. I spent a lot of time to get GCC to generate code with independent indirect transitions for each service procedure.

• Checked different levels of optimization. The correct code was obtained only with -Og, the levels of optimizations from -O1 to -O3 collapsed DISPATCH.
• I tried to replace goto with assembly insertion and thus hide the fact of switching from the compiler to the label:
  

   #define DISPATCH () \
   __asm__ __volatile __ ("mov (% 0,% 1, 8), %% rcx \ n" \
                        "jmpq * %% rcx \ n" \
                       :: "r"(&service_routines), "r"((uint64_t)decoded.opcode): "%rcx");
  

  
  . (sr_Add, sr_Nop ..) , service_routines . .
• service_routines - , : . . GCC DISPATCH !

, , , .

, . - , . :

Please note the warning under -fgcse about invoking -O2 on programs that use computed gotos .
<...>
Note: When compiling a program using computed gotos, a GCC extension, you may get better run-time performance if you disable the global common subexpression elimination pass by adding -fno-gcse to the command line.

! -fgcse threaded . , , . , «Fast interpreter using gcc's computed goto»:

I have the same problem as Philip. With G++ the compiler seems to go though incredible contortions to preserve a single indirect jump. Even going so far as to combine jumps from separate jump tables — with a series of direct jumps. This seems utterly bewildering behaviour as it specially breaks the performance gain having a jmp \*%eax for each interpreter leg.

-fno-gcse , :


, . , . , — , .. «» . , , DISPATCH , , - . .

threaded . — . .

(subroutined)

goto . — ( subroutined.c). service_routine_t:

typedef void (*service_routine_t)(cpu_t *pcpu, decode_t* pdecode);

:

void sr_Dec(cpu_t *pcpu, decode_t *pdecoded) {
    uint32_t tmp1 = pop(pcpu);
    BAIL_ON_ERROR();
    push(pcpu, tmp1-1);
 }

service_routines[] :


. , .


VTune — :



, subroutined switched. , — . subroutined . «, — !». .

(tailrecursive)

, … — !

tailrecursive.c. subroutined.c .
fetch_decode() DISPATCH():

void sr_Dec(cpu_t *pcpu, decode_t *pdecoded) {
    uint32_t tmp1 = pop(pcpu);
    BAIL_ON_ERROR();
    push(pcpu, tmp1-1);
    ADVANCE_PC();
    *pdecoded = fetch_decode(pcpu);
    DISPATCH();
 }

DISPATCH:

#define DISPATCH() service_routines[pdecoded->opcode](pcpu, pdecoded);

, , . main(), , :

decode_t decoded = fetch_decode(&cpu);
service_routines[decoded.opcode](&cpu, &decoded);

And that's all. . , , , — …
, ?! , , , , . However, this does not happen.
, — . — . . call jmp, .
GCC -foptimize-sibling-calls (, -O1). ( tailrecursive-noopt), , . 90000 :

$ ./tailrecursive-noopt 90000 > /dev/null 
 Segmentation fault (core dumped)

tailrecursive VTune . -, «» fetch(_decode) decode:



, ( ) .

-, , call jmpq. , sr_Swap(), Branch Mispredict:

(binary translation)

, , ( translated.c). : , (). , , translated . , , , , .

. — , POSIX-.

translated Intel 64 (x86_64, AMD64, x64... ), . translate_program() .

«», -. . .

.


, Intel 64. .


cpu_t, , R15. GNU- , -std=gnu11 ( Makefile), — -std=c11.


gen_code . -, . -, (.text), (.data), - . , , . gen_code — .text .


gen_code. longjmp() — goto ( goto ). , , setjmp() c (return_buf).
, . exit_generated_code() , Halted/Break, PC. , , , — longjmp .


, (, Drop), pcpu. (, Je) . , ABI . System V ABI ( Linux) — RDI.



The most difficult block of the program requires detailed consideration. As a result of the work of the guest program prog length len, two arrays must be filled: out_code — the host guest code simulating a sequence of instructions from prog, and an array of entrypoints at the beginning of the individual capsules inside out_code.
Each guest instruction is decoded, and then translated into one or two host instructions. For guest instructions without operands, this is “call rel32”; for instructions with operand, the pair is “mov imm,% rdi; call rel32 ". RDI is here because the called procedures expect to see their argument in it.
rel32 is a 32-bit offset of the address of the function being called with respect to the current instruction. For each new CALL instruction, it is different, so it is calculated each time (offset32) relative to the current position.
Why did I use relative addresses here, not absolute ones? Because the host system uses 64-bit addresses, and to transfer 64 bits to the CALL, one more instruction and one more register would be required. Because of this, the gen_code is placed in the code section - so that all offsets fit into 32 bits. After all, the data section can be placed very far from the code.
Notice that both the template code (mov_template_code and call_template_code) and the subsequent manipulations with them (calls to memcpy ()) depend on the way in which the host instructions are encoded. When porting translated to another architecture, they will have to be fixed first.

The result of the translation of the program Primes, obtained using GDB at the time of the completion of translate_program ():

Once again I note: at the time of the start of the translation of this code did not exist.
Of course, instead of calling them endlessly, it would be better to substitute the bodies of the service procedures themselves in out_code. At the same time, the input and output time in the function would be saved. But I would have to do something with the epilogue prologues of the procedures, i.e. Learn to inline code behind the compiler. I will leave this exercise to readers who want to get deeper into the issues of code generation.

Finally, let's examine what is happening in main ():


First, it is imperative that you allow writing to gen_code. This is done using the mprotect () system call. Then just in case, fill in the gen_code with the whole INT3 single-byte instruction - 0xcc. If something goes wrong when executing the generated code, and the control is transferred to the empty part of the array, an interrupt will occur immediately, which will make debugging easier.
Then we broadcast the program and set the return point with setjmp (). It is here, at the beginning of the while () loop, that execution will be returned.

The while loop will each time transfer control using the values ​​from the display of the entrypoints for the current PC as the address. Perhaps the question arose - why bother exiting gen_code before the generated code ends?

Pay your attention once again to the listing of gen_code above. There is no branch instruction in it - all MOV and CALL will be executed sequentially. However, the original program had cycles!
The translation of the guest transition instructions is a difficult point: the displacements of the addresses of the guest code are generally non-linearly related to the displacements between the capsules of the master code. I circumvented this difficulty using the following trick. All service procedures that change the PC in a non-linear manner (ie, Jump, JE, JNE) are required to call exit_generated_code (). And already the external code, using the saved values ​​in the entrypoints, will re-enter the guest code at the correct address. For the rest, "normal" service procedures, longjmp is not needed - they just fall through to the next procedure code.

I have an idea how to do without longjmp inside the procedures for JNE, JE and Jump. You can find the next entry point from entrypoints right inside the procedure, and put the additional value of the return address of the RIP on the stack so that when you exit the current procedure, you will not be in the function that called it, but immediately in the desired procedure! Another exercise for the inquisitive reader is to implement this idea.

Bottlenecks have changed. Now VTune has designated the main problem “Front End Bound”:


At the top of the list are service procedures, which can be considered to some extent a success:


Note that for a dynamically generated code, VTune is not expected to associate character information. However, this tool provides the JIT Profiling API , which allows you to mark the entry and exit to the regions of the generated code. translated does not use it, but it would obviously be useful for serious profiling.

Who is measuring

For test runs, the old, but still smart Lenovo Thinkpad X220i notebook was used.

• OS: Ubuntu 12.04.5 LTS, Linux version 3.2.0-75-generic x86_64
• Processor: Intel® Core (TM) i3-2310M CPU @ 2.10GHz
• 4 GB of RAM

Compilers:

• GCC 4.8.1-2ubuntu1 ~ 12.04
• ICC 15.0.3 20150407

Compare options for programs.

• switched - switchable interpreter.
• threaded - sewn interpreter.
• predecoded - the pre-decoded switchable interpreter.
• subroutined - the procedural interpreter.
• threaded-cached is a pre-decoded interpreter.
• tailrecursive is a procedural interpreter with optimized tail calls.
• translated - binary translator.
• native is an implementation of the Primes C algorithm. It is not quite fair to compare a static program with implementations of a VM capable of executing arbitrary code. However, in comparison, the native participates to show the potential for possible acceleration.

The experiments were automated using the measure.sh script. For each option, the execution time of the five program runs was measured and the average value was calculated.

For GCC:


predecoded runs only slightly faster than switched. For reasons unknown to me, simple threaded and remained slower switched. But the combination of pre-decoding with threaded code, threaded-cached, gave a noticeable increase. The procedural interpreter subroutined and procedural with tail optimizations tailrecursive have shown themselves remarkably well. It was also expected that the translated bypassed all the interpreters.

For ICC:


These results are even stranger. Absolutely the worst result showed threaded, despite all my efforts. predecoded, on the contrary, is so fast that I had doubts about the correctness of its execution. However, additional checks and repeated measurements found no problems. threaded-cached bypassed procedural options in speed, almost equaling translated, which, in turn, is not the fastest.

I note that the ICC did not understand my attempts to help with the generation of the code for the sewn variants, since not all the GCC options he understands:

 icc -std = c11 -O2 -Wextra -Werror -gdwarf-3 -fno-gcse -fno-thread-jumps -fno-cse-follow-jumps -fno-crossjumping -fno-cse-skip-blocks -fomit-frame- pointer threaded-cached.c -o threaded-cached
 icc: command line warning # 10006: ignoring unknown option '-fno-gcse'
 icc: command line warning # 10006: ignoring unknown option '-fno-thread-jumps'
 icc: command line warning # 10006: ignoring unknown option '-fno-cse-follow-jumps'
 icc: command line warning # 10006: ignoring unknown option '-fno-crossjumping'
 icc: command line warning # 10006: ignoring unknown option '-fno-cse-skip-blocks'

Of course, it would be very interesting to study the causes of anomalies found on ICC assemblies. But the article and without it swelled to indecent size, so let me postpone this analysis for the next time.

Conclusion

As expected, various interpreter construction techniques vary in speed. However, it is impossible to advance, only from the structure of the VM code, to draw conclusions about which of the options will be faster in practice. Moreover, various techniques can be combined, but the effects that arise in this case are not cumulative: see how performance changes when using only pre-decoding or sewn code, and what effect is obtained from their sharing.
A significant, and not always positive, role is played by the compiler. Depending on the optimizations applied by them, a very simple interpretation scheme can show itself well, but a super-elaborated one will end up in the tail of the list.
The article is written, my conscience is clear to myself, it's time to go on vacation. Thanks for attention!

Literature

1. Baranov S. N., Nozdrunov N. R. Language Fort and its implementation. 1988 Mechanical Engineering Publishing House 2.1. Sewn code and its versions www.netlib.narod.ru/library/book0001/ch02_01.htm
2. M. Anton Ertl. 2007. Speed ​​of various interpreter dispatch techniques V2 www.complang.tuwien.ac.at/forth/threading
3. James E. Smith and Ravi Nair. Virtual machines - Versatile Platforms for Systems and Processes. Elsevier, 2005. ISBN 978-1-55860-910-5.
4. M. Anton Ertl and David Gregg. Efficient interpreters // Journal of Instruction-Level Parallelism 5 (2003), pp. 1-25. www.jilp.org/vol5/v5paper12.pdf
5. Terrence Parr. Language Implementation Patterns - The Pragmatic Bookshelf, 2010. ISBN-10: 1-934356-45-X ISBN-13: 978-1-934356-45-6