Writing kernel modules in Haskell [LWN.net]

Writing kernel modules in Haskell

Posted Sep 14, 2009 5:11 UTC (Mon) by jordanb (subscriber, #45668)
In reply to: Writing kernel modules in Haskell by nix
Parent article: Writing kernel modules in Haskell

You can do real-time garbage collection, such that any GC run will not take more than a given amount of time, but you then can't guarantee that all stale objects will be collected. If the GC strategy is to run to free space for a given newly-created object when a limit is reached, you can't guarantee that space for the object will be found in the given amount of time, even if it is available somewhere.

Think about it like this. Someone asks you to do a finite-time tree traversal, where the tree can be of an arbitrary size. You can't guarantee complete traversal and the time constraint at the same time. You can only meet the constraint by being willing to stop traversal early.

In the case of GC you may be willing to stop before traversal is complete, and you can work out your strategy such that you're likely to make gains early. But the time constraint means that there will always be a possibility of failing to find sufficient space even when it exists.

(Log in to post comments)

Writing kernel modules in Haskell

Posted Sep 14, 2009 6:03 UTC (Mon) by nybble41 (subscriber, #55106) [Link]

I'm not sure about the GC strategies you're referring to, but it is at least possible to implement a compacting GC algorithm in real-time. The trick is that you don't try to set an upper bound on the time required to traverse the entire active set; rather, you perform part of the GC at every allocation, and include some translation/bookkeeping when reading or writing pointer fields. The amount of work performed per allocation determines the amount of extra memory needed vs. your maximum active set: more time spent on GC per allocation results in more efficient use of memory.

Writing kernel modules in Haskell

Posted Sep 14, 2009 8:26 UTC (Mon) by nix (subscriber, #2304) [Link]

Yes indeed. This is part of how the Metronome GC works, for instance: GC
times with that can be in the submillisecond range.

Writing kernel modules in Haskell

Posted Sep 14, 2009 18:57 UTC (Mon) by Pc5Y9sbv (guest, #41328) [Link]

Right, while deterministic GC is unsolvable (reduces to halting problem), the realistic goal is just to converge towards the same non-deterministic memory usage as well-designed manual memory management for the same application.

Through compile-time analysis and incremental GC methods, you can play with these space and time overheads and with their granularity.

Writing kernel modules in Haskell

Posted Sep 17, 2009 2:51 UTC (Thu) by Pseudonym (guest, #60861) [Link]

Of course. The issue here is essentially how you want to divide up work between the programmer and the implementation.

There's always the risk of your GC not having enough time to reclaim all of memory, but that is a risk with a non-GC'd implementation, too.

First off, deallocating memory is always more expensive than allocating it in a concurrent environment. You can allocate memory from whichever region has the lowest contention, but you can only deallocate it to the place that it came from.

Secondly, if your time constraints were that tight, then you probably didn't have enough time to manually free all that memory right now, either.

Yes, there's always the possibility of your program misbehaving. But in the real-time space, that's always a risk. Using a GC'd implementation doesn't free you from hard thinking, it just frees you from bothering with a certain amount of boilerplate.