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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 16F41BBAF; Mon, 2 Nov 2009 21:00:38 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkoDAIfJ7krBMHhLhWdsb2JhbACbVgEBAQoLCgUVwHuEPAQ X-IronPort-AV: E=Sophos;i="4.44,669,1249250400"; d="asc'?ml'?mli'?scan'208";a="36040425" Received: from net.univ-savoie.fr ([193.48.120.75]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/EDH-RSA-DES-CBC3-SHA; 02 Nov 2009 21:00:37 +0100 Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by net.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id nA2K0Vpk030733 ; Mon, 2 Nov 2009 21:00:31 +0100 Received: from [193.48.123.45] (d45.lama.univ-savoie.fr [193.48.123.45]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id nA2K0TYp013703 ; Mon, 2 Nov 2009 21:00:29 +0100 Message-ID: <4AEF3A5F.2060306@univ-savoie.fr> Date: Mon, 02 Nov 2009 21:00:31 +0100 From: Christophe Raffalli User-Agent: Thunderbird 2.0.0.23 (X11/20090817) MIME-Version: 1.0 To: Damien Doligez Cc: OCaml List Subject: Re: [Caml-list] tip for tail recursive map References: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> In-Reply-To: <8F7FB895-BC42-49C6-BAB3-4EDDF761C78B@inria.fr> X-Enigmail-Version: 0.95.7 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig61930F3BF45393982E64AEB8" X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 recursive:01 ad-hoc:01 segfaults:01 damien:01 l'':01 l'':01 trivial:01 trivial:01 xavier's:01 ocaml:01 X-Attachments: type="text/x-ocaml" name="prelist.ml" name="prelist.ml" type="text/x-ocaml" name="prelist.mli" name="prelist.mli" type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig61930F3BF45393982E64AEB8 Content-Type: multipart/mixed; boundary="------------070904060305050803050702" This is a multi-part message in MIME format. --------------070904060305050803050702 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable >=20 > You can do better with an ad-hoc encoding of the continuation > instead of using closures: >=20 > let rec map k f =3D function > | [] -> List.rev k > | x :: rl -> map (f x :: k) f rl > ;; >=20 > The memory footprint is smaller, and you spend much less time > invoking closures. >=20 > Note that I haven't bothered benchmarking these two functions. I did the benchmark with four version of map (below): List of size 10, 10000000 times with standard map : 0.948059s List of size 10, 10000000 times with map with rev : 1.800112s List of size 10, 10000000 times with map with prelist : 3.060192s List of size 10, 10000000 times with map with obj : 1.704105s List of size 100, 1000000 times with standard map : 1.068068s List of size 100, 1000000 times with map with rev : 1.448090s List of size 100, 1000000 times with map with prelist : 2.668166s List of size 100, 1000000 times with map with obj : 1.652104s List of size 1000, 100000 times with standard map : 1.792112s List of size 1000, 100000 times with map with rev : 2.912182s List of size 1000, 100000 times with map with prelist : 3.520220s List of size 1000, 100000 times with map with obj : 2.460154s List of size 10000, 10000 times with standard map : 7.564473s List of size 10000, 10000 times with map with rev : 15.452965s List of size 10000, 10000 times with map with prelist : 12.672792s List of size 10000, 10000 times with map with obj : 11.572724s List of size 100000, 1000 times with standard map : 33.018063s List of size 100000, 1000 times with map with rev : 42.142634s List of size 100000, 1000 times with map with prelist : 22.161385s List of size 100000, 1000 times with map with obj : 20.801299s standard map with size 1000000 segfaults on my machine List of size 1000000, 100 times with map with rev : 55.211450s List of size 1000000, 100 times with map with prelist : 23.549472s List of size 1000000, 100 times with map with obj : 21.777361s standard map =3D List.map map with rev =3D the above code given by Damien Doligez map with prelist =3D a dirty map using Obj but through a not too dirty, but not completely safe interface prelist (attached) : let pmap f l =3D let pl =3D start () in let rec fn =3D function [] -> Prelist.extract pl | a::l -> Prelist.cons (f a) pl; fn l in fn l map with obj : a directly dirty obj map : let objmap f l =3D match l with [] -> [] | x::l' -> let start =3D [f x] in let rec fn current =3D function [] -> start | x::l' -> let l'' =3D [f x] in Obj.set_field (Obj.repr current) 1 (Obj.repr l''); fn l'' l' in fn start l' Conclusion : dirty map wins for large lists, Standard map wins for small = lists, but if you map a non trivial function (here I map the trivial succ functi= on on int), there should be no difference so I would suggest to use map with reverse.= The conclusion is that I would replace Xavier's suggestion in another thr= ead : << Repeat after me: "Obj.magic is not part of the OCaml language". >> By << Try very very very hard not to use object. If it fails try very hard = to use Obj but no C. >> I still think Obj is safer than C (I do not speak for interfacing with ex= ternal library where C is mandatory), but you should be aware that Obj needs as much knowledge abou= t the runtime than C interface without using the provided C macro ... Cheers, Christophe --=20 Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- --------------070904060305050803050702 Content-Type: text/x-ocaml; name="prelist.ml" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="prelist.ml" type 'a prelist =3D { mutable start : 'a list; mutable current : 'a list}= let start () =3D { start =3D []; current =3D []} let cons a pl =3D match pl.current with [] -> let l =3D [a] in pl.current <- l; pl.start <- l | l ->=20 let l' =3D [a] in Obj.set_field (Obj.repr l) 1 (Obj.repr l'); pl.current <- l' let extract pl =3D=20 let r =3D pl.start in=20 pl.current <- []; pl.start <- [];=20 (* to guaranty that we can not mute the list once it has been =20 extracted *) r --------------070904060305050803050702 Content-Type: text/x-ocaml; name="prelist.mli" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="prelist.mli" type 'a prelist (* mutable type of a list under construction *) val start : unit -> 'a prelist val extract : 'a prelist -> 'a list val cons : 'a -> 'a prelist -> unit --------------070904060305050803050702-- --------------enig61930F3BF45393982E64AEB8 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iEYEARECAAYFAkrvOmMACgkQi9jr/RgYAS5hlQCdEY6x1qwzT55qnrUwRxyOsUCX Q88An2GbHiNqbTxO1DPfC+kRSIMd38Tq =QTZj -----END PGP SIGNATURE----- --------------enig61930F3BF45393982E64AEB8--