Switch statement with huge number of cases

Question

What happens if the switch has more than 5000 case. What are the drawbacks and how we can replace it with something faster?

Note: I am not expecting to use array to store cases as it's the same.

Answer 1

As food for thought... in case one might be stuck with an old/buggy/inefficient compiler or just love hacking.

Inner work of switch statement consist of two parts. Finding address to jump, and well jumping there. For the first part you need to use a table to find the address. If the number of cases increases, table gets bigger - searching address to jump takes time. This is the point compilers tries to optimize, combining several techniques but one easy approach is to use table directly which depends on case value space.

In a back of the napkin example;

switch (n) {
    case 1: foo(); break;
    case 2: bar(); break;
    case 3: baz(); break;
}

with such piece of code compiler can create an array of jump_addresses and directly get the address by array[n]. Now search just took O(1). But if you had a switch like below:

switch (n) {
    case 10: foo(); break;
    case 17: bar(); break;
    case 23: baz(); break;
    // and a lot other
}

compiler needs to generate a table containing case_id, jump_address pairs and code to search through that structure which with worst implementation can take O(n). (Decent compilers optimize the hell out of such scenario when they are fully unleashed by enabling their optimization flags to a degree that when you need to debug such optimized code your brain starts to fry.)

Then question is can you do this all yourself at C level to beat the compiler? and funny thing is while creating tables and searching through them seems easy, jumping to a variable point using goto is not possible in standard C. So there is a chance that if you are not going to use function pointers due to overhead or code structure, you are stuck... well if you are not using GCC. GCC has a non-standard feature called Labels as Values which helps you to get pointers to labels.

To complete the example you can write the second switch statement with "labels as values" feature like this:

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....};
goto *labels[n];
case_foo:
    foo();
    goto switch_end;
case_bar:
    bar();
    goto switch_end;
case_baz:
    baz();
    goto switch_end;
// and a lot other
switch_end:

Of course if you are talking about 5000 cases, it is much better if you write a piece of code to create this code for you - and it is probably only way to maintain such software.

As closing notes; will this improve your daily work? No. Will this improve your skills? Yes and talking from experience, I once found myself improved a security algorithm in a smart card just by optimizing case values. It is a strange world.

Answer 2

There's no specific reason to think you'd want anything other than a switch/case statement (and indeed I'd actively expect it to be unhelpful). The compiler should create efficient dispatching code, which might involve some combination of static [sparse] table(s) and direct indexing, binary branching etc.; it's got insights into the static values of the cases and should do an excellent job (retuning it on the fly each time you change the cases, whereas new values that don't fit well with a hand-crafted approach - such as wildly differing values when you'd had a pretty packed array lookup - could require reworking of code or silently cause memory bloat or a performance drop).

People really cared about this kind of thing back when C was trying to win over hard-core assembly programmers... the compilers were held accountable for generating good code. Put another way - if it's not (measurably) broken, don't fix it.

More generally, it's great to be curious about this kind of thing and get people's ideas on alternatives and their performance implications, but if you really care and the performance difference could make a useful difference to your program (especially if profiling suggests it) then always benchmark with your program doing real work.

Answer 3

Big switch statement, generally auto-generated one, may take long time to compile. But I like the idea that compiler optimizes the switch statement.

One way to break apart the switch statement is to use bucketing,

int getIt(int input)
{
  int bucket = input%16;
  switch(bucket)
  {
    case 1:
      return getItBucket1(input);
    case 2:
      return getItBucket2(input);
    ...
    ...
  }
  return -1;
}

So in the code above, we broke apart our switch statement into 16 parts. It is easy to change the number of buckets in auto-generated code.

This code has added run-time cost of one layer of indirection or function-call. . But considering the buckets defined in different files, it is faster to compile them in parallel.

Answer 4

Try to use Dictionary class with Delegate values. At least it makes code a little bit more readable.