[Haskell-cafe] Floyd Warshall performance (again)

[Roman Leshchinskiy]

On 16/04/2010, at 18:06, Mathieu Boespflug wrote:

> 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

In general, GHC doesn't like nested loops. You might want to try the following structure:

  loop1 SIZE = return ()
  loop1 k = loop2 k 0

  loop2 k SIZE = loop1 (k+1)
  loop2 k i = loop3 k i 0

  loop3 k i SIZE = loop2 k (i+1)
  loop3 k i j = do
                  ...
                  loop3 k i (j+1)

And, as Max suggested, the llvm backend ought to improve things.

Roman