| |||||||||||||
|
| |||||||||||||
Writing kernel modules in HaskellWriting kernel modules in HaskellPosted Sep 13, 2009 14:38 UTC (Sun) by Baylink (subscriber, #755)Parent article: Writing kernel modules in Haskell
ZOMGBBQ. These people are serious, aren't they?
It's not April 1st?
(Log in to post comments)
Writing kernel modules in Haskell Posted Sep 13, 2009 15:16 UTC (Sun) by Baylink (subscriber, #755) [Link]
No, I have a serious comment, too.
Garbage Collection? In a kernel module?
As someone who spends an inordinate amount of time staring at a spinning clock on a blackberry because *its* code is all written in garbage-collected Java, no thanks.
Writing kernel modules in Haskell Posted Sep 13, 2009 15:56 UTC (Sun) by nix (subscriber, #2304) [Link]
There is actually such a thing as hard-realtime garbage collection (where
the GC is guaranteed to take no longer than some time T to complete). It's hardly mainstream but it exists.
Writing kernel modules in Haskell Posted Sep 14, 2009 5:11 UTC (Mon) by jordanb (subscriber, #45668) [Link]
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.
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.
Not just GC Posted Sep 13, 2009 22:44 UTC (Sun) by salimma (subscriber, #34460) [Link]
.. it's worse than that: while Haskell supports SMP, its garbage-collector is still single-threaded -- http://www.haskell.org/ghc/docs/latest/html/users_guide/u...
A friend of mine worked on it a couple of summers ago at MSR Cambridge; I guess it's not quite done yet.
Not just GC Posted Sep 14, 2009 17:20 UTC (Mon) by TomMD (guest, #56998) [Link]
No - you can use a parallel GC with GHC. SimonM has some publications on the details they implemented [1]. Never-the-less, the RTS used by House (which I used as a base) is single threaded, so of coarse the GC will be. To get a hold of multiple processors in the Kernel for any stop-the-world GC would not be very cool.
Not just GC Posted Sep 15, 2009 20:07 UTC (Tue) by solidsnack (guest, #60840) [Link] Last I checked, the multicore collector for GHC was a parallel, stop-the-world collector. From Parallel Generational-Copying Garbage Collection with a Block-Structured Heap (2008): We focus on parallel, rather than concurrent, collection. In a concurrent collector the mutator and collector run at the same time, whereas we only consider garbage collecting in parallel while the mutator is paused. Parallel GC doesn't directly address the problem of intermittent, hard to control GC latency. For soft real-time apps like the kernel, file systems, games and network services, this is less than ideal. I haven't measured typical pause times for Haskell programs. Non-stop Haskell (2000) mentions average pause times of between 1 and 117 milliseconds on various benchmarks with GHC 4's standard collector. Their concurrent garbage collector, implemented for GHC 4, is able to get sub-millisecond average pause times (and, for a price, average pauses of much less than a millisecond). Another interesting piece of work in this vein is John Meacham's region inference for JHC (2009). The idea is that some (all?) Haskell programs can have their memory statically allocated if that's desired; then you don't need a garbage collector. I'd be very unhappy with my kernel module if it froze for 100ms; depending on what you're doing, even 1ms might be too much. On the other hand, strongly typed, purely functional programming is the way of the future and a lot of good work is being done to sort this stuff out.
Not just GC Posted Sep 14, 2009 19:07 UTC (Mon) by simonmar (guest, #60806) [Link]
Thankyou, i really need to fix that section in the manual :)
Writing kernel modules in Haskell Posted Sep 14, 2009 0:31 UTC (Mon) by flewellyn (subscriber, #5047) [Link]
GC isn't the reason for Java's slowness. Blame that on the VM.
Writing kernel modules in Haskell Posted Sep 14, 2009 12:55 UTC (Mon) by nye (guest, #51576) [Link]
Indeed. Java is perfectly fast enough for long running, non-graphical tasks.
I suspect this is why a lot of Java developers think that the 'Java slowness myth' is complete FUD, whereas users who sit twiddling their thumbs waiting for the JVM to start or some godawful Swing application to draw think those developers must be on crack.
Totally different experiences.
Writing kernel modules in Haskell Posted Sep 15, 2009 1:01 UTC (Tue) by mikov (subscriber, #33179) [Link]
Offtopic:
As someone who has the misfortune of running Java applications on 200MHz x86 CPUs, I feel that it is my duty to announce in public: The "Java slowness" is not a myth! It is real :-)
The overabundance of computing power has made everybody lose their objectivity. Nowadays we even have people claiming that JavaScript (!!!) is as fast as C. Similarly, a couple of years ago we had (the same?) people claiming the same for Java. In reality, I am thinking that Java is probably about 10x slower than C, and JavaScript 10x slower than Java :-)
People seem to believe that JITs can offer infinite improvements. In reality I suspect that we will never see a 2x improvement for JavaScript JITs compared to now without changing the language itself.
Java speed arguments Posted Sep 17, 2009 22:29 UTC (Thu) by smoogen (subscriber, #97) [Link]
It all depends on how the application is written. Many C applications can be quite boggy slow when you make them do the same things that most java bogs down on: graphics, UTF-8, etc.
Look at how slow grep and some other Linux applications got when they started dealing with UTF-8 environments versus good old 'C' environment. Or how slow some applications could be when run in a 'newer' graphical terminal versus say a console or older xterm.
The biggest problem that people run into is that few development groups work on the hardware many users have (though I don't think I have any 200Mhz working systems here anymore myself).
|
|
||||||||||||