[Caml-list] stdlib → Queue → iter : implementation question / (possibly) bikeshedding

[Caml-list] stdlib → Queue → iter : implementation question / (possibly) bikeshedding

[Matej Košík]

[-- Attachment #1.1: Type: text/plain, Size: 1403 bytes --]

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/c08532f561548f6164278ba0d156da841aefe44a/stdlib/queue.ml#L100-L108 *)

  let iter =
    let rec iter f cell =
      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 =
    let rec iter cell =
      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 =
    let rec iter cell =
      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?


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [Caml-list] stdlib → Queue → iter : implementation question / (possibly) bikeshedding

[Nicolás Ojeda Bär]

[-- Attachment #1: Type: text/plain, Size: 3351 bytes --]

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 =
    let g u = 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 =
    let g x u = 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ás



On Fri, Dec 22, 2017 at 12:05 PM, Matej Košík <mail@matej-kosik.net> 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 =
>     let rec iter f cell =
>       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 =
>     let rec iter cell =
>       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 =
>     let rec iter cell =
>       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?
>
>

[-- Attachment #2: Type: text/html, Size: 5035 bytes --]