21

Suppose that someone would translate this simple Python code to Haskell:

def important_astrological_calculation(digits):
  # Get the first 1000000 digits of Pi!
  lucky_numbers = calculate_first_digits_of_pi(1000000)
  return digits in lucky_numbers

Haskell version:

importantAstrologicalCalculation digits =
  isInfixOf digits luckyNumbers
  where
    luckyNumbers = calculateFirstDigitsOfPi 1000000

After working with the Haskell version, the programmer is astonished to discover that his Haskell version "leaks" memory - after the first time his function is called, luckyNumbers never gets freed. That is troubling as the program includes some more similar functions and the memory consumed by all of them is significant.

Is there an easy and elegant way to make the program "forget" luckyNumbers?

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
yairchu
  • 23,680
  • 7
  • 69
  • 109
  • 1
    Not elegant, but what happens if you add `{-# NOINLINE importantAstrologicalCalculation #-}`? – John L Jul 07 '11 at 17:17
  • 5
    There was a question recently, asking apparently the same thing, but using more advanced terminology. You may want to have a look at it: http://stackoverflow.com/questions/6090932/how-to-make-a-caf-not-a-caf-in-haskell – Rotsor Jul 07 '11 at 17:17

2 Answers2

21

In this case, your pidigits list is a constant (or "constant applicative form ), and GHC will probably float it out, calculate it once, and share amongst uses. If there are no references to the CAF, it will be garbage collected.

Now, in general, if you want something to be recalculated, turn it into a function (e.g. by adding a dummy () parameter) and enable -fno-full-laziness. Examples in the linked question on CAFs: How to make a CAF not a CAF in Haskell?

yairchu
  • 23,680
  • 7
  • 69
  • 109
Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • Does floating it out changes anything? stackoverflow.com/questions/6208006 creates a similar situation without anything being a constant.. – yairchu Jul 09 '11 at 19:33
0

Three ways to solve this (based on this blog post)

Using INLINE pragmas

Add {-# INLINE luckyNumbers #-} and another for importantAstrologicalCalculation.

This will make separate calls be independent from each other, each using their own copy of the luckyNumbers which is iterated once and is immediately collected by the GC.

Pros:

  • Require minimal changes to our code

Cons:

  • Fragile? kuribas wrote wrote that "INLINE doen’t guarantee inlining, and it depends on optimization flags"
  • Machine code duplication. May create larger and potentially less efficient executables

Using the -fno-full-laziness GHC flag

Wrap luckyNumbers with a dummy lambda and use -fno-full-laziness:

{-# OPTIONS -fno-full-laziness #-}

luckyNumbers _ = calculateFirstDigitsOfPi 1000000

Without the flag, GHC may notice that the expression in luckyNumbers doesn't use its parameter and so it may float it out and share it.

Pros:

  • No machine code duplication: the implementation of fibs is shared without the resulting list being shared!

Cons:

  • Fragile? I fear that this solution might break if another module uses fibs and GHC decides to inline it, and this second module didn't enable -fno-full-laziness
  • Relies on GHC flags. These might change more easily than the language standard does
  • Requires modification to our code including in all of fibs's call sites

Functionalization

Alonzo Church famously discovered that data can be encoded in functions, and we can use it to avoid creating data structures that could be shared.

luckyNumbers can be made to a function folding over the digits of pi rather than a data structure.

Pros:

  • Solid. Little doubt that this will resume working in the face of various compiler optimization

Cons:

  • More verbose
  • Non-standard. We're not using standard lists anymore, and those have a wealth of standard library functions supporting them which we may need to re-implement
yairchu
  • 23,680
  • 7
  • 69
  • 109
  • 1
    This seems very nearly like [a link-only answer](https://meta.stackexchange.com/a/168714/399408). – AKX Sep 27 '22 at 19:41
  • @AKX thanks. I've added the info to the answer, by changing the text of the post to terms of the example in the question. – yairchu Sep 28 '22 at 09:28