[Haskell-cafe] Re: Haskell Speed

[Bulat Ziganshin]

Hello Branimir,

Friday, December 30, 2005, 3:44:26 AM, you wrote:
BM> myHashString = fromIntegral . ff''' . ff'' . ff' . foldr f 0

i use the following hash function in my program:

filenameHash  =  fromIntegral . foldl (\h c -> h*37+(ord c)) 0

(it's written without explicit parameter in order to try to help GHC
machinery better optimize this function)

BM> All in all functional version consumes less memory and is twice as
BM> fast.

IOArrays is second-class citizens in GHC/Haskell. they are scanned on
_each_ GC, and this can substantially slow down program which uses
large IOArrays. below is two runs of the almost the same program using
different array types. this program unpickles 10^6 Word32 values,
using 

1) Array Int Word32
2) IOArray Int Word32

first program just unpickles list and then uses listArray to transform
it to Array, while the second program writes unpickled values directly
to IOArray. the second solution uses less memory, creates less temporary
data and obviously must be faster. but really it works 8 times slower
because these dramatical GC times

for your program, things will be not so bad because IOArray, used inside
your HashTable, contains far less than million elements and
because your program has more to do itself. but try to compare MUT
time of functional and imperative version - may be your algorithm is
really faster and only GC times makes this comparision unfair

.. writing this message i thought that reducing number of GCs can
speed up my program and your program too. so there is third variant -
using IOArray, but with "+RTS -A100m"


>1) Array Int Word32

make array: 1.392 secs (arr = listArray0 [1..10^6] :: Array Int Word32)
put array: 1.833 secs  (put_ h arr)
get array: 2.163 secs  (a <- get h :: IO (Array Int Word32))

381,202,596 bytes allocated in the heap
143,766,944 bytes copied during GC
 24,937,228 bytes maximum residency (8 sample(s))

       1439 collections in generation 0 (  1.65s)
          8 collections in generation 1 (  0.77s)

         54 Mb total memory in use

  INIT  time    0.01s  (  0.00s elapsed)
  MUT   time    2.88s  (  2.93s elapsed)
  GC    time    2.42s  (  2.45s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    5.32s  (  5.39s elapsed)

  %GC time      45.6%  (45.5% elapsed)

  Alloc rate    131,721,698 bytes per MUT second

  Productivity  54.2% of total user, 53.5% of total elapsed



>2) IOArray Int Word32

make array: 6.569 secs (v <- newListArray (0,10^6-1) [1..10^6] :: IO (IOArray Int Word32))
put array: 14.110 secs (put_ h arr)
get array: 23.874 secs (a <- get h :: IO (IOArray Int Word32))

360,377,080 bytes allocated in the heap
 87,007,920 bytes copied during GC
 18,237,472 bytes maximum residency (6 sample(s))

       1344 collections in generation 0 ( 40.77s)
          6 collections in generation 1 (  0.38s)

         36 Mb total memory in use

  INIT  time    0.01s  (  0.00s elapsed)
  MUT   time    3.15s  (  3.16s elapsed)
  GC    time   41.15s  ( 41.40s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   44.31s  ( 44.56s elapsed)

  %GC time      92.9%  (92.9% elapsed)

  Alloc rate    114,007,301 bytes per MUT second

  Productivity   7.1% of total user, 7.1% of total elapsed


  
>3) IOArray Int Word32 with "+RTS -A100m"

make: 0.391 secs
put: 2.343 secs
get: 2.003 secs

440,654,968 bytes allocated in the heap
 26,413,568 bytes copied during GC
 20,043,828 bytes maximum residency (2 sample(s))

          4 collections in generation 0 (  0.23s)
          2 collections in generation 1 (  0.64s)

        120 Mb total memory in use

  INIT  time    0.02s  (  0.00s elapsed)
  MUT   time    3.81s  (  3.83s elapsed)
  GC    time    0.87s  (  0.90s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    4.71s  (  4.74s elapsed)

  %GC time      18.6%  (19.1% elapsed)

  Alloc rate    114,963,466 bytes per MUT second

  Productivity  81.0% of total user, 80.5% of total elapsed
  

-- 
Best regards,
 Bulat                            mailto:bulatz at HotPOP.com