Editing Shootout/Nsieve (section)

== Old entry ==

Studying the Core shows the the mapM was preventing things from being
unboxed properly. Big speedup. The extra `seqs` also help the unboxing.
Should be around the fastest entry now.

''Is anyone else bothered by the usage of unsafeWrite?  I agree that
excellent speed is being gained, but this speed is gained at the cost
of functional-style coding.  I'm a novice Haskeller, but using unsafeWrite
seems like an imperative hack to gain speed.'' -- AlsonKemp

''Response: unsafeWrite is just the same as a normal array update,
without an extraneous bounds check (since it's already performed in the
outer loop). We're just avoiding redundant computation (as we do in all
entries for this problem). SPJ actually recommends unsafe* ops in
arrays, see the "loop performance bug" thread in the haskell mail
archives from 2005. 

In summary, its not a hack -- the name just makes clear that you have to
do your own bounds check (Haskell is good at letting you know when there
are extra proof considerations for the programmer to take). Since this
program runs [http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsieve&lang=all faster than GCC], then I think we should not be worried
about avoiding a redundant bounds check :)'' -- DonStewart

<haskell>
--
-- $Id: nsieve-ghc.code,v 1.27 2006/01/08 22:44:56 igouy-guest Exp $
-- Written by Einar Karttunen, optimised further by Don Stewart
--

import Data.Array.IO; import Data.Array.Base; import Data.Bits; import System; import Text.Printf

main = (\n -> mapM_ (sieve.(10000 *).shiftL 1) [n,n-1,n-2]) . read . head =<< getArgs

sieve m = do c <- newArray (2,m) True >>= \a -> loop a m 2 0
             printf "Primes up to %8d %8d\n" (m::Int) (c::Int) :: IO ()

loop arr m n c | arr `seq` m `seq` n `seq` c `seq` False = undefined
loop arr m n c = if n == m then return c else do
    el <- unsafeRead arr n
    if el then let loop' j | j > m     = loop arr m (n+1) (c + 1)
                           | otherwise = unsafeWrite arr j False >> loop' (j+n)
               in loop' (n+n)
          else loop (arr :: IOUArray Int Bool) m (n+1) c
</haskell>