[Haskell-cafe] Efficiency of passing function arguments

[Viktor Dukhovni]

On Sat, Apr 04, 2020 at 11:31:41AM +0300, Georgi Lyubenov wrote:

> For example, consider this idList:
> ```
> idList :: [a] -> [a]
> idList [] = []
> idList (x:xs) = x : idList xs
> ```
> Semantically this is the same as (a stricter) id, but we're deconstructing
> values and then constructing other ones (putting them in new boxes), so in
> effect, we're "copying" the input list.

But the function is not in fact strict, and so if one uses the value of
"idList xs" no more than once to traverse the list (print it, fold it, ...)
the list *as a whole* is never copied, and total memory used remains small
even for very long lists (that are lazily generated).

That said, interposing idList betweent a fold and the input list
increates the amount of GC work that ultimately takes place to cleanup
the per-element thunks.  The elements themselves are not copied, but the
enclosing lazy thunks are somewhat larger as a result of hiding the real
list behind idList.

> I'm not sure if ghc will do some magic optimisation to transform this
> particular function into an operation with no copying, but you can imagine
> something more complicated like map/foldr/reverse etc where it isn't
> possible (although other stuff like fusion is, to eliminate intermediate
> results from composed maps for example).

Construction of copies of lists typically happens when you traverse them
more than once.  Otherwise you just force each element in turn (possibly
via a more complex thunk that still produces that element).

-- 
    Viktor.

--- Folding 100 million Ints without idList:

       8,000,045,248 bytes allocated in the heap
             771,488 bytes copied during GC
              44,504 bytes maximum residency (2 sample(s))
              29,224 bytes maximum slop
                   0 MB total memory in use (0 MB lost due to fragmentation)

                                         Tot time (elapsed)  Avg pause  Max pause
      Gen  0      7658 colls,     0 par    0.022s   0.022s     0.0000s    0.0018s
      Gen  1         2 colls,     0 par    0.001s   0.001s     0.0004s    0.0007s

      INIT    time    0.001s  (  0.001s elapsed)
      MUT     time    0.981s  (  0.982s elapsed)
      GC      time    0.023s  (  0.023s elapsed)
      EXIT    time    0.000s  (  0.000s elapsed)
      Total   time    1.005s  (  1.005s elapsed)

      %GC     time       0.0%  (0.0% elapsed)

      Alloc rate    8,153,859,656 bytes per MUT second

      Productivity  97.6% of total user, 97.7% of total elapsed

--- Folding 100 million Ints with idList:

      12,800,039,208 bytes allocated in the heap
           1,701,952 bytes copied during GC
              44,504 bytes maximum residency (2 sample(s))
              29,224 bytes maximum slop
                   0 MB total memory in use (0 MB lost due to fragmentation)

                                         Tot time (elapsed)  Avg pause  Max pause
      Gen  0     12206 colls,     0 par    0.030s   0.029s     0.0000s    0.0007s
      Gen  1         2 colls,     0 par    0.001s   0.001s     0.0004s    0.0007s

      INIT    time    0.000s  (  0.000s elapsed)
      MUT     time    1.484s  (  1.485s elapsed)
      GC      time    0.031s  (  0.030s elapsed)
      EXIT    time    0.000s  (  0.000s elapsed)
      Total   time    1.516s  (  1.516s elapsed)

      %GC     time       0.0%  (0.0% elapsed)

      Alloc rate    8,622,777,676 bytes per MUT second

      Productivity  97.9% of total user, 98.0% of total elapsed