3 ms·
OK, I'm rephrasing to make sure I understand. In the ordinary, C compliant switch code, you would do this: int instructions[] = { /* bytecode */ }; // ma
by loup-vaillant 11y ago
OK, I'm rephrasing to make sure I understand.
In the ordinary, C compliant switch code, you would do this:
int instructions[] = { /* bytecode */ };
// main loop
int* ip = instructions;
while(1) {
switch (*ip) {
case 1: /* instruction 1 */ break;
case 2: /* instruction 2 */ break;
case 3: /* instruction 3 */ break;
/* etc */
}
ip++; /* goto next instruction. beware jumps */
}
With a jump threaded implementation, you would do this instead:
int instructions[] = { /* bytecode */ };
void jump_table[] = {
&&lbl1,
&&lbl2,
&&lbl3,
/* etc */
};
// main loop
int* ip = instructions;
goto *jump_table[*ip];
lbl1: /* instruction1 */ ip++; goto *jump_table[*ip];
lbl2: /* instruction2 */ ip++; goto *jump_table[*ip];
lbl3: /* instruction3 */ ip++; goto *jump_table[*ip];
/* etc */
Which means, instead of having the compiler constructing a jump table under the hood, I do this myself, and get the benefit of jumping from several locations instead of just one. But I still look up that table. Now the indirect threading you speak of:
int instructions[] = { /* bytecode */ };
void jump_table[] = {
&&lbl1,
&&lbl2,
&&lbl3,
/* etc */
};
// translating bytecode into adresses
void* labels[] = malloc(sizeof(void*) * nb_instructions);
for (uint i = 0; i < nb_instructions; i++)
labels[i] = jump_table[instructions[i]];
// main loop
void** lp = labels;
goto **lp;
lbl1: /* instruction1 */ lp++; goto **lp;
lbl2: /* instruction2 */ lp++; goto **lp;
lbl3: /* instruction3 */ lp++; goto **lp;
/* etc */
If I got that correctly, instead of accessing the jump table at some random place, I only access the label table in a much more linear fashion, saving one indirection and some memory access in the process —this should relieve some pressure off the L1 cache.
Did I get that right?
- sklogic 11y agoExactly, you got it right. One indirection less, and no jump table in the cache. And CPUs are very well optimised for this kind of indirect jumps, because of vtables. There is also one step further - emit the actual jump instructions, making a direct threaded code. It is a bit more complicated and not very portable, but if you want to squeeze all the cycles you can it's still an easy and fast option before resorting to a full-scale compiler.
- ehaliewicz2 11y agoI think direct threading is usually implemented just by reducing the indirection another level, e.g. goto *lp rather than goto **lp You could implement an interpreter with generated JMP instructions, which might be called direct-threading, but at least in the forth world, where most jumps are to nested user-defined subroutines, subroutine-threading using JSR instructions is typically used.