Does dispatching on a Boost variant type take linear time ?

Question

How efficient is dispatching on a boost::variant ?

If it's a switch statement, it should only take O(1) time, but as far as I know, template metaprogrammign can only generate if's, which would put boost::variant dispatchs at a runtime overhead of O(n), where n = number of types in the variant.

Can anyone confirm/deny/enlighten me on this?

Thanks!

Answer 1

but as far as I know, template metaprogrammign can only generate if's, which would put boost::variant dispatchs at a runtime overhead of O(n),

No: template metaprogramming ifs are evaluated at compile time so if the overhead is defined by template metaprogramming, it will be a compile time overhead. Runtime overhead will then be constant.

Caveat: I do not know how boost::variant dispatch works. But if it’s implemented using compile-time if, it will behave as described above.

Answer 2

Looking at the source, it should be constant time. Boost uses Boost.PreProcessor to generate a switch-table, and keeps track of which index it should jump to (via the type being stored).