Personal tools

Performance/Arrays

From HaskellWiki

< Performance(Difference between revisions)
Jump to: navigation, search
m (Added question)
(moved question to talk page)
Line 9: Line 9:
   
 
* See also [[Arrays]], a thorough exploration of the various array types available in most Haskell compilers.
 
* See also [[Arrays]], a thorough exploration of the various array types available in most Haskell compilers.
 
Q: What is meant by "arrays are monolithic" above? Just that they are constructed all in one go?
 
   
 
== GHC-specific techniques ==
 
== GHC-specific techniques ==

Revision as of 04:13, 17 January 2006

Haskell Performance Resource

Constructs:
Data Types - Functions
Overloading - FFI - Arrays
Strings - Integers - I/O
Floating point - Concurrency
Modules - Monads

Techniques:
Strictness - Laziness
Avoiding space leaks
Accumulating parameter

Implementation-Specific:
GHC - nhc98 - Hugs
Yhc - JHC

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).
  • See also Arrays, a thorough exploration of the various array types available in most Haskell compilers.

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.