For larger switch case statements, is it better to separate them?

Question

Quick question. For example, working with a some-what larger case of ~1000 options: which is the 'best' method? I'm not specifically wanting straight up faster results.

switch (foo) {
    case 0: 
        // code ...
        break; 

    // One, two, skip a few...

    case 1000:
        // code ...
}

or something that splits possible results so it can quickly find the proper case statement. Similar too:

if (foo < 101) {
    if (foo < 51)
        switch (foo) {}
    else
        switch (foo) {}
} else if (foo > 100 && foo < 201) {

// skipped for convenience 

} else if (foo > 900) {
    if (foo < 951)
        switch (foo) {}
    else
        switch (foo) {}
}

I imagine the second method is much faster for the larger numbers, but the first method also seems it may be able to breeze through it since it's not constantly checking statements. Is one of these methods frowned upon or is there a better method? This is for C, but I am interested in knowing its consistency with other languages. Thanks!

Answer 1

switch statements can be incredibly fast if the compiler implements them using jump tables, but this is only possible on special sequence of cases, and may not be practical it really depends on the possible cases. The compiler may or may not use jump tables, I did find this http://blog.jauu.net/2010/06/15/GCC-generated-Switch-Jump-Tables/ which was kind of interesting.

JUMP tables can be incredibly fast, since it just calculates the offset and jumps to the appropriate address.

GCC does have -fno-jump-tables which does disable it completely.

Sometimes you can build your own jump table, using arrays of function pointers, and special indices, this can make your code incredibly fast but its not practical in all cases, imagine you had a switch and in every case you would call a function, you could build an array of function pointers, set a default function just to be safe, then instead of a switch you would simply do fun_table[indice](); I did this once for my own virtual machine.

Answer 2

I think switch statements are often interpreted as goto's in the underlying assembly language, which would make the first method significantly faster.

This seems to support that, although it isn't exactly proof: http://en.wikibooks.org/wiki/Optimizing_C%2B%2B/Writing_efficient_code/Performance_improving_features#Case_values_of_switch_statements