On Sun, May 18, 2008 at 2:00 AM, Daniel Fischer
Am Samstag, 17. Mai 2008 22:48 schrieb anton muhin:
Why not -O3?
As far as I know - and Brandon S.Allbery said so, too - -O3 isn't better than -O2.
I didn't know that, sorry.
Using a real list of primes,
What's the size of the real list?
arbitrary, however, since it's [Int], it will actually be at most 105097565 primes long, but since only numbers up to 5000 are checked, only 670 primes will ever be considered - When I check numbers 1 to 50000 (5133 primes, so 5134 primes evaluated),
with -O0 / -O2, it's Jeroen 1 : 14.5 s / 2.4 s Jeroen 2 : 52.5 s / 49.7 s
So it's just a relatively sparsed sorted list of 5134 numbers and the greatest of them still fits into Int, correct? probably Jeroen's hypothesis about temporary list built might explain that slowdown, what do you think?
(== x) . head . dropWhile (< x) : 8.2 s /4.1 s go primes : 5.5 s / 2.5 s
So Jeroen 1 is the best to be optimised :)
:)
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
for primes up to 50000, that's 6.8 s / 2.1 s with -O0 / -O2 respectively on mine
So it seems to be reproducible.
Jeroen's first variant, while head $ dropLess notably worse.
5.8 s / 2.4 s here.
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..]?
With -O2, Jeroen 1 was best (1.62), nex firstNotLess (1.63), head . dropLesst (1.74), then in close succesion Jeroen 2 (1.92), go primes (1.96) and head . dropWhile (1.99),
go primes ran 1.96? Indeed weird, does anybody know if it's due to pattern matching?
with -O0, it's head . dropWhile (1.7 s, YES, that actually is faster with -O0 than with -O2!), head . dropLess (2.0), Jeroen 2 and firstNotLess (2.1 s), go primes (2.3 s), Jeroen 1 (3.2 s).
Weirder and weirder.
agree yours, anton