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

[Alexey Khudyakov]

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))