[Haskell-cafe] memory, garbage collection and other newbie's issues

[Bulat Ziganshin]

Hello Andrea,

Wednesday, October 18, 2006, 9:34:28 PM, you wrote:

> solution? Or just some hints on the kind of problem I'm facing: is it
> related to strictness/laziness, or it's just that I did not understand
> a single bit of how garbage collection works in Haskell?

i think, the second. unfortunately, i don't know good introduction to
the actual GC implementation although i can give you a pair of
not-so-friendly references:

Generational garbage collection for Haskell
  http://research.microsoft.com/~simonpj/Papers/gen-gc-for-haskell.ps.gz
GHC Commentary about GC
  http://hackage.haskell.org/trac/ghc/wiki/GarbageCollectorNotes
  http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage

shortly speaking, memory allocated by GHC never shrinks. GHC by
default use 2-stage memory allocator. First, memory for new objects
are allocated in 256k chunks ("nursery", whose size controlled by RTS -A
option). when these 256 kb is exhausted, "minor GC" occurs. minor GC
scans nursery and moves to the global heap all objects that are still
alive. btw, it's great idea because minor GC runs very fast and most
objects are died at this stage and don't participate in slow major GCs

when all the memory, currently allocated for the heap, exhausted -
major GC occurs. it scans all objects in the heap and copy alive ones
to the new memory blocks that are allocated during this process. so,
for example, if just before major GC we have 30 mb heap where only 10
mb alive, then during GC we will alloc 10 mb more, copy alive obejcts
there and at the end will free the original 30 megs

but these 30 megs don't returned to the OS! instead, they becomes free
part of the heap that then filled with new objects. so, after this
major GC we have 40 megs heap of which 30 megs are free. next major GC
will occur when these 30 megs will be filled by objects that survived
after minor GCs

well, it's default scenario. with compacting GC or with -H, -F, -G the
scenario will slightly change. you can look at behavior of memory
manager using +RTS -Sfile option. here is example:

    Alloc    Collect    Live    GC    GC     TOT     TOT  Page Flts
    bytes     bytes     bytes  user  elap    user    elap
...
   262116    266240 119095740  0.00  0.00   23.72   47.33    0    0  (Gen:  0)
   262116    266240 119269488  0.01  0.01   23.73   47.34    0    0  (Gen:  0)
   262116    266240 119443236  0.00  0.00   23.73   47.34    0    0  (Gen:  0)
   262116    266240 119616988  0.01  0.01   23.74   47.35    0    0  (Gen:  0)
   262116 119365632  81473776  1.54  1.66   25.29   49.01    0    0  (Gen:  1)
   262116    266240  81647512  0.00  0.00   25.29   49.01    0    0  (Gen:  0)
   262116    266240  81821260  0.00  0.00   25.29   49.01    0    0  (Gen:  0)
...

each line here reports stats of one GC. '1' in last column means major
GC, other are minor ones. third column displays current heap size. as
you can see, after each minor GC heap size is increased at 100-200 kb.
this means that from 256kb allocated only 100-200k was survived to be
moved in the main heap. Heap size was 120 mb and when heap was filled,
major GC occurs. after it ends, only 81 mb of data survived, the heap
was extended to 120+80=200 megs and next minor GCs continues to fill
it up. so, each major GC extends heap (in absence of additional
RTS options) and nothing between major GCs can do it. because it was
last GC in this run, its stats defined stats of entire program run:

989,191,980 bytes allocated in the heap
467,301,272 bytes copied during GC
 81,473,776 bytes maximum residency (9 sample(s))

       3584 collections in generation 0 (  6.33s)
          9 collections in generation 1 (  3.23s)

        194 Mb total memory in use

here GHC reports that maximum amount of really used memory was 81 megs
(GHC can determine real memory usage only at major GCs), while memory
allocated by RTS was 200 megs. so signal/noise ratio is 40% here.
sorry, but it is rather typical. there are various techniques to fight
with it but in general any memory allocation technique involves a lot
of vanished memory. at least GHC GC is enough efficient in terms of time:

  MUT   time   21.73s  ( 45.57s elapsed)
  GC    time    9.56s  (  9.94s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   31.31s  ( 55.51s elapsed)

  %GC time      30.6%  (17.9% elapsed)

ps: if your program uses a lot if string, FPS will be a very great. it
don;t change the GC behavior, just makes everything 10 times smaller
:)
  


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com