RE: comparison of execution speed of array types
I was curious about how fast the different array implementations were so I decided to test it. I wrote five programs all of which take an array containing 50001 elements, reverse it a couple of times then sum (modulo) them finally printing the sum. The programs are as follows:
NormalArray -- uses the standard Array package for everything NormalArrayReplace -- same as NormalArray but builds a new array every time it is reversed UnboxedArray -- uses UArray UnboxedArrayReplace -- obvious IOMutArray -- uses the IOArray from IOExts and everything is in the IO monad
Could you try IOUArray for completeness too? (An IOUArray is the unboxed version of IOArray, it can be found in Data.Array.IO).
I've stuck the code for these at the bottom of this message, but here are the timing results:
NormalArray 1.65u 0.20s 0:01.89 97.8% NormalArrayReplace 2.40u 0.08s 0:02.56 96.8% UnboxedArray 0.80u 0.04s 0:00.87 96.5% UnboxedArrayReplace 1.83u 0.07s 0:01.99 95.4% IOMutArray 0.60u 0.03s 0:01.09 57.7%
GHC doesn't do any analysis to detect when a pure array can be updated in place, so I'm surprised that the Replace versions of the test performed much differently from the originals - I'd have expected them to be about the same, because in both cases a new array is being built for each reverse. I suspect the difference is due to more deforestation happening in the replace case; we know there are some issues with deforestation of the array operations at the moment.
clearly IOMutArray is the best, even outperforming the UnboxedArray. Unfortunately, writing code in the IOMutArray format is much uglier than writing it in the UnboxedArray or NormalArray formats, even though I know that I'm never going to refer to an old version of the array, so inplace updates are a-okay.
You could try testing DiffArray (Data.Array.Diff) which is optimised for in-place updates, and should show a bigger difference between the normal and 'replace' versions. It might be nearly as fast as IOArray (I don't think we've ever benchmarked it), and it doesn't need to be in the IO monad. Cheers, Simon
Could you try IOUArray for completeness too? (An IOUArray is the unboxed version of IOArray, it can be found in Data.Array.IO).
It fits in as the fastest: IOUnboxedMutArray 0.48u 0.04s 0:00.58 89.6%
NormalArray 1.65u 0.20s 0:01.89 97.8% NormalArrayReplace 2.40u 0.08s 0:02.56 96.8% UnboxedArray 0.80u 0.04s 0:00.87 96.5% UnboxedArrayReplace 1.83u 0.07s 0:01.99 95.4% IOMutArray 0.60u 0.03s 0:01.09 57.7%
You could try testing DiffArray (Data.Array.Diff) which is optimised for in-place updates, and should show a bigger difference between the normal and 'replace' versions. It might be nearly as fast as IOArray (I don't think we've ever benchmarked it), and it doesn't need to be in the IO monad.
DiffArray seems to be broken :). Either that or I'm using it incorrectly. I've attached the relevant code, but when I don't reverse the array everything works fine; when I reverse it the program doesn't (seem to) halt. module Main where import Data.Array.IO import Data.Array.Diff testArray :: IOToDiffArray IOArray Int Int testArray = array (0,50000) [(i, (19*i+23) `mod` 911) | i <- [0..50000]] reverseArray :: IOToDiffArray IOArray Int Int -> IOToDiffArray IOArray Int Int reverseArray arr = arr // [(50000-i, arr!i) | i <- [0..50000]] sumArrayMod :: IOToDiffArray IOArray Int Int -> Int sumArrayMod arr = sumArrayMod' low 0 where sumArrayMod' pos sum | pos > high = sum | otherwise = sumArrayMod' (pos+1) ((sum + arr!pos) `mod` 911) (low,high) = bounds arr main = print $ sumArrayMod $reverseArray testArray
Could you try IOUArray for completeness too? (An IOUArray is the unboxed version of IOArray, it can be found in Data.Array.IO).
It fits in as the fastest:
IOUnboxedMutArray 0.48u 0.04s 0:00.58 89.6%
NormalArray 1.65u 0.20s 0:01.89 97.8% NormalArrayReplace 2.40u 0.08s 0:02.56 96.8% UnboxedArray 0.80u 0.04s 0:00.87 96.5% UnboxedArrayReplace 1.83u 0.07s 0:01.99 95.4% IOMutArray 0.60u 0.03s 0:01.09 57.7%
Hello.
I have recently coded in Haskell a little program which evaluates
a function given as a series of matrix products. Matrices and vectors
are represented as type X. Surprisingly, compiled with 'ghc -O2'
(vers 5.02.2) the program runs faster with X=Array than with X=UArray Double.
I was quite puzzled by this result, I suppose that maybe the laziness
helps to avoid memory allocation or something. Is that possible?
I am not posting the program here, because: a) it is somewhat long,
and b) I am a Haskell beginner. However, if somebody wants to play
with it, I will try to reduce and polish my code and to post it here.
Jan
--
-------------------------------------------------------------------------
Jan Kybic
Jan Kybic
I have recently coded in Haskell a little program which evaluates a function given as a series of matrix products. Matrices and vectors are represented as type X. Surprisingly, compiled with 'ghc -O2' (vers 5.02.2) the program runs faster with X=Array than with X=UArray Double. I was quite puzzled by this result, I suppose that maybe the laziness helps to avoid memory allocation or something. Is that possible?
This should only have an effect if parts of the resulting matrices were not used to compute the final result. Given that the interface to H98 arrays heavily relies on lists for generating arrays and extracting results, the list computations can easily dominate the actual array computations. If that happens, it often depends on how much deforestation[1] GHC can perform. Cheers, Manuel [1] Static removal of intermediate data structures
participants (4)
-
Hal Daume III -
Jan Kybic -
Manuel M T Chakravarty -
Simon Marlow