C++ – way to speed up a big switch statement

coptimizationsimulationswitch statement

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?

Best Answer

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.

Related Solutions

C Programming – Searching Algorithm Used in Switch Statement

Several options:

the naive method would be an if else cascade (slow)
the compiler can sort the cases behind the scene and then do a binary search (good for disjoint cases)
a jump table; only good for sequential cases but very fast.

For string-based switches there is the option of the prefix Trie, a sorted table that can be binary searched or the strings are hashed and used for the cases of a switch against the hash of the input string with a double check in each case.

C++ – Mailbox Pattern with Variable Arguments in C++

Instead of using an array, you could use a vector<EventClass> (where EventClass is whatever type your current array is). Then you could just iterate through the vector and process each event until it's empty, assuming the GUI thread won't be adding events while the simulation thread is processing them (this could be achieved with mutexes of some kind)... You'd then only have to process active events, since the vector would only contain events that have happened. It could work like so:

class EventClass {
    EventClass(int _o, string _d) : opcode(_o), data(_d) {}
    int opcode;
    string data;
}
//somewhere available to both threads, declare the vector:
vector<EventClass> ActiveEvents;

void GUI_Process_Events(){
    //...
    ActiveEvents.push_back(The_Event_That_Just_Happened);
}

void Simulation_Process_Events(){
    //this will iterate through all the active events and
    //act on each of them
    for(int i = 0; i < ActiveEvents.size(); i++){
        //this gets the item at the back of the vector
        EventClass Current_Event = ActiveEvents.back();

        //assuming Process(EventClass e) will process the event
        Process(Current_Event);

        //this will then remove the event from the vector
        ActiveEvents.pop_back();
    }
}

If necessary, you could use a vector of pointers to EventClass objects (but then of course you must destroy them as well):

class EventClass {
    EventClass(int _o, string _d) : opcode(_o), data(_d) {}
    int opcode;
    string data;
}
//somewhere available to both threads, declare the vector:
vector<EventClass*> ActiveEvents;

void GUI_Process_Events(){
    //...
    ActiveEvents.push_back(PointerTo_The_Event_That_Just_Happened);
}

void Simulation_Process_Events(){
    //this will iterate through all the active events and
    //act on each of them
    for(int i = 0; i < ActiveEvents.size(); i++){
        //this gets the item at the back of the vector
        EventClass* Current_Event = ActiveEvents.back();

        //assuming Process(EventClass e) will process the event
        Process(Current_Event);

        //delete the object pointed to by the element in the vector
        delete Current_Event;

        //this will then remove the event from the vector
        ActiveEvents.pop_back();
    }
}

Related Topic