title: Which implementations are conformant for constant time dispatch of std::visit?
body: <p>It is often quoted that C++s <code>std::variant</code> has worse performance than variants in other languages. See e.g. <a href="https://pbackus.github.io/blog/beating-stdvisit-without-really-trying.html" rel="nofollow noreferrer">https://pbackus.github.io/blog/beating-stdvisit-without-really-trying.html</a></p>
  
  <p>One of the reasons is the <code>exception</code> state, the other was said to be the requirement of the standard that <code>std::visit</code> complexity <a href="https://en.cppreference.com/w/cpp/utility/variant/visit" rel="nofollow noreferrer">does not depend on the number of types</a> which forces implementers to use a dispatch table of function pointers which inhibits certain optimizations like inlining.</p>
  
  <p>Questions:</p>
  
  <ol>
  <li>Would it be legal to implement <code>std::visit</code> as a chain of <code>if-elseif</code> where each check is like <code>if(v.index() == I) return visitor(get&lt;I&gt;(v));</code>? It seems like it does not because dispatching to higher indices would take more checks for the index.</li>
  <li>Is it legal to implement it with a switch like <code>switch(v.index()) case I: return visitor(get&lt;I&gt;(v));</code>? This looks like "independent of the number of types" as control flow jumps directly to the case and it is how e.g. Microsoft implemented it for less than 64 (or so) types.</li>
  <li>If the switch is legal, is it legal for the optimizer to convert small switches to if-elseif ladders? Again the MSVC compiler does this: <a href="https://godbolt.org/z/D2Q5ED" rel="nofollow noreferrer">https://godbolt.org/z/D2Q5ED</a>. But IMO this violates the "independent of number of types" complexity mandated by the standard although it would in practice be faster.</li>
  </ol>
  
  <p>I'm asking based on a discussion on reddit where someone claimed <a href="https://www.reddit.com/r/cpp/comments/dnyneq/proof_of_concept_runtime_heterogeneous_containers/f5siesd/" rel="nofollow noreferrer">"Constant time" again refers to the behavior in the limit.</a> which I don't really agree with. IMO "Constant time" means the time is constant no matter the input which for an <code>if-elseif</code>-chain is not the case.</p>
  
  <p>But I'm not sure how this applies here. It seems 1. is illegal, 2. is legal but the optimizer (may) transforms it into 1. which means that 2. is also illegal. At least if following the standard to the letter.</p>