[commit: containers] master: Improve performance of folds. (e076b33)

[Ian Lynagh]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/containers

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/e076b33f4cee3f657b5bdc5bf6f5a4c9e249d00c

>---------------------------------------------------------------

commit e076b33f4cee3f657b5bdc5bf6f5a4c9e249d00c
Author: Milan Straka <fox at ucw.cz>
Date:   Sat Nov 19 10:54:06 2011 +0100

    Improve performance of folds.
    
    We use wordsize-dependent implementation for GHC, for both
    32-bit and 64-bit architectures.
    
    It is based on fast constant-time implementation of indexOfTheOnlyBit,
    which computes index of the only bit set in a word, suggested
    by Edward Kmett.
    
    Using that we can enumerate indexes of 1 bits, in the order from
    LSB to MSB. That results in fast foldl implementations.
    
    Foldr implementations bit-reverse the word and then iterate from the LSB
    to MSB using accumulator. That is faster then either not using
    accumulator or iterating from MSB to LSB.

 Data/IntSet.hs |  189 +++++++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 146 insertions(+), 43 deletions(-)


Diff suppressed because of size. To see it, use:

    git show e076b33f4cee3f657b5bdc5bf6f5a4c9e249d00c