🔒 Locked

Optimizing a large switch statement

Started by RajanSky Oct 17, 2003 at 12:27 PM 17 replies 1.5k views

Original Post

Oct 17, 2003 at 12:27 PM

Hi, I''m working on emulating the 6502 microprocessor right now (it''s part of a NES emulator I''m writing with a buddy), so right now we''re working onexecuting a particular instruction based on what opcode is read from memory. So, the way I have it set up right now is I have an array of function pointers, and each instruction is implemented as its own function. I figured this would be more efficient than a big switch statement, right? Because a switch statement is like a bunch of if/elseifs. Well, I recently found out that good compilers will actually convert the switch statement into a jump table when there are many entries. Whoa! So, what this means is a big switch is actually *more* efficient than a function table because it does not incur the extra function overhead. I have heard that there may even be something more efficient, but I don''t exactly understand how it works. It''s called "precomputed labels", and basically the idea is that you have an array of *labels*, so you can do something like this: opcode = GetOpcode(); goto instructionArray[opcode]; I guess in assembly language it is common to treat labels as addresses but I haven''t seen this done in C++. Maybe I could just have a bunch of labels like: instruction1_label: instruction2_label: ... instructionN_label And then create an array like: long *instructionArray[] = { instruction1_label, instruction2_label, ... instructionN_label }; I don''t know, C++ tends to be so much more strict than asm when it comes to mixing up types like this so would this be valid code? Also, I''m not sure if the "big switch optimization" will be performed by all compilers. Does anyone know if it''s safe to rely on this optimization being done on, say, a compiler for the GBA system? (because my partner and I are planning to port the emulator to GBA eventually) Anyways I''ll probably play around with this to see if I can make it a bit faster, but if anyone might happen to know this stuff I''d really appreciate any info! Thanks! Raj

superpig

276

superpig

Oct 17, 2003 at 12:35 PM

I don't think that's legal in C++, as the labels aren't symbols that can be handled in that way. Where did you get that they're long* from? I guess that makes sense, as they'd be pointers to locations in memory, but I'm still not sure...

You could always code that bit of it directly in ASM, I guess.

Superpig
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

[edit: You are missing a closing </small> tag]

[edited by - Magmai Kai Holmlor on October 17, 2003 6:05:32 PM]

RajanSky

Author

RajanSky

Oct 17, 2003 at 12:53 PM

Hey superpig, thanks for the reply...

hmm I just made up the long *, hehe... I mean, i don't know what other type a label would have?

Yeah actually I guess for the GBA version we might just do it in asm, that's a good idea. For the PC version though prolly stick to C++ because there's over 100 different instructions to be implemented

[Edit]: Btw I should mention that I have heard of the precomputed labels idea being done in C++... So I know it is possible, the only question is really does MSVC++ and GCC support it and what is the syntax for doing it.

Thanks,

Raj

[edited by - Rajansky on October 17, 2003 1:54:46 PM]

Null and Void

163

Null and Void

Oct 17, 2003 at 1:32 PM

GCC Extensions to the C Language: Labels as Values. I''d probably just stick with the switch though...

Namethatnobodyelsetook

118

Namethatnobodyelsetook

Oct 17, 2003 at 2:16 PM

MAME is open source, and emulates many CPUs, 6502 included. I looked at the 6502 code once, and I remember it being only 2-3 screens of code. You could use this... then again, if you want to write the CPU emulation yourself, you can ignore this post, or maybe take a peek just to see what they did.

MESS and supports NES, is based on MAME, and is probably open source (I never checked). You could use this... then again, if you want to write the emulator yourself, ignore this post, or maybe take a peek just to see what they did.

superpig

276

superpig

Oct 17, 2003 at 2:29 PM

Here's a thought: if the processing code for each instruction was the same size (or was set to jump out to somewhere else if the size was too small) you could jump by directly calculating the address based on the opcode.

Pseudo-ASM Example:


mov ax, theCurrentOpcode;
jmp instructionBase+(ax*5)

instructionbase:
//operation 0 (positions 0->4): add operands

0x00: add virtualAX, operand1, operand2
0x01: ret
0x02: nil
0x03: nil
0x04: nil
//operation 1 (positions 5->9): subtract operands

0x05: sub virtualAX, operand1, operand2
0x06: ret
0x07: nil
0x08: nil
0x09: nil
//operation 2 (positions a->e): some really complex routine

0x0a: jmp someReallyComplexRoutine
0x0b: ret
0x0c: nil
0x0d: nil
0x0e: nil

I think you get the idea. You might need to experiment to get the correct size of each code block - 5 seems a little large, but 2 would likely be too small (enough for one instruction and a ret).

Superpig
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

[edit: You are missing a closing </small> tag]

[edited by - Magmai Kai Holmlor on October 17, 2003 6:05:50 PM]

Extrarius

234

Extrarius

Oct 17, 2003 at 3:38 PM

It looks to me like you''re just trying to implement a jump table manually when the switch will do it automatically.

RajanSky

Author

RajanSky

Oct 17, 2003 at 4:16 PM

Cool thanks for the replies! Especially Null and Void, that''s exactly what I was looking for. I guess I''ll just stick with the switch. Supposedly the "goto" way is actually faster when compiled so this just made me really curious that something would be faster than a jump table, but I guess the speed gain would be minimal at best.

Raj

iaretony

Oct 17, 2003 at 4:24 PM

Sort you''re switch from most used case to least used case.

Tony

superpig

276

superpig

Oct 17, 2003 at 4:37 PM

quote:
Original post by Extrarius
It looks to me like you're just trying to implement a jump table manually when the switch will do it automatically.

I thought a jump table implied an actual lookup, whereas my example was jumping based on a mathematical expression. If it's a very large jump table, I would have thought that my method would be faster, rather than searching the table.

Of course, I may be completely wrong about how jump tables are implemented. If so, please feel free to make me look stupid.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

[edit: You are missing a closing </small> tag]

[edited by - Magmai Kai Holmlor on October 17, 2003 6:06:08 PM]

Ready4Dis

Oct 17, 2003 at 4:46 PM

quote:
Original post by superpig
I don't think that's legal in C++, as the labels aren't symbols that can be handled in that way. Where did you get that they're long* from? I guess that makes sense, as they'd be pointers to locations in memory, but I'm still not sure...

You could always code that bit of it directly in ASM, I guess.

Superpig
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

I am sorry to inform you mister, but you are incorrect. I wrote a Virtual machine, and had similar issues to this man, and my solution was to try all posibilities and time them. I had a function table, switch statements that called functions, switch statements with inlined functions, and a custom jump table. The inlined switch statement was the fastest, even faster than my custom jump table because the hoops you must jump through to get it to work properly. I had it down to about the same # of instructions, but it definetly wasn't worth the effort (well, it was worth it for educational purposes, but not worth the speed). The trick to getting the compiler to create the jump table is to make sure you put all the numbers in order, starting with zero. Also, you can keep your current setup, just make all the functions inlined and make the function with the switch inlined and compile as release

.

[edited by - Magmai Kai Holmlor on October 17, 2003 6:04:27 PM]

Ready4Dis

Oct 17, 2003 at 4:51 PM

quote:
Original post by superpig
quote:
Original post by Extrarius
It looks to me like you're just trying to implement a jump table manually when the switch will do it automatically.

I thought a jump table implied an actual lookup, whereas my example was jumping based on a mathematical expression. If it's a very large jump table, I would have thought that my method would be faster, rather than searching the table.

Of course, I may be completely wrong about how jump tables are implemented. If so, please feel free to make me look stupid.

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

This is how jump tables are created in MSVC 6.0 according to my asm output

.

It stores a table of address, and does a simple multiply to get the value...

SomeTable dd
Func1, Func2, Func3

mov bp, dd ;Move our table address into bp
shl eax, 2 ;Multiply by 4 to get it's position in the table
jmp ds[bp+eax] ;Jump to the location of the code we want

This isn't exact, because I haven't looked at it in some time, but this is the jist of it

. About 3 instructions NO MATTER what # it ends up in the switch

.

[edited by - Magmai Kai Holmlor on October 17, 2003 6:04:45 PM]

MaggotX

Oct 17, 2003 at 4:56 PM

The function pointer array is much better than the large switch statement if the switch cases are calling functions. The switch can be optimized by making the opcode functions inline. But I think the function overhead is going to be minimal compared to the switch overhead. Even an optimized switch statement breaks down to a jump table.

I think the more important optimization is going to be coding your most used opcodes in assembly. Doing this well you will minimize the function overhead also.

Extrarius

234

Extrarius

Oct 17, 2003 at 6:56 PM

MaggotX: I think you are incorrect about switch overhead being almost as much as function overhead. There is no overhead to a switch if the values are consecutive integers. It would still have to do the table lookup for a function table, except that it also has to call the function and mess with the stack.
A jump table is O(1), so I don't think you're going to get any faster than an optimized switch.

[edited by - extrarius on October 17, 2003 7:56:44 PM]

superpig

276

superpig

Oct 17, 2003 at 7:45 PM

Ah, thanks Ready4Dis. So I guess the compiler was just doing it my way all along

oliii

271

oliii

Oct 17, 2003 at 8:22 PM

you could save loads of typing by using macros like these


#define PARSE_OPCODE(x) case x: { Parse_Opcode_##x(); printf("opcode " #x " parsed.\n"); break; }


//.....

//.....

//.....


[source]
switch(opcode)
{
PARSE_OPCODE(0x01)
PARSE_OPCODE(0x02)
PARSE_OPCODE(0x03)
PARSE_OPCODE(0x04)
PARSE_OPCODE(0xA0)
}


#define PARSE_OPCODE(x, y) case x: { Parse_Opcode_##y(); printf("opcode " #y " (" #x ")" " parsed.\n"); break; }


//.....

//.....

//.....



void Parse_Opcode_mul() {}
void Parse_Opcode_add() {}
void Parse_Opcode_nop() {}

switch(opcode)
{
PARSE_OPCODE(0x01, mul)
PARSE_OPCODE(0x02, add)
PARSE_OPCODE(0xA0, nop)
}

ivquatch

Oct 17, 2003 at 8:53 PM

Mate,

Yeah I''ve come across dis problem before when coding the AI FSMs for a game I''m working on. Function pointers or switch statements? That is the question. It seems that switch statements SHOULD be faster because accessing a case statement should be about as fast as accessing an array (more specifically, an indexed array of case statment pointers), but it''s not! Bugger!

I decided to go with a function table implementation just cause I knew for certain it''s fast and it''s speed wasn''t dependent on the compiler.

Anyway, since speed is such an issue in your situation, I would suggest maybe getting down and dirty with some assembly code. That is, try coding just the instruction table in assem. A bunch of fast jump intructions may be the answer. Incase you didn''t know already, in MSVC++ you can include assembly code in your C/C++ code like this

_asm
{
//your code here
}

Anyway, happy trails.

Cheers,

Quatch

RajanSky

Author

RajanSky

Oct 17, 2003 at 11:00 PM

Hey guys,

Wow, lot of really knowledgeable people around here, I expected this issue to be pretty arcane knowledge but you guys really know your stuff. Thanks for all the help!

I didn''t realize is that you have to sort the case statements, many thanks for that tidbit of information because I wouldn''t have considered it important otherwise.

Raj

iaretony

Oct 18, 2003 at 12:05 AM

Yes, short circuiting compilers are a beautiful thing.

Tony

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.