From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 171A78239C for ; Fri, 22 Dec 2017 12:56:29 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=nicolas.ojeda.bar@lexifi.com; spf=SoftFail smtp.mailfrom=nicolas.ojeda.bar@lexifi.com; spf=None smtp.helo=postmaster@vrout10.yaziba.net Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of nicolas.ojeda.bar@lexifi.com) identity=pra; client-ip=185.56.204.32; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.ojeda.bar@lexifi.com"; x-sender="nicolas.ojeda.bar@lexifi.com"; x-conformance=sidf_compatible Received-SPF: SoftFail (mail3-smtp-sop.national.inria.fr: domain of nicolas.ojeda.bar@lexifi.com is inclined to not designate 185.56.204.32 as permitted sender) identity=mailfrom; client-ip=185.56.204.32; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.ojeda.bar@lexifi.com"; x-sender="nicolas.ojeda.bar@lexifi.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@vrout10.yaziba.net) identity=helo; client-ip=185.56.204.32; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.ojeda.bar@lexifi.com"; x-sender="postmaster@vrout10.yaziba.net"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AT/URQRMO+jPpgrQT/pcl6mtUPXoX/o7sNwtQ0KIM?= =?us-ascii?q?zox0I/z/rarrMEGX3/hxlliBBdydt6odzbKO+4nbGkU4qa6bt34DdJEeHzQksu?= =?us-ascii?q?4x2zIaPcieFEfgJ+TrZSFpVO5LVVti4m3peRMNQJW2aFLduGC94iAPERvjKwV1?= =?us-ascii?q?Ov71GonPhMiryuy+4ZLebxlViDanfb9+MAi9oBnMuMURnYZsMLs6xAHTontPde?= =?us-ascii?q?RWxGdoKkyWkh3h+Mq+/4Nt/jpJtf45+MFOTav1f6IjTbxFFzsmKHw65NfqtRbY?= =?us-ascii?q?UwSC4GYXX3gMnRpJBwjF6wz6Xov0vyDnuOdxxDWWMMvrRr0vRz+s87lkRwPpiC?= =?us-ascii?q?cfNj427mfXitBrjKlGpB6tvgFzz5LIbI2QMvd1Y6HTcs4ARWdZXMlRWSxPDI2/?= =?us-ascii?q?YYUSEeQOIf1VoJPhq1YUtxayGRWgCeHpxzRVhnH2x6o60+E5HA/e3QwvA9UOsH?= =?us-ascii?q?DWq9XuLKgcSOK1w7fVwjrZd/xbxDL66JLVeR0mp/GMXK5/cc3VyUY1DAPJlFKQ?= =?us-ascii?q?qY77MDyIzOsBqXOU4PB6Ve+0j24otQ5wojmhxsctkIXGmoUVylXd+Ch/3Y07K9?= =?us-ascii?q?q4SEthbt6lFptdry+aN4xxQs84RmFovD42yrIHuZ6nfCgK1Y8oywTDZPyAdoiF?= =?us-ascii?q?5A/oWuWJITpgmX5oe7Kyiwyy/EWh0OHwSNW43VlQoidLjNXArm4B2wDX58SdSf?= =?us-ascii?q?Zw/l2t1SiS2w3S8O1IPEM5mbTdJpU82LA/jIATvl7GHiLumEX5kquWdkI89+i2?= =?us-ascii?q?8eTnZajmpoOBO4NokA3/Mr4hm82+AesjKAcCRW6b9vqg1LH7/E35RqtFjuEun6?= =?us-ascii?q?XEs53XJd4Xq664DgNPzIov9xmyAy2o3dgGhXUHKUhKeBODj4jnIVHOJ/X4AO+5?= =?us-ascii?q?g1StjDhrwPTGMaf6ApnXKXjDkqnucqtn5EJG0wU818pf6olQCr4fL/PzW0HxtN?= =?us-ascii?q?3CAhAlNAy0xv7rCM9h2YMGRWKPHqiZPbvOvlCS4+IvJ/CAZIsUuDbmN/go/OXu?= =?us-ascii?q?jH88mV8FZ6alx5oXaHaiHvRnOUqVe3Tsgs0ZHWcPuQoxUfLlhUWZUT5We3ayR6?= =?us-ascii?q?U85iwnCNHuMYCWY4mxjb7J/yBJm54eMmVPC1SkFH70eofBWPAXaSHUJMJ9xG8q?= =?us-ascii?q?T7+kHqkg3haqPRTN7LhqIuPj0KEC/cbl1dNy4+TI0xYw+DB9Sc6UyUmJQnF1kG?= =?us-ascii?q?JOTDgzivMs6Xdhw0uOhPAry8dTEsZesrYQCl83?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CYAQCj8jxafSDMOLldHAEBAQQBAQoBA?= =?us-ascii?q?YQkdCcHg3+BOZd9ggEUlyiCAQolg11VZAKERwdDFAEBAQEBAQEBAQESAQELFAh?= =?us-ascii?q?XgjgkAYJHAQICASMEUgULCQILNwICIhIBBQEcBhOKJggEAQuHaJEcQIwQgW06i?= =?us-ascii?q?FOCAwEBAQcBAQEBASOEC4IShm2DLwGBNhgBAYM1gmUFik6Ye4gBg3GJPZN6jSG?= =?us-ascii?q?JShQFH4EVAjZHgSpvUTIGgXEJghI5HBmBT3cFh0CCOwEBAQ?= X-IPAS-Result: =?us-ascii?q?A0CYAQCj8jxafSDMOLldHAEBAQQBAQoBAYQkdCcHg3+BOZd?= =?us-ascii?q?9ggEUlyiCAQolg11VZAKERwdDFAEBAQEBAQEBAQESAQELFAhXgjgkAYJHAQICA?= =?us-ascii?q?SMEUgULCQILNwICIhIBBQEcBhOKJggEAQuHaJEcQIwQgW06iFOCAwEBAQcBAQE?= =?us-ascii?q?BASOEC4IShm2DLwGBNhgBAYM1gmUFik6Ye4gBg3GJPZN6jSGJShQFH4EVAjZHg?= =?us-ascii?q?SpvUTIGgXEJghI5HBmBT3cFh0CCOwEBAQ?= X-IronPort-AV: E=Sophos;i="5.45,440,1508796000"; d="scan'208,217";a="249273164" Received: from vrout10.yaziba.net ([185.56.204.32]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 22 Dec 2017 12:56:14 +0100 Received: from mtaout10.int.yaziba.net (mtaout10.int.yaziba.net [10.4.20.36]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by vrout10.yaziba.net (mx10.yaziba.net) with ESMTPS id E251A522C6 for ; Fri, 22 Dec 2017 12:56:13 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by mtaout10.int.yaziba.net (Postfix) with ESMTP id DCC1016038C for ; Fri, 22 Dec 2017 12:56:13 +0100 (CET) X-Virus-Scanned: amavisd-new at Received: from mtaout10.int.yaziba.net ([127.0.0.1]) by localhost (mtaout10.int.yaziba.net [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id j2Q2debXa3mO for ; Fri, 22 Dec 2017 12:56:13 +0100 (CET) Received: from mail-qt0-f182.google.com (mail-qt0-f182.google.com [209.85.216.182]) by mtaout10.int.yaziba.net (Postfix) with ESMTPSA id 99B27160381 for ; Fri, 22 Dec 2017 12:56:13 +0100 (CET) Received: by mail-qt0-f182.google.com with SMTP id e2so36015067qti.0 for ; Fri, 22 Dec 2017 03:56:13 -0800 (PST) X-Gm-Message-State: AKGB3mJbXkfFnTv3YfD4Mn539W6fLGSnGo9ytRDXYna3a5b8UJNKXADP VU1OpMIVyKHKrXZa2r8qWFRZH4DEjVtoZTUsSNc= X-Google-Smtp-Source: ACJfBouUjImRRQDTns0GgdKOvVlQnLsrdjeaY0v/CjDKGwKS8cKSjiH9Rd0mrMIdEKfsb1Vjfymk+Z1gLcBz2gcUXZc= X-Received: by 10.200.46.50 with SMTP id r47mr19163130qta.314.1513943772545; Fri, 22 Dec 2017 03:56:12 -0800 (PST) MIME-Version: 1.0 Received: by 10.200.24.163 with HTTP; Fri, 22 Dec 2017 03:55:52 -0800 (PST) In-Reply-To: <64f1e880-fb8c-4432-3597-3485ec06c046@matej-kosik.net> References: <64f1e880-fb8c-4432-3597-3485ec06c046@matej-kosik.net> From: =?UTF-8?Q?Nicol=C3=A1s_Ojeda_B=C3=A4r?= Date: Fri, 22 Dec 2017 12:55:52 +0100 X-Gmail-Original-Message-ID: Message-ID: To: =?UTF-8?B?TWF0ZWogS2/FocOtaw==?= Cc: OCaml Mailing List Content-Type: multipart/alternative; boundary="001a1137b0f6c5d0cf0560ec801c" X-DRWEB-SCAN: ok X-VRSPAM-SCORE: -100 X-VRSPAM-STATE: legit X-VRSPAM-CAUSE: gggruggvucftvghtrhhoucdtuddrgedtuddrgeekgdefgecutefuodetggdotefrucfrrhhofhhilhgvmecuggftfghnshhusghstghrihgsvgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhepjghfhfffkffuvfgtsegrtderredttdejnecuhfhrohhmpefpihgtohhljohspgfqjhgvuggrpgeumohruceonhhitgholhgrshdrohhjvggurgdrsggrrheslhgvgihifhhirdgtohhmqeenucffohhmrghinhepfhhoohdrmhhlpdhgihhthhhusgdrtghomhenucfkphepvddtledrkeehrddvudeirddukedvnecurfgrrhgrmhepmhhouggvpehsmhhtphhouhht X-VRSPAM-EXTCAUSE: mhhouggvpehsmhhtphhouhht Subject: Re: [Caml-list] =?UTF-8?Q?stdlib_=E2=86=92_Queue_=E2=86=92_iter_?= =?UTF-8?Q?=3A_implementation_question_/_=28possibly=29_bikeshedding?= --001a1137b0f6c5d0cf0560ec801c Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Dear Matej, The reason is efficiency: absent any special optimizations, functions with free variables need to allocate a closure for their values in order to be able to find them when needed. On top of the allocation of the closure, any access to a free variable will have to go through the closure adding the cost of an extra indirection. No such penalties are paid in the absence of free variables. You can see this quite clearly in a simple example if you inspect the C-- intermediate language: if foo.ml contains let f x y =3D let g u =3D x + u in g y then g is allocated a closure due to its free variable x and ocamlopt -dcmm -inline 0 -c foo.ml shows (function{foo.ml:1,6-40} camlFoo__f_1328 (x/1329: val y/1330: val) (let g/1331 (alloc block-hdr(3319){foo.ml:2,8-17} "camlFoo__g_1331" 3 x/1329) (app{foo.ml:3,2-5} "camlFoo__g_1331" y/1330 g/1331 val))) (function{foo.ml:2,8-17} camlFoo__g_1331 (u/1332: val env/1337: val) (+ (+ (load val (+a env/1337 16)) u/1332) -1)) where you can see the allocation of the closure for g with (alloc block-hdr(3319) ...) and the extra indirection to access x in this closure with (load val (+ env 16))). On the other hand, if we pass x explicitly, as in let f x y =3D let g x u =3D x + u in g x y then no closure required and ocamlopt -dcmm -inline 0 foo.ml shows (function{foo.ml:1,6-44} camlFoo__f_1328 (x/1329: val y/1330: val) (let g/1331 "camlFoo__3" (+ (+ x/1329 y/1330) -1))) (function{foo.ml:2,8-19} camlFoo__g_1331 (x/1332: val u/1333: val) (+ (+ x/1332 u/1333) -1)) where you can see that no closure is allocated and no indirection is needed to access x. Best wishes, Nicol=C3=A1s On Fri, Dec 22, 2017 at 12:05 PM, Matej Ko=C5=A1=C3=ADk wrote: > Hi, > > I just had a look at Queue.iter function as it is implemented by Ocaml > standard library. > > The original version > > (* https://github.com/ocaml/ocaml/blob/c08532f561548f6164278ba0d156da > 841aefe44a/stdlib/queue.ml#L100-L108 *) > > let iter =3D > let rec iter f cell =3D > match cell with > | Nil -> () > | Cons { content; next } -> > f content; > iter f next > in > fun f q -> iter f q.first > > I am wondering about two things. > > ------------------------------------------------------------ > -------------------- > > (1) > > Why is the original implementation preferred over > > let iter f =3D > let rec iter cell =3D > match cell with > | Nil -> () > | Cons { content; next } -> > f content; > iter next > in > fun q -> iter q.first > > where "f" would be bound once and then reused as many times as necessary > (instead of passed over and over again within the inner "iter" loop). > > ------------------------------------------------------------ > -------------------- > > (2) > > Why is the original implementation preferred over the following version > > let iter f q =3D > let rec iter cell =3D > match cell with > | Nil -> () > | Cons { content; next } -> > f content; > iter next > in > iter q.first > > ? > > Similar decisions where made elsewhere in stdlib so I am wondering what am > I missing? > > --001a1137b0f6c5d0cf0560ec801c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear Matej,

The reason is efficiency: a= bsent any special optimizations, functions with free variables need to allo= cate a closure for their values in order to be able to find them when neede= d.
On top of the allocation of the closure, any access to a free = variable will have to go through the closure adding the cost of an extra in= direction.

No such penalties are paid in the absen= ce of free variables.

You can see this quite c= learly in a simple example if you inspect the C-- intermediate language: if= foo.ml contains
=
=C2=A0 let f x y =3D
=C2=A0 =C2=A0 let g u = =3D x + u in
=C2=A0 =C2=A0 g y

the= n g is allocated a closure due to its free variable x and ocamlopt -dcmm -i= nline 0 -c foo.ml shows

=C2=A0 (function{foo.ml:1,6-40} camlFoo__f_1328 (x/1329: val y/1330: val)=
=C2=A0 =C2=A0(let
=C2=A0 =C2=A0 =C2=A0g/1331 (alloc bl= ock-hdr(3319){foo.ml:2,8-= 17} "camlFoo__g_1331" 3 x/1329)
=C2=A0 =C2=A0 =C2=A0(ap= p{foo.ml:3,2-5} "cam= lFoo__g_1331" y/1330 g/1331 val)))

=C2=A0 (fu= nction{foo.ml:2,8-17} cam= lFoo__g_1331 (u/1332: val env/1337: val)
=C2=A0 =C2=A0(+ (+ (load= val (+a env/1337 16)) u/1332) -1))

where yo= u can see the allocation of the closure for g with (alloc block-hdr(3319) .= ..) and the extra indirection to access x in this closure with (load val (+= env 16))).

On the other hand, if we pass x explic= itly, as in

=C2=A0 let f x y =3D
=C2=A0 = =C2=A0 let g x u =3D x + u in
=C2=A0 =C2=A0 g x y

<= /div>
then no closure required and ocamlopt -dcmm -inline 0 foo.ml shows

<= div>
=C2=A0 (function{foo= .ml:1,6-44} camlFoo__f_1328 (x/1329: val y/1330: val)
=C2=A0 = =C2=A0(let g/1331 "camlFoo__3" (+ (+ x/1329 y/1330) -1)))

=C2=A0 (function{foo.ml:2,8-19} camlFoo__g_1331 (x/1332: val u/1333: val)
=C2=A0 =C2=A0(+ (+ x/1332 u/1333) -1))

whe= re you can see that no closure is allocated and no indirection is needed to= access x.

Best wishes,
Nicol=C3=A1s



On Fri, Dec 22, 2017 at 12:05 PM, Matej Ko= =C5=A1=C3=ADk <mail@matej-kosik.net> wrote:
Hi,

I just had a look at Queue.iter function as it is implemented by Ocaml stan= dard library.

The original version

=C2=A0 (* https://github.com/ocaml/ocaml/blob/c08532f561548f616= 4278ba0d156da841aefe44a/stdlib/queue.ml#L100-L108 *)

=C2=A0 let iter =3D
=C2=A0 =C2=A0 let rec iter f cell =3D
=C2=A0 =C2=A0 =C2=A0 match cell with
=C2=A0 =C2=A0 =C2=A0 | Nil -> ()
=C2=A0 =C2=A0 =C2=A0 | Cons { content; next } ->
=C2=A0 =C2=A0 =C2=A0 =C2=A0 f content;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 iter f next
=C2=A0 =C2=A0 in
=C2=A0 fun f q -> iter f q.first

I am wondering about two things.

-----------------------------------------------------------------= ---------------

(1)

Why is the original implementation preferred over

=C2=A0 let iter f =3D
=C2=A0 =C2=A0 let rec iter cell =3D
=C2=A0 =C2=A0 =C2=A0 match cell with
=C2=A0 =C2=A0 =C2=A0 | Nil -> ()
=C2=A0 =C2=A0 =C2=A0 | Cons { content; next } ->
=C2=A0 =C2=A0 =C2=A0 =C2=A0 f content;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 iter next
=C2=A0 =C2=A0 in
=C2=A0 =C2=A0 fun q -> iter q.first

where "f" would be bound once and then reused as many times as ne= cessary
(instead of passed over and over again within the inner "iter" lo= op).

-----------------------------------------------------------------= ---------------

(2)

Why is the original implementation preferred over the following version

=C2=A0 let iter f q =3D
=C2=A0 =C2=A0 let rec iter cell =3D
=C2=A0 =C2=A0 =C2=A0 match cell with
=C2=A0 =C2=A0 =C2=A0 | Nil -> ()
=C2=A0 =C2=A0 =C2=A0 | Cons { content; next } ->
=C2=A0 =C2=A0 =C2=A0 =C2=A0 f content;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 iter next
=C2=A0 =C2=A0 in
=C2=A0 =C2=A0 iter q.first

?

Similar decisions where made elsewhere in stdlib so I am wondering what am = I missing?


--001a1137b0f6c5d0cf0560ec801c--