[Haskell-cafe] In-place modification

[Donald Bruce Stewart]

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