On Sun, May 18, 2008 at 2:00 AM, Daniel Fischer <[EMAIL PROTECTED]> wrote: > 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), So it's just a relatively sparsed sorted list of 5134 numbers and the greatest of them still fits into Int, correct? > with -O0 / -O2, it's > Jeroen 1 : 14.5 s / 2.4 s > Jeroen 2 : 52.5 s / 49.7 s 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
