Cost of polymorphic variants over normal ones.
Sven LUTHER
> On Thu, 11 Jan 2001, Sven LUTHER wrote:
>
> > 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.
>
> AFAIK, the hashing is done only during the compilation (or explicitly
> by external C functions). For instance (output of ocaml -dinstr):
Thanks for this info, i almost guessed that such was the cas,e but was not
sure,
Friendly,
Sven Luther
Alain Frisch
> 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.
AFAIK, the hashing is done only during the compilation (or explicitly
by external C functions). For instance (output of ocaml -dinstr):
# function `ABC -> 10 | `DEF -> 20;;
closure L1, 0
return 1
L1: const 3247170
push
acc 1
eqint
branchifnot L2
const 10
return 1
L2: const 20
return 1
> 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 ?
There may be a small overhead because the variants tags are large, so
the compiler can't use the "switch" instruction of the abstract machine.
Compare with (type t = ABC | DEF):
# function ABC -> 10 | DEF -> 20;;
closure L1, 0
return 1
L1: acc 0
switch 3 2/
L3: const 10
return 1
L2: const 20
return 1
For the native code, the difference is less visible (ocamlopt -S):
.L102:
cmpl $6494341, %eax
jne .L101
movl $21, %eax
ret
.L101:
movl $41, %eax
ret
and:
.L105:
sarl $1, %eax
testl %eax, %eax
je .L104
movl $41, %eax
ret
.L104:
movl $21, %eax
ret
(I think the new compilation scheme for pattern matching doesn't affect
these cases).
For more complex case, small value for tags allow optimizations. (see for
instance the assembler code produced for:
function `ABC -> 10 | `DEF -> 20 | `GHI -> 30;;
type t = ABC | DEF | GHI;;
function ABC -> 10 | DEF -> 20 | GHI -> 30;;
)
--
Alain Frisch
Jacques Garrigue
> 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
Markus Mottl
> 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.
This is also in accordance with a test that I did a few years ago
(in C++): I wondered whether it is more efficient to use function
pointers (jump tables) or case switches to choose the next code part
to be executed. I was surprised to find out that such tables only
started paying off at numbers of around 100 alternatives (I certainly
did this test on Intel chips, but if I remember correctly, it is also
true for Alphas). I guess this may have to do with pipelining and/or
cache effects. Processor experts can probably tell us more...
- Markus Mottl
--
Markus Mottl, mo...@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl