[GHC] #13165: Speed up the RTS hash table

[GHC]

#13165: Speed up the RTS hash table
-------------------------------------+-------------------------------------
        Reporter:  dobenour          |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.4.1
       Component:  Runtime System    |              Version:  8.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Ben Gamari <ben@…>):

 In [changeset:"542f89ff23e4deb66debca0b5de3ac3047befb28/ghc" 542f89f/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="542f89ff23e4deb66debca0b5de3ac3047befb28"
 Replace hashing function for string keys implementation with xxhash

 When doing profiling on startup time of ghci on Windows, both cold and
 startup loading static LLVM libs, the profiler is showing a glaring red
 spot on the division operation of the the hashStr function.

 In fact profiling shows 14% of the time is spent hashing the keys.

 So I am replacing the hash function with xxHash which is a very fast
 non-crypto hash. It's faster than MurMurHash which node etc use.

 It also passes SMHasher. I can provide if required the collected raw
 data.  But from analysis done on the keys, xxHash does not introduce
 more collisions than before, the amount splits seem about the same and
 the distributions among the buckets are slightly more uniform than
 before.

 However the runtime dropped enough to remove the function completely
 from the profiler's report.

 There's also a noticeable improvement in responsiveness.

 xxHash is BSD licensed and can be found
 https://github.com/Cyan4973/xxHash

 Test Plan: ./validate

 Reviewers: austin, bgamari, erikd, simonmar

 Reviewed By: bgamari

 Subscribers: rwbarton, thomie

 GHC Trac Issues: #13165

 Differential Revision: https://phabricator.haskell.org/D3909
 }}}

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13165#comment:5>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler