consolidated function is much slower

Question

I wrote isPrime function. It checks if a given number is prime or not. The last "prime" list is given separately.

prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

I thought it was always better to consolidate two functions into one if possible..so I consolidated isPrime and prime into one function isPrime2. But the isPrime2's performance is very bad.

isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]

isPrime 40000000000000000001

=> 0.5 second

isPrime2 40000000000000000001

=> 19.8 seconds

My machine is Ubuntu 17.10 x86-64. I am using ghc 8.2.1. Does anyone know why?

Stroud

My guess would be that since prime is a constant, it gets memoised, whereas isPrime2 is a function, so it doesn't. That's only a guess, however... – Rangoon

Thanks! Your explanation gave me insights. – Stroud

@eii0000 are you testing it compiled or interpreted? how does it compare if you simplify your isPrime2 n as all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : [3,5..]? – Linneman

all (\p -> n mod p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : [3,5..] is very fast... in my machine it took 0.025 second. I also tried all (\p -> n mod p /= 0) . takeWhile ((<=n) . (^2)) $ [2,3,5]++[6*x+y|x<-[1..],y<-[1,5]], which is slightly faster than 2:[3,5..] – Stroud

I compiled it. thanks! – Stroud

ok, thanks. now, what happens if you test the same number 10 times (or 100), with your 1st function vs with the function in the answer? (can you tell, without running it?) @eii0000 (when you respond, use @ sign so I get pinged :) ) – Linneman

Answer 1

The first snippet will keep only one list of primes in memory.

The second snippet will compute its own prime until n^2 every single time isPrime2 is called. Previously discovered primes are discarded and recomputed from scratch at every call. Since isPrime2 is recursive this leads to a blow-up.

An intermediate approach can be this one:

isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
   where
   prime :: [Integer]
   prime = 2 : filter isPrime [3..]
   isPrime :: Integer -> Bool
   isPrime n | n < 2 = False
   isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

This will recompute prime at every call of isPrime2, but will not lead to a blow-up since each call of the inner isPrime will share the same list of primes.

Hessler

great... your isPrime2 is 0.5 second too.. Thanks! – Stroud

Won't GHC usually float prime and isPrime out to the top level during optimisation? – Ervin

@BenjaminHodgson No, GHC is conservative here since it is not always an optimization. I believe this transformation is called (or related to) the "full laziness" transformation, where \x -> let y = ... in .... becomes let y= ... in \x -> ... provided that y does not depend on x. The semantics is preserved, but it is hard to predict which one has the best performance (IIRC). – Hessler