[Caml-list] teil recursive function and GC

[Christophe Raffalli <raffalli@univ-savoie.fr>]

Hello,

It seems that the two follwing functions are not equivalent: the tail
recursive version keeps pointers on all the intermediate sets and use a
huge amount of memory (with around 200000 triangles) while the
imperative version works well.

I think the compiler should generate code that do not keep useless
pointer accessible by the GC for tail recursive function calls (and also
for other function call) ?

(I use ocaml-3.03 with the native code compiler)

Imperative version (it is only a piece of my code):

  let vertices_number = 
    let adone = ref Vertex_set.empty in
    let count_vertices (p1,p2,p3) =
      adone := Vertex_set.add p1 
		       (Vertex_set.add p2
			  (Vertex_set.add p3 !adone))
    in
    List.iter count_vertices triangles;
    Vertex_set.cardinal !adone
  in
  let edges_number = 
    let adone = ref Edge_set.empty in
    let count_edges (p1,p2,p3) =
      adone := Edge_set.add (p1,p2)
		         (Edge_set.add (p2,p3)
			  (Edge_set.add (p1,p3) !adone))
    in
    List.iter count_edges triangles;
    Edge_set.cardinal !adone
  in

Tail recursive version:

  let rec count_vertices adone ts =
    match ts with 
      [] -> Vertex_set.cardinal adone
    | (p1,p2,p3)::ts -> count_vertices (Vertex_set.add p1 
		       (Vertex_set.add p2
			  (Vertex_set.add p3 adone))) ts
  in
  let vertices_number = count_vertices Vertex_set.empty triangles in
  let rec count_edges adone ts =
    match ts with 
      [] -> Edge_set.cardinal adone
    | (p1,p2,p3)::ts -> count_edges (Edge_set.add (p1,p2)
		         (Edge_set.add (p2,p3)
			  (Edge_set.add (p1,p3) adone ))) ts
  in
  let edges_number = count_edges Edge_set.empty triangles in


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (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
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr