Dear haskell-cafe,
I implemented the Floyd Warshall algorithm for finding the shortest
path in a dense graph in Haskell, but noted the performance was
extremely poor compared to C. Even using mutable unboxed arrays it was
running about 30 times slower. I rewrote the program several times, to
arrive at the following definition:
module Main where
import Data.Array.Base
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad.ST
import Control.Monad
import System.IO
import GHC.Exts
#define SIZE 1500
-- Actual graph is immaterial for this benchmark.
graph = []
shortestPath :: [(Int, Int, Int)] -> UArray Int Int
shortestPath g = runSTUArray $ do
let mnew = newArray (0, SIZE * SIZE) 1
mread arr i j = unsafeRead arr (i * SIZE + j)
mwrite arr i j x = unsafeWrite arr (i * SIZE + j) x
unsafeIOToST $ hSetBuffering stdout LineBuffering
unsafeIOToST $ putStrLn "Allocating ..."
pm <- mnew
unsafeIOToST $ putStrLn "Allocating ... done"
let loop1 SIZE = return ()
loop1 k = let loop2 SIZE = return ()
loop2 i = let loop3 SIZE = return ()
loop3 j = do
xij <- mread pm i j
xik <- mread pm i k
xkj <- mread pm k j
mwrite pm i j (min xij (xik + xkj))
loop3 (j + 1)
in loop3 0 >> loop2 (i + 1)
in loop2 0 >> loop1 (k + 1)
loop1 0
return pm
main = shortestPath graph `seq` return ()
These 3 nested loops run a lot faster than generating a list of IO
actions and then running them using sequence_. But still this program
runs 3 times slower than it's C counterpart:
$ time ./FloydWarshall
Allocating ...
Allocating ... done
./FloydWarshall 45,75s user 0,09s system 97% cpu 46,815 total
$ time ./a.out
./a.out 14,92s user 0,03s system 98% cpu 15,230 total
The source code for the C program is given below. Using the vector
package instead of GHC's inbuilt ST arrays doesn't improve the
situation any, neither does compiling via C. Any idea why the rather
unidiomatic Haskell program is still 3 times slower, despite using
unchecked indexing and the fact that the three nested tail recursive
functions above shoud behave exactly as the 3 nested for loops in the
C program?
Best regards,
Mathieu
