[GHC] #7662: Improve GC of mutable objects
#7662: Improve GC of mutable objects -----------------------------+---------------------------------------------- Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Component: Runtime System Version: 7.7 | Keywords: Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Blockedby: Blocking: | Related: -----------------------------+---------------------------------------------- Haskell is a purely functional language at its core, but it can be also used for workloads involving mutation; it is for these workloads that our GC can be pretty poorly tuned (historically, we’ve fixed these issues case-by-case when they were causing problems for users, e.g. #650). Fortunately, the question of generational garbage collection in the face of lots of mutability is a well-studied one (c.f. the JVM) so this bug asks whether or not we can systematically appropriate any of the machinery developed here for GHC. Some ideas include: * Utilizing card marking at the page level for write barriers, instead of our current mutable lists, * Separating mutable and immutable (and lazy) data on the heaps, to make the previous scheme more likely to work well, * Organizing our generations in different pages, so that checking the generation of any object is as simple as a pointer comparison, * Figure out if we can do better than permanently keeping all mutable arrays permanently on the mutable list (which is really killer when you have lots of tiny mutable arrays), * More mutable closure types to remove the indirection that would normally result from an IORef (actually, you can UNPACK these, and I’m not 100% what happens in that case; it depends on how MutVar#s are represented) There’s probably more things but this is just a start to get things rolling. Test cases and benchmarks also appreciated! -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7662: Improve GC of mutable objects -----------------------------+---------------------------------------------- Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Component: Runtime System Version: 7.7 | Keywords: Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Blockedby: Blocking: | Related: -----------------------------+---------------------------------------------- Changes (by jwlato): * cc: jwlato@… (added) -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7662: Improve GC of mutable objects ---------------------------------+------------------------------------------ Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Milestone: _|_ Component: Runtime System | Version: 7.7 Keywords: | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: | ---------------------------------+------------------------------------------ Changes (by simonmar): * difficulty: => Unknown * milestone: => _|_ Comment: One problem with card marking is that you need to be able to traverse the heap linearly to scan the objects in a card. GHC's heap doesn't support this, because we have gaps between objects left behind when a thunk is overwritten by an indirection. It's possible to fill in the gaps (we do this when `DEBUG` is enabled), but it's a fair bit of overhead on every update. This is why we only have card marking for arrays. We should have a small array type that uses the same write barrier as a `MutVar#`, i.e. it isn't on the mutable list until it is modified, and there's no card marking. This would help in the `unordered-containers` package I believe. I've often wondered whether we can fully unpack an `IORef`, that is have a mutable pointer field in an ordinary constructor. It would be nice if we could do it, but I fear it is hard to achieve - you can't re-box a mutable field like you can with an immutable field. Perhaps we could represent a `MutVar#` as a pointer plus an offset instead. (I'm leaving the milestone for this at _|_, which is not to say that none of this will ever happen, just that we don't have concrete plans right now). -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7662: Improve GC of mutable objects ---------------------------------+------------------------------------------ Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Milestone: _|_ Component: Runtime System | Version: 7.7 Keywords: | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: | ---------------------------------+------------------------------------------ Comment(by josef): The ML community has though quite a bit about unpacking refs in datatypes and records. It's hard to do a good job in general and this is the reason that ocaml includes the `mutable` keyword to allow the programmer to specify that a record field should be mutable. The ocaml compiler can generate pretty tight code for mutable record fields. I suppose we could have something similar in Haskell but it would take some work to iron out all the details. My feeling is that it would require coming up with new syntax for setting and getting mutable fields. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7662: Improve GC of mutable objects ---------------------------------+------------------------------------------ Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Milestone: _|_ Component: Runtime System | Version: 7.7 Keywords: | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: | ---------------------------------+------------------------------------------ Comment(by simonmar): I wanted to record an idea that occurred to me: if we were to switch to a mark/sweep (probably mark-region, e.g. Immix) collection for the old generation, which is something I've been wanting to try for some time, then it gives us a way to do card marking. The idea is to retain the bitmap after GC, and use it to find the live objects when sweeping a marked card. The bitmap costs ~3% extra heap size on a 32-bit machine, half that on 64-bits. I'm quite optimistic that mark-region would be a win, and furthermore, because mark/sweep is non-destructive, it could be done incrementally, or concurrently with the mutator (you have to be careful about mutation, but the write-barrier techniques for doing this are well known). The idea is that going incremental or concurrent would improve pause times. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7662: Improve GC of mutable objects ---------------------------------+------------------------------------------ Reporter: ezyang | Owner: Type: feature request | Status: new Priority: normal | Milestone: _|_ Component: Runtime System | Version: 7.7 Keywords: | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: | ---------------------------------+------------------------------------------ Changes (by nicolast): * cc: ikke+ghc@… (added) -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7662#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC