3

As a practice I'm working on a CPU simulator (runs at about 1.78MHz) and I'm using a switch statement to execute correct opcodes based on the value in the IR (instruction register) variable. This switch statement needs 256 cases. While it may not be that big, the switch statement needs to be executed many times in a short period of time. Are there any better ways to make fast code than using a switch statement for the same purpose?

The opcodes can be broken into two parts: Addressing mode and the actual operation. For compact code these probably could be arranged into functions and placed in the cases based on which ones are needed. I'm just not sure if writing each one out separately would be much more efficient though even if it makes the code itself larger.

Another idea, which I'm not sure how to do yet, is that I could try to detect the addressing mode and operation from the opcode before the switch statement(s) and then use one to run the addressing modes to get the effective address and then a second switch statement to perform the actual operation (and write back to memory if it was RMW instruction).

So any thoughts? Is switch statement the best choice here and what other optimization can I do to make sure the simulation runs fluently?

  • 2
    The standard way is to replace that large switch statement with a hashmap of functions as an item in a hashmap can be located faster, on average, than just running down through a list of cases. Many languages (I know C# does this for example) will optimise large switch statements to hashmaps for you as it's such a well recognised optimisation. – David Arno Oct 8 at 10:50
  • 4
    @DavidArno for C (and I suppose C++, too) a switch with dense labels such as byte opcodes is normally translated into an array of jump targets, which is more efficient than a hash table would be as there is no need to hash. – Hans-Martin Mosner Oct 8 at 11:04
  • 1
    @Hans-MartinMosner, thanks. I didn't know that. So am I correct to conclude that the advice to the OP should be "don't try and optimise it; the compiler is better at it than you"? Or isn't it as simple as that? – David Arno Oct 8 at 11:06
  • 5
    @DavidArno yes that's pretty much it, it's very hard to outsmart a compiler when it comes to micro-optimization. – Hans-Martin Mosner Oct 8 at 11:13
  • 4
    Possible duplicate of Most efficient method for large switch statements Note though that question was for C#, the answer will most probably apply to C++ as well. – Doc Brown Oct 8 at 11:32
9

For an architecture such as this, a switch statement is actually pretty efficient. If your target speed is 1.78 MHz (sounds like some Z80 machine, the TRS-80 model II had this clock speed) and your emulator runs on a modern CPU, you really shouldn't worry about this detail though, your emulator will be fast enough.

More speed can be achieved by doing just-in-time compilation of emulated machine code to native code, but it is very unlikely that you need this.

  • +1 for compilation into the native machine code. If switch table isn't able to provide the necessary performance, I cannot think of another way other than translating into the native machine code. – rwong Oct 18 at 5:39
6

The switch instruction is a good choice here: the optimizer generally makes use of a jump table or an indirect branch. It’s difficult to outperform it with other constructs (even on older cpus).

An alternative would be to use an indexed array of function pointers. This would make use of an indirect call, but might result in additional instructions required for the stack management and parameter passing. So this would not necessarily yield higher performance than the switch.

  • +1 for links to techniques. – Hans-Martin Mosner Oct 8 at 12:59
  • @Hans-MartinMosner Thanks, I had already upvoted yours for the general principle. It could also be a 6502 although there were more machines soldd with a Z80 at this clock rate ;-). – Christophe Oct 8 at 18:15
1

The one emulator that may have had the most use of all was the 68,000 emulator that was used on the first PowerPC based Macs to provide compatibility for older software.

It used a switch statement with 65,536 cases. Each case was implemented using 16 byte = 4 PowerPC instructions, of which the last instruction was a jump to the code for the switch statement.

Anything that could be implemented in three instructions was very fast. I think by the second or third generation the PowerPC Macs ran 68,000 code faster than any 68,000 processor.

1

Note: I base this answer on the assumption that you're writing an emulation of a real hardware device. I assume this is true largely because of its suspicious number of instructions and the mention of addressing modes.

Is switch statement the best choice here and what other optimization can I do to make sure the simulation runs fluently?

The best way to make sure your system runs fluently is to test it and see if it meets your predefined criteria for "fluently". A good benchmark here is the advertised speed of the hardware you're trying to emulate. If I understand correctly and that speed is 1.78MHz, then if you have a 1.78GHz processor (which is approximately smartphone speed in late 2019), you just need to execute one emulated instruction with 1000 or less of your own instructions.

Let's assume that your code fails your benchmark for "fluent". The next step is to profile your code and see where you're actually spending too much time. It may or may not be in your switch statement.

Let's assume the switch statement is the problem. Modern compilers are really good at optimizations. If you have a switch statement like this, I'd expect it to already be using something like a Branch Table. It may be worth checking your compiler's generated assembly for this kind of technique before you implement it yourself. Compiler writers are very smart; if the compiler did it already, it's unlikely that you will do better by hand.

Let's assume the attempts at optimizing the switch statement failed. The next thing I'd recommend is looking into how your target CPU works. See if it uses microcode. If it's a real CPU, then it's nearly certain they were designed with hardware engineering input. Try some analysis on the instruction sets. 256 instructions is just eight bits, so look for patterns in the bit representations of related instructions. For example, if there is an "add from register" and "add immediate value", they likely vary by one bit. Look for similar multiply and subtract instructions. There is a good chance that you can deduce something like "bit 3 controls whether the first argument is an immediate value or a register number".

Let's assume that you found some patterns. Consider emulating multiple instructions at once in a phased approach. Assuming you have a five bit instruction that always takes three arguments, you may get something like this:

// Parse out these values in advance
int instruction_id = memory[program_counter];
int firstArgRaw = memory[program_counter + 1];
int secondArgRaw = memory[program_counter + 2];
int thirdArgRaw = memory[program_counter + 3];

// Resolve first argument based on bit 0
int firstArgValue = 0;
if (instruction_id & FIRST_ARG_BITMASK){
    firstArgValue = firstArgRaw;
} else {
    firstArgValue = registers[firstArgRaw];
}

// Resolve second argument based on bit 1
int secondArgValue = 0;
if (instruction_id & SECOND_ARG_BITMASK){
    secondArgValue = secondArgRaw;
} else {
    secondArgValue = registers[secondArgRaw];
}

// Apply operator to args 1 and 2, which is defined by bits 2 and 3
int result = 0;
if (instruction_id & ADD_BITMASK == ADD_SUBINSTRUCTION){
    result = firstArgValue + secondArgValue;
} else if (instruction_id & SUB_BITMASK == SUB_SUBINSTRUCTION){
    result = firstArgValue - secondArgValue;
} else if (instruction_id & MUL_BITMASK == MUL_SUBINSTRUCTION){
    result = firstArgValue * secondArgValue;
} else if (instruction_id & DIV_BITMASK == DIV_SUBINSTRUCTION){
    result = firstArgValue / secondArgValue;
}

// Save result to register or memory as defined by bit 4
if (instruction_id & RESULT_BITMASK) {
    memory[thirdArgRaw] = result;
} else {
    registers[thirdArgRaw] = result;
}

The above is around 31 lines of code and handles 32 different instructions. Your results may vary.

It would be pretty natural in this setup to do situational checks for specific values early on to bypass most logic. Noop comes to mind here.

Let's suppose that helped, but not quite enough. Naturally, you should profile to see what's slow. One potential issue is the above code involves a bunch of if statements. Since the data is essentially random, this can be very hard on your CPU's branch predictor. If the mathematics works out, you might be able to optimize an if statement like this

int firstArgValue = 0;
if (instruction_id & FIRST_ARG_BITMASK){
    firstArgValue = firstArgRaw;
} else {
    firstArgValue = registers[firstArgRaw];
}

into something like this

int firstArgValue = (instruction_id & FIRST_ARG_BITMASK) * firstArgRaw +
                    !(instruction_id & FIRST_ARG_BITMASK) * registers[firstArgRaw];

The idea here is to calculate both values, multiply one of them by 1 (to keep it) and the other by 0 (to discard it), then add them together. You will always do this and get the right value; there is no branch here to mispredict. A branch and one or two instructions may well be slower than a fixed five instructions if it invalidates your instruction pipelining. As with all performance tweaks, you don't know whether it helped or hurt until you've measured it. In this case, it's also a bit obfuscated, so a comment clarifying why you didn't use the more obvious if statement is in order.

0

I am not an expert, but I will tell what I remember.

In the 8086 processor, the codes were encoded in bitfields. Int he same byte, one could find a fragment of an instruction AND a fragment of data.

So you should better concentrate on the actual information to be decoded, instead of analyzing all bits in the memory.

I will give an example. Let's assume you have 3 instructions, bit-ancoded:

110
1110
1111

Now you can make 16 switch cases, or you can optimize and make only 4 such cases:

1100
1101
1110
1111

Even so, you need ONLY 3 tests, everything else is "trash".

Therefore I would implement something like:

if ( 1110 == code )
{

}
else if ( 1111 == code)
{

}
else if ( 110 == code)
{

}

Please note that the order of the tests MIGHT be important. Also, the code above is actually pseudo-code. I did not present bit operations to extract the useful data from inside the byte.

So the bottom line is, do not write code at all for something you do not need.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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