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