Re: [Caml-list] tail-recursion vs. no tail-recursion in list functions

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: sebastian.egner@philips.com

> Did anybody every consider the following simple solution for the 'map' 
> problem?
> 
> let unbreakable_map f xs =
>     let rec 
>       map limit f xs = (* recursion depth limited to limit *)
>         match xs with
>           []                   -> []
>         | x::xs when limit > 0 -> let f_x = f x in f_x::(map (limit-1) f 
> xs)
>         | _                    -> List.rev_append (List.rev_map f xs) []
>     in  map 512 f xs;;
> 
> The function is not tail-recursive for lists of length up to
> 512---at which point it switches to a tail-recursive algorithm and
> uses the heap instead of the stack to keep track of structural
> recursion.

I just tried to do it, and it seems to work well. The
overhead of the counter is really small.
Note that in the long list case I call the extlib map function rather
than rev o rev_map, as it performs better on such long lists.

Results: (ocamlopt, limit=1000)
using List.map
l10*10000: 0.117188s
l100*1000: 0.132812s
l1000*100: 0.195312s
l10000*10: 0.843750s
l100000*1: 3.328125
using your approach (reverting to ExtLib.List.map)
l10'*10000: 0.140625s
l100'*1000: 0.140625s
l1000'*100: 0.203125s
l10000'*10: 1.265625s
l100000'*1: 1.945312s
using ExtLib.List.map
l10'*10000: 0.187500s
l100'*1000: 0.203125s
l1000'*100: 0.304688s
l10000'*10: 1.382812s
l100000'*1: 1.937500s

The performance is even better with append, and with bytecode also.
So this seems that at least extlib could use that.

One criticism is that it is not really tail recursive, as it consumes
some large amount of stack, albeit limited. Brian seemed to imply that he
has programs for which even this would be bad, but I'm really curious
to such case. Basically it would mean using map recursively rather
deep, meaning exponential runtime anyway, so I'm not sure this is a
problem.

> Since the "magic number" 512 necessarily represents a trade-off, I
> would like to see it being chosen at the time the Ocaml compiler is
> constructed for a specific target architecture, i.e. at the time
> somebody more or less knows the stack size.

Honestly, this part is going to be difficult.
And I'm not sure it is that relevant anyway.
A fixed value already gives safety, good performance on small lists,
and reasonable overall performance.

Jacques Garrigue