2

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?

  • "Assume polymorphism isn't applicable and each case [of the 1000 possible] has totally unique functions which cannot be abstracted further." I'm sorry but this sounds simply ludicrous. Anyway, the only way to know for sure is to test and measure. switch statements are pretty fast. hash table lookups too. can't really give a good answer without more context though. – sara Jun 20 '16 at 17:11
  • 1
    "Assume polymorphism isn't applicable" – You can encode booleans using polymorphism (see examples in PHP, Scala, Ruby). IOW: every decision can always be encoded using polymorphism. See also Smalltalk, which doesn't even have conditionals. – Jörg W Mittag Jun 20 '16 at 21:56
8

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.

  • 1
    I thought most compilers for languages like java and C# converted switch statements with more than n cases (for some value of n) to jump tables? might be mistaken though. – sara Jun 20 '16 at 17:15
  • @kai: You are correct. I was wrong. I have updated the answer. – JacquesB Jun 20 '16 at 17:30
  • Thankfully this is more of a thought experiment that occurred after I had to refactor someone else's massive switch statement. I was wondering if, besides readability, I was actually saving any cycles by getting rid of the switch, or if there was an even (theoretically) better method like a dictionary. Interesting to learn a switch actually converts to a dictionary at higher numbers of branches. – thanby Jun 20 '16 at 17:48
  • 3
    I have written a 1000-ish way switch statement: it's the core emulation loop for Fuse. Is it maintainable? Yes, but only because the actual C code is generated. – Philip Kendall Jun 20 '16 at 19:19
  • 1
    @PhilipKendall: "only because the actual C code is generated" – Then you haven't written it ;-) – Jörg W Mittag Jun 20 '16 at 21:46
2

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.