CODEWITHSUNDEEP
cperformance
T.Jones
T.Jones

Reputation: 55

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

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!

Upvotes: 3

Views: 1788

Answers (5)

Benny
Benny

Reputation: 4321

I'm posting this just for information purpose, since samy.vilar already gave the most elegant solution with the function array. If you use GCC, it understands case range. This code would eventually behave in quite similar way as your second solution, resulting in some binary-tree code path (assuming there is no compiler optimization).

int             nested_switch(int i)
{
  switch (i) {
    /* i is in the 1..10 range */
  case 1 .. 10:
    switch (i) {
      /* i is in the 0..5 range */
    case 1 .. 5:
      switch (i) {
      case 1:
        break;
      case 2:
        break;
      ...
      case 5:
        break;
      }
    case 5 .. 10:
      switch (i) {
      case 6:
        break;
      case 7:
        break;
      ...
      case 10:
        break;
      }
    }
    /* i is in the 11..20 range */
  case 11 .. 20:
    switch (i) {
      ...
    }
  }

  return 0;
}

Upvotes: 0

Samy Vilar
Samy Vilar

Reputation: 11130

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.

Upvotes: 9

Ed Heal
Ed Heal

Reputation: 59997

Is it not recommended that any function should fit onto about 1.5 screens, so such a huge switch statement will not fit this bill. To overcome this have a dispatch table.All you have to do is index into the array to find the appropriate function to call.

Upvotes: 0

mutoso
mutoso

Reputation: 31

I believe that the switch statement is better, at least from a code readability standpoint (and maybe from a speed standpoint since it's only picking out one block to run as apposed to have to evaluate multiple conditions, as in the second example.)

Upvotes: 1

noisecapella
noisecapella

Reputation: 814

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

Upvotes: 1

Related Questions