pierwszości zmiana check że wydawało optymalizacji okazało się pessimization w Haskell

Question

Napisałem dwie funkcje, aby sprawdzić, czy liczba jest pierwsza w Haskell:

prime :: Int -> Bool 
prime 0 = False 
prime 1 = False 
prime 2 = True 
prime n | even n = False 
prime n = all (\x -> n `rem` x /= 0) [3,5..intSqrt] 
    where intSqrt = (floor . sqrt . fromIntegral) n 

prime2 :: Int -> Bool 
prime2 0 = False 
prime2 1 = False 
prime2 n = all (\x -> n `rem` x /= 0) [2..intSqrt] 
    where intSqrt = (floor . sqrt . fromIntegral) n 

Pierwsza wersja powinna średnio zrobić pół obliczeń po drugie, ponieważ parzyste liczby są pomijane, ale okazuje się, że druga wersja, która wydaje się wolniejsza, jest prawie 2x szybciej! Załączam czasy sesji Terminala dosłownie.

Prime 1 wersja:

$ ghc -O2 prime.hs 
[1 of 1] Compiling Main    (prime.hs, prime.o) 
Linking prime ... 
$ time ./prime 
142913828922 

real 0m4.617s 
user 0m4.572s 
sys 0m0.040s 

Teraz używam zmienić program, aby skorzystać z prime2 wersji:

$ ghc -O2 prime.hs 
[1 of 1] Compiling Main    (prime.hs, prime.o) 
Linking prime ... 
$ time ./prime 
142913828922 

real 0m2.288s 
user 0m2.268s 
sys 0m0.020s 
$ 

Kod w main jest prosta:

main :: IO() 
main = print $ sum $ filter prime2 [1..2000000] 

Dlaczego druga wersja jest szybsza, jeśli robi dwa razy więcej niż modolus?

Answer 1

Jak zauważył Daniel w komentarzach, pytanie even n wykonałoby operację mod, podobnie jak w drugiej wersji. Co więcej, byłby to pierwszy przypadek trafienia w drugą wersję. Druga wersja ma mniej oddziałów skrzynek, ale taką samą wydajność. Pamiętaj, że Haskell jest językiem nieostrym, więc wszystkie inne operacje mod nie zostaną wymuszone, jeśli pierwszy z nich już zwróci True.