[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?

[Daniel Fischer]

Am Dienstag, 29. Juli 2008 13:12 schrieb Rafael Gustavo da Cunha Pereira 
Pinto:
> 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
> stack.
> 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 
1MB.

>
>
> 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.
>
> Rafael

Cheers,
Daniel