I’ve mentioned before my CS888 project, which is taking GHC‘s garbage collector and adding real-time hooks into it. There will be two functions exported on the Haskell level: Control.RealTime.gcNextCollectionUpperBound :: IO Int and Control.RealTime.gcBound :: Int -> IO a -> IO a. The latter function is “where the magic happens” (after Mark pointed out that I used this phrase 3 times in my comments in my CS833 project source, I realize I use it all the time). Indeed the former function isn’t even necessary, but is useful for making garbage collection more predictable. But the latter function is used to force the garbage collector to limit itself during some chunk of code and not go off on some tangent collecting, behaviour which would be disastrous in real-time code. Note that gcBounds can be nested.

I bolded the word “force” up there, because I want to stay hard real-time if at all possible. If the user wants soft and I provide hard, that’s just a bonus. If the user wants hard and I proved soft, that’s no good.

The more I think about gcNextCollectionUpperBound, the tricker it gets. In case its name is not clear, its job is to estimate how long it thinks the next round of garbage collection will take, in milliseconds. This function should be fairly quick—it shouldn’t simulate a collection just to figure out how much garbage there is; it should be moderate accurate—hopefully within an order of magnitude in most cases; and it should return a hard upper bound, such that it is impossible for garbage collection to take more than the number returned.

So, consider the worst case scenario for garbage collection. The worst case is that garbage collection will have to swap in, from disk, the objects that it’s collecting. In the worst case, pages will be scattered all throughout, such that it will have to do a swap for every page. Thus, if we assume an 8ms seek time on the hard drive, the hard upper bound is 8p, where p is the number of pages to be collected. Then you think: maybe even assuming an 8ms seek time isn’t being hard enough; maybe the user is running this real-time system with a network-mounted swap partition, and the swap file is actually on Mars. Then the hard upper bound is something like 2400000p. Suddenly it seems obvious that getting a bound within an order of magnitude—one of the properties I wanted for gcNextCollectionUpperBound is looking hopeless.

Probably I will have to abandon my dream of returning a hard upper bound. This isn’t the end of the world: as long as gcBound provides a hard guarantee, that’s all that matters in the end. Probably what I will do to get a soft upper bound is:

  1. set up some compile-time latency constants: something like 8ms for swap, 1μs for RAM, 1ns for cache;
  2. come up with some arbitrary hand-wavish heuristics for semi-conservatively guessing when a page is going to come up from one of those 3 locations;
  3. look at total memory usage and start multiplying page numbers by constants.

It’s point #2 that’s the hard one, and I’m sceptical as to how much I’ll be able to glean about the structure of the heap without actually diving into it.

This is sadly the only research I’ve found on the subject.

Advertisements