4 ms·

The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytec

by sklogic 11y ago

The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytecode into a threaded code. A difference in performance between these two is huge.

loup-vaillant 11y ago
> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand. But what does it mean for the bytecode itself to be compiled into a threaded form?
- sklogic 11y ago
  > Wait a minute, how is that even possible? Or rather, what do you mean? It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example. See the definition of the "Next" macro in interp.c [2] for details. [1] https://en.wikipedia.org/wiki/Threaded_code#Indirect_threading https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi... [2] https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c EDIT: if you wonder where the actual threading is done, see https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c
  - 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 ago
      Exactly, 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 ago
        I 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.

by sklogic 11y ago

loup-vaillant 11y ago

> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand. But what does it mean for the bytecode itself to be compiled into a threaded form?

sklogic 11y ago
> Wait a minute, how is that even possible? Or rather, what do you mean? It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example. See the definition of the "Next" macro in interp.c [2] for details. [1] https://en.wikipedia.org/wiki/Threaded_code#Indirect_threading https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi... [2] https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c EDIT: if you wonder where the actual threading is done, see https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c
- 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 ago
    Exactly, 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 ago
      I 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.