[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?
daniel.is.fischer at web.de
Tue Jul 29 11:43:39 EDT 2008
Am Dienstag, 29. Juli 2008 13:12 schrieb Rafael Gustavo da Cunha Pereira
> Thanks Daniel!
> I only asked, because I was comparing the versions:
> 1) Steve's first version, without g x took forever to run and ate all the
> 2) Mine (with Map) ran somewhat fast, but it takes almost 2 minutes running
> and eats 48MB of stack
> 3) Steve's last version (with g x) took less than 30s on my machine and
> needed no more than 8MB of stack.
Odd, I get quite different results.
Steve's first, with type signature
f :: Int -> Integer -> Int
runs fine, although it takes 760 seconds and allocates *tons* when
interpreted, takes 50 seconds when compiled (with -O2, that's my standard).
I suspect you ran it with type signature
f :: Int -> Int -> Int ?
Then you hit a loop containing -68 for f 1 113383, no wonder it doesn't finish
Yours does far better here:
./rafa +RTS -sstderr
1,794,748,252 bytes allocated in the heap
110,383,616 bytes copied during GC (scavenged)
45,186,920 bytes copied during GC (not scavenged)
35,016,704 bytes maximum residency (7 sample(s))
3424 collections in generation 0 ( 2.74s)
7 collections in generation 1 ( 1.26s)
68 Mb total memory in use
INIT time 0.00s ( 0.00s elapsed)
MUT time 22.79s ( 25.17s elapsed)
GC time 4.00s ( 4.28s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 26.79s ( 29.45s elapsed)
%GC time 14.9% (14.5% elapsed)
Alloc rate 78,751,568 bytes per MUT second
Productivity 85.1% of total user, 77.4% of total elapsed
Though that difference may partly be due to different compiling options (-O2
for me). But I doubt it consumes much stack, the Map, which takes a lot of
memory, should live on the heap.
Steve's new version doesn't differ much from the first with respect to running
time and memory usage, takes about 50 seconds here and runs happily within
> If I understood it right, using (g x) on foldl' forced the strictness of
> the thunk (acc+1), without the need of using the bang pattern.
No, the strictness of the acc parameter was found by the strictness analyser
(at least with optimised compilation), neither foldl' nor g play a role here.
If my reading of the core is correct, without optimisations, the strictness
isn't inferred and I would've thought that is largely responsible for the
approximately doubled running time and more than doubled allocation figures
vs. -O2. Then each of the ((...(1+1)+1...)+1) thunks would only be evaluated
when the strictness of foldl' forces the evaluation of max (a,b) (g k). Since
these thunks contain some 100 nested additions on average, that should cost
considerable time and allocation, but as none contains more than a few
hundred additions, it'd be no problem for the stack.
However, things apparently aren't so simple, because with -O0, a strictifying
acc with a bang makes no difference :-(
What blows the stack pretty fast is a gigantic thunk of
max (max ... max (max (0,0) (g 1)) (g 2) ... (g 999999))
which is constructed when using foldl instead of foldl' and compiling without
optimisations (with -O1 already, all necessary strictness is seen, and the
compiler makes foldl behave like foldl' here).
The essential thing here is to avoid that thunk of maxes. Best done by using
foldl' and compiling with optimisations.
> I'll try to play with the strictness on my code, trying to take advantage
> of both the Map and strictness.
More information about the Beginners