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@HotPOP.com

Hello Branimir, Saturday, December 31, 2005, 4:55:51 AM, you wrote:

...

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.

BM> Hm, there is Hans Boehm GC for C and C++ and I have gcmalloc and BM> gcmalloc_atomic. Why this isn;t present in Haskel? gcmalloc_atomic is BM> usefull BM> when allocating large arrays that does not contain any references/pointers. because these arrays CONTAINS references :) they reference all the values inserted in the array so far there is also IOUArray, which contains plain unboxed values of simple types (Int, Float..) and don't slow down the program

...

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

BM> Wow, that option almost doubled speed of HashTable program (memory leak BM> remains).

use option "+RTS -sstderr" to see runtime of the program itself ("MUT time") and "GC time" separately. see section "4.14.2. RTS options to control the garbage collector" of GHC guide for more information -- Best regards, Bulat mailto:bulatz@HotPOP.com