News for hackers. Stuff that matters.
Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:26PM (#9827749)
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.

Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @04:14AM (#9829613)
I 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.

Re:Things Rust shipped without by obastani on Saturday July 04, 2015 @08:41AM (#9829980)
I 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.
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @09:22AM (#9830065)
Switches 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.
Re:Things Rust shipped without by ectoplasm on Sunday July 05, 2015 @01:58AM (#9832633)
Since you asked, there's an assembly comparison on pages 5-6 of http://www.jilp.org/vol5/v5paper12.pdf and a performance comparison on page 12 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.... . Note that the "inline threading" in the second paper is a further optimization that hasn't been brought up here yet.

In summary, the assembly of the goto version is much shorter and there's a 10% speedup over SPEC JVM98. The optimization works out because: a) instruction bodies are often short; b) instruction dispatch is the hottest code path of any interpreter; c) it's orthogonal to all or almost all other optimizations.

Re:Things Rust shipped without by jacquesm on Sunday July 05, 2015 @05:20AM (#9833008)
That's about what I expected, contrary to the 2-4x times speedup mentioned above. Still, I can imagine in isolated cases you really would get a better number than that 10%. So, for code where performance is super important and where the effort of the optimization and lack of transparency is outweighed by the performance boost this makes sense.
Re:Things Rust shipped without by ectoplasm on Sunday July 05, 2015 @05:12PM (#9835012)
Yes, that 10% is an average over seven benchmarks. The numerical one gets a 25% speedup, the one with a bunch of exceptions doesn't benefit at all. The funny thing is, if you're interested in performance, you're probably going to be writing a JIT, so this optimization is really just a stop-gap measure. In fact, the inline threading I mentioned is a kind of cheap JIT: it copies the in-memory executable code from the instructions at these goto labels to form basic blocks in an executable CFG. That gets you 1.6x speedup on those benchmarks, but it's a lot more work.
Re:Things Rust shipped without by jacquesm on Monday July 06, 2015 @06:12AM (#9837992)
> The funny thing is, if you're interested in performance, you're probably going to be writing a JIT, so this optimization is really just a stop-gap measure.

Exactly. And stop-gap measures are fine if and when they're followed up by a proper solution. Unfortunately stop-gap measures tend to be a lot more permanent than originally intended in practice.

Re:Things Rust shipped without by unholiness on Friday July 03, 2015 @10:47PM (#9828935)
Okay, 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.
Re:Things Rust shipped without by TheLoneWolfling on Friday July 03, 2015 @10:52PM (#9828955)
That'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.
Re:Things Rust shipped without by unholiness on Saturday July 04, 2015 @09:45AM (#9830114)
A 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.

Re:Things Rust shipped without by TheLoneWolfling on Saturday July 04, 2015 @06:32PM (#9831804)
You'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.

Re:Things Rust shipped without by zem on Friday July 03, 2015 @04:56PM (#9827911)
~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 :)
Re:Things Rust shipped without by banthar on Friday July 03, 2015 @05:06PM (#9827953)
Re:Things Rust shipped without by arcticbull on Friday July 03, 2015 @05:43PM (#9828111)
There 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.

Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:58PM (#9827919)
And they say C is a simple language... :)

To be fair, I've seen code like this exactly once.

Re:Things Rust shipped without by tjradcliffe on Friday July 03, 2015 @09:13PM (#9828738)
They say C is a low level language. That is not the same as simple.
Re:Things Rust shipped without by jcoffland on Friday July 03, 2015 @05:49PM (#9828131)
Who says that?
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @04:16AM (#9829619)
Before 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.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @06:46AM (#9829818)
This 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.
Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @09:35AM (#9830096)
Yes, 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.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @10:01AM (#9830159)
> 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.

Re:Things Rust shipped without by jacquesm on Saturday July 04, 2015 @10:41AM (#9830283)
2-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?
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @02:25PM (#9831064)
Take a look at the OCaml bytecode interpreter: case bodies are all very small there, so the instruction dispatch time really counts. I got this 2x times difference when comparing this bytecode interpreter built with and without computed goto, but I don't remember any other details at the moment. In my own bytecode interpreters the difference was up to 4x, again, because each bytecode instruction implementation was tiny and trivial (like, move something from one register to another, or perform an arithmetic operation).

> Even the inner loop of an interpreter usually calls routines

These are too high level interpreters for the too dynamic languages, they're beyond any hope in terms of performance, by design. I'm talking about some simpler and better designed things (like OCaml, for example).

Re:Things Rust shipped without by sklogic on Friday July 03, 2015 @06:56PM (#9828356)
There is one next step - eliminate jump_table and rewrite your bytecode before executing it, replacing opcodes with the jump addresses.
Re:Things Rust shipped without by api on Friday July 03, 2015 @04:31PM (#9827780)
That'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.
Re:Things Rust shipped without by sklogic on Friday July 03, 2015 @06:55PM (#9828352)
This 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.
Re:Things Rust shipped without by frivoal on Saturday July 04, 2015 @04:42PM (#9831542)
Hadn'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.
Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @04:53PM (#9831593)
32-bit opcodes are ok, even on 64-bit architectures, if you add a constant offset - see how it's done in OCaml.
Re:Things Rust shipped without by frivoal on Saturday July 04, 2015 @05:59PM (#9831730)
An offset from the first label, or some nearby alignment point? Makes sense.

Do you have a pointer to the relevant part of OCaml's source? The whole thing is probably worth a read, but don't think I can set aside enough time for that soon, and it could take me a while to find the right part.

Re:Things Rust shipped without by sklogic on Saturday July 04, 2015 @06:10PM (#9831762)
Re:Things Rust shipped without by frivoal on Sunday July 05, 2015 @03:06AM (#9832787)
Nice. Simple and efficient. I am going to read more from that code base. Looks like this might be a nice read as well: https://ocaml.org/docs/papers.html#BytecodeCompilerandByteco...
Re:Things Rust shipped without by Redoubts on Friday July 03, 2015 @06:47PM (#9828330)
Well, 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/

Re:Things Rust shipped without by frivoal on Friday July 03, 2015 @04:38PM (#9827822)
This 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.