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@gmail.com