On Sat, May 17, 2008 at 10:40 PM, Daniel Fischer <[EMAIL PROTECTED]> wrote: > Am Samstag, 17. Mai 2008 19:52 schrieb anton muhin: >> On Sat, May 17, 2008 at 8:19 PM, Jeroen <[EMAIL PROTECTED]> 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.
Why not -O3? > Using a real list of primes, What's the size of the real list? > [EMAIL PROTECTED]:~/EulerProblems/Testing> ghc --make experiment -o > expleriment3 > [1 of 1] Compiling Main ( experiment.hs, experiment.o ) > Linking experiment3 ... > [EMAIL PROTECTED]:~/EulerProblems/Testing> time ./experiment3 > 669 > > real 0m0.222s > user 0m0.220s > sys 0m0.000s > [EMAIL PROTECTED]:~/EulerProblems/Testing> ghc --make experiment -o > experiment4 > [1 of 1] Compiling Main ( experiment.hs, experiment.o ) > Linking experiment4 ... > [EMAIL PROTECTED]:~/EulerProblems/Testing> time ./experiment4 > 669 > > real 0m0.299s > user 0m0.290s > sys 0m0.000s > > But > [EMAIL PROTECTED]:~/EulerProblems/Testing> ghc -O2 --make experiment -o > experiment3 > [1 of 1] Compiling Main ( experiment.hs, experiment.o ) > Linking experiment3 ... > [EMAIL PROTECTED]:~/EulerProblems/Testing> ghc -O2 --make experiment -o > experiment4 > [1 of 1] Compiling Main ( experiment.hs, experiment.o ) > Linking experiment4 ... > [EMAIL PROTECTED]:~/EulerProblems/Testing> time ./experiment3 > 669 > > real 0m0.053s > user 0m0.040s > sys 0m0.010s > [EMAIL PROTECTED]:~/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. Well, head has its overhead as well. Cf. two variants: firstNotLess :: Int -> [Int] -> Int firstNotLess s (x:xs) = if x < s then firstNotLess s xs else x dropLess :: Int -> [Int] -> [Int] dropLess s l@(x:xs) = if x < s then dropLess s xs else l isPrime :: Int -> Bool isPrime x = x == (firstNotLess x primes) isPrime' :: Int -> Bool isPrime' x = x == (head $ dropLess x primes) On my box firstNotLess gives numbers pretty close (if not better) than Jeroen's first variant, while head $ dropLess notably worse. > 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 .. ]. And what happens for [1..]? > However, more than can be squished out of fiddling with these versions could > be gained from a better algorithm. Definitely. yours, anton. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
