Gabriela's Coding Blog: A fake switch

This post is about a trick from the Dalvik VM Internals video, which was mentioned in the Coursera Android course that is currently running. (maybe the next million years will be more exciting?)

The claim was that this is the one case where goto isn't evil around minute 33:31 and that it performs better than switch. Well, does it? And if so, by how much?

This was the example:

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
#define DISPATCH() \
{ goto *op_table[*((s)++) - 'a']; }

static void interp_old(const char* s)
{
static void *op_table[] = {
&&op_a, &&op_b, &&op_c, &&op_d, &&op_e };
DISPATCH();
op_a: printf("Hell"); DISPATCH();
op_b: printf("o "); DISPATCH();
op_c: printf("wo"); DISPATCH();
op_d: printf("rld!\n"); DISPATCH();
op_e: return;
}
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Switch is pretty switched on, so let's see how this compares!

The code that does the comparison can be found here. Results(on my ancient 32 bit Dell):

With gcc -g:

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 
Using default value of 100000.  Usage: ./dispatch #
Sample size = 100000 chars * 100000 iterations. 
Dispatch method:                         0.002152 
Dispatch shuffled method:                0.002144
Goto switch method:                      0.002641
Goto switch method 2:                    0.002351
For loop Switch method:                  0.002667
For loop Switch shuffled method:         0.002660 
Recursive switch method:                 0.010798
Recursive shuffled Switch method:        0.006913
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

With gcc -O3:

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Using default value of 100000.  Usage: ./dispatch #
Sample size = 100000 chars * 100000 iterations.
Dispatch method:                         0.001083
Dispatch shuffled method:                0.001108
Goto switch method:                      0.001338
Goto switch method 2:                    0.001381
For loop Switch method:                  0.001465
For loop Switch shuffled method:         0.001385
Recursive switch method:                 0.001437
Recursive shuffled Switch method:        0.001385
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

So, there is a small difference, but it's really not that big a deal, unless you really are pressed for time and space.

The ever useful gcc manual has an entry about fun with local labels which will tell you more. Still, building this by hand is tedious, even if emacs is your best friend.

What if you have a huge array of a struct that maps variable A to variable B and also has an optional function pointer F? What you need is a 'fake_switch' generator, here is my version. It should be easily adjustable for your taste.

Goto it ;-)

Ps.: For extra fun, try this C to Assembler translator. I really like the hover feature they built, but another thing that would be useful is showing the size of the generated code.

Monday, 25 May 2015

A fake switch