From: Alain Frisch <frisch@clipper.ens.fr>
To: Sven LUTHER <luther@dpt-info.u-strasbg.fr>
Cc: caml-list@inria.fr
Subject: Re: Cost of polymorphic variants over normal ones.
Date: Thu, 11 Jan 2001 11:40:05 +0100 (MET) [thread overview]
Message-ID: <Pine.GSO.4.04.10101111120260.18041-100000@clipper.ens.fr> (raw)
In-Reply-To: <20010111101703.A3683@lambda.u-strasbg.fr>
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):
# 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
next prev parent reply other threads:[~2001-01-11 17:30 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-01-10 18:25 questions about costs of nativeint vs int Norman Ramsey
2001-01-11 9:17 ` Cost of polymorphic variants over normal ones Sven LUTHER
2001-01-11 10:40 ` Alain Frisch [this message]
2001-01-11 10:44 ` Sven LUTHER
2001-01-11 14:50 ` Jacques Garrigue
2001-01-11 19:14 ` Markus Mottl
2001-01-11 18:34 ` questions about costs of nativeint vs int Xavier Leroy
2001-01-11 22:17 ` Norman Ramsey
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.GSO.4.04.10101111120260.18041-100000@clipper.ens.fr \
--to=frisch@clipper.ens.fr \
--cc=caml-list@inria.fr \
--cc=luther@dpt-info.u-strasbg.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).