From: Jon Harrop <jon@ffconsultancy.com>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Re: Hash clash in polymorphic variants
Date: Tue, 15 Jan 2008 04:59:03 +0000 [thread overview]
Message-ID: <200801150459.03896.jon@ffconsultancy.com> (raw)
In-Reply-To: <20080115.123621.184910428.garrigue@math.nagoya-u.ac.jp>
On Tuesday 15 January 2008 03:36:21 Jacques Garrigue wrote:
> Unfortunately, this would make marshalling between different programs
> much more complicated...
Do people marshal polymorphic variants between different programs?
> Another advantage of knowing the hash function at compile time is
> that you can generate efficient code for pattern matching. Since you
> already know the ordering of tags, it is easy to generate a decision
> tree. I didn't check very recently about efficiency for polymorphic
> variants, but the depth of the decision tree is logarithmic in the
> number of tags involved in the pattern matching, and if you can keep
> it below 3 or 4 (about 10 tags) you can be actually faster than a
> jump table.
For 3-16 tags on AMD64, jump tables (ordinary variants) are 2x slower than
decision trees (polymorphic variants) when branches are taken at random.
However, jump tables are consistently up to 2x faster when a single branch is
taken repeatedly. So caching jump tables is more effective at run-time
optimizing pattern matches over ordinary variants than branch prediction is
at optimizing decision trees for pattern matches over polymorphic variants.
So the advantage of a decision tree is probably insignificant on real code
because it will lie between these two extremes.
> Now concerning the risks of name conflicts. The main point of
> polymorphic variants is that there is only a conflict if the two tags
> appear in the same type. And logically the type should stay small.
> If you want to put all GLenum's inside the same type, then you may
> well end up with conflicts. But what LablGL shows is that in practice
> only a small number of tags are used together.
Can LablGL's design support OpenGL extensions?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
next prev parent reply other threads:[~2008-01-15 5:06 UTC|newest]
Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-01-10 17:09 Jon Harrop
2008-01-10 20:35 ` [Caml-list] " Eric Cooper
2008-01-10 21:24 ` Jon Harrop
2008-01-10 21:40 ` David Allsopp
2008-01-11 13:30 ` Kuba Ober
2008-01-11 13:48 ` Jon Harrop
2008-01-11 16:14 ` Kuba Ober
2008-01-11 18:40 ` David Allsopp
2008-01-14 12:20 ` Kuba Ober
2008-01-14 14:44 ` Stefan Monnier
2008-01-14 14:56 ` [Caml-list] " Kuba Ober
2008-01-14 15:37 ` David Allsopp
2008-01-14 15:44 ` Kuba Ober
2008-01-14 16:03 ` David Allsopp
2008-01-14 15:45 ` Stefan Monnier
2008-01-15 3:36 ` [Caml-list] " Jacques Garrigue
2008-01-15 4:59 ` Jon Harrop [this message]
2008-01-15 9:01 ` Jacques Garrigue
2008-01-15 18:17 ` Jon Harrop
2008-01-15 19:20 ` Gerd Stolpmann
2008-01-15 22:04 ` Jon Harrop
2008-01-16 13:48 ` Kuba Ober
2008-01-16 15:02 ` Dario Teixeira
2008-01-16 19:00 ` Jon Harrop
2008-01-17 13:09 ` Kuba Ober
2008-01-18 5:33 ` Kuba Ober
2008-01-18 5:19 ` Kuba Ober
2008-01-18 5:39 ` Kuba Ober
2008-01-16 3:26 ` Jacques GARRIGUE
2008-01-16 3:34 ` Yaron Minsky
2008-01-16 3:42 ` Jon Harrop
2008-01-16 4:40 ` Jon Harrop
2008-01-16 16:03 ` Eric Cooper
2008-01-16 10:50 ` Richard Jones
2008-01-14 17:14 ` Jon Harrop
2008-01-14 17:36 ` Alain Frisch
2008-01-11 0:15 ` [Caml-list] " Jacques Garrigue
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=200801150459.03896.jon@ffconsultancy.com \
--to=jon@ffconsultancy.com \
--cc=caml-list@yquem.inria.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