> 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?

> 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_threadi...

[2] 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

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?

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.

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.