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

Thanks for everyone's answers. The concept of "boxed" and "unboxed" types seems to be in the correct direction. I found some relevant sections in GHC's user guide: https://downloads.haskell.org/~ghc/8.8.3/docs/users_guide.pdf#page=269 . It might be an interesting read. Best, Kram On Sat, Apr 4, 2020 at 6:37 AM Will Yager wrote:

As a slight refinement on the previous responses,

* you do not need to worry about this at all, at least not in the direction you’re thinking. * you don’t need to use IORef or anything for efficiency - almost everything is passed by reference already (one benefit of immutable data) * GHC can automatically switch to pass-by-value when appropriate

In fact, the tricky part is actually getting your program to *stop* passing by reference when there’s a performance gain associated with pass-by-value.

My mental model of GHC’s rule for when to use pass-by-value is approximately

* it won’t change the semantics of the problem * the value is small

E.g. if we’re writing a very fast small loop that operates over Int64s, there’s no point passing by reference when a value is the same size as a pointer anyway, and we can avoid extraneous dereferences and heap allocations.

The interesting part is “won’t change the semantics of the program”. That basically boils down to the fact that pass-by-value is strict, so often times all you need to do is tell GHC that a function is strict on some of its arguments and GHC can choose to make those arguments PBV. See BangPatterns.

Haskellers don’t normally use the terminology PBV and PBR, however, but rather “unboxed” and “boxed” (referring to the values themselves).

Will

...

On Apr 4, 2020, at 12:55 AM, KS wrote:

Should I worry about this at all?