[Haskell-cafe] Another optimization question

[Daniel Fischer]

Am Samstag, 17. Mai 2008 19:52 schrieb anton muhin:
> On Sat, May 17, 2008 at 8:19 PM, Jeroen <yrn001 at gmail.com> wrote:
> > Hi, I know there's been quite some performance/optimization post lately,
> > so I hope there still room for one more. While solving a ProjectEuler
> > problem (27), I saw a performance issue I cannot explain. I narrowed it
> > down to the following code (never mind that 'primes' is just [1..],
> > the problem is the same or worse with real primes):
> >
> > primes :: [Int]
> > primes = [1..]
> >
> > 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]))
> >
> > $ time ./experiment1
> > 5000
> >
> > real    0m4.037s
> > user    0m3.378s
> > sys     0m0.060s
> >
> >
> > All good, but if I change isPrime to the simpeler
> >
> > isPrime x = elem x (takeWhile (<= x) primes)
> >
> > it takes twice as long:
> >
> > time ./experiment2
> > 5000
> >
> > real    0m7.837s
> > user    0m6.532s
> > sys     0m0.141s
> >
> > With real primes, it even takes 10 times as long.
> > I tried looking at the output of ghc -ddump-simpl,
> > as suggested in a previous post, but it's a bit over
> > my head (newby here...).
> >
> > Any suggestions?
>
> Just a thought: in your first approach you compare any element of the
> list once.  In second---twice: once to check if <= x and second time
> to check if it is equal to x.  That's a hypothesis,

I thought so, too, but I couldn't reproduce the behaviour, so I'm not sure 
what happens. In fact, compiling without optimisations, the first version 
takes almost twice as long as the second. Compiled with -O2, the second takes 
about 13% more time.

Using a real list of primes,
dafis at linux:~/EulerProblems/Testing> ghc --make experiment -o experiment3
[1 of 1] Compiling Main             ( experiment.hs, experiment.o )
Linking experiment3 ...
dafis at linux:~/EulerProblems/Testing> time ./experiment3
669

real    0m0.222s
user    0m0.220s
sys     0m0.000s
dafis at linux:~/EulerProblems/Testing> ghc --make experiment -o experiment4
[1 of 1] Compiling Main             ( experiment.hs, experiment.o )
Linking experiment4 ...
dafis at linux:~/EulerProblems/Testing> time ./experiment4
669

real    0m0.299s
user    0m0.290s
sys     0m0.000s

But
dafis at linux:~/EulerProblems/Testing> ghc -O2 --make experiment -o experiment3
[1 of 1] Compiling Main             ( experiment.hs, experiment.o )
Linking experiment3 ...
dafis at linux:~/EulerProblems/Testing> ghc -O2 --make experiment -o experiment4
[1 of 1] Compiling Main             ( experiment.hs, experiment.o )
Linking experiment4 ...
dafis at linux:~/EulerProblems/Testing> time ./experiment3
669

real    0m0.053s
user    0m0.040s
sys     0m0.010s
dafis at linux:~/EulerProblems/Testing> time ./experiment4
669

real    0m0.257s
user    0m0.250s
sys     0m0.010s

Wow! 
I've no idea what optimising did to the first version, but apparently it 
couldn't do much for the second.

> but another
> implementation of isPrime:
>
> isPrime x = (== x) $ head $ dropWhile (< x) primes

With -O2, this is about 20% slower than the Jeroen's first version, without 
optimisations 50% faster.
Strange.
isPrime :: Int -> Bool
isPrime x = go primes
      where
        go (p:ps) = case compare x p of
                        LT -> False
                        EQ -> True
                        GT -> go ps

does best (on my box), with and without optimisations (very very slightly with 
-O2) for a list of real primes, but not for [1 .. ].

However, more than can be squished out of fiddling with these versions could 
be gained from a better algorithm.
>
> seems to behave closer to your first version than to the second.  Note
> that that does unnecessary comparison as well the find first element
>
> >= x.
>
> yours,
> anton.

perplexed,
Daniel