Actual GHC memory usage for versions of 'any'

[Eric Shade]

My questions about 'any' and 'all' really had more to do with pedagogy
than anything else, but now that I got GHC figured out, I ran some
tests using their profiler.  I used version 4.08 on FreeBSD 4.2 and
did not enable optimization.  I called the function 'atLeastOne'
instead of 'any' just to make sure I didn't confuse myself.


Prelude Version
---------------

GHC's default 'any' and 'or' differ from the Prelude specification, so
I wrote the equivalent versions by hand.

>   default (Int)

>   main = print (atLeastOne (> 1000000) [0..999999])

>   atLeastOne :: (a -> Bool) -> [a] -> Bool
>   atLeastOne p = foldr (||) False . map p

Here are the results:

	Tue Jan 23 16:01 2001 Time and Allocation Profiling Report  (Final)

	   foo +RTS -p -RTS

	total time  =        1.16 secs   (58 ticks @ 20 ms)
	total alloc =  88,001,188 bytes  (excludes profiling overheads)

        COST CENTRE          MODULE     %time %alloc

        atLeastOne           Main        63.8   54.5
        main                 Main        36.2   45.5
        SYSTEM               MAIN        17.2    0.1

Total allocation due to atLeastOne: 0.545 * 88001188 = 47,960,647 bytes


Recursive Version
-----------------

I wrote 'atLeastOne' by hand so that it wouldn't use GHC's builtin
version, which has rewrite rules that may allow better optimization.

>   default (Int)

>   main = print (atLeastOne (> 1000000) [0..999999])

>   atLeastOne :: (a -> Bool) -> [a] -> Bool
>   atLeastOne _ [] = False
>   atLeastOne p (x:xs) = p x || atLeastOne p xs

Here are the results: 

	Tue Jan 23 16:01 2001 Time and Allocation Profiling Report  (Final)

	   bar +RTS -p -RTS

	total time  =        0.76 secs   (38 ticks @ 20 ms)
	total alloc =  64,001,096 bytes  (excludes profiling overheads)

        COST CENTRE          MODULE     %time %alloc

        atLeastOne           Main        71.1   37.5
        SYSTEM               MAIN        39.5    0.2
        main                 Main        28.9   62.5

Total allocation due to atLeastOne: 0.375 * 64001096 = 24,000,411 bytes


Summary
-------

I realize that this is not a perfect test, but it does say something.

To those who read my previous post, when I said that 'any' takes
linear space, I meant in the worst case.  And as Tom Pledger pointed
out to me privately via email, all of that space immediately becomes
garbage, so it may not be fair to count it against the space
requirements of the program.  However, it does take time to reclaim
it.

Thanks to all who replied.

-- 
Dr. Eric Shade, Associate Professor
Computer Science Department (CSAB Accredited)
Southwest Missouri State University