Performance/Arrays
From HaskellWiki
m (→Use unboxed arrays (<tt>UArray</tt>, <tt>IOUArray</tt>): link) |
m (→Use unboxed arrays (<tt>UArray</tt>, <tt>IOUArray</tt>)) |
||
Line 12: | Line 12: | ||
=== Use unboxed arrays (<tt>UArray</tt>, <tt>IOUArray</tt>) === | === Use unboxed arrays (<tt>UArray</tt>, <tt>IOUArray</tt>) === | ||
− | GHC supports arrays of unboxed elements, for several basic arithmetic element types including <tt>Int</tt> and <tt>Char</tt>: see the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-Unboxed.html 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. | + | GHC supports arrays of [[unboxed]] elements, for several basic arithmetic element types including <tt>Int</tt> and <tt>Char</tt>: see the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-Unboxed.html 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 | + | There are also mutable unboxed arrays: <tt>IOUArray</tt> and <tt>STUArray</tt> (see [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-IO.html Data.Array.IO] and [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-ST.html Data.Array.ST] respectively). Using unboxed mutable arrays is often a good way to translate imperative algorithms into Haskell with similar performance. |
Revision as of 23:14, 12 January 2006
Haskell Performance Resource
Constructs: Techniques: |
1 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).
2 GHC-specific techniques
2.1 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.