Consider the following lazy list type, similar to Seq.t.
type 'a lazylist = 'a node Lazy.t
and 'a node = Cons of 'a * 'a lazylist | Nil
I realize such a thing is rarely used in OCaml—though if you look at the implementation of Seq.memoize, a roughly equivalent structure is used internally.
I also understand that one drawback is that such a list is built in memory, and checking the state tag is just one more thing for the CPU to do—both undesirable if you only iterate over the data once, where one is better served by Seq.t (or just list in some cases).
I’m just wondering if it’s really so bad. Obviously, like Seq.t, map/filter type operations will not build out the list at all. The real concern, I suppose, must be once iteration actually occurs.
I don’t know a ton about OCaml’s GC and what’s coming might be a stupid question, but is this really so bad? Won’t GC just clean up nodes that don’t have any references left, or will the whole list be built and not collected until the iteration function completes?
I guess I’m just confused why I never, er, uh, rarely see any lazy lists in OCaml. What’s the hold up?
Interestingly enough, I had this same question while trying to translate the Power series, power serious lazy sequence technique into OCaml. I expected to get a magic speedup switching coefficient representation from bare Seq.t to the memoized variant, but it did not perform anywhere near how I expected (or even in the same ballpark as a naive Haskell implementation). I assumed I just had some perf bug somewhere (which may still be the case), but now I wonder how much that can be attributed to Seq memoization.
I’m still curious about what the expected memory retention is in any case. If you do not retain references to the head of a memoized Seq.t, is it at least in theory eligible for collection? In particular, I’m trying to understand this comment and why it would even be possible for a tail to retain a reference to some “earlier” head (unless your generating closure was cyclic).
Yeah, the lazy keyword in OCaml works much differently than laziness in GHC.
In OCaml, it’s basically just this:
type 'a lazy_node =
| Suspension of unit -> 'a
| Value of 'a
type 'a my_lazy = 'a node ref
let force lz =
match !lz with
| Value v -> v
| Suspension s ->
let v = s () in
lz := Value v;
v
It has a more efficient memory representation internally, but it’s basically always checking a tag when you access the value. GHC uses this graph reduction approach to laziness (GHC doesn’t use graph reduction after all, but does use a graph-based approach), where it can check if entire branches of code have been evaluated and save on a lot of these redundant checks.
So it doesn’t surprise me that a lazy list in Haskell will be faster in basically all cases than in OCaml. What does surprise me is that OCaml’s lazy list is so slow that it’s almost never used in practice.
Note that the GC does shortcut pointers to already-forced lazy values, in contrast to always checking a tag. This reminded me of some previous discussion on the performance of laziness in OCaml vs Haskell. OCaml’s lazy is designed for nontrivial computations whose values will be used multiple times, not very cheaply computed values which will be used once.
What I understand from this thread is that the optimization was partially removed in 4.13 and only applied in cases where the lazy value is forced before the next minor GC, and it sounds like it was fully removed in 5.0. Perhaps there are more updates regarding this optimization that don’t appear in the thread?
To be more precise, the OCaml runtime always checks the tag. It is just that, after pointer short-cutting, it does not need to dereference a pointer to get to the forced value. It also means that the lazy block can be collected, hence freeing two words of memory a bit earlier. But at no point does the tag check disappears.
I might have phrased this a bit wrong. What I mean is that I observe that OCaml programmers rarely use lazy lists. Them being too slow is a hypothesis as to why that might be—but if there’s no evidence to support this, I guess it must be another reason.
I’m still trying to find out the reason why people don’t use them.
I don’t think the issue is speed in the sense you’re talking about. It has to do with them not being entirely first class unlike Haskell, and also with the fact that eager evaluation is generally easier to reason about and to get predictable performance from. Lazy values are a very specific tool, and there aren’t many cases where you absolutely need them, which is why most languages don’t even have them.