openlang
Abstraction and composition

foldl composes fine and leaks anyway

The conversation continues 4 ↓Explore the sources ↓

foldl (+) 0 over a long list is the smallest space leak I know, and it's a composition problem more than an arithmetic one. Each step builds a thunk (acc + x) that nobody forces until the end, so the accumulator grows into a chain as long as the list. foldl' from Data.List forces the accumulator to weak head normal form at every step, and the chain never forms.

The trap is that both versions have the same type. Nothing in foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b says how much memory the result holds before it is demanded. Wrap the fold in a nicer combinator and the strictness decision gets buried one level deeper, where a reader can't see it.

With optimization on, GHC's strictness analysis often rescues the plain foldl anyway. That's exactly why it catches people off guard in GHCi.

Worse, foldl' only goes to WHNF. Accumulate a pair (sum, count) and the pair constructor is evaluated while both fields stay lazy. You need strict fields or bang patterns on the components.

So I've stopped treating strictness as an optimization detail. For a combinator that folds, it belongs in the name or the docs, right next to the type.

The conversation continues 4

Follow the reasoning
  1. Permalink

    Before anyone posts a fix, say what was measured. Total bytes allocated and peak residency are different numbers, and a leak lives in the second one. A strict fold can allocate about as much as the lazy one while keeping almost nothing live. For GHC that means reading maximum residency in the -s runtime statistics, not the allocation line above it. Python's tracemalloc.get_traced_memory() returns current and peak as two numbers for the same reason.

  2. Permalink
    Following an earlier reply ↗

    Maximum residency alone won't get you to a fix. It says there is a leak, not what it's made of. So residency first, then the heap profile by closure type, -hT, which works without a profiling build, and the thunks should stand out at once. Same rule as on the JVM. Only after that do you touch a single collector flag. Tuning a collector around a thunk chain only makes the leak more comfortable.

  3. Permalink

    Names and docs won't hold this. In SQL nobody even calls it laziness, and the planner decides what actually runs from a composed view. PostgreSQL inlines a non-recursive, side-effect-free CTE that is referenced once, unless you write MATERIALIZED, so wrapping a subquery in WITH stopped acting as an optimization fence in version 12. Same query text, different evaluation, and no doc comment noticed. ilse's GHCi point says the same about GHC. Run EXPLAIN. That's where evaluation order lives.

  4. Permalink

    We could give the accumulator its own type with strict fields, something like data Acc = Acc !Int !Int. Then foldl' forcing the outer constructor forces both counts too, and the strictness is written once, where the data is defined, instead of at every fold. That may be enough for most of these combinators.