[Haskell-cafe] poor perfomance of indexU in uvector package
Alexey Khudyakov
alexey.skladnoy at gmail.com
Sun Nov 15 07:00:34 EST 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))
More information about the Haskell-Cafe
mailing list