25

In a pure language like Haskell, all data is immutable and no existing data structures can be changed in any way. Additionally, many algorithms on immutable data and functional programming patterns generate large amounts of garbage by nature (chains of map creating intermediate lists for example).

What strategies and techniques do garbage collectors employ in the face of purity that they wouldn't otherwise? What works very well in an impure language's GC that doesn't in a pure context? What other new problems do pure languages create for GCs?

13

The current implementation of ghc uses a strategy that only works because the language is pure functional and data is immutable: because no variable can ever be altered to refer to anything newer, objects only hold references to older objects, so it runs a generational garbage collector; since an object referred to by a higher generation cannot be deleted until that generation is GCd, it promotes objects to higher generations eagerly; and since nothing is going to alter references while the GC is sweeping them, it can run in parallel.

Here’s a paper with more detail.

  • 4
    Eager promotion relies on laziness—updating a thunk in an old generation can create a pointer into the new generation, but thunks are only ever mutated once, so it suffices to promote the young object eagerly. Other old-to-young references (e.g., from mutable arrays) are tracked using “remembered sets”, which are also used in case eager promotion fails. – Jon Purdy Nov 22 '15 at 0:41
1

In a pure language like Haskell, all data is immutable and no existing data structures can be changed in any way

Actually that is not generally true. Pure languages use non-strict (lazy) evaluation so the evaluation of potentially all subexpressions is deferred. Unevaluated expressions are generally heap allocated as a "thunk". When required the expression is evaluated and the thunk is mutated into the resulting value.

What strategies and techniques do garbage collectors employ in the face of purity that they wouldn't otherwise?

The only thing I can think of is black holes. I don't recall seeing anything else new on the GC side in the Haskell research papers.

What works very well in an impure language's GC that doesn't in a pure context?

The GC write barrier. Impure languages tend to write pointers into the heap a lot more so they tend to have their write barriers more heavily optimised.

Other GC algorithms such as mark-region are much more viable in the context of impure languages because they can have much lower allocation rates than pure languages.

What other new problems do pure languages create for GCs?

Pure languages are very rare so there is a lot less data on how pure programs use memory and, therefore, you are starting in a worse position when trying to write a GC for a pure language.

  • "When required the expression is evaluated and the thunk is mutated into the resulting value." That's an internal implementation detail as far as a Haskell user is concerned. There's no way to observe the mutation, so it's not mutation from the user's point of view. – Jack Jan 27 '16 at 6:13
  • Additionally it's entirely possible for a pure language to be strict - see Idris for an example. – Jack Jan 27 '16 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.