GHC shuffle more efficient than Perl5.

[audreyt]

So, I ported your Perl 5 program to Haskell, and benchmarked both against the 1millionlines.dat generated with this:

for (1..1_000_000) { print int(rand(10)), $/ }

Result on my FreeBSD 5.3 laptop is:

Perl5: 4.619u 1.010s 0:05.89 95.4% 10+79736k 0+0io 0pf+0w
GHC: 3.007u 0.038s 0:03.10 97.7% 323+359k 0+0io 0pf+0w

Note the constant memory use by GHC. The Haskell source code is attached as below.

{-# OPTIONS -O2 #-}

import Foreign
import Data.Array.IArray
import Data.Array.ST
import Control.Monad
import Control.Monad.ST.Strict
import System.IO
import System.Random
import System.Environment


main :: IO ()
main = do
    args <- getArgs
    when (null args) $ error "filename required"
    fh   <- openBinaryFile (head args) ReadMode
    sz   <- return . fromInteger =<< hFileSize fh
    allocaBytes sz $ \buf -> do
        hGetBuf fh buf sz
        ixs <- foldM (build buf) [-1] [0 .. sz-1]
        gen <- newStdGen
        let len = length ixs + 1
            stu :: ST s (STUArray s Int Int)
            stu = do
                arr <- newListArray (1, len) (sz-1:ixs)
                foldM_ (swap arr) gen [len `div` 2,(len `div` 2)-1..1]
                return arr
        display buf . elems $ runSTUArray stu

build :: Ptr Word8 -> [Int] -> Int -> IO [Int]
build buf ixs ix = do
    chr <- peek (plusPtr buf ix) :: IO Word8
    return $ if chr == 0o12 then (ix:ix:ixs) else ixs

swap arr g ix = do
    let (iy, g') = randomR (1, ix) g
    x1 <- readArray arr $ ix*2-1; x2 <- readArray arr $ ix*2
    y1 <- readArray arr $ iy*2-1; y2 <- readArray arr $ iy*2
    writeArray arr (ix*2-1) y1; writeArray arr (ix*2) y2
    writeArray arr (iy*2-1) x1; writeArray arr (iy*2) x2
    return g'

display buf [] = return ()
display buf (x1:x2:xs) = do
    hPutBuf stdout (plusPtr buf x2) (x1 - x2)
    display buf xs

[Anonymous Monk]

I have added this code to the Haskell Wiki:

http://haskell.org/hawiki/ImperativeHaskell