Tail-call optimisation not working properly on s390x machines

[icristescu]

The following code crashes with Segmentation fault on s390x machines, which is actually a stack overflow issue. The code below prints the size of the stack during a traversal of a very large map. The stack size is normally constant, but on an s309x machine, the stack is gradually growing until it raises the segmentation fault error.

module StepMap = struct
  module X = struct
    type t = string

    let compare = String.compare
  end

  include Map.Make (X)
end

type t = string StepMap.t

let add t step v = StepMap.add step v t
let rcons t s = t @ [ s ]

let stack_size p =
  let stats = Gc.stat () in
  Fmt.epr "stack_size at position %d is %d \n%!" p stats.Gc.stack_size

type ('a, 'r) cont = ('a -> 'r) -> 'r

type ('v, 'acc, 'r) folder =
  path:string list -> 'acc -> int -> 'v -> ('acc, 'r) cont

(* If we remove the [path] or the [d] argument the test passes. *)
let fold : type acc. path:string list -> t -> acc -> acc =
 fun ~path t acc ->
  let counter = ref 0 in
  let rec step : type r. (string * string, acc, r) folder =
   fun ~path:_ acc _d _h k ->
    incr counter;
    if !counter mod 20_000 = 0 then stack_size !counter;
    k acc
  and steps : type r. ((string * string) Seq.t, acc, r) folder =
   fun ~path acc d s k ->
    match s () with
    | Seq.Nil -> (k [@tailcall]) acc
    | Seq.Cons (h, t) ->
        let steps' acc = (steps [@tailcall]) ~path acc d t k in
        (* If we replace the call of [step] with its code, the test passes.*)
        (step [@tailcall]) ~path acc d h steps'
  and map : type r. (t, acc, r) folder =
   fun ~path acc d t k ->
    let bindings = StepMap.to_seq t in
    (steps [@tailcall]) ~path acc d bindings k
  in
  map ~path acc 0 t Fun.id

let test () =
  let size = 830829 in
  let t =
    List.init size string_of_int
    |> List.fold_left (fun acc i -> add acc i i) StepMap.empty
  in
  fold ~path:[] t [] |> ignore

let () = test ()

[xavierleroy]

Right, that's an old limitation of the OCaml native-code compiler: tail calls with too many arguments are turned into regular calls. "Too many" depends on the target processor, but is quite low for s390x, so this may be a reason why you saw the problem on s390x first.

At any rate, this limitation was lifted in the working sources, see #10595. So, everything should work fine in the next release of OCaml. version 4.14.

[icristescu]

Thank you for the response. I run my example with ocaml#trunk and indeed it works (constant stack size and no seg fault).