Stack overflow serialising long list

[ian-barnes]

Serialising an array with many (i.e. hundreds of thousands) elements using the generated to_yojson function produced a stack overflow. Tracked this down to the use of List.map in this snippet of the generated code:

fun x ->
  `List
    (List.map
      (fun x ->
        <element-type>.to_yojson x) x)

Replacing List.map with the tail-recursive List.rev_map fixes this but reverses the order. Calling List.rev on the result of List.rev_map should generate correct results without the risk of a crash, but at a performance penalty.

[AlexKnauth]

Is this a known limitation of List.map, or is it something that can be fixed on the List.map side?

Could List.map detect when it would otherwise overflow the stack, and if it would, allocate on the heap instead? (That's basically what the rev_map rev thing would do, but only in the just-before-overflow special case.)

[ian-barnes]

It's a known limitation of List.map, mentioned in the documentation. See https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html:

val map : ('a -> 'b) -> 'a list -> 'b list
List.map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f. Not tail-recursive.
...
val rev_map : ('a -> 'b) -> 'a list -> 'b list
List.rev_map f l gives the same result as List.rev (List.map f l), but is tail-recursive and more efficient.

There are alternative smarter versions of map that do the sort of thing you're suggesting, but then you'd have to weigh up whether it's worth adding a dependency. See for example https://discuss.ocaml.org/t/a-new-list-map-that-is-both-stack-safe-and-fast/865/25.

[ian-barnes]

Actually the OCaml-containers CCList.map does exactly what you're suggesting, with different behaviour depending on the length of the list. See https://github.com/c-cube/ocaml-containers/blob/8e3dc5e006cfd82c78c7784b366b637189191d07/src/core/CCList.ml#L104

[AlexKnauth]

Now is it worth a dependency on ocaml-containers or some other package that implements map properly?

• yes -> depend on package, use their map function instead
• no -> implement map here in ppx_deriving_yojson_runtime.ml ??

[gasche]

No, I don't think this is worth an extra dependency. We could just use List.rev (List.rev_map f li) for now, and wait for tail-recursion modulo cons to arrive so that List.map becomes tail-recursive again.

[AlexKnauth]

Is there a length of list to check that would be a stack overflow on most machines?

I'm trying to make a test that would fail with the current implementation but succeed with a stack-safe rev and rev_map. However, the tests I've tried aren't even failing when I use a list of length 1000000 (1 million).

[gasche]

On my machine ulimit -s reports a stack-size limit of 8192. My suspicion is that the test you generate is not hitting this List.map call, because I think a million elements should blow the stack on basically any machine.

P.S.: I can't read the integer literal you wrote to check that it is a million, do not hesitate to use underscores in numeric literals: 1_000_000 is immediately checkable for me.

[ian-barnes]

Nice! Many thanks. I think it's an improvement. Can't really see any serious downsides...

I'm not super-familiar with GitHub processes... My understanding is that this is now merged back to the master branch but not yet released. Is that correct? When do you anticipate making a new release with this change included in it?