[Haskell-cafe] In-place modification
Donald Bruce Stewart
dons at cse.unsw.edu.au
Sun Jul 15 08:30:13 EDT 2007
dons:
> hughperkins:
> >
> > Hey, I just realized I can shave off another 30% in C# ;-)
> > So now the timings become:
>
> Ok. So do the same thing to the Haskell program. The compilers should
> produce pretty much identical assembly.
>
Oh, and I forgot you count up by two now. Here's the Haskell
transliteration (again).
{-# OPTIONS -O2 -optc-O -fbang-patterns #-}
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Base
import System
import Control.Monad
import Data.Bits
main = print (pureSieve 10000000)
pureSieve :: Int -> Int
pureSieve n = runST( sieve n )
sieve n = do
a <- newArray (3,n) True :: ST s (STUArray s Int Bool)
let cutoff = truncate (sqrt (fromIntegral n)) + 1
go a n cutoff 3 1
go !a !m cutoff !n !c
| n >= m = return c
| otherwise = do
e <- unsafeRead a n
if e then
if n < cutoff
then let loop !j
| j < m = do
x <- unsafeRead a j
when x $ unsafeWrite a j False
loop (j+n)
| otherwise = go a m cutoff (n+2) (c+1)
in loop ( if n < 46340 then n * n else n `shiftL` 1)
else go a m cutoff (n+2) (c+1)
else go a m cutoff (n+2) c
Marginally faster:
$ time ./primes
664579
./primes 0.34s user 0.00s system 89% cpu 0.385 total
Very cache-dependent though, so widely varying runtimes could be
expected.
-- Don
More information about the Haskell-Cafe
mailing list