[Haskell-cafe] poor perfomance of indexU in uvector package

15 Nov 2009

      Hello

This post meant to be literate haskell.

I found that perfomace of indexU is very poor and it is not fast O(1)
operation which is very surprising. Here is some benchmarcking I've
done. Everything compiled with -O2

Code below converts square 2D array to list of 1D arrays. Summation of
array contents is done in force evaluation
...
import Control.Monad
import Control.Monad.ST
import Data.Array.Vector
import System
arr :: Int -> UArr Double
arr n = toU $ map fromIntegral [1 .. n*n]
This is fastest function. It slice arrays along another direction and used
mainly as upper bound of speed
...
sliceY :: Int ->  UArr Double -> [UArr Double]
sliceY n a = map (\i -> sliceU a (i*n) n) [0 .. n-1]
Naive implementation using lists and index lookup.
  2.15 second for 200*200 array
...
sliceXlist :: Int -> UArr Double -> [UArr Double]
sliceXlist n a = map mkSlice [0 .. n-1]
    where
      mkSlice x = toU $ map (\y -> indexU a (x + y*n)) [0 .. n-1]
Similar implementation in ST monad and it uses indexU too.
  2.14 seconds for 200*200 array
...
sliceXst :: Int ->   UArr Double -> [UArr Double]
sliceXst n a = map mkSlice [0 .. n-1]
    where
      mkSlice x = runST $ do arr <- newMU n
                             forM_ [0 .. n-1] $ \y -> writeMU arr y (indexU a (y*n + x))
                             unsafeFreezeAllMU arr
This implementation avoids use of indexU by copying entire
2D array into mutable array and using it for lookup. Surprisingly
it outperform previsious implementations for sufficiently big n
  1.19 seconds for 200*200 array
...
sliceXcopy :: Int ->  UArr Double -> [UArr Double]
sliceXcopy n a = map mkSlice [0 .. n-1]
    where
      mkSlice x = runST $ do arr <- newMU n
                             cp  <- newMU (n*n)
                             copyMU cp 0 a
                             forM_ [0 .. n-1] $ \y -> writeMU arr y =<< readMU cp (y*n + x)
                             unsafeFreezeAllMU arr
This is another  implementation with lists which convert whole
array to list and picks appropriate element it. It is fastest implementation
so far.
0.039 seconds for 200*200 array
...
sliceXlistfast :: Int -> UArr Double -> [UArr Double]
sliceXlistfast n a = map mkSlice [0 .. n-1]
    where
      takeEvery n []     = []
      takeEvery n (x:xs) = x : takeEvery n (drop (n-1) xs)
      mkSlice x = toU $ takeEvery n . drop x $ fromU a

...
----------------------------------------------------------------
main :: IO ()
main = do
  [str,a] <- getArgs
  let n = read str
  case a of
      "y"    -> print $ sum $ map sumU (sliceY     n (arr n))
      "list" -> print $ sum $ map sumU (sliceXlist n (arr n))
      "lf"   -> print $ sum $ map sumU (sliceXlistfast n (arr n))
      "st"   -> print $ sum $ map sumU (sliceXst   n (arr n))
      "copy" -> print $ sum $ map sumU (sliceXcopy n (arr n))

[Haskell-cafe] poor perfomance of indexU in uvector package

Alexey Khudyakov