Opened 23 months ago

Last modified 7 days ago

#13165 new bug

Speed up the RTS hash table

Reported by: dobenour Owned by:
Priority: normal Milestone:
Component: Runtime System Version: 8.1
Keywords: newcomer Cc: simonmar, mboes, ThrashAbaddon
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by simonmar)

The RTS hash table is rather slow. Every lookup involves at least one indirect call (to get a hash code). It also uses separate chaining, which is itself slow.

Until recently, this didn't really matter, since the RTS hash table wasn't used for anything particularly performance critical other than StableName operations. However, it has since become the bottleneck when compacting with sharing, to the point that compacting without sharing is around 10x faster and is thus the default.

Fortunately, there are easy ways to make the hash table faster. These include:

  • Use linear probing instead of separate chaining.
  • Specialize for the case of pointer keys
  • Don't use indirect calls for hashing
  • Use a fast, universal hash function for pointers.
  • Use SSE instructions where available to do fast searches.
  • Minimize the number of indirections in the use of the table.

In both the case of the StablePtr table and that of compact regions, the keys of the table are not GC pointers, but the values are, so there needs to be a way to ensure that the GC handles the table correctly

Change History (16)

comment:1 Changed 23 months ago by simonmar

This would be great - are you planning to do it?

To avoid the indirect calls don't we need to specialise the hash table to the key type? There are at least two key types in use (strings and pointers).

Also, couldn't we pull in a good third-party hash table implementation instead of writing our own? When I was working on the compact code I did try https://troydhanson.github.io/uthash/userguide.html but it was slower than the RTS hash table. I'm sure there are better ones.

comment:2 Changed 23 months ago by simonmar

Description: modified (diff)

comment:3 Changed 23 months ago by siddhanathan

Different implementations for different key types would be nice. Doing so would allow type specific optimizations, such as using judy arrays for string keys.

comment:4 Changed 21 months ago by bgamari

Milestone: 8.2.18.4.1

Given that 8.2.1-rc1 is imminent, I'm bumping these off to the 8.4

comment:5 Changed 16 months ago by Ben Gamari <ben@…>

In 542f89f/ghc:

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

comment:6 Changed 16 months ago by bgamari

The switch to xxhash should help although I suspect more can be done here.

comment:7 Changed 16 months ago by simonmar

The xxHash patch only improves hashing for strings, compaction uses address hashing which is unaffected.

comment:8 Changed 11 months ago by bgamari

Milestone: 8.4.18.6.1

This ticket won't be resolved in 8.4; remilestoning for 8.6. Do holler if you are affected by this or would otherwise like to work on it.

comment:9 Changed 9 months ago by bgamari

Keywords: newcomer added
Milestone: 8.6.1

Removing milestone as no one is currently working on this.

Do holler if this is something that you would be interested in trying.

comment:10 Changed 6 months ago by Crazycolorz5

I'd be interested in helping in resolving this ticket. I'm just a bit unclear as to what needs to be altered / what it's used for. I see the previous changes improve string hashing, but word hashing seems fairly swift (no library calls, just bit-level manipulations) as-is? Are there specific examples that may illustrate the suboptimal performance?

comment:11 Changed 6 months ago by simonmar

@Crazycolorz5 for a benchmark, try compacting a large data structure with Data.Compact.compactWithSharing. A good way to get some sample data is to take a large JSON and decode it using Aeson.

comment:12 Changed 4 months ago by NoidedSuper

I'm going to take a crack at implementing a linear probing table today, since that seems to be the easiest thing to do. I think specializing the hash table for different key types will probably yield more performance benefits in the long run, but getting some cache-friendliness with linear probing is better than nothing!

comment:13 Changed 4 months ago by bgamari

I'm looking forward to hearing how it goes!

comment:14 Changed 4 months ago by NoidedSuper

Well, I attempted an implementation at https://phabricator.haskell.org/D5073, but sadly the test suite seems to break when you run the check (although just building, compiling, and running was working fine). I haven't had the chance to look too much at it but I'm guessing I have a problem with either deleting or mapping over hash tables. I'll work on it some more tomorrow, see if I can fix it. Of course, help is always appreciated!

comment:15 Changed 4 months ago by mboes

Cc: mboes added

comment:16 Changed 7 days ago by ThrashAbaddon

Cc: ThrashAbaddon added
Note: See TracTickets for help on using tickets.