[Haskell-cafe] Another optimization question

[John Dorsey]

Jeroen,

> isPrime :: Int -> Bool
> isPrime x = isPrime' x primes
>     where isPrime' x (p:ps) | x == p = True
>                             | x > p = isPrime' x ps
>                             | otherwise = False
> 
> main = print $ length (filter (== True) (map isPrime [1..5000]))
[...]
> isPrime x = elem x (takeWhile (<= x) primes)

Here's a couple of things, although I don't know if they account for what
you're seeing.  All code is untested.

1)  A simpler main would be:

main = print $ length $ filter isPrime [1..5000]

This version manually fuses your map and filter.  Of course it's not
the same if you're doing anything else besides 'length'.

2)  The takeWhile in your second isPrime creates a throwaway list, which
doesn't exist in the explicit-recursion isPrime.  Unless this gets
optimized out, this could be the droid you're looking for.  I'd compile
with profiling (ghc -O2 --make -prof -auto-all experiment2), and run
./experiment2 +RTS -p -s
Find profiling stats in experiment2.prof, and check whether the latter
version isn't allocating a lot more.  When you feel like Core-diving,
it's something specific to look for.

3)  Maybe you can get the best of your two versions -- meaning the
relative speed of the first and functional style of the second -- by
writing your own 'elem' replacement that works on a sorted list.
Something like this, with suitably defined elemAsc:

-- elemAsc: tests presence of element in an ascending list
elemAsc :: (Ord a) => a -> [a] -> Bool
elemAsc ...
isPrime x = elemAsc x primes

Here's a good habit:  abstract things like this out.  Read the
libraries, and look for better and more abstract patterns.
Rinse, repeat.

4)  This doesn't explain why the version with real primes was 10x slower.
Are you comparing apples to apples?  Specifically, comparing both
versions of isPrime above using real primes, so both of them have to
create the primes list?  Does your code for real primes still use [Int]
and not [Integer] or (Num t) => [t] ?

I haven't invested the time yet to stare at GHC Core until it clicks,
excepting a few snippets that have been discussed here.  I'm not sure
how early in the learning curve it's advisable.  Probably depends on
your background.

Good luck Eulering,
John