comparison of execution speed of array types

[Simon Marlow]

> I was curious about how fast the different array=20
> 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:
>=20
> 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,=20
> but here are the timing results:
>=20
> 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=20
> NormalArray formats,
> even though I know that I'm never going to refer to an old=20
> 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