Difference between two kinds of recursive function-CodePudding

In OCaml, there are two ways I have seen to write a map function for example

let rec map f xs =
  match xs with
  | [] -> []
  | x::rest -> f x :: map f rest

and

let map f xs =
  let rec go xs = 
    match xs with
    | [] -> []
    | x::rest -> f x :: go rest
  in go xs

The second one looks like more optimizing because it is similar to loop invariant elimination but in functional programming it may involve allocating a new closure. Can anyone explain the difference between the two styles of recursive function, in particular in terms of performance? Thanks for your help!

I couldn't find similar questions in SO and I'm expecting there is a term like "recursive invariant elimination" to describe the kind of transformation from the first program to the second one.

CodePudding user response：

I've always wondered the exact same thing: does the compiler optimizes invariant argument in recursive function ? Since your question motivated me to benchmark it, let me share here my results.

Protocol

I have not tried it with map, since it would require big lists, which would result in a stack_overflow. I could try it with rev_map but i don't see the point of allocating huge lists while it's easier to test an equivalent behavior on integers (plus I'm afraid that allocations. would ultimately trigger a round of GC which would mess with my time measures).

The following code reproduces your usecase with a dummy recursive function with an invariant argument, as in map:

let rec g f x = if x = 0 then 0 else g f (f x)

let g2 f x =
  let rec aux x = if x = 0 then 0 else aux (f x) in
  aux x

let time title f x =
  let t = Sys.time () in
  let fx = f x in
  Printf.printf "%s: %fs\n%!" title (Sys.time () -. t) ;
  fx

let main =
  let nb = int_of_string Sys.argv.(1) in
  ignore (time "normal" (g pred) nb) ;
  ignore (time "invariant elimination" (g2 pred) nb)

You can compile it (ocamlopt a.ml for example) and run it by doing ./a.out 10000000000. You can obviously change the integer parameter to tune the number of recursive calls.

Results

On my computer, this outputs: 10000000000

normal: 11.813643s
invariant elimination: 11.646377s

On bigger values:

20000000000

normal: 23.353022s
invariant elimination: 22.977813s

30000000000

normal: 35.586871s
invariant elimination: 35.421313s

I didn't bother going higher. This to me seems to indicate that both versions are equivalent, maybe the compiler does optimize invariant argument in recursive function and it's just not measurable, maybe it doesn't.

I have also tried to see if the generated bytecode is the same or not (ocamlc -dinstr a.ml, and it does differ slightly as you can see in the following code snippet

normal

compiling a file with only this in it:

let g f x =
  let rec aux f x = if x = 0 then 0 else aux f (f x) in
  aux f x

    branch L2
    restart
L3: grab 1
    acc 1
    push
    const 0
    eqint
    branchifnot L4
    const 0
    return 2
L4: acc 1
    push
    acc 1
    apply 1
    push
    acc 1
    push
    offsetclosure 0
    appterm 2, 4
    restart
L1: grab 1
    closurerec 3, 0
    acc 2
    push
    acc 2
    push
    acc 2
    appterm 2, 5
L2: closure L1, 0
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal E!

invariant elimination

compiling a file with only this in it:

let g2 f x =
  let rec aux x = if x = 0 then 0 else aux (f x) in
  aux x

gives:

    branch L2
L3: acc 0
    push
    const 0
    eqint
    branchifnot L4
    const 0
    return 1
L4: acc 0
    push
    envacc 1
    apply 1
    push
    offsetclosure 0
    appterm 1, 2
    restart
L1: grab 1
    acc 0
    closurerec 3, 1
    acc 2
    push
    acc 1
    appterm 1, 4
L2: closure L1, 0
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal E2!

But i'm not expert enough to draw any conclusion as i don't speak bytecode. That's also around here that i decided that the answer is not that important for now and it's easier anyway to ask @gasche next time i see him.

CodePudding user response：

The use of go suggests a Haskell background. Both OCaml and Haskell are functional programming languages, but there are substantial differences and what one knows about Haskell should not be used to make assumptions about OCaml.

I see no particular reason to write map the second way. If you're using OCaml 4.14.0 or later, you might want to use tail_mod_cons to make map tail-recursive without an explicit accumulator as in Stef's comment.

let[@tail_mod_cons] rec map f = 
  function 
  | [] -> [] 
  | x::xs -> f x :: map f xs

And of course, the real solution is:

let map = List.map