Opened 3 years ago

Last modified 6 days ago

#7662 new feature request

Improve GC of mutable objects

Reported by: ezyang Owned by:
Priority: normal Milestone:
Component: Runtime System Version: 7.7
Keywords: Cc: lelf, jwlato@…, ikke+ghc@…, simonmar, idhameed@…, osa1
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

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!

Change History (11)

comment:1 Changed 3 years ago by jwlato

  • Cc jwlato@… added

comment:2 Changed 3 years ago by simonmar

  • difficulty set to Unknown
  • Milestone set to _|_

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).

comment:3 Changed 3 years ago 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.

comment:4 Changed 3 years ago 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.

comment:5 Changed 3 years ago by nicolast

  • Cc ikke+ghc@… added

comment:6 Changed 2 years ago by simonmar

  • Cc simonmar added

comment:7 Changed 2 years ago by ihameed

  • Cc idhameed@… added

comment:8 Changed 13 months ago by lelf

  • Cc lelf added

comment:9 Changed 12 days ago by dobenour

MLton does manage to unpack refs in records though. I think that it can be done in general IF you either:

  • support interior pointers in the GC (which GHC probably doesn't).
  • represent mutable refs as "fat pointers", consisting of both a pointer to the object being mutated and a pointer to the cell within the object. In this case
    data SomeType = SomeType { x :: {-# UNPACK #-} !(IORef Int)
                             , y :: {-# UNPACK #-} !Char
                             }
    getRef :: SomeType -> IORef Int
    getRef = x
    

x (v :: SomeType) would produce an object that contains a pointer to v (for the GC) and a pointer to field x of v (used to mutate x).

comment:10 Changed 12 days ago by rwbarton

I think this has been discussed elsewhere too, but I don't understand how the above could be consistent with Haskell's semantics. What if I define

upperize :: SomeType -> SomeType
upperize s = s { y = toUpper (y s) }

Obviously this needs to allocate a new SomeType closure on the heap, but if the IORef Int is completely unpacked into a mutable field of SomeType closures, then the new closure can't share x with the old closure. In general just constructing a SomeType value would have the observable effect of creating a new mutable cell and so would have to live in IO.

In short, ML's records with mutable fields have identity, and so are quite different than just sticking an IORef inside a record in Haskell. In Haskell the IORef itself has identity (and thus is created and accessed through IO actions) but the record SomeType does not.

comment:11 Changed 6 days ago by osa1

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