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 076EABB9C for ; Sat, 26 Nov 2005 00:53:57 +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 jAPNruHh027785 for ; Sat, 26 Nov 2005 00:53:56 +0100 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 AAA21327 for ; Sat, 26 Nov 2005 00:53:56 +0100 (MET) Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.203]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAPNrtEp027781 for ; Sat, 26 Nov 2005 00:53:55 +0100 Received: by wproxy.gmail.com with SMTP id i22so1341255wra for ; Fri, 25 Nov 2005 15:53:55 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=goG2JfAaNu2cWHuuypzwXXuG14C96gtjCHiIYEthHMreQQBfziylaQsASVDpgUqQ2/jRpRy0hBthMC34FswgPguBQIlBB6ZfA9k/6yXWNJ9lR2YZNf2ByWzA5NDKVCcLrj+jhr06pRYD3VOkq4BViNgNkeGJqVKxHMLNNfhmUxY= Received: by 10.65.234.16 with SMTP id l16mr8881930qbr; Fri, 25 Nov 2005 15:53:54 -0800 (PST) Received: by 10.65.192.4 with HTTP; Fri, 25 Nov 2005 15:53:54 -0800 (PST) Message-ID: Date: Fri, 25 Nov 2005 17:53:54 -0600 From: "Michael D. Adams" To: caml-list@inria.fr Subject: Efficency of varient types MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline X-Miltered: at concorde with ID 4387A414.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4387A413.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 ackermann:01 ackermann:01 ocamlopt:01 ocaml:01 char:01 char:01 pointer:01 pointer:01 constructors:01 pointers:01 byte:01 byte:01 aligned:01 pointers: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 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 | String of int" (program 2). The second one is ten times slower! (Using ocamlopt.) I am working on a program that translates code from scheme into ocaml. (Later I will try python into ocaml.) Because it is a dynamicly typed language, the most natural translation would make everything a function of a large variant type like: type value =3D Int of int | Char of char | String of string (* etc. *) However the point of my project is to translate into *efficient* ocaml code so I would like to avoid the ten times slow down that I've seen with variant types. Is there is a way to make program 2 as fast as program 1? (Still keeping the variant type of course.) Why is program 2 so slow? Is it the cost of heap allocation? The GC? Having to access memory instead of registers? Constructor matching? One trick that I've thought of would be to push some of the tag information into the pointer. For example an Int would be represented exactly like an int (i.e. an odd address), but a String would be represented as a pointer to a block (i.e. an even address). I could hack around with the Obj module (indeed some experiments with that show very good performance), but it would be nice if there were a cleaner way such as a way to annotate constructors so OCaml tries to avoid using blocks for them. (Stuffing tags into pointers is very common in the Scheme world.) Along those lines, what does the OCaml GC do when it finds an even but not multiple of 4 pointer? Somewhere in the documentation it noted that everything is allocated on 4 byte boundaries so in theory the GC could ignore everything that is not 4 byte aligned, not just odd pointers. This would leave more bits available for stuffing the tag into the pointer. For example, XX1 could be an Int constructor, 110 a char constructor, 010 a bool constructor and X00 be a pointer to any of the constructors that are represented with blocks. Michael D. Adams mdmkolbe@gmail.com (* Program 1 *) (*************) let rec ack m n =3D if m =3D 0 then n + 1 else if n =3D 0 then ack (m - 1) 1 else ack (m - 1) (ack m (n - 1)) let _ =3D ack 3 9 (* Program 2 *) (*************) type value =3D Int of int | String of string let zero =3D Int 0 let one =3D Int 1 let plus x y =3D match x,y with | Int x,Int y -> Int (x + y) let minus x y =3D match x,y with | Int x,Int y -> Int (x - y) 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 (Int 3) (Int 9)