iterate and garbage collection in Haskell

user_8845822 0
Viewed 65

I have a question about how the GHC implements a simple code. A question of performance and also technical.

This is a simple example from John Hughes' "Why Functional Programming Matters" article. The square root calculation.

To do the calculation we need the previous approximation and we can use the iterate function that creates a list with approximations:

[a0, f(a0), f(f(a0), ...] and so on

And then with within it will stop when it is convenient:

within eps (a:b:xs) = if abs(a-b) < eps then b else within eps (b:xs)

The question is how is this performed in constant space?

Does the GC know in the recursive call, within eps (b: xs) that head a of the list is no longer in scope and then it is collected?

If this is the case, then at each iteration, would the GHC always create and then destroy a location in memory (variable)? And how can this perform as well as in a procedural language where the variable is always reused?

ghc garbage-collection haskell
1 Answers

Does the GC know in the recursive call, within eps (b: xs) that head a of the list is no longer in scope and then it is collected?

Correct.

If this is the case, then at each iteration, would the GHC always create and then destroy a location in memory (variable)?

For this example, almost certainly yes. There are some cases where list fusion can turn list-based algorithms into tight, non-allocating loops; this is most likely to happen if you use only built-in functions for producing and consuming the list.

how can this perform as well as in a procedural language where the variable is always reused?

The allocator and GC are tuned for doing lots of allocation and collection. Usually allocation just bumps a pointer. Occasionally you hit a GC, but only one Float needs to be copied from the first generation to the second (or only a Float and a few closures or whatever -- you get the idea, most of the data need not be touched as it's not reachable), which is similarly very cheap. There is some overhead, obviously, but usually the computation you're doing is complicated enough that it takes the majority of the run time.

user_7916040
Related