11 ms·
A bitecode interpreter is another place where it's nice to have gotos. Here's the base code without gotos: typedef enum { ADD, MUL, ..., END } opcode; vo
by frivoal 11y ago
A bitecode interpreter is another place where it's nice to have gotos.
Here's the base code without gotos:
typedef enum { ADD, MUL, ..., END } opcode;
void run() {
opcode ins;
while (1) {
ins = fetch_next_inst();
switch (ins) {
case ADD:
perform_addition();
break;
case MUL:
perform_multiplication();
break;
...
case END:
wrap_up();
return;
}
}
}
You have 3 jumps on each loop. From the break to the end of the loop, then from the end to the top, and one from the switch to the right case. The first one might be optimized away, but let's remove it explicitly.
typedef enum { ADD, MUL, ..., END } opcode;
void run() {
opcode ins;
start:
ins = fetch_next_inst();
switch (ins) {
case ADD:
perform_addition();
goto start;
case MUL:
perform_multiplication();
goto start;
...
case END:
wrap_up();
return;
}
}
Assuming a non lousy compiler, we haven't improved anything yet. But now the fun starts. We can go down to one jump for each iteration.
typedef enum { ADD, MUL, ..., END } opcode;
#define NEXT() \
do { \
ins = fetch_next_inst(); \
goto *jump_table[ins]; \
} while(0)
void run() {
opcode ins;
static void *jump_table[] = { &&add_l, &&mul_l, ..., &&end_l };
NEXT();
add_l:
perform_addition();
NEXT();
mul_l:
perform_multiplication();
NEXT();
...
end_l:
wrap_up();
return;
}
Voila! a single jump every time around. Now, depending on what kind of architecture you're running on, the size of the cache, etc, this may or may not be faster.
Granted, this is not the kind of code you write everyday. But sometimes speed matters, and good luck writing this without gotos.
- zem 11y ago~20 years of using various combinations of C and C++, and i never knew you could take the address of a label! reminds me of computed GOSUBs from my basic days :)
- frivoal 11y agoAnd they say C is a simple language... :) To be fair, I've seen code like this exactly once.
- jcoffland 11y agoWho says that?
- tjradcliffe 11y agoThey say C is a low level language. That is not the same as simple.
- banthar 11y agoYou can't. This is a GCC extension: https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
- arcticbull 11y agoThere is actually a neat feature where you can take the address of the thing you're assigning in a static context: static void* address = &address; This is helpful for things that take void* context pointers that you want to match with logical equality.
- jacquesm 11y agoBefore you use such constructs make sure your team lead or boss is ok with it, it's incompatible with many compilers and ugly to boot. This is the kind of code that gives C its bad reputation.
- sklogic 11y agoThis is the kind of code which makes OCaml the fastest bytecode interpreter out there, and selection between an ad hoc switch and a comuted goto is done transparently with a single ifdef.
- jacquesm 11y agoYes, there may be exceptions when this kind of code is preferable. But it's definitely not the rule and the speed difference between the one and the other is so small that only a profiler can guide you to optimizations like these.
- sklogic 11y ago> Yes, there may be exceptions when this kind of code is preferable. In my practice these exceptions are ubiquitous. Multiple tiny interpreted DSLs (which cannot be compiled more efficiently for the latency reasons), efficient protocols, all that stuff. System programming, in other words, and it's exactly the stuff Rust was supposed to be designed for. > But it's definitely not the rule and the speed difference between the one and the other is so small 2-4 times difference is not "small" in system-level programming.
- jacquesm 11y ago2-4 times is a spectacular speed-up, of course the inner loop of an interpreter is important but you're implying the rest of the code-path is only 3-4 instructions long (otherwise you can't get that kind of speed-up) which I find hard to believe. Even the inner loop of an interpreter usually calls routines that are longer than the inner loop itself. Is there a particular benchmark you have in mind for that 2-4 number?
- api 11y agoThat's pretty nifty, but it seems like something a really good compiler could achieve automatically. Of course I'm not sure if any compilers actually are that good.
- frivoal 11y agoThis is a fairly mechanical conversion, so suppose a sufficiently smart compiler could do that. But assuming a sufficiently smart compiler when you depend on your code being fast tends to cause issues. Especially if you expect it to run on a bunch of platforms with compilers of varying qualities. Last time I saw code last this, we certainly couldn't rely on compilers being particularly smart, and we did care about speed.
- Redoubts 11y agoWell, this is what is going into Python 2.7.11 for a 15% speed up, so apparently compilers aren't that good yet. https://lwn.net/Articles/646888/ https://lwn.net/Articles/646888/
- sklogic 11y agoThis is not exactly how fast bytecode interpreters are implemented. There is one next step - pre-caching the jump table straight into the bytecode. And there is absolutely no way compiler can transform your ad hoc switch-based interpreter into a threaded code interpreter automatically - it is not allowed to rewrite your data willy-nilly.
- frivoal 11y agoHadn't thought of that, but it sounds interesting. I guess this means that opcodes in your bytecode need to be large enough to store a pointer, this could involve some tradeoffs in terms of minimizing instructions vs fitting in the cache, but I suppose it could fall on the right side of things often enough.
- sklogic 11y ago32-bit opcodes are ok, even on 64-bit architectures, if you add a constant offset - see how it's done in OCaml.
- deleted 11y ago[deleted]
- sklogic 11y agoThere is one next step - eliminate jump_table and rewrite your bytecode before executing it, replacing opcodes with the jump addresses.
- deleted 11y ago[deleted]
- unholiness 11y agoOkay, but a much more readable and maintainable way to achieve this same optimization is with function pointers. In your example: void (*[10])() function_table = { &perform_addition, &perform_multiplication, ... } while(1) { ins = fetch_next_inst(); *(function_table[ins])(); } Edit: Seeing it written like this now, it's clear you could save yet another jump by defining a macro for what's in the while loop and putting it at the end of every function call.
- TheLoneWolfling 11y agoThat's an additional pointer-chase per loop. And more function prefix / suffix work. In actuality, I suspect that it'd be optimized out - but you cannot say "you cannot do X because it relies on compiler optimizations" and replace that with Y that relies on compiler optimizations.
- unholiness 11y agoA function call is nothing more than putting your return address and parameters on the stack and jumping to the address of the function. By referring directly to the function's address, there's no "additional pointer chase", since calling the function already does exactly that. If you were to inline all of the perform functions in the GOTO version vs putting a macro at the end of each function, you're right that there's some function overhead, but I think it's as small as a single instruction to put the return address on the stack. Maybe that would be optimized away, maybe not. To your point: My argument isn't that you can't do the GOTO version. With optimizations, it's essentially identical. My point is, that is a lot more hard-to-grok code to maintain for something that can be achieved in a simpler way.
- TheLoneWolfling 11y agoYou're forgetting the overhead of popping / pushing registers. Both in terms of direct instruction overhead, and indirectly through code size and working set bloat. Which, especially for smaller functions, can be significant. It's one of the problems with a register-oriented architecture. Sometimes this can be optimized away, but not always.
- jacquesm 11y agoI really dislike 'clever' code like this, even when speed is paramount you will find that by obscuring the flow you make it harder, not easier to really optimize the code. Over time it tends to evolve into ever messier and harder to understand versions of the initial run after which a future maintainer will end up losing sleep and or hair chasing some production bug. Consider this (slower!) much clearer alternative, and consider too that if you need to eliminate one goto for speed reasons that you're most likely doing something wrong: typedef enum { ADD, MUL, ..., END } opcode; int process_instruction(opcode ins) { switch (ins) { case ADD: perform_addition(); break; case MUL: perform_multiplication(); break; ... case END: return FALSE; } return TRUE; } void run() { do { } while (process_instruction(fetch_next_instruction()); wrap_up(); } That's a whole function call overhead (but you can eliminate that with an 'inline'), it's easier to test and much easier to follow what it does. It would be interesting to see what the actual difference is in speed when comparing those two versions, I suspect that the contents of 'perform_addition' and 'perform_multiplication' are going to be the key here, not whether or not the loop uses a short-cut or an instruction (or two) less. Oh, and you could have eliminated that 'ins' variable.
- obastani 11y agoI imagine that if you have more instructions (a few hundred) the overhead of the switch starts to become significant. At 256 opcodes you need 8 jumps, and hence 8 CPU cycles. That's non-trivial, especially if most of the opcodes can be implemented more quickly than this. For example, a quick Google search says that for an Intel CPU, addition is 1 cycle and multiplication is 3 cycles.
- jacquesm 11y agoSwitches over enums are usually compiled to jump tables. What you see in source and what you get after the optimizer is done with it are sometimes very far apart. Looking at the output of gcc -S can be very enlightening at various levels of optimization.
- deleted 11y ago