I was noodling around with a couple different VM implementations
and thought I would ask other people if they were doing the same.
It would be nice to divide and conquer the exploration of different
implementations.
I looked into 3 different dispatching techniques. Here's the list
with timings on a 600 MHz Pentium III running Linux and gcc 2.95:
-g -O
Switch/case 6.0 sec 2.0 sec
Computed goto (gcc feature) 6.1 sec 1.4 sec
Function call 11.9 sec 11.8 sec
Both the switch and goto implementations put all the opcodes into
a single function body and just bounce around inside the function.
The function call implementation runs something similar to perl 5's
tiny while loop dispatcher with each opcode implemented as a
separate function.
The timings above were collected for more than 200 million VM
instructions. That's a lot faster than what I was expecting -- and
makes me wonder whether we need to do something platform-specific
like a TIL to improve performance. My testing code is way too small
to indicate problems with data cache vs. instruction cache, but I
suspect that that issue is the only issue that will really drive
us towards a TIL implementation.
I'll put together a TIL (Intel -- same machine as above) for my toy
VM and run some timings. If anybody else has already done this
please let us know!
I'll also try to expand my toy VM to something a little more
practical so we can start to see memory delays. Again, if anybody
has done work in this area, I'm sure everybody on the list would
love to hear about it. A VM with "registers" might be really
interesting too -- especially in a computed goto or TIL machine.
The code is given as a MIME attachment. BTW, are MIME attachments
ok on the list? I strongly prefer plain-text, but for attachments
there aren't many good alternatives.
- Ken
1 0
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
1 10
2
/* This code is in the public domain. Ken Fox, Oct 2000 */
#define USE_GOTO
#include <stdlib.h>
#include <stdio.h>
typedef union {
int i;
void *p;
} cell;
void load(char *filename, cell *code)
{
FILE *input;
cell *pc = code;
if (input = fopen(filename, "r")) {
int i;
while (fscanf(input, " %d ", &i) != EOF) {
pc->i = i;
++pc;
}
fclose(input);
}
pc->i = 0;
}
void dump(cell *code)
{
cell *pc = code;
printf("byte code:\n");
while (pc->i) {
printf(" %5d\n", pc->i);
++pc;
}
}
enum {
STOP = 0,
PUSH = 1,
ADD = 2,
PRINT = 3
};
int count_ops(cell *code)
{
int icount = 0;
cell *pc = code;
op: switch (pc->i) {
case STOP:
return icount;
case PUSH:
++icount;
pc += 2;
goto op;
case ADD:
++icount;
pc += 1;
goto op;
case PRINT:
++icount;
pc += 1;
goto op;
}
}
void fixup(cell *code, void *ops[])
{
cell *pc = code;
op: switch (pc->i) {
case STOP:
pc->p = ops[pc->i];
return;
case PUSH:
pc->p = ops[pc->i];
pc += 2;
goto op;
case ADD:
pc->p = ops[pc->i];
pc += 1;
goto op;
case PRINT:
pc->p = ops[pc->i];
pc += 1;
goto op;
}
}
#ifdef USE_SWITCH
void execute(cell *code)
{
static int stack[1000];
cell *pc = code;
int *sp = stack;
int x, y;
op: switch (pc++->i) {
case STOP:
return;
case PUSH:
*sp++ = pc++->i;
goto op;
case ADD:
y = *--sp;
x = *--sp;
*sp++ = x + y;
goto op;
case PRINT:
printf("--> %d\n", *--sp);
goto op;
}
}
#else
#ifdef USE_FUNCALL
typedef void *(*op)();
cell *pc;
int *sp;
void *op_stop()
{
return 0;
}
void *op_push()
{
*sp++ = pc[1].i;
return pc + 2;
}
void *op_add()
{
int y = *--sp;
int x = *--sp;
*sp++ = x + y;
return pc + 1;
}
void *op_print()
{
printf("--> %d\n", *--sp);
return pc + 1;
}
void execute(cell *code)
{
static void *ops[] = { op_stop, op_push, op_add, op_print };
static int stack[1000];
if (code->i > 0 && code->i < 255) {
fixup(code, ops);
}
pc = code;
sp = stack;
while (pc = ((op)(pc->p))())
;
}
#else
#ifdef USE_GOTO
void execute(cell *code)
{
static void *ops[] = { &&op_stop, &&op_push, &&op_add, &&op_print };
static int stack[1000];
cell *pc = code;
int *sp = stack;
int x, y;
if (code->i > 0 && code->i < 255) {
fixup(code, ops);
}
goto *((pc++)->p);
op_stop:
return;
op_push:
*sp++ = pc++->i;
goto *((pc++)->p);
op_add:
y = *--sp;
x = *--sp;
*sp++ = x + y;
goto *((pc++)->p);
op_print:
printf("--> %d\n", *--sp);
goto *((pc++)->p);
}
#endif
#endif
#endif
int main(int argc, char *argv[])
{
static cell code[10000];
int n;
if (argc != 2) {
printf("vm-test [byte-code-file]\n");
return 1;
}
load(argv[1], code);
printf("executing %d ops.\n", 100000 * count_ops(code));
for (n = 0; n < 100000; ++n) {
execute(code);
}
return 0;
}
