Skip to content

Instantly share code, notes, and snippets.

@benhoyt
Last active Dec 16, 2021
Embed
What would you like to do?
See how fast we can make direct-threaded code in C (using computed goto)
static void* prog[] = {
- // loop:
&&i_pushvar0, // pushvar i
&&i_pushnum, (void*)100000000, // pushnum 100000000
&&i_jge, (void*)5, // jge end
+ // loop:
&&i_pushvar0, // push i
&&i_addvar1, // addvar s
&&i_incvar0, // incvar i
- &&i_jmp, (void*)((long long)-10), // jmp loop
+ &&i_pushvar0, // pushvar i
+ &&i_pushnum, (void*)100000000, // pushnum 100000000
+ &&i_jl, (void*)((long long)-8), // jl loop
// end:
/*
$ time awk 'BEGIN { for (; i<100000000; i++) s+=i; print s }'
4999999950000000
real 0m6.141s
user 0m6.140s
sys 0m0.000s
gcc -O2 vm-direct.c && time ./a.out
original: 0.635s
superinstruction "jge" instead of "less jz": 0.596s
pushvar0, pushvar1, addvar1, incvar0: 0.546s
(moving literals to nums array: same as above -- reverted!)
(tos variable: 0.756 -- reverted!)
repeat while condition: 0.455s
*/
#include <stdio.h>
#include <stdlib.h>
// #define NEXT printf("ip=%ld i=%lld s=%lld stack=[%lld %lld %lld %lld] sp=%ld\n", ip-prog, vars[0], vars[1], stack[0], stack[1], stack[2], stack[3], sp-stack); goto **ip++
#define NEXT goto **ip++
#define FETCH() (long long)(unsigned long long)(*ip++)
#define POP() (*sp++)
#define PUSH(x) *--sp = x
int main() {
static void* prog[] = {
&&i_pushvar0, // pushvar i
&&i_pushnum, (void*)100000000, // pushnum 100000000
&&i_jge, (void*)5, // jge end
// loop:
&&i_pushvar0, // push i
&&i_addvar1, // addvar s
&&i_incvar0, // incvar i
&&i_pushvar0, // pushvar i
&&i_pushnum, (void*)100000000, // pushnum 100000000
&&i_jl, (void*)((long long)-8), // jl loop
// end:
&&i_pushvar1, // pushvar s
&&i_printnum, // printnum
&&i_exit, // exit
};
void** ip = prog;
long long vars[2] = {0, 0};
long long stack[4] = {0, 0, 0, 0};
long long* sp = &stack[4];
NEXT;
i_pushvar0: {
PUSH(vars[0]);
NEXT;
}
i_pushvar1: {
PUSH(vars[1]);
NEXT;
}
i_pushnum: {
long long a = FETCH();
PUSH(a);
NEXT;
}
i_jge: { // ( a b -- )
long long b = POP();
long long a = POP();
long long offset = FETCH();
if (a >= b) {
ip += offset;
}
NEXT;
}
i_jl: { // ( a b -- )
long long b = POP();
long long a = POP();
long long offset = FETCH();
if (a < b) {
ip += offset;
}
NEXT;
}
i_jmp: {
long long offset = FETCH();
ip += offset;
NEXT;
}
i_addvar1: {
vars[1] += POP();
NEXT;
}
i_incvar0: {
vars[0]++;
NEXT;
}
i_printnum: {
long long x = *sp++;
printf("%lld\n", x);
NEXT;
}
i_exit: {
exit(0);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment