Personal tools

Performance/Arrays

From HaskellWiki

< Performance(Difference between revisions)
Jump to: navigation, search
m (fixed links (libraries/base to libraries/array))
m (typo)
Line 17: Line 17:
 
=== 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/array/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/array/Data-Array-Unboxed.html Data.Array.Unboxed] 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: <tt>IOUArray</tt> and <tt>STUArray</tt> (see [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IO.html Data.Array.IO] and [http://www.haskell.org/ghc/docs/latest/html/libraries/array/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.
 
There are also mutable unboxed arrays: <tt>IOUArray</tt> and <tt>STUArray</tt> (see [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-IO.html Data.Array.IO] and [http://www.haskell.org/ghc/docs/latest/html/libraries/array/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 17:23, 28 April 2008

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).
  • 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.

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 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.

Extra strictness on functions taking unboxed arrays as arguments can help, as GHC will then unbox the array argument to a primitive type. For example, the following language shootout program for the nsieve benchmark, combining unboxed arrays, unsafe writes and strictness, runs faster than the equivalent hand-optimised C program:

import Data.Array.IO
import Data.Array.Base
import Data.Bits
import System
import Text.Printf
main = (\n -> mapM_ (sieve.(10000 *).shiftL 1) [n,n-1,n-2]) . read . head =<< getArgs
sieve m = do c <- newArray (2,m) True >>= \a -> loop a m 2 0
             printf "Primes up to %8d %8d\n" (m::Int) (c::Int) :: IO ()
loop arr m n c | arr `seq` m `seq` n `seq` c `seq` False = undefined
loop arr m n c = if n == m then return c else do
    el <- unsafeRead arr n
    if el then let loop' j | j > m     = loop arr m (n+1) (c + 1)
                           | otherwise = unsafeWrite arr j False >> loop' (j+n)
               in loop' (n+n)
          else loop (arr :: IOUArray Int Bool) m (n+1) c

It also uses bitwise arithmetic, which can further improve some code. Another note, for ghc 6.4.1 at least, an explicit loop seems to be better than mapM_.