Skip to content

Instantly share code, notes, and snippets.

@mmozeiko mmozeiko/test.c
Last active Jun 4, 2019

Embed
What would you like to do?
switch vs computed goto
#include <stdint.h>
#include <stdio.h>
#include <time.h>
#define HALT 0
#define LOAD 1
#define INC 2
#define DEC 3
#define ADD_7 4
#define SUB_7 5
#define MUL_100 6
#define DIV_100 7
#define NEG 8
#define JNZ 9
void execute_goto(uint8_t* data)
{
static void** opcodes[] = {
&&OP_HALT, &&OP_LOAD, &&OP_INC, &&OP_DEC,
&&OP_ADD_7, &&OP_SUB_7, &&OP_MUL_100, &&OP_DIV_100,
&&OP_NEG, &&OP_JNZ,
};
// this line prevent compiler to evaluate this function at compile time
volatile size_t zero = 0;
size_t ip = zero;
int x = 0;
goto *opcodes[data[ip++]];
OP_HALT:
return;
OP_LOAD:
x = data[ip++];
goto *opcodes[data[ip++]];
OP_INC:
++x;
goto *opcodes[data[ip++]];
OP_DEC:
--x;
goto *opcodes[data[ip++]];
OP_ADD_7:
x+=7;
goto *opcodes[data[ip++]];
OP_SUB_7:
x-=7;
goto *opcodes[data[ip++]];
OP_MUL_100:
x*=100;
goto *opcodes[data[ip++]];
OP_DIV_100:
x/=100;
goto *opcodes[data[ip++]];
OP_NEG:
x=-x;
goto *opcodes[data[ip++]];
OP_JNZ: {
uint8_t dst = data[ip++];
if (x) ip = dst;
goto *opcodes[data[ip++]];
}
}
void execute_goto_opt(uint8_t* data, int count)
{
static void** opcodes[] = {
&&OP_HALT, &&OP_LOAD, &&OP_INC, &&OP_DEC,
&&OP_ADD_7, &&OP_SUB_7, &&OP_MUL_100, &&OP_DIV_100,
&&OP_NEG, &&OP_JNZ,
};
void* ops[count];
for (int i=0; i<count; i++)
{
switch (data[i])
{
case HALT: ops[i] = &&OP_HALT; break;
case LOAD: ops[i++] = &&OP_LOAD; ops[i] = (void*)(intptr_t)data[i]; break;
case INC: ops[i] = &&OP_INC; break;
case DEC: ops[i] = &&OP_DEC; break;
case ADD_7: ops[i] = &&OP_ADD_7; break;
case SUB_7: ops[i] = &&OP_SUB_7; break;
case MUL_100: ops[i] = &&OP_MUL_100; break;
case DIV_100: ops[i] = &&OP_DIV_100; break;
case NEG: ops[i] = &&OP_NEG; break;
case JNZ: ops[i++] = &&OP_JNZ; ops[i] = (void*)&ops[data[i]]; break;
}
}
// this line prevent compiler to evaluate this function at compile time
void** volatile start = ops;
void** ip = start;
int x = 0;
goto **ip++;
OP_HALT:
return;
OP_LOAD:
x = (intptr_t)(*ip++);
goto **ip++;
OP_INC:
++x;
goto **ip++;
OP_DEC:
--x;
goto **ip++;
OP_ADD_7:
x+=7;
goto **ip++;
OP_SUB_7:
x-=7;
goto **ip++;
OP_MUL_100:
x*=100;
goto **ip++;
OP_DIV_100:
x/=100;
goto **ip++;
OP_NEG:
x=-x;
goto **ip++;
OP_JNZ: {
void* dst = *ip++;
if (x) ip = (void**)dst;
goto **ip++;
}
}
void execute_switch(uint8_t* data)
{
// this line prevent compiler to evaluate this function at compile time
volatile size_t zero = 0;
size_t ip = zero;
int x = 0;
for (;;)
{
switch (data[ip++])
{
case HALT: return;
case LOAD: x = data[ip++]; break;
case INC: ++x; break;
case DEC: --x; break;
case ADD_7: x+=7; break;
case SUB_7: x-=7; break;
case MUL_100: x*=100; break;
case DIV_100: x/=100; break;
case NEG: x=-x; break;
case JNZ: {
uint8_t dst = data[ip++];
if (x) ip = dst;
} break;
default:
__builtin_unreachable();
}
}
}
int main()
{
uint8_t p[10];
p[0] = LOAD;
p[1] = 10;
p[2] = MUL_100; // x = 10^3
p[3] = MUL_100; // x = 10^5
p[4] = MUL_100; // x = 10^7
p[5] = MUL_100; // x = 10^9
p[6] = DEC;
p[7] = JNZ;
p[8] = 6;
p[9] = HALT;
uint64_t start_switch = clock();
execute_switch(p);
uint64_t end_switch = clock();
uint64_t start_goto = clock();
execute_goto(p);
uint64_t end_goto = clock();
uint64_t start_goto_optimized = clock();
execute_goto_opt(p, 10);
uint64_t end_goto_optimized = clock();
uint64_t delta_switch = end_switch - start_switch;
printf("switch = %llu\n", delta_switch);
uint64_t delta_goto = end_goto - start_goto;
printf("goto = %llu\n", delta_goto);
uint64_t delta_goto_optimized = end_goto_optimized - start_goto_optimized;
printf("goto_opt = %llu\n", delta_goto_optimized);
printf("goto improvement = %llu%%\n", (delta_switch - delta_goto) * 100 / delta_switch);
printf("goto_opt improvement = %llu%%\n", (delta_switch - delta_goto_optimized) * 100 / delta_switch);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.