What is more efficient a switch case or an std::map

Question

I'm thinking about the tokenizer here.
Each token calls a different function inside the parser.
What is more efficient:

• A map of std::functions/boost::functions
• A switch case

Answer 1

I would suggest reading switch() vs. lookup table? from Joel on Software. Particularly, this response is interesting:

" Prime example of people wasting time trying to optimize the least significant thing."

Yes and no. In a VM, you typically call tiny functions that each do very little. It's the not the call/return that hurts you as much as the preamble and clean-up routine for each function often being a significant percentage of the execution time. This has been researched to death, especially by people who've implemented threaded interpreters.

In virtual machines, lookup tables storing computed addresses to call are usually preferred to switches. (direct threading, or "label as values". directly calls the label address stored in the lookup table) That's because it allows, under certain conditions, to reduce branch misprediction, which is extremely expensive in long-pipelined CPUs (it forces to flush the pipeline). It, however, makes the code less portable.

This issue has been discussed extensively in the VM community, I would suggest you to look for scholar papers in this field if you want to read more about it. Ertl & Gregg wrote a great article on this topic in 2001, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures

But as mentioned, I'm pretty sure that these details are not relevant for your code. These are small details, and you should not focus too much on it. Python interpreter is using switches, because they think it makes the code more readable. Why don't you pick the usage you're the most comfortable with? Performance impact will be rather small, you'd better focus on code readability for now ;)

Edit: If it matters, using a hash table will always be slower than a lookup table. For a lookup table, you use enum types for your "keys", and the value is retrieved using a single indirect jump. This is a single assembly operation. O(1). A hash table lookup first requires to calculate a hash, then to retrieve the value, which is way more expensive.

Using an array where the function addresses are stored, and accessed using values of an enum is good. But using a hash table to do the same adds an important overhead

To sum up, we have:

• cost(Hash_table) >> cost(direct_lookup_table)
• cost(direct_lookup_table) ~= cost(switch) if your compiler translates switches into lookup tables.
• cost(switch) >> cost(direct_lookup_table) (O(N) vs O(1)) if your compiler does not translate switches and use conditionals, but I can't think of any compiler doing this.
• But inlined direct threading makes the code less readable.

Answer 2

STL Map that comes with visual studio 2008 will give you O(log(n)) for each function call since it hides a tree structure beneath. With modern compiler (depending on implementation) , A switch statement will give you O(1) , the compiler translates it to some kind of lookup table. So in general , switch is faster.

However , consider the following facts:

The difference between map and switch is that : Map can be built dynamically while switch can't. Map can contain any arbitrary type as a key while switch is very limited to c++ Primitive types (char , int , enum , etc...).

By the way , you can use a hash map to achieve nearly O(1) dispatching (though , depending on the hash table implementation , it can sometimes be O(n) at worst case). Even though , switch will still be faster.

Edit

I am writing the following only for fun and for the matter of the discussion

I can suggest an nice optimization for you but it depends on the nature of your language and whether you can expect how your language will be used.

When you write the code: You divide your tokens into two groups , one group will be of very High frequently used and the other of low frequently used. You also sort the high frequently used tokens. For the high frequently tokens you write an if-else series with the highest frequently used coming first. for the low frequently used , you write a switch statement.

The idea is to use the CPU branch prediction in order to even avoid another level of indirection (assuming the condition checking in the if statement is nearly costless). in most cases the CPU will pick the correct branch without any level of indirection . They will be few cases however that the branch will go to the wrong place. Depending on the nature of your languege , Statisticly it may give a better performance.

Edit : Due to some comments below , Changed The sentence telling that compilers will allways translate a switch to LUT.