3

Context


My question is twofold (really two questions) but quite basic*. But first, I will show some relevant code for some context. For the TL;DR 'meat and potatoes', skip to the bottom for the actual questions.

*(I'm assuming answerers are aware of what is happening/how a virtual machine operates fundamentally before attempting to answer).

As mentioned, I am writing a (toy) VM, which executes a custom byte code instruction set.

(ellipses here only represent omission of some cases)

Here is a snippet of my code:

for (ip = 0; (ip < _PROGRAM_SIZE || !cstackempty); ip++) {
        if (breakPending) { break; }

            switch (_instr) {

               case INST::PUSH: {
                   AssertAbort(wontoverflow(1), "Stack overflow (1 byte)");
                   cmd_ "PUSH";
                   push(_incbyte);
                   printStack();
                   break;
               }

        ...
               case INST::ADD: {
                   AssertAbort(stackhas(2), "Can't pop stack to add 2 bytes. Stack does not contain 2 bytes");
                   cmd_ "ADD";
                   byte popped8_a = pop();
                   byte popped8_b = pop();
                   byte result = popped8_a + popped8_b;
                   push(result);
                   cmd_ " "; cmd_(byte)result;
                   printStack();
                   break;
               }

               case INST::ADD16: {
                   AssertAbort(stackhas(4), "Can't pop stack to add 4 bytes. Stack does not contain 4 bytes");
                   cmd_ "ADD16";
                   u16 popped16_a = pop16();
                   u16 popped16_b = pop16();
                   u16 result = popped16_a + popped16_b;
                   push16(result);
                   cmd << " "; cmd << (u16)result;
                   printStack();
                   break;
               }
        ...
            }
}

Only because it's relevant, I will mention that _cstack is the call stack, hence the !cstackempty macro, which checks in case the call is empty before calling quits (exiting the for loop) just because it's the last instruction being executed (because that last instruction could we be part of a function, or even a return). Also, ip (instruction pointer) is simply an unsigned long long (u64), as is _PROGRAM_SIZE (size of program in bytes). instr is a byte and is a reference to the current instruction (1 byte).


Meat and potatoes

Question 1: Since I'm initialising two new integers of variable size per block/case (segmented into blocks to avoid redeclaration errors and such), would declaring them above the for loop be helpful in terms of speed, assignment latency, program size etc?

Question 2: Would continue be faster than break in this case, and is there any faster way to execute such a conditional loop, such as some kind of goto-pointer-to-label like in this post, that is implementation agnostic, or somehow avoid the cost of either continue or break?

To summarize, my priorities are speed, then memory costs (speed, efficiency), then file size (of the VM).

4
  • 1
    For your Question 1, you should keep the declarations in the for loop. Having a smaller scope lets registers be managed more efficiently.
    – llllvvuu
    Feb 18, 2016 at 19:33
  • @LawrenceWu Thanks! Now I know to keep them there :) , but I'll leave it in the question to get some other opinions etc.
    – SolaGratia
    Feb 18, 2016 at 19:57
  • I realize now that the answer I gave had really nothing to do with your question. I must have gotten totally sleepy. Sorry!
    – Paulo1205
    Feb 18, 2016 at 20:46
  • @Paulo1205 You have nothing to apologise for :) Thanks for your time!
    – SolaGratia
    Feb 18, 2016 at 20:48

2 Answers 2

3

Before answering the specific questions, a note: There isn't any CPU that executes C++ directly. So any question of this type of micro-optimization at the language level depends heavily on the compiler, software runtime environment and target hardware. It is entirely possible that one technique works better on the compiler you are using today, but worse on the one you use tomorrow. Similarly for hardware choices such as CPU architecture.

The only way to get a definitive answer of which is better is to benchmark it in a realistic situation, and often the only way to understand the benchmark results is to dive into the generated assembly. If this kind of optimization is important to you, consider learning a bit about the assembly language for your development architecture.

Given that, I'll pick a specific compiler (gcc) and a common architecture (x86) and answer in that context. The details will differ slightly for other choices, but I expect the broad strokes to be similar for any decent compiler and hardware combination.

Question 1

The place of declaration doesn't matter. The declaration itself, doesn't even really turn into code - it's only the definition and use that generate code.

For example, consider the two variants of a simple loop below (the external sink() method is just there to avoid optimizing way the assignment to a):

Declaration Inside Loop

int func(int* num) {
  for (unsigned int i=0; i<100; i++) {
    int a = *num + *num;
    sink(a);
    sink(a);
  }
}

Declaration Outside Loop

int func(int* num) {
  int a;
  for (unsigned int i=0; i<100; i++) {
    a = *num + *num;
    sink(a);
    sink(a);
  }
}

We can use the godbolt compiler explorer to easily check the assembly generated for the first and second variants. They are identical - here's the loop:

.L2:
        mov     ebp, DWORD PTR [r12]
        add     ebx, 1
        add     ebp, ebp
        mov     edi, ebp
        call    sink(int)
        mov     edi, ebp
        call    sink(int)
        cmp     ebx, 100
        jne     .L2

Basically the declaration doesn't produce any code - only the assignment does.

Question 2

Here it is key to note that at the hardware level, there aren't instructions like "break" or "continue". You really only have jumps, either conditional or not, which are basically gotos. Both break and continue will be translated to jumps. In your case, a break inside a switch, where the break is the last statement in the loop, and a continue inside the switch have exactly the same effect, so I expect them to be compiled identically, but let's check.

Let's use this test case:

int func(unsigned int num, int iters) {
  for (; iters > 0; iters--) {
    switch (num) {
      case 0:
        sinka();
        break;
      case 1:
        sinkb();
        break;
      case 2:
        sinkc();
        break;
      case 3:
        sinkd();
        break;
      case 4:
        sinkd();
        break;
    }
  }
}

It uses the break to exist the case. Here's the godbolt output on gcc 4.4.7 for x86, ignoring the function prologue:

.L13:
        cmp     ebp, 4
        ja      .L3
        jmp     [QWORD PTR [r13+r12*8]] # indirect jump
.L9:
        .quad   .L4
        .quad   .L5
        .quad   .L6
        .quad   .L7
        .quad   .L8
.L4:
        call    sinka()
        jmp     .L3
.L5:
        call    sinkb()
        jmp     .L3
.L6
        call    sinkc()
        jmp     .L3
.L7
        call    sinkd()
        jmp     .L3
.L8
        call    sinkd()
.L3:
        sub     ebx, 1
        test    ebx, ebx
        jg      .L13

Here, the compile has chosen a jump table approach. The value of num is used to look up a jump address (the table is the series of .quad directives), and then an indirect jump is made to one of the label L4 through L8. The breaks change into jmp .L3, which executes the loop logic.

Note that a jump table isn't the only way to compile a switch - if I used 4 or less case statements, the compile instead chose a series of branches.

Let's try the same example, but with each break replaced with a continue:

int func(unsigned int num, int iters) {
  for (; iters > 0; iters--) {
    switch (num) {
      case 0:
        sinka();
        continue;
... [16 lines omitted] ...
    }
  }
}

As you might have guessed by now, the results are identical - at for this particular compiler and target. The continue statements and break statements imply the exact same control flow, so I'd expect this to be true for most decent compilers with optimization turned on.

6
  • Fantastic! Exactly what I was after. Your effort hasn't gone unnoticed. Here, have a chocolate chip cookie :) +1 for the assembler breakdown as well. Thanks a lot.
    – SolaGratia
    Feb 18, 2016 at 23:47
  • No problem. Godbolt is a great tool which makes these kinds of explorations very easy, and allows you to do it across a bunch of different compilers (with whatever flags you want) and architectures, and then lets you link right to them!
    – BeeOnRope
    Feb 18, 2016 at 23:53
  • Awesome stuff! I have to check it out (it will help me with my own bytecode construction, I'm sure). Do you recommend using inline assembler for any of this loop, even for performance critical parts?
    – SolaGratia
    Feb 18, 2016 at 23:59
  • 1
    You can get much faster with inline assembler or perhaps with non-standard compiler extensions such as gcc's labels with values. Without benchmarking, I'm going to guess that the overall bottleneck of your interpreter on desktop/server CPUs (i.e., long pipeline, OoO processors that suffer large misprediction penalties) will be branch prediction failures. In particular, the indirect jump in the switch (or, worse, the cascade of conditional branches if the compiler chose that) is inherently unpredictable.
    – BeeOnRope
    Feb 19, 2016 at 0:10
  • 1
    See for example here for some discussion of different interpreter designs and tradeoffs, and here for a comparison of the switch vs computed goto approaches and some discussion of the prediction behavior.
    – BeeOnRope
    Feb 19, 2016 at 0:13
1

For Question 2, a processor should be able to handle break reasonably well since it is effectively a branch that will always occur in assembly so it shouldn't cause too much issue. This should mean there is no pipeline flush for the reason stated as the branch prediction unit should get this one right. I believe Question 1 was answered above.

5
  • 1
    HI, thanks for your reply. Could you expand a little on the details of why the "processor should be able to handle break reasonably well", because it is a little ambiguous and doesn't really give me any information as to its efficiency when compared to my current implementation? Does break translate to the same instruction as continue in my case, as this would avoid two instructions (escape switch, then continue loop)? Thanks.
    – SolaGratia
    Feb 18, 2016 at 22:15
  • Sure. A break will translate into an unconditional branch in assembly regardless of the assembly(x64..)or at least it should. In most processors now there is a piece of hardware called a branch prediction unit. They are quite sophisticated in desktop/laptop/server processors and much simpler in embedded systems if they are there at all. This will load the processors pipeline based on what branch it thinks is likely to be taken. Since a break should translate into and unconditional branch in assembly this is very easy to predict what will be taken. en.wikipedia.org/wiki/Branch_predictor Feb 18, 2016 at 22:26
  • That wiki page will cover what i can't get into a comment which is probably a lot. If you want more i will make a separate answer and do it properly. Feb 18, 2016 at 22:26
  • Hi, thanks for the reply but I'll have to get back to you, as it's quite late. I've just been 'debugging' a release version of my VM for quite a few builds now and, well, Oh god. Oh god. Overflows everywhere. LOL. Will get back to you on that wiki page. Thanks again.
    – SolaGratia
    Feb 18, 2016 at 23:09
  • 1
    In general, the branch predictor isn't even used for unconditional branches, since no prediction needs to be made. Branch prediction is for conditional branches. A type of predictor - the branch target predictor - may be used for unconditional branches with non-constant targets (aka indirect branches), but that's not the case here.
    – BeeOnRope
    Feb 18, 2016 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.