[Haskell-cafe] Re: Looking for the fastest Haskell primes
lennart at augustsson.net
Thu Apr 16 05:28:52 EDT 2009
But things are a little more complicated than that.
If the () argument to primes' is not used in calculating the primes
then ghc might decide to lift the computed list of primes into a top
level CAF, and so you will have a memory leak anyway.
If ghc does so or not depends, e.g., on the optimization level.
On Thu, Apr 16, 2009 at 11:21 AM, Heinrich Apfelmus
<apfelmus at quantentunnel.de> wrote:
> Niemeijer, R.A. wrote:
>> Heinrich Apfelmus wrote:
>>> +1 except that exporting the potentially infinite list of primes is
>>> problematic in that it may become a memory leak.
>>> I'd suggest to export two versions
>>> primes :: [Integer]
>>> primes' :: () -> [Integer]
>>> for casual (i.e. throwaway program to solve a Project Euler problem) and
>>> for memory aware use respectively.
>> I'm afraid I don't quite follow. Would you mind explaining what the
>> first parameter is for and how it would solve the memory leak?
> Lazy evaluation means that values, once evaluated, are stored in memory
> until garbage collections reclaims them because it is clear that they
> won't be used anymore. A memory leak happens when the programmer knows
> that values won't be used anymore while this knowledge is not available
> to the garbage collector.
> More specifically, consider the following example
> main = do
> print (primes !! 100)
> print (primes !! 20)
> This program will calculate the first 100 primes, and then print the
> 100th and the 1st prime. Now, after having printed the 100th prime, the
> 21th to 100th prime won't be used anymore and could thus be safely
> reclaimed by garbage collection. But since they are part of the primes
> list and this list is still in use for printing the 20th prime, this
> won't happen; we have a memory leak.
> The memory leak above can be avoided at the expense of recalculating the
> list. Using a function primes' with a dummy argument ensures^1 that
> the list of primes will be recalculated and garbage collected each time
> it is used:
> main = do
> print (primes' () !! 100)
> print (primes' () !! 20)
> Here, the first 100 primes are calculated, garbage collected and then
> the first 20 primes are (re-)calculated and garbage collected.
> We can fine control memory usage with the dummy argument version by
> using let statements or where clauses
> main = do
> let ps = primes' () in do
> print (ps !! 101)
> print (ps !! 100) -- no recalculation of ps
> print (primes' () !! 20) -- recalculates first 20 primes
> ^1: Compiler optimizations may interfere with that behavior. Generally,
> consensus is that the compiler should preserve sharing meticulously, but
> this is not guaranteed. See also: "full laziness transform".
> The above is folklore and should be written down properly at someplace
> prominent. The wiki page
> is a start, but I think the explanation there is currently a bit murky.
> Feel free to incorporate my writings above.
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe