Some time ago when discussing with my brother, we concluded that
switch statements can be better optimized at machine
if/else. The discussion started because
python does not support
Some time later I was questioning myself if this was really true.
I mean the most obvious way to implement
a list of conditional jumps in assembly code. In this case there
would be no performance advantage at all. But there is not a
hashtable created by the compiler, right?!
switch in C
Okay, let's take a simple program with a
C, C++, Java, PHP and ActionScript use the same syntax. It's like
default block can be added, which is executed
whenever no other case matches.
break terminates the
current switch; missing to use it will lead to a program executing all
Let's start with this C code. It uses some input character as condition and has 3 case branches. Just for the record: The input character is only used here to urge the compiler to not optimize the switch away (which is the case whenever a constant is the condition).
My assumption is that this source code will get translated into the following machine pseudo code:
In this case the machine has to test each condition separately, which
simply takes Ο(n). This would be equal to a program using
if else repetitions.
elif in python
python does not have a
switch statement. Guido asked the
community and they did not like it
[pyt01]. Like me. Default case,
break and lots of control flow. It's just as low-level like
for (i=0; i<42; i++) and not easy to process in our
brain. Furthermore in some languages there is not only one comparison
operator (weakly vs strongly typed) and the way of comparsion has to
define another convention. Well, the last point is actually not a
problem in python…
So we have to use
if/else again. The equivalent python
program looks like this:
Of course we are interested into the assembler generated by python. So let's have a look using the dis module [dis01].
Comparisons for each case. Pretty much the same like
if/else in C. Now we have seen enough source code.
What about the reality?
What it looks like when we choose the red pill.
Hashtables are important data structures. They are widely used among different software implementations. This includes programming languages like PHP [php01] and python [pyh01].
The primary reason we are mentioning hashtables here is the lookup
runtime. We were talking about Ο(n) before in context
if/else. Looking up the last case statement (= worst
case) takes as long as iterating over all case conditions. Hashtables
using hashing functions allow us runtimes with Ο(1).
C to amd64 assembly
gcc -Wall -S switch.c
I will reduce the source code to important parts and add comments.
This assembler code comes with 3 neat tricks. The first one is to subtract 65 from variable a. 65 is so special only because it's the first number to be a condition to be tested (ASCII A). If you subtract 65 from a, you have to jump to the default case if a is greater than 4. The compiler recognized this situation (all numbers between 65 and 69 point to some case) and this is trick number two for me.
The third trick is also referenced in the source code by brackets and describes the way to lookup the pointer to the case codeblock by a hashtable. We have to do some arithmetic and have to explain GAS (GNU assembly syntax):
means take the content of the address
.L8 + (%rax * 8).
And what does that mean? Well, on L8 we have the array of pointers to
the cases. The margin between the pointers is 8 on a 64bit system. So
case 'A' is on
.L8 + 1 * 8.
case 'B' is on
.L8 + 2 * 8. And so on.
Solving this expression returns an pointer to the first command of the
case code block. So
.L8 + (%rax * 8) is actually our
hashing function and there is no iteration over cases. Lookup takes
So it is true:
switch statements can be translated to
hashtables at assembler level and therefore are more efficient than
if/else constructs. If you use the
code in C at least GCC is not able to evaluate this "hashtable would
be possible" situation. As far as python is concerned, it does not
support switches and therefore cannot be translated to hashtables