News for hackers. Stuff that matters.
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.