Andrew Herron (@TheSpyder) suggested on Twitter that modern branch predictors are pretty smart, and it looks like he may be right. I replaced the sequential case access pattern with running a PRNG inside the pattern-matching loop, and got results that look like this instead:
Again, this is hardware architecture-specific.
I thought the sequential access pattern might be wrong because adjacent variands will trigger descent down nearly the same path in the binary search each time. So, if the branch predictor, say, caches the result of a few recent jumps, and predicts they will be taken the same way again the next time, it will predict correctly most of the time.
To check this, I also tried randomizing the array that controls the access pattern once, during initialization, using a PRNG, instead of generating random indexes during the loop. This produced the same results as in the original post, though, strongly favoring polymorphic variants on my machine. So, I’m not sure what the branch predictor is doing, or if it is even the branch predictor that is responsible for such performance. It may just be that an array access is easier for some kind of other speculative execution to handle, than whatever is done by the PRNG (module Random).
Anyway, polymorphic variants still seem to do pretty well. Just not better by an absurd and outrageous margin 