|Haskell Performance Resource|
General Array techniques
- Remember that ordinary arrays are monolithic, and individual elements are not mutable. In particular, the (//) operator copies the entire array, so it is rarely what you want. (Data.Array.Diff provides a variant of arrays with O(1) (//), but that library has performance problems of its own).
- Monolithic arrays are by no means useless! Powerful array-construction facilities like accumArray can often eliminate the need for truly mutable arrays.
- If you really need mutable arrays for speed, then if possible use the ST variant, so that the stateful part of your program can be encapsulated (Data.Array.ST).
- Avoid redundant bounds checks by using Data.Array.Base.unsafeAt, Data.Array.Base.unsafeRead, Data.Array.Base.unsafeWrite (these are currently undocumented, unfortunately). This can make a large difference.
- See also Arrays, a thorough exploration of the various array types available in most Haskell compilers.
Use unboxed arrays (UArray, IOUArray)
GHC supports arrays of unboxed elements, for several basic arithmetic element types including Int and Char: see the Data.Array.Unboxed library library for details. Unboxed arrays support the same programmer interface as ordinary boxed arrays, so converting your code is easy. Using unboxed arrays will be a win in terms of both time and space.
There are also mutable unboxed arrays: IOUArray and STUArray (see Data.Array.IO and Data.Array.ST respectively). Using unboxed mutable arrays is often a good way to translate imperative algorithms into Haskell with similar performance.