From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA03465 for caml-red; Thu, 11 Jan 2001 18:42:31 +0100 (MET) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA00193 for ; Thu, 11 Jan 2001 15:50:21 +0100 (MET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f0BEoEj22367 for ; Thu, 11 Jan 2001 15:50:20 +0100 (MET) Received: from tet.kurims.kyoto-u.ac.jp (isdnppp3.kurims.kyoto-u.ac.jp [130.54.16.104]) by kurims.kurims.kyoto-u.ac.jp (8.9.3/3.7W) with ESMTP id XAA06821; Thu, 11 Jan 2001 23:50:09 +0900 (JST) Received: from localhost (localhost [127.0.0.1]) by tet.kurims.kyoto-u.ac.jp (8.11.1/8.11.1) with ESMTP id f0BEofw00749; Thu, 11 Jan 2001 23:50:41 +0900 (JST) (envelope-from garrigue@kurims.kyoto-u.ac.jp) To: luther@dpt-info.u-strasbg.fr Cc: caml-list@inria.fr Subject: Re: Cost of polymorphic variants over normal ones. In-Reply-To: <20010111101703.A3683@lambda.u-strasbg.fr> References: <200101101825.NAA17093@labrador.eecs.harvard.edu> <20010111101703.A3683@lambda.u-strasbg.fr> X-Mailer: Mew version 1.94.2 on Emacs 20.7 / Mule 4.0 (HANANOEN) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20010111235041Z.garrigue@kurims.kyoto-u.ac.jp> Date: Thu, 11 Jan 2001 23:50:41 +0900 From: Jacques Garrigue X-Dispatcher: imput version 20000228(IM140) Sender: weis@pauillac.inria.fr From: Sven LUTHER > 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