From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 6E85ABB9C for ; Sun, 27 Nov 2005 06:06:34 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAR56XEJ019063 for ; Sun, 27 Nov 2005 06:06:34 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id GAA12477 for ; Sun, 27 Nov 2005 06:06:33 +0100 (MET) Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.206]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAR56WXa024880 for ; Sun, 27 Nov 2005 06:06:33 +0100 Received: by zproxy.gmail.com with SMTP id n29so2747867nzf for ; Sat, 26 Nov 2005 21:06:32 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=QFn4jbHEpSyTY8dKFe2LGpUUtq9CjJTeleVWQrQ7r+/f/xxXJ09QzWFCR3UjnKP0n8fjJx/0Z54AXFahfLK8mqvxMqM3FP9USgkYzMDQZosZ88tHg9j6PT+U8CxKpUgtAX5OIIcJDFF67T2QZ1WiQjxSbPdccK0VOSJAg2gjtJg= Received: by 10.65.214.4 with SMTP id r4mr155088qbq; Sat, 26 Nov 2005 21:06:32 -0800 (PST) Received: by 10.65.192.4 with HTTP; Sat, 26 Nov 2005 21:06:32 -0800 (PST) Message-ID: Date: Sun, 27 Nov 2005 00:06:32 -0500 From: "Michael D. Adams" To: caml-list@inria.fr Subject: Re: [Caml-list] Efficency of varient types In-Reply-To: <4387ACC9.2040107@motion-twin.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <4387ACC9.2040107@motion-twin.com> X-Miltered: at concorde with ID 43893EDA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 43893ED8.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 cannasse:01 ncannasse:01 motion-twin:01 ocaml:01 ackermann:01 ackermann:01 ocamlopt:01 ocaml:01 model:01 runtime:01 unboxed:01 pointers:01 variants:01 booleans:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled version=3.0.3 On 11/25/05, Nicolas Cannasse wrote: > Michael D. Adams wrote: > > I have recently learned about OCaml and have been impressed by how > > fast it is in the benchmarks. However I have discovered that variant > > types can slow down a program quite a bit. For example, consider the > > Ackermann function implemented for int (see program 1) and the same > > Ackermann function implemented for a "type value =3D Int of int | Strin= g > > of int" (program 2). The second one is ten times slower! (Using > > ocamlopt.) > > In order to understand what there is such difference, it's useful to > learn the ocaml memory model at runtime : > > - int are 31 bits unboxed value with last bit set to 1 in order to > differenciate them with GC allocated pointers. > - tagged variants are GC allocated blocks with a discriminating "tag" in > the header. > - chars and booleans are integers at runtime That all makes sense. > The second bit is used to mark an exception but it's only internal and > temporary when dealing with callbacks. Could to elaborate on this "second bit"? (I assume you mean the bit in the two's position.) Or is there a document that might describe it? I am very interested in how this bit is used and whether the GC will ignore values ending with the bits 10. > If you have a tagged variant where all constructors have a parameter, > you can use Obj module to unbox the Int variant but the code is a lot > less readable. I agree, which is why it was my hope that OCaml might do some of that for me. Consider a home brew bool type, "type mybool =3D Mytrue | Myfalse". If the compiler were smart enough, it could represent that as an unboxed type. From there it might be a small step to semi-unboxed types such as the one I started this discussion with, "type value =3D Int of int | Bool of bool | String of string". It sounds like that is not possible, so I have to settle for the Obj module= . Michael D. Adams mdmkolbe@gmail.com P.S. I should note that experiments using the Obj module to manually do semi-boxing show very good performance. The following code performs only 50% slower than a completely unboxed version. Compare that with 900% slower with boxed, variant types. let plus x y =3D if Obj.is_int (Obj.repr x) && Obj.is_int (Obj.repr y) then Obj.magic ((Obj.magic x) + (Obj.magic y)) else Obj.magic (0) let minus x y =3D if Obj.is_int (Obj.repr x) && Obj.is_int (Obj.repr y) then Obj.magic ((Obj.magic x) - (Obj.magic y)) else Obj.magic (0) let zero =3D 0 let one =3D 1 let rec ack m n =3D if m =3D zero then plus n one else if n =3D zero then ack (minus m one) one else ack (minus m one) (ack m (minus n one)) let _ =3D ack (3) (9)