Every readArray and writeArray checks that the index tuple is in range. You could try an use Data.Array.Base (in GHC) and unsafeWrite and unsafeRead. They do not do bounds checking like readArray and writeArray. Oleg has a good interface to unchecked array usage here: http://okmij.org/ftp/Haskell/types.html#branding -- Chris frederic@ka-ge-ro.org wrote:

Hi,

I'm new to Haskell (yet I am very familiar with Lisp and OCaml), and I am trying to implement the Floyd-Warshall algorithm (finding the minimal distance between two nodes in a weighted graph). For an input graph with 101 nodes, the obvious C version takes 0.01 s on my machine. My first totally functional implementation in Haskell took 6s... for a graph with 10 edges. (This version considered that a graph is given as its adjacency matrix, which is represented as a 2-uple in ([k], k -> k -> Double)). [I do not show my code, as I am ashamed of it :-S] My first question is: what would an (efficient?) version of the algorithm using this representation would look like ? Is it possible to do without ressorting to the ST monad ?

Now, I have been trying to implement it in a more imperative way, to understand how the ST monad works. It runs in 0.6s for a 101-noded graph, which is much, much faster than the original version but still much slower than the C version. I would be very grateful if someone cared to explain why this is unefficient and how to make it faster (Without using the FFI :-|) Thanks by advance. (BTW, I'm using the ghc-6.42 compiler with -O2 flag).

-- Frederic Beal

-- Code begins here module FW (bench) where

import Control.Monad import Control.Monad.ST import Data.Array.ST

update :: STUArray s (Int, Int) Double -> Int -> Int -> Int -> ST s () update arr i j k = do aij <- readArray arr (i, j) ajk <- readArray arr (j, k) aik <- readArray arr (i, k) if aij + ajk < aik then do writeArray arr (i, k) (aij + ajk) else return ()

updateLine arr i j n = do mapM_ (update arr i j) [0..n] updateRow arr i n = do mapM_ (\x -> updateLine arr i x n) [0..n] updateStep arr n = do mapM_ (\x -> updateRow arr x n) [0..n]

-- The actual FW invocation canonicalize = updateStep

-- From here on, the "testing" suite count = 100

-- A test array: M[i, j] = 1 + ((x+y) mod count) orgArray :: ST s (STUArray s (Int, Int) Double) orgArray = do v <- newArray ((0, 0), (count, count)) 0.0 mapM_ (\x -> mapM_ (\y -> writeArray v (x, y) ((1+) $ fromIntegral (mod (x+y) count))) [0..count]) [0..count] return v

sumDiag :: STUArray s (Int, Int) Double -> Int -> ST s Double sumDiag arr n = do foldM (\y x -> do a <- readArray arr (x, x) return $ a + y) 0.0 [0..n]

orgDiag = do arr <- orgArray v <- sumDiag arr count return v

cptDiag = do arr <- orgArray canonicalize arr count v <- sumDiag arr count return v

bench = do val <- stToIO cptDiag diag <- stToIO orgDiag print val print diag

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Hello frederic, Friday, July 28, 2006, 10:44:51 AM, you wrote:

much slower than the C version. I would be very grateful if someone cared to explain why this is unefficient and how to make it faster

update :: STUArray s (Int, Int) Double -> Int -> Int -> Int -> ST s () update arr i j k = do aij <- readArray arr (i, j) try update arr i j k | arr `seq` i `seq` j `seq` k `seq` True = do aij <- readArray arr (i, j) and make the same changes in other update functions. we has http://haskell.org/haskellwiki/Performance page, you should read it second problem is bounds checking in readArray. if you want better speed, you should use unsafeRead/unsafeWrite and compute index with something like (i*count+j) btw, 'newArray ((0, 0), (10, 10))' creates array with 121 elements. is this what you really need? also, "foreach=flip mapM_" will be useful for you. i also recommend you to read http://haskell.org/haskellwiki/IO_inside - ST monad differs from IO one only in what its operations are restricted to array/reference ones -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com