Re: Cost of polymorphic variants over normal ones.

[Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>]

From: Sven LUTHER <luther@dpt-info.u-strasbg.fr>
> A (somewhat) related question would be, what is the cost of polymorphic
> variants compared to noarmal ones ?
> 
> The normal variants are coded as integers, and using them is fast, while
> polymorphic variants use some kind of hash functionn, but very simple.

They are also coded as integers. The hash function is only used at
compile time.

> If i use a datatype that i will be pattern matching very often and i want it
> to be quick, how much is the overhead of using polymorphic patterns over
> noraml ones ?

The difference is that since the integers are the result of a hash
function, you cannot use an indirect jump through a table, like with
normal variants. So pattern matching is compiled as a binary tree of
"if" statements. Same thing happens in C when you switch on scattered
cases.

I did benchmarks a long time ago, and the overhead was rather costly
with the bytecode interpreter, which has a builtin table-switch
operation. Something like 3 times slower for a 10 way match,
which just corresponds to the depth of the decision tree. Yet this is
logarithmic, so a 100-way match would still only be around 6 times
slower.

However I was surprised to see that with the native code compiler
polymorphic variants appeared to be faster than normal ones. That
seems to mean than on modern CPUs, an indirect jump is about 3 times
more expansive than a conditional, and that polymorphic variants are
only going to be slow on huge matches. But this was a single, very
simple benchmark, so I'm not sure this behaviour is stable.

So, I wouldn't suggest using polymorphic variants to encode
instructions in a virtual machine (too many cases), but in almost any
other cases the overhead should be neglectable anyway. Keeping typing
straightforward is another problem.

Jacques Garrigue