[GHC] #8158: Replace IO manager's IntMap with a mutable hash table
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------------------+------------------------------- Reporter: bos | Owner: Type: feature request | Status: new Priority: normal | Milestone: 7.8.1 Component: libraries/base | Version: 7.7 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Easy (less than 1 hour) | Type of failure: Other Blocked By: | Test Case: Related Tickets: | Blocking: -------------------------------------------+------------------------------- I've written a patch that replaces the immutable !IntMap used by GHC.Event with a mutable hashtable, !IntTable. There's a standalone version of the new data structure, complete with !QuickCheck tests and benchmarks, [[https://github.com/bos/inttable|available on github]]. It's about 15x faster than !IntMap, and substantially simpler. In practice, this translates to a small but measurable improvement in throughput (and presumably latency). I see a 3% to 10% bump in requests handled per second by the tiny [[http://hackage.haskell.org/package/acme- http|acme-http http server]] when benchmarked using the [[https://github.com/lighttpd/weighttp|weighttp load tester]]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by bos): * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by hvr): * cc: hvr (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by tibbe): * cc: tibbe (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by hvr): ...what's the benefit of using a `ForeignPtr Int` over `IORef Int` in {{{#!hs data IT a = IT { tabArr :: {-# UNPACK #-} !(Arr (Bucket a)) , tabSize :: {-# UNPACK #-} !(ForeignPtr Int) } }}} ? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by tibbe): Same question as hvr, otherwise LGTM. I'd like Andreas to have a look as well. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by hvr): Now that I think of it, the motivation might be, that decrementing/incrementing a `IORef Int` might require to allocate new `I#`s and let the previous `I#` become garbage, as `IORef Int` doesn't unpack the `Int` value. (However, if that's really the case, isn't there some kind of lightweight (unpackable) "unboxed" IORef for integers types with [https://developer.gnome.org/glib/unstable/glib-Atomic-Operations.html atomic operations] provided by GHC somewhere?) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by bos): The !ForeignPtr avoids additional boxing, as hvr observes. The atomic ops stuff that he points at does the same thing behind the scenes, except using a !MutableByteArray#. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by simonmar): @bos: GHC has a `FastMutInt` type for this purpose, which is a 1-element mutable unboxed array. I'd be interested to know whether performance differs between this and `ForeignPtr`. source:ghc/compiler/utils/FastMutInt.lhs -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by nicolast): * cc: ikke+ghc@… (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: Type: feature | Status: patch request | Milestone: 7.8.1 Priority: normal | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by simonmar): I should clarity: I'm not suggesting that switching to `FastMutInt#` is a prerequisite for the patch going in. `ForeignPtr` is fine by me. I'd just be interested in the difference if anyone felt like measuring it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by thoughtpolice): * owner: => AndreasVoellmy * priority: normal => high Comment: As an aside, this validates cleanly for me, and the overall patch looks fairly principled and straightforward after reviewing. Unfortunately I obviously don't have a machine to measurably test any real differences (the patch mentions increases on dual 32 core machines with 10gbE links, which I don't really have hanging around.) Andreas - could you take a look please? Feel free to merge this yourself if you'd like, or otherwise just give the OK. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by kazu-yamamoto): One concern is that IntTable does not shrink. When many connections come, this table grows. Then, even if the upper half table becomes not used at all, this table does not shrink. If I understand correctly, the size of this table possibly grows to the size of Int64. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by kazu-yamamoto): If you guys are interested in to make multicore IO manager faster, please give a look at witty: https://github.com/kazu-yamamoto/witty I think that the biggest bottleneck is the overhead of MVar. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): Replying to [comment:11 thoughtpolice]:
Andreas - could you take a look please? Feel free to merge this yourself
if you'd like, or otherwise just give the OK. Sorry - I've been out of touch for the past week. I'll be able to take a look at this at the end of the week and over the weekend. I'll run tests on my big multicore machine that I used for the mio paper. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by kazu-yamamoto): Andi, you should not execute "git pull" on your ghc source directroy. The latest GHC can be built but "cabal install <something>" with the latest GHC head fails. You should use the GHC source tree on your machine as it is. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): In GHC.Event.IntTable.grow, why is a new bucket created, with Arr.write called for each item in the bucket? Couldn't you copy the bucket with a single write, copying the bucket in the old array to the new array? I see that you want to know the number of items in the bucket, but couldn't you count this but avoid the many writes? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by bos): The keys need to be rehashed so they can be found after the arrays grows. For instance, fd 53 hashes to slot 5 if the array size is 16, but to slot 21 after growing the array to 32 entries. Is this what you're asking about? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): OK, I see now. It looks good to me. I'll do a few tests later today. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): OK, I re-did the measurement of acme-http (pong) scaling with the same setup as I used in the Mio paper (same server, same acme parameters (-A32m), same test machine and software (weighttp), etc). I've attached the graph. On my server the patch does make a small, but noticeable improvement of about 5-10% improvement for values of -N parameter from 1-4. At higher cores I can't see any difference. @bos: does my measurement seem reasonable to you? Are you seeing the same thing? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by bos): That matches what I see: a nice performance bump with a small number of cores, and it's harder to see an effect as the number of cores increases. (No idea why, but presumably it means there's a bottleneck somewhere else as the core count rises.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): Great. The patch looks good to me. I'll validate and push. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by thoughtpolice): Thanks Andreas! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by bos): Thanks, Andi! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): I only had 1 unexpected failure due to T7918, which doesn't seem to be related. So I went ahead and pushed the patch. Thanks Bryan! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: patch request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Comment (by AndreasVoellmy): What is the right status? Should it be marked "fixed in GHC HEAD" or "resolve as fixed"? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#8158: Replace IO manager's IntMap with a mutable hash table -------------------------------+------------------------------------------- Reporter: bos | Owner: AndreasVoellmy Type: feature | Status: closed request | Milestone: 7.8.1 Priority: high | Version: 7.7 Component: | Keywords: libraries/base | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Easy (less than 1 hour) Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Other | Test Case: | Blocking: | -------------------------------+------------------------------------------- Changes (by thoughtpolice): * status: patch => closed * resolution: => fixed Comment: You just want to resolve as 'fixed', since "fixed in HEAD" will put it in the merge state. We don't need this yet because we haven't cut a 7.8 branch. Thanks a lot Andreas! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8158#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC