#14854: The size of FastString table is suboptimal for large codebases -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Context: I was profiling a no-op rebuild (build once, do incremental build with nothing changed) of a large code base. It takes `35.829s`, and according to the profile about `20%` of the time is spent in `mkFastStringByteString`. I run it with `-dfaststring-stats +RTS -s` and got: {{{ FastString stats: size: 4091 entries: 829959 longest chain: 268 has z-encoding: 0% 50,011,906,640 bytes allocated in the heap 7,936,277,664 bytes copied during GC 3,106,526,336 bytes maximum residency (8 sample(s)) 123,108,224 bytes maximum slop 10169 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 117 colls, 37 par 32.390s 2.293s 0.0196s 0.0911s Gen 1 8 colls, 3 par 19.722s 2.266s 0.2832s 0.6936s Parallel GC work balance: 60.62% (serial 0%, perfect 100%) TASKS: 93 (1 bound, 92 peak workers (92 total), using -N30) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.009s ( 0.009s elapsed) MUT time 277.370s ( 31.261s elapsed) GC time 52.113s ( 4.558s elapsed) EXIT time 0.005s ( 0.001s elapsed) Total time 329.497s ( 35.829s elapsed) Alloc rate 180,307,295 bytes per MUT second Productivity 84.2% of total user, 87.3% of total elapsed }}} That's pretty bad, fitting `800k` elements in `4k` buckets is hard. To confirm this indeed could be improved I changed the size to `2^20` (`1048576`) and also removed division in `hashStr` function (it come up on `perf` profile), like this: {{{ hashStr :: Ptr Word8 -> Int -> Int -- use the Addr to produce a hash value between 0 & m (inclusive) hashStr (Ptr a#) (I# len#) = loop 0# 0# where loop h n | isTrue# (n ==# len#) = I# h | otherwise = loop h2 (n +# 1#) where !c = ord# (indexCharOffAddr# a# n) -- !h2 = (c +# (h *# 128#)) `remInt#` -- hASH_TBL_SIZE# -- NOTE: below is multiplication by 127 (a prime) and division by 2^20, it's by no means the best hashing function !h2 = (c +# ((h `uncheckedIShiftL#` 7#) -# h)) `andI#` hASH_TBL_SIZE_MASK# }}} Here's what I ended up with: {{{ FastString stats: size: 1048576 entries: 829959 longest chain: 8 has z-encoding: 0% 51,012,218,048 bytes allocated in the heap 8,948,377,768 bytes copied during GC 3,543,797,248 bytes maximum residency (8 sample(s)) 139,428,352 bytes maximum slop 10502 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 115 colls, 39 par 32.261s 2.677s 0.0233s 0.2225s Gen 1 8 colls, 3 par 21.786s 2.329s 0.2911s 0.5737s Parallel GC work balance: 48.75% (serial 0%, perfect 100%) TASKS: 93 (1 bound, 92 peak workers (92 total), using -N30) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.008s ( 0.008s elapsed) MUT time 65.508s ( 23.791s elapsed) GC time 54.047s ( 5.006s elapsed) EXIT time 0.007s ( 0.001s elapsed) Total time 119.570s ( 28.806s elapsed) Alloc rate 778,712,134 bytes per MUT second Productivity 54.8% of total user, 82.6% of total elapsed }}} The realtime improvement is nice (`-20%`), but even nicer is the "serial" time improvement, from `329.497s`to `119.570s` (`2.75x` speedup). This is on modified 8.0.2, but the related code looks about the same on HEAD. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14854 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler