Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Write Your Own Virtual Machine

justinmeiners.github.io

Post reply on HN
Print view View original

1–10 of 79 posts

Re: Write Your Own Virtual Machine

#2

Post by chrisaycock »

One of my favorite techniques for implementing VMs is the "computed goto":

https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...

Consider this example for dispatching instructions from the article:

    while (running)
    {
        uint16_t op = mem_read(reg[R_PC]++) >> 12;
        
        switch (op)
        {
            case OP_ADD:
                {ADD, 6}
                break;
            case OP_AND:
                {AND, 7}
                break;
            case OP_NOT:
                {NOT, 7}
                break;
            case OP_BR:
                {BR, 7}
                break;
            ...
        }
    }
That code has a lot of branching. The switch statement has to jump to the corresponding case, the break statement branches to the bottom, and then there is third branch to get back to the top of the while loop. Three branches just to hit one instruction.

Now imagine we had written the above as:

    static void* dispatch_table[] = { &&OP_ADD, &&OP_AND, &&OP_NOT, &&OP_BR,
                                      ... };
    #define DISPATCH() goto *dispatch_table[memory[reg[R_PC]++] >> 12]

    DISPATCH();

    OP_ADD:
        {ADD, 6}
        DISPATCH();
    OP_AND:
        {AND, 7}
        DISPATCH();
    OP_NOT:
        {NOT, 7}
        DISPATCH();
    OP_BR:
        {BR, 7}
        DISPATCH();
    ...
Now there is only one branch per instruction. The handler for each instruction directly jumps to the next location via the goto. There is no need to be in an explicit loop because the interpreter runs until it hits a halting instruction.

Many VMs now use this technique, including the canonical Ruby and Python interpreters.

Re: Write Your Own Virtual Machine

#3

Post by sgillen »

chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

Do you know if an optimizing compiler will ever make this transformation?

Re: Write Your Own Virtual Machine

#4

Post by chc4 »

sgillen wrote: post #3
chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

Do you know if an optimizing compiler will ever make this transformation?

Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax8]` and the other is `mov edx, [ecx+eax8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.

Re: Write Your Own Virtual Machine

#5

Post by banachtarski »

sgillen wrote: post #3
chrisaycock wrote: post #2

One of my favorite techniques for implementing VMs is the "computed goto": https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Consider this example for dispatching instructions from the article: while (running) { uint16_t op = mem_read(reg[R_PC]++) >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; ... } } That code has a…

Do you know if an optimizing compiler will ever make this transformation?

Oh psh optimizing compilers go way beyond this. In fact, even hand implemented VMs also generally go further. The technique above is called tail dispatch and is really just the beginning.

Re: Write Your Own Virtual Machine

#6

Post by toolslive »

banachtarski wrote: post #5
sgillen wrote: post #3

Earlier quoted context omitted.

Do you know if an optimizing compiler will ever make this transformation?

Oh psh optimizing compilers go way beyond this. In fact, even hand implemented VMs also generally go further. The technique above is called tail dispatch and is really just the beginning.

indeed. I think the second optimization on the list is super-instructions: frequent combinations of 2 (or even 3) instructions are transformed into 1 equivalent instruction, lowering the average cycle count.

Re: Write Your Own Virtual Machine

#7

Post by techno_modus »

I like this tutorial but it should be mentioned that before implementing a virtual machine one should understand that there are many computing models and many alternative mechanisms within each of them. Implementing VM for sequential program execution is relatively easy. What is more (conceptually) difficult is concurrency, asynchronous processes etc.

Re: Write Your Own Virtual Machine

#8

Post by vardump »

chc4 wrote: post #4
sgillen wrote: post #3

Earlier quoted context omitted.

Do you know if an optimizing compiler will ever make this transformation?

Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax 8]` and the other is `mov edx, [ecx+eax 8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.

HN formatting ate some * from the parent post:

  jmp [ecx+eax * 8]

  and the other is

  mov edx, [ecx+eax * 8]; 
  jmp edx
> The later is faster because of weird branch prediction reasons...

Things like that are microarchitecture dependent. Might be true on particular CPUs.

Of course it's possible separate MOV could be executed much earlier in the out of order pipeline while JMP effective address calculation might not. So JMP address (edx) would be already resolved by the time JMP is actually executing.

Re: Write Your Own Virtual Machine

#9

Post by dawkins »

chc4 wrote: post #4
sgillen wrote: post #3

Earlier quoted context omitted.

Do you know if an optimizing compiler will ever make this transformation?

Every single C compiler worth mentioning will turn a switch statement into a jump table. The difference between a jump table and computed goto is only that one is `jmp [ecx+eax 8]` and the other is `mov edx, [ecx+eax 8]; jmp edx`. The later is faster because of weird branch prediction reasons, and no bounds checks in the switch.

Do you know if the Go compiler does this too?

Edit: Nevermind, it doesn't: https://github.com/golang/go/issues/5496

Post reply on HN