Most efficient method for large switch statements

Question

Let's say you have many paths that an application can take at a certain point based on the value of a specific input (for example a simple int). Is there a certain method that is most efficient for picking which path to follow? A nice and organized way would be a simple switch statement, but does that scale as the number of possible cases grows larger? Is there a better method when you have, say 100 or 1000 possible cases? Assume polymorphism isn't applicable and each case has totally unique functions which cannot be abstracted further.

Edit: Just to clarify, this is a thought experiment, I'm not actually writing code with 1000 cases. Also I found this related question to be enlightening on how the compiler/JIT handle the issue: Why use an OO approach instead of a giant "switch" statement?

Answer 1

I hope this is just a thought experiment, because if you have a real-wold program with a thousand distinct code path selected by an int parameter, performance considerations should be way down you list of worries. It sounds completely unmaintainable.

But to actually answer the question: switch is O(n). If you really want to scale you need a O(1) algorithm, so you create an array or dictionary which maps the integer values to delegates, pick the delegate based on the int, and executes it.

I was wrong: Apparently a switch with enough branches are compiled into a jump table or a dictionary lookup anyway. So you can't do faster than a switch.

Answer 2

If we're just talking about pure performance and tossing aside all notions of productivity and maintainability, then it's hard to beat a switch statement with compile-time constants for case expressions.

It's potentially even faster than a jump table, at least on the C++ side (I imagine C# optimizers are pretty smart too). I was surprised one time looking through some disassembly in Godbolt for a switch statement like so:

switch (opcode)
{
case 0x01:
    call_some_function_which_calls_other_functions(...);
    break;
case 0x2:
    ...
}

Only to get a moment where I was extremely confused. Where's the jump table? Then the confusion was followed by a moment of awe. Instead of using a jump table, the optimizer actually figured out that the entire switch and nest of function calls can boil down to a simple LUT. It turned the analogical equivalent above to something completely branchless like:

data = some_other_data[opcode];

And I was so impressed because I never even conceived that that whole mess of switch statements and nested function calls with parameters being passed could boil down to a simple assignment from a look-up table of data. I then looked through all the code and function calls and realized, "Hey, actually you could just use a LUT here." So what an optimizer can do with some switch statements and nested function calls which it knows ahead at compile-time is pretty amazing.

I haven't been quite as amazed yet when dynamic dispatch is involved. I've never seen disassembly of a kind that suggested an optimizer could inline a function call involving virtual dispatch supplied only a base pointer/reference or function pointer which it'd have to do first before it can do all its wizardry with things like register allocation and instruction selection. If C optimizers could do this, then qsort would rival C++'s std::sort instead of typically taking twice as long or longer (qsort's only conceptual disadvantage is its use of dynamic dispatch on the comparator). Nevertheless, polymorphism often yields code that's so much easier to maintain and looks so much nicer.

Also while it is kinda gross, there can actually be cases where you need to branch off 100+ different conditions in a real-world scenario. A prime example I've looked at is an emulator which has to deal with a boatload of opcodes for the target hardware which supported an instruction set that contained 100 instructions or more.

So I generally think whatever you do, you have to provide the optimizer with as much information it can know in advance at compile-time as possible. The switch statement achieves that. Not all optimizers are so smart at figuring out in advance where a function call involving dynamic dispatch (virtual function, function pointer, etc) will ultimately lead to at compile-time.

Answer 3

Is this a real application you're working on? 1000 different paths based on one parameter, all totally unrelated? I suppose if that parameter is "transaction code" it might be barely possible. Even there, 1000 is a lot of different paths.

But that said ...

As JacquesB notes, a C# switch creates a jump table. This is about as efficient as it is going to get as far as the dispatching side goes. If all 1000 blocks of code are in one module, there might be an issue with getting it all loaded into memory.

You could use an if/then/else but that would involve hundreds of tests on average.

Second obvious option is an array or hash table where the target value is a pointer to a function, or, in OOP-land, a reference to a class containing the function, where all the classes implement the same interface.