CS 888

I haven’t updated the blog in a bit, so I thought I’d write a bit about what’s happened. First of all, I have some vindication for my 833 project, yesno. This past week there was a small thread on comp.functional about Boehm GC on OS X and how it sucks. Apparently there is some problem with reliably getting the registers on OS X—one poster claimed it to be “Apple’s fault”. In any case, I don’t feel so bad about having to work around libgc weirdness with yesno now.

My 833 project apparently went alright too. I was nervous handing it in, as ghc is fickle to get compiling and working, and I just sort of duct taped it together as best I could and handed it to Watt, half-expecting him to email me back the next day saying “how in the hell do you get this thing working?”. But I checked my mark today: after two courses I’m now sitting with a 100.0 GPA—it’s a little unsettling—so I’ll have to talk to him some time and see what he liked about it.

I’ve shifted my focus to static analysis of functional languages with real-time applications: primarily guaranteeing time and memory constraints. I’m vaguely playing around with Martin-Löf type theory, trying to come up with a good model to capture caching policy, with the aim of hopefully coming up with some cool cache model to submit to POPL this summer.


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.

A Google search for real-time haskell yields little of interest, which I suppose isn’t too surprising. Haskell, if you’re not familiar, is not just a pure functional language, but a lazy one. On the surface, this makes it a dreadfully poor choice for a couple of reasons.

  1. Haskell code tends to be slow. I’ve started using the Gentoo language shootout as my baseline for language comparisons—it seems fairly unbiased if nothing else—and with a few exceptions, Haskell just doesn’t stack up well. This isn’t too surprising: laziness adds overhead. My mentioning performance might get the hardcore real-timers in a tiff—theoretically performance has nothing to do with real-time—but in the real world, real-time is typically either done in embedded situations where hardware resources are scarce, or else we’re in a soft real-time situation playing pr0n, and speed is important.
  2. Haskell code is unpredictable. This is the biggest flaw in Haskell that Simon Peyton-Jones has offered (that I’m aware of). When tracing through Java code, it’s trivial to derive complexity, and even a rough gauge on absolute running time, just by glancing at the code. Laziness takes this all away. I’ll talk about this in a later post perhaps.
  3. Haskell is garbage collected.

It’s that last point I want to talk about. Garbage collection is typically not used in real-time systems, particularly hard real-time systems, for good reason. Imagine writing the quintessential real-time example code—nuclear power plant code; yes, I can dream—and you’ve reserved your time slice, grabbed your mutex, and then the garbage collector decides to run for 400ms. Not cool.

For my CS 888 project, I think I’m going to propose changing Haskell’s garbage collector to provide a real-time interface. Something along the lines of:
gcNextCollectionUpperBound :: IO Int
gcBound :: Int -> IO a -> IO a

The first function would give an upper bound on how long the next round of garbage collection would take (in milliseconds). The second function/combinator would execute a section of code, guaranteeing a bound on the amount of time garbage collection will take, such as:
do  gcTime <- gcNextCollectionUpperBound
    return $ gcBound (gcTime + 200) do
        requestTimeSlice (gcTime + 200)
        mutex <- getMutex
        giveUpMutex mutex
        return answer

This way we’re guaranteed that we complete saveLives before the garbage collector eats up all our time. So that’s about all I need for the interface; all I need now is the implementation. Yay, I’m half done!

GHC’s documentation on its garbage collector is a big weak, so I’ll have to dig into the source. My understanding through a bit of reading is that right now GHC uses a hybrid system, with almost all programs using the copy collector exclusively, and the other part of the system being a generational collector. This is somewhat exciting because I haven’t found any papers yet discussing real-time copy collector systems yet.

We’ll see how far I get in this. The nice thing about a project like this is that a naïve implementation can be done hopefully without too much work (do garbage collecting until you run out of time, then just give up). Even coming up with a naïve upper bound is easy (return INT_MAX). But the project offers itself to putting effort into a more finessed solution, too.

I don’t know, we’ll see what Watt says about it.