Writing kernel modules in Haskell
By making GHC and the Linux build system meet in the middle we can have modules that are type safe and garbage collected. Using the copy of GHC modified for the House operating system as a base, it turns out to be relatively simple to make the modifications necessary to generate object files for the Kernel environment." This leads to code which looks like:
hello = newCString "hello" >>= printk >> return 0
Just don't try to merge it upstream.
Posted Sep 13, 2009 14:38 UTC (Sun)
by Baylink (guest, #755)
[Link] (15 responses)
It's not April 1st?
Posted Sep 13, 2009 15:16 UTC (Sun)
by Baylink (guest, #755)
[Link] (14 responses)
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.
Posted Sep 13, 2009 15:56 UTC (Sun)
by nix (subscriber, #2304)
[Link] (5 responses)
Posted Sep 14, 2009 5:11 UTC (Mon)
by jordanb (guest, #45668)
[Link] (4 responses)
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.
Posted Sep 14, 2009 6:03 UTC (Mon)
by nybble41 (subscriber, #55106)
[Link] (1 responses)
Posted Sep 14, 2009 8:26 UTC (Mon)
by nix (subscriber, #2304)
[Link]
Posted Sep 14, 2009 18:57 UTC (Mon)
by Pc5Y9sbv (guest, #41328)
[Link]
Through compile-time analysis and incremental GC methods, you can play with these space and time overheads and with their granularity.
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.
Posted Sep 13, 2009 22:44 UTC (Sun)
by salimma (subscriber, #34460)
[Link] (3 responses)
A friend of mine worked on it a couple of summers ago at MSR Cambridge; I guess it's not quite done yet.
Posted Sep 14, 2009 17:20 UTC (Mon)
by TomMD (guest, #56998)
[Link] (1 responses)
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):
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.
Posted Sep 14, 2009 19:07 UTC (Mon)
by simonmar (guest, #60806)
[Link]
Posted Sep 14, 2009 0:31 UTC (Mon)
by flewellyn (subscriber, #5047)
[Link] (3 responses)
Posted Sep 14, 2009 12:55 UTC (Mon)
by nye (subscriber, #51576)
[Link] (2 responses)
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.
Posted Sep 15, 2009 1:01 UTC (Tue)
by mikov (guest, #33179)
[Link] (1 responses)
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.
Posted Sep 17, 2009 22:29 UTC (Thu)
by smoogen (subscriber, #97)
[Link]
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).
Posted Sep 13, 2009 15:11 UTC (Sun)
by MisterIO (guest, #36192)
[Link]
Posted Sep 13, 2009 16:13 UTC (Sun)
by dilinger (subscriber, #2867)
[Link]
Posted Sep 13, 2009 16:23 UTC (Sun)
by bjacob (guest, #58566)
[Link] (52 responses)
An example is if eventually a kernel module needs to do matrix computations. C++ or Fortran matrix libraries are much more powerful than C ones (Fortran because of native array arithmetic; C++ because templates allow to do that and much more) so one could imagine a kernel module that would be written in C++ with extern "C", for example. Actually, this will happen as soon as some kernel module needs to implement some clever math algorithm.
Posted Sep 13, 2009 16:49 UTC (Sun)
by cesarb (subscriber, #6266)
[Link] (40 responses)
Posted Sep 13, 2009 16:58 UTC (Sun)
by bjacob (guest, #58566)
[Link] (39 responses)
Posted Sep 13, 2009 21:10 UTC (Sun)
by csamuel (✭ supporter ✭, #2624)
[Link] (38 responses)
Posted Sep 13, 2009 21:13 UTC (Sun)
by bjacob (guest, #58566)
[Link] (37 responses)
Posted Sep 13, 2009 21:30 UTC (Sun)
by daney (guest, #24551)
[Link] (34 responses)
Posted Sep 13, 2009 22:57 UTC (Sun)
by cesarb (subscriber, #6266)
[Link] (32 responses)
Posted Sep 13, 2009 23:17 UTC (Sun)
by bjacob (guest, #58566)
[Link] (31 responses)
Posted Sep 13, 2009 23:36 UTC (Sun)
by cesarb (subscriber, #6266)
[Link] (3 responses)
As a bonus, I just found two threads even older than the 2004 one (the link above is from 2007):
http://web.archive.org/web/20020821190433/kt.linuxcare.co... (from 2000)
http://web.archive.org/web/20020717162937/kt.linuxcare.co... (from 1999!)
Posted Sep 13, 2009 23:46 UTC (Sun)
by bjacob (guest, #58566)
[Link] (2 responses)
These arguments are against introducing c++ throughout the kernel, object models etc. Still, coming back to the original topic --- these arguments don't apply to the case where C++ would only be used in the back-end of a kernel module.
Posted Sep 14, 2009 6:26 UTC (Mon)
by jgg (subscriber, #55211)
[Link] (1 responses)
The general gist seems to be a damning of OOP principles, which I think is entirely appropriate for large swaths of git, but as usual, has very little to do with C++ in particular. The strange thing is that in the end git ended up using C for all the performance sensitive stuff and really sketchy languages like shell script for much of the hard-to-do-wrappering tasks that are painful in C..
To me the argument was never that a OOP/C++ style of programming should replace the excellent optimized inner stuff, but that a C++ style and language would have been a better, more efficient and maintainable choice than all the shell script/perl/etc.
But these days it seems a lot has been (painstakingly?) implemented in C, so no matter.
Anyhow, Linus is bang on, about most C++ programmers.. C programmers that understand and use OOP concepts tend to understand that it is just a tool and not everything needs to be done with OOP, while C++ programmers with narrow experience think everything is an OOP problem. Java programmers too. Usually makes a very long and painful mess.
To me the biggest programmer folly is to design, then execute a huge slogging painful pointless mess. You see this a lot with inexperienced programmers. Some languages (like C and C++) seem to make it a lot worse. There is ALOT of slogging to do in C if you want to handle errors sensibly.
Look at something like *swan or trousers for great examples of this in action. I had to write an IKEv2 daemon for commercial/embedded/special case/blah, and it turned out to be 8,000 LOC of C++. Does about 80% of what strongswan does and maybe another 5% that strongswan doesn't (the 5% was why this was done, no hope of fitting the 5% into strongswan without being a frickin expert at that mess). Strongswan is 140,000 lines of C. I kid you not, the difference is that great.
Did C++ cause this LOC reduction? Not really, just a smart design, a lot of care and an eye toward eliminating repetition.
Posted Sep 14, 2009 14:00 UTC (Mon)
by marcH (subscriber, #57642)
[Link]
Aaahhh, OOP... "Dude, not everything is an object."
http://steve-yegge.blogspot.com/2006/03/execution-in-king...
Posted Sep 14, 2009 0:14 UTC (Mon)
by cesarb (subscriber, #6266)
[Link] (12 responses)
Of course, that can only happen if you create a class elsewhere which does memory allocation (and the other evil things) on "operator+" (and if you have not decided to forbid operators in your classes). But I think Linus's point is that, once you allow the language, people will want to use the features of the language, and before long you lose the ability to tell at a glance the costs and side effects of even simple operations like "a = b" (which in C can only mean the equivalent of a simple "MOV").
In fact, if you look at it this way, the fact that C is less expressive than C++ can be a feature. Having to write things like "obj->ops->fn(obj, foo)" instead of "obj->fn(foo)" makes explicit the extra costs (in this case, an additional memory read for the vtable and the extra "hidden" parameter).
Posted Sep 14, 2009 0:32 UTC (Mon)
by bjacob (guest, #58566)
[Link] (2 responses)
That said, if we discuss why C++ isn't used throughout the kernel --- I understand your point. One remark though: about your first paragraph, one might turn the argument upside down and say that C is evil because a function named print_hello() may actually do a lot of malloc's and send a network packet too ;) The difference between C++ and C here is that functions in C++ may appear is more various forms than in C (operators, constructors, etc). It's really a matter of knowing what to expect: an experienced C++ programmer will understand spontaneously when an operator+ is likely to have to allocate memory for the result. Which takes us back to what is really Linus' best argument against C++ throught the kernel, and to your last paragraph... in other words, we agree.
Posted Sep 14, 2009 6:13 UTC (Mon)
by drag (guest, #31333)
[Link]
Now the haskell thing is a interesting experiment and as such it does not
Posted Sep 14, 2009 15:17 UTC (Mon)
by bfields (subscriber, #19510)
[Link]
I don't see how you're using that distinction.
The bulk of the kernel is drivers. If drivers were written in a variety of languages, that would make the drivers as a whole more difficult to maintain.
Posted Sep 14, 2009 7:36 UTC (Mon)
by alankila (guest, #47141)
[Link] (5 responses)
Posted Sep 14, 2009 13:20 UTC (Mon)
by cesarb (subscriber, #6266)
[Link] (4 responses)
Posted Sep 14, 2009 21:27 UTC (Mon)
by alankila (guest, #47141)
[Link] (2 responses)
Since Java is sort of C++'s successor, perhaps I can be justified to drag it into this discussion. There is something fairly nice about its way to have essentially two languages in it: a simple unextendable arithmetic language for doing underlying operations with -- no confusion possible about what any of the expressions mean and it's analogous to C -- and an object language which is used for extending the core language. It has plenty of the good parts of C++, I guess, but I would agree that it's far from perfect.
However, the discussion we are having now can not occur in Java. In fact, since defining classes is the only possible way you can extend Java in any sense of word, you are even encouraged to not know or care what happens behind a method. It's an unusual dichotomy, but I must agree that it works. It's sort of brilliant, even.
(I'm watching myself turn into a Java enthusiast. Oh dear.)
Posted Sep 16, 2009 2:37 UTC (Wed)
by ringerc (subscriber, #3071)
[Link] (1 responses)
I'm suffering the same pain. Built-in GUI toolkit (even if it's pretty dire), sane and complete libraries, native Unicode string class (do not mention std::wstring in my presence), no build system pain, solid built-in threading and concurrency ... I'm getting to like it. I really miss RAII, though. It's not really possible in Java as there's no way to ensure a dtor fires reliably when an object exists scope, as with stack-based instances in C++. It's a real shame and a pain point for me, as working with program flow when exceptions are involved is excruciating without RAII. If I'm missing something and there's a reasonable way to do or approximate RAII in Java, please let me know...
Posted Sep 17, 2009 6:10 UTC (Thu)
by pynm0001 (guest, #18379)
[Link]
And you get RAII.
Posted Sep 15, 2009 9:42 UTC (Tue)
by etienne_lorrain@yahoo.fr (guest, #38022)
[Link]
Do not be so sure of this "of course", for instance GCC:
I have to say that older compiler version were copying fields of structure more efficiently, because they were not optimised to compile
Posted Sep 18, 2009 1:25 UTC (Fri)
by kbob (guest, #1770)
[Link] (2 responses)
Posted Sep 14, 2009 0:17 UTC (Mon)
by Ed_L. (guest, #24287)
[Link] (13 responses)
Posted Sep 14, 2009 7:24 UTC (Mon)
by felixfix (subscriber, #242)
[Link] (11 responses)
That is no way to design anything. I remember being disgusted with quite a few other things which I have gratefully mostly forgotten, Virtual should have been the default, I think, some pretense at giving you another knob to fine tune efficiency, You can define methods with a ridiculous number of keywords, more pretentious knobs. There are a zillion things you can do to hide the complexity of your class, to the point that there is no way to tell which operations are expensive, and debugging is a nightmare of chasing from one source file to another to see the secret details of classes to find out what little pitfalls were thrown in simply because they could be. People like to call Perl line noise, but C++ makes Perl look like a nice kindergarten language in the ways you can write write-only code, and every fool CS major thinks he is cool for doing so.
It reminds me of steampunk after it got past the initial fun stage: full of pointless knobs stuck on in an attempt to look like there's a reason behind them, when all they do is ... nothing except add clutter to make a fashion statement.
Posted Sep 14, 2009 8:11 UTC (Mon)
by alankila (guest, #47141)
[Link]
From design point of view, C++ seems to be quite unpleasant to program with, so I agree with you on that one. I think I feel some kind of a personal laundry list banging the backside of my skull wanting to come out, but there's no point to it -- C++ is a lost cause, and as long as backwards compatibility is required there is not much improvement on the horizon.
Posted Sep 14, 2009 16:17 UTC (Mon)
by tjc (guest, #137)
[Link] (4 responses)
I'm aware that arrays are converted to pointers in parameter declarations and (most) expressions, but I don't think that's an issue here. There should be enough information in the symbol table to identify an object as an array and [de]allocate memory for it without resorting to a special form.
Posted Sep 14, 2009 16:21 UTC (Mon)
by avik (guest, #704)
[Link] (1 responses)
Posted Sep 14, 2009 16:30 UTC (Mon)
by nye (subscriber, #51576)
[Link]
Posted Sep 14, 2009 16:26 UTC (Mon)
by nye (subscriber, #51576)
[Link] (1 responses)
Posted Sep 14, 2009 17:43 UTC (Mon)
by tjc (guest, #137)
[Link]
IIUC the size of an object could be stored in the symbol table, but that would only work with objects within lexical scope-- a dynamically allocated object returned from a library function would still be a problem, since there is no portable way to attach size information to an object in C.
Posted Sep 14, 2009 17:37 UTC (Mon)
by jgg (subscriber, #55211)
[Link] (4 responses)
And C has an infinite variety of alloc/free functions..
Foo *foo = calloc(1,sizeof(Foo));
It is ever so much fun in mixing and matching them! Heaven help you if you use the incorrect free for the alloc that was chosen!!
new/new [] is actually a substantial increase in API uniformity compared to C and the multitude of libraries.
Posted Sep 14, 2009 18:28 UTC (Mon)
by felixfix (subscriber, #242)
[Link] (1 responses)
Posted Sep 14, 2009 20:06 UTC (Mon)
by jgg (subscriber, #55211)
[Link]
Wow, that is just so pedantic. You do realize that the ISO C standard includes a library and that library includes functions like I described (fopen/fclose for instance). SUS adds more. It isn't like there is another way to do this ..
Posted Sep 14, 2009 19:46 UTC (Mon)
by bronson (subscriber, #4806)
[Link] (1 responses)
If you say, "well, don't use X in C++" then I'll just say "don't use X in C."
Posted Sep 15, 2009 14:33 UTC (Tue)
by nix (subscriber, #2304)
[Link]
(The same applies to malloc()/free(): they shouldn't be used in well-written C++ programs, at all. They're not typesafe.)
Posted Sep 17, 2009 6:17 UTC (Thu)
by pynm0001 (guest, #18379)
[Link]
> evaluates "true" only when ptr = new T; is in fact replaceable by ptr =
You mean as opposed to the more generic C:
ptr = (T*)malloc(sizeof(T));
that a C++ "ptr = new T;" is capable of expressing? You weren't going to
Posted Sep 15, 2009 0:24 UTC (Tue)
by jengelh (guest, #33263)
[Link]
VMware WS has, or used to have, some C++ (IIRC, only for some little templates, there was not much too much visible C++ classes, operator-overloads or otherwise)
The latter is not particularly hard ever since the FPU state is properly saved and restored.
Posted Sep 13, 2009 21:31 UTC (Sun)
by Randakar (guest, #27808)
[Link]
10x the effort might still cheap enough for some people.
A factor 10 effort multiplication on some minor addition to an already working system might easily be dwarfed by a) how much effort is already expended daily on regular maintenance and b) is saved further down the chain because a million distributers and kernel devs don't need to understand how to get Haskell going for their kernel build when that module is written in C ;-)
Posted Sep 14, 2009 9:01 UTC (Mon)
by dgm (subscriber, #49227)
[Link]
Posted Sep 14, 2009 9:22 UTC (Mon)
by sagrailo (guest, #48054)
[Link] (10 responses)
If you need vector/matrix computation, you need to use BLAS/LAPACK/etc., period; no one should try to re-implement that kind of code on his own. As for general numerical calculations, I'd agree with your statement that so far Fortran compilers were able to generate much better code than C compilers, but I certainly disagree that C++ template numerical libraries are better than C code - I worked with number of them, and these are all crap, regarding performance, readability etc.; this stuff is good only if you're into writing some papers on how smart and wonderful your usage of templates is.
Posted Sep 14, 2009 21:23 UTC (Mon)
by gmaxwell (guest, #30048)
[Link] (1 responses)
Any kind? Er, so the kernel should be including megabytes of unswappable finite field matrix algebra library code just to perform raid-6? I think notÂ…
General tools are nice for general things. The kernel is not, almost by definition, a general thing.
Posted Sep 15, 2009 10:24 UTC (Tue)
by sagrailo (guest, #48054)
[Link]
Posted Sep 14, 2009 22:50 UTC (Mon)
by Ed_L. (guest, #24287)
[Link] (7 responses)
Call me a crappy coder, but I have been singularly unsuccessful using multidimensional C++ arrays without resort to template wrappers, for which there is discernible run-time penalty for only the smallest of arrays. (Numerical Recipes style solutions also work.)
Posted Sep 15, 2009 10:35 UTC (Tue)
by sagrailo (guest, #48054)
[Link] (6 responses)
Yeah, right... I just quickly wrote this code (to multiply two matrices):
Complied with (I've put TNT into /tmp, and I have ATLAS installed in /usr/local):
The output, on my old ThinkPad T61p:
Posted Sep 15, 2009 12:01 UTC (Tue)
by jbh (guest, #494)
[Link] (4 responses)
ATLAS: 0.43s
The major additions to your test program are (in different places):
#include <Eigen/Core>
Posted Sep 15, 2009 12:50 UTC (Tue)
by bjacob (guest, #58566)
[Link] (3 responses)
I'm surprised by your result, because in our experience, we are consistently faster than ATLAS for matrix products. Already with Eigen 2.0, and even more so in the development branch. In fact, on single-CPU systems, we have almost the performance of vendor-tuned BLAS.
development branch:
2.0:
It's good that you passed -msse2, indeed.
Some things to consider:
* did you allow ATLAS to use more than one thread? That would probably not be applicable in the setting of a kernel module! (As far as I understand) so perhaps it's more fair to require ATLAS to use only one thread.
* did you tune ATLAS for your hardware, especially CPU cache size? You can do the same for Eigen, then. For example with the development version it's
Posted Sep 15, 2009 13:09 UTC (Tue)
by jbh (guest, #494)
[Link] (1 responses)
Eigen already looks very impressive, for a relatively young project in a
Posted Sep 15, 2009 13:29 UTC (Tue)
by bjacob (guest, #58566)
[Link]
(If it wasn't obvious, the largest advantage of a c++ template library like Eigen over a large C or Fortran binary library like a BLAS, is that it spontaneously generates only the code that's needed at build-time, and after that you can forget about it, so your kernel module is only a few dozen kilobytes self-contained; by comparison vendor-tuned BLAS take dozens of megabytes).
Posted Sep 29, 2009 23:14 UTC (Tue)
by Auders (guest, #53318)
[Link]
Posted Sep 16, 2009 20:50 UTC (Wed)
by cry_regarder (subscriber, #50545)
[Link]
...
and this compile:
to get run times like:
ATLAS: 0.16s
...
Cry
Posted Sep 14, 2009 8:31 UTC (Mon)
by simlo (guest, #10866)
[Link] (7 responses)
At my work I write "drivers" in Java (in user space, through simple native calls to get access to memory mapped hardware registers in the hardware). There is nothing wrong about writing hardware near stuff in higher level languages, where you have no direct access to low-level bit manipulation. In fact, to make C portable you must avoid doing the very low-level bit-manipulations directly but put them away in libraries. Then you can just as well access those libraries from another language.
In fact, if I were to write an OS kernel from scratch, I would start out by making a small runtime system for a language like OCAML and then write drivers and filesystem etc. in that language. Some of the scheduler and the garbage collector would have to be written in C. The major technological hurdle would be to make a scaleable, realtime garbage collector, but if you can construct it along with the compiler and the scheduler, it might turn out to be easier than doing it in userspace. And you can also use that in "almost functional" languages, you make far fewer memory modifications than in Java. I.e. you can optimize the system for "many readers", "few writers". Old memory can not have pointers to new memory.
This also tells us one of the benifits: Better scaleability since the garbage collector superseeds the RCU. A functional language makes it natural to write good RCU client code, since you never change objects. You (almost) only need locks to protect the hardware from simultanious access, since (almost) all ordinary memory structures are read-only. And then, strongly typed functional language makes must safer code. Writing the kernel in such a system, would be a more efficient way to get a stable system than using microkernels.
Posted Sep 14, 2009 14:56 UTC (Mon)
by PaulMcKenney (✭ supporter ✭, #9624)
[Link]
In the meantime, make sure you use the "volatile" keyword appropriately...
Posted Sep 15, 2009 18:10 UTC (Tue)
by dambacher (subscriber, #1710)
[Link]
Posted Sep 17, 2009 10:56 UTC (Thu)
by bboissin (subscriber, #29506)
[Link] (3 responses)
Posted Sep 18, 2009 14:19 UTC (Fri)
by simlo (guest, #10866)
[Link] (2 responses)
I also disagree with the main page statement
"It could then be used as an educational tool for teaching OS design, for instance, or may be just replace Linux before Hurd goes out. "
Sorry, it is the other way around: It would be faster and more stable than any microkernel, it is just a question of optimizing the compiler. Even in very optimized assambly a microkernel will be slower - and each "service" will be more buggy since it typically will be written in C.
Posted Sep 18, 2009 14:30 UTC (Fri)
by bboissin (subscriber, #29506)
[Link] (1 responses)
Secondly, I think you took that comment too seriously, the reference to
Posted Sep 19, 2009 22:41 UTC (Sat)
by simlo (guest, #10866)
[Link]
But with help from the compiler and the scheduler, it ought to be possible to make a system with no central lock - making it scale - although it will be very hard. But using an (almost) pure functional language will help in that: You for instance know that an old piece of memory can never have references to later allocated memory since it wasn't change. And in the few places where you do update a reference the compiler can put in checks to help the GC as well as the right read/write barriers for the readers on other CPUs.
Well, I can always keep on dreaming..
Posted Sep 27, 2009 13:46 UTC (Sun)
by xoddam (guest, #2322)
[Link]
Otherwise you will end up doing *everything* as garbage-collected RCU. Great, in theory, for scalability on the grand scale but dreadful for performance on typical machines with only a few CPUs(!) and a few gigabytes (!) of RAM.
Perhaps best to implement the kernel of your kernel in well-audited C but begin to adopt the secure languages for peripheral components such as device drivers.
Writing kernel modules in Haskell, you might say.
Posted Sep 21, 2009 14:12 UTC (Mon)
by shlomif (guest, #11299)
[Link] (4 responses)
<p>
<p>
<p>
<p>
Posted Sep 21, 2009 14:13 UTC (Mon)
by shlomif (guest, #11299)
[Link] (3 responses)
(Sorry for the bad formatting, I pressed the wrong button by accident.)
this IRC conversation on my page should be instructive (I am "rindolf" there). Essentially, even an elegant dinky "log analyser" that people showed me how to write properly using ghc segfaulted. And I don't mean thrown an exception - it segfaulted. As much as I like Haskell, I still think the language has many inherent limitations due to its restrictive design decisions, and ghc still has many bugs, and is a huge memory hog (possibly due to a good reason). Haskell and ghc are still fine to play with and highly enlightening, but I'd never use them in anything "industrial strength", that I want to depend on.
Someone I talked with on IRC, said he'd like to create an alternative operating system written in Haskell, that would be incompatible with Linux. Then when I said no one will use it because it won't run any UNIX (or Windows for that matter) applications, he said that "fine, we can implement a nice POSIX emulation subsystem in a jail.". The reason GNU/Linux was successful was because the GNU run-time and other open-source UNIX/POSIX programs were ported to it easily, and in time it also proved attractive to vendors of commercial and/or non-FOSS software. If the Linux kernel was incompatible with anything else, it would have faded into obscurity.
So I don't see why I should use the new OS with a POSIX-compatible system that will run everything I'm using now more slowly, less natively and less reliably. Granted, the C/UNIX/TCP/IP system is not without its inherent philosophical problems, but everything today relies on it too much. In a Star Trek screenplay I started writing (a fan-fiction of sorts) I whimsically contemplated that their tricorder still runs a UNIX-based OS, and can be operated in X mode from the command line. I'm not sure UNIX (whether Linux, BSD or a different kernel) will still be prevalent 300 years from now, but we cannot rule it out.
My experience told me that such grand re-inventing everything from scratch schemes tend to amount to very little of promise. (And yes - I've tried some of them myself). Inertia is important and like it or not, reality needs to be obeyed in order to be conquered.
In short - nice hack, but not terribly useful. The kernel developers are likely to reject Haskell modules, and I would too in their shoes. Now, it's time for Perl, Python, Ruby, Lua, Tcl, PHP, etc. to reciprocate... ;-)
Posted Sep 23, 2009 5:45 UTC (Wed)
by TomMD (guest, #56998)
[Link] (2 responses)
PERL folks bashing on Haskell in #perl is instructive? I think your a tad under the bar.
> Essentially, even an elegant dinky "log analyser" that people showed me how to write properly using ghc segfaulted.
On a practical level: this isn't helpful without a version of GHC, platform information, and a copy of the progrma that was "properly written". On a theoretical level: this says nothing about the language.
> As much as I like Haskell, I still think the language has many inherent limitations due to its restrictive design decisions
There are many design decisions I'd happily question - but I wouldn't call those ones limiting. Which ones are you referring to?
> and ghc still has many bugs
True! But its been a while since I've been caught by a segfault.
> and is a huge memory hog
Are you saying your programs are huge memory hogs? The compilation process takes too much memory? Perhaps you are claiming "all" or "too many" progrmas use unnecessary amounts of memory? If your claim is either of the second two I must disagree. I've built many memory friendly programs, but it does take a little more skill to predict the memory use than most people think it should.
> Someone I talked with on IRC, said he'd like to create an alternative operating system written in Haskell
Hundreds of them out there (alternative OSes) and Haskell is fun to play with. I'd like to do this too. His lack of care about POSIX doesn't say anything about the language or the tool - so I'm not sure what you're getting at there or if you're just going on a tangent.
> The kernel developers are likely to reject Haskell modules
Upstreaming was never a goal - oh, that would be a headache without any reward!
Posted Sep 27, 2009 7:25 UTC (Sun)
by shlomif (guest, #11299)
[Link] (1 responses)
Essentially, even an elegant dinky "log analyser" that people showed me how to write properly using ghc segfaulted.
On a practical level: this isn't helpful without a version of GHC, platform information, and a copy of the progrma that was "properly written". On a theoretical level: this says nothing about the language.
Here is the Haskell program in all its glory - I lost the original one, but people on #haskell have recreated a mostly equivalent one:
This program no longer segfaults (even though I recall it segfaulting), but it consumes 38.3% of my 2.5 GB of RAM (I still remember my first 20 MB hard-disk), and takes a long time to run. On the other hand, the equivalent Perl program consumes less than 2% of my RAM and finishes faster:
The Lisp program using SBCL also runs adequately.
I'm running it on this file:
There are many design decisions I'd happily question - but I wouldn't call those ones limiting. Which ones are you referring to?
The very strong typing, the lazy-only evaluation, the lack of assignment. All of these are essential cornerstones of Haskell, yet result in under-performing code when put together.
Posted Oct 7, 2009 17:53 UTC (Wed)
by TomMD (guest, #56998)
[Link]
2) You are using linked lists of linked lists for processing
The first issue seems especially obvious, making me think this is done on purpose. Please don't troll on LWN.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
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
Writing kernel modules in Haskell
Writing kernel modules in Haskell
times with that can be in the submillisecond range.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Not just GC
Not just GC
Not just GC
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.
Not just GC
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Java speed arguments
Writing kernel modules in Haskell
Writing kernel modules in Haskell
maybe it's just me. :)
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
assembler for specific CPUs. ;-)
Writing kernel modules in Haskell
Writing kernel modules in Haskell
floating point. From a technical point of view, it is not difficult to do. The politics of merging it upstream on the other hand...
Writing kernel modules in Haskell
Interesting...Writing kernel modules in Haskell
Linus's quote leave little hope that C++ code ever makes it into the kernel, indeed.
Just for the record, here's how I would counter his claims (in the link you posted):
Quote:
"The fact is, C++ compilers are not trustworthy. They were even worse in
1992, but some fundamental facts haven't changed: 1) the whole C++ exception handling thing is fundamentally broken. It's _especially_ broken for kernels. 2) any compiler or language that likes to hide things like memory allocations behind your back just isn't a good choice for a kernel. 3) you can write object-oriented code (useful for filesystems etc) in C, _without_ the crap that is C++."
1) Doesn't matter, nobody's forced to use exceptions, there are lots of C++ project who don't (KDE for example) for a variety of reasons. So exceptions being inappropriate isn't an argument against C++ in general.
2) C++ doesn't hide any memory allocation behind your back. When you replace ptr = (T*)malloc(sizeof(T)); by ptr = new T;, you haven't hidden the memory allocation!
3) meh, if Linus is happy about the object-oriented-C style that they use in the kernel, who am I to argue against that. I just have yet to hear the details of how C++ is "crap" here. It just does this repetitive work for you, in a standardized way.
***
It's funny that Linus doesn't mention what seems to me to be the most sensible reason to oppose C++ : it's far easier to organize a community of C programmers than a community of C++ programmers, to make everyone understand and use the same coding paradigms, to review patches etc... since C is such a simple language.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
term, it should be every modules goal to get integrated into the kernel
proper. Therefore its counter productive to use any language other than the C
version that is acceptable by the kernel folks.
make sense to be constrained by conventions.. But it may make some change to
the status quo if something is learned from it. So it's neat.
Writing kernel modules in Haskell
they are arguments against using C++ throughout the kernel, and hardly constitute an argument against using C++ internally in the back-end of a kernel module.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
(I'm watching myself turn into a Java enthusiast. Oh dear.)
Writing kernel modules in Haskell
C++ without Qt. Just as an aside, Qt has a built-in GUI toolkit (not dire,
btw), sane and complete libraries (although not as comprehensive as Java
I'd imagine), a native Unicode string class, minimal build system pain
(usually as easy as qmake -project && qmake && make), and solid built-in
threading and concurrency.
Writing kernel modules in Haskell
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22141
and last time I tried Clang (LLVM) was worse (mov $4,ecx; rep mov stosb).
C++ code which may trigger constructor for each fields of the structure.
Writing kernel modules in Haskell
Even a seemingly simple statement like "a = b + c;" can allocate memory in C++, while in C the only way that statement will allocate memory is if the compiler has to spill registers
#define a (buf[read(open("/dev/hda", 0), buf, sizeof buf) - 1])
#define b (send(some_sock, buf, sizeof buf, 0))
#define c (system("xloadimage /usr/share/cups/doc-root/images/smiley.jpg &"))
You were saying?
Writing kernel modules in Haskell
When you replace ptr = (T*)malloc(sizeof(T)); by ptr = new T;, you haven't hidden the memory allocation!
evaluates "true" only when ptr = new T; is in fact replaceable by ptr = (T*)malloc(sizeof(T)); Are you certain you want to debate this one? ;)
C++, the steampunk language
C++, the steampunk language
C++, the steampunk language
My experience with C++ is summed up by having replaced the simple malloc/free paradigm with THREE different ways to allocate : new/delete, new[]/delete[], and the original.
Since you bring it up, do you happen to know why C++ requires a separate form (new[] v. new) for allocating and deallocating arrays? C++, the steampunk language
C++, the steampunk language
C++, the steampunk language
Thanks for the link. There is some other useful information on that page; see the post by Andrew Grant. C++, the steampunk language
C++, the steampunk language
Foo *foo = LIBRARY_foo_Alloc();
Foo foo; LIBRARY_foo_Init(&foo);
Foo **foo = malloc(n*sizeof(Foo *)); for (int i = 0; i != n; i++) foo[i] = LIBRARY_foo_Alloc();
C++, the steampunk language
C++, the steampunk language
C++, the steampunk language
C++, the steampunk language
Writing kernel modules in Haskell
> > haven't hidden the memory allocation!
> (T*)malloc(sizeof(T)); Are you certain you want to debate this one? ;)
foo_type_initialize_default(ptr);
use that ptr uninitialized were you? This is 2009, there's no reason to
be using uninitialized structs!
Writing kernel modules in Haskell
floating point.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Second, 1/10th the development time, at the cost of losing control would be OK for a one off number crunching app, but it's not an option for an OS Kernel.
Finally, if you care so much about rapid development, then maybe C++ is not your best option. Go with Python (I have read there are wonderful math libraries) or something like that.
That coming from somebody that has been writing C++ code for the last 14 years.
My biggest gripe with C++ is that it's like a ubercomplex laser scalpel: great in the right hands, deadly in the the wrong ones. It's a great language for top-down communication (for example, writing libraries), but sucks for interchange of code among peers.
Writing kernel modules in Haskell
An example is if eventually a kernel module needs to do matrix computations. C++ or Fortran matrix libraries are much more powerful than C ones (Fortran because of native array arithmetic; C++ because templates allow to do that and much more)...
Writing kernel modules in Haskell
Writing kernel modules in Haskell
I'm sure you have good foundation for your opinions. But my experience, specifically with the Template Numeric Toolkit, is decidedly different. In one application where I implemented Lapack and TNT equivalents side by side, the TNT code was roughly twice as fast as Lapack. This was on CentOS, GCC 4.1.2. I don't recall whether I was linking the system-supplied Lapack or one I custom compiled, and I don't know if the difference was attributable to optimization flag differences or not. FWIW, library code is typically optimized -O2, my TNT segment was -O3 and there were several adjacent function call candidates for successive inline optimization. Perhaps a different example would skew a different direction.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
extern "C" {
#include <cblas.h>
}
#include <tnt.h>
#define N 1024
int
main(void)
{
float* A = new float[N * N];
float* B = new float[N * N];
float* C = new float[N * N];
std::fill(C, C + N * N, 0);
TNT::Array2D<float< ATNT(N, N);
TNT::Array2D<float< BTNT(N, N);
TNT::Array2D<float< CTNT(N, N);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) {
A[i * N + j] = ATNT[i][j] = 1;
B[i * N + j] = BTNT[i][j] = 1;
}
clock_t start, end;
start = clock();
cblas_sgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, N, N, N, 1, A, N, B,
N, 0, C, N);
end = clock();
std::cerr
<< "ATLAS: "
<< (float) (end - start) / CLOCKS_PER_SEC
<< "s"
<< std::endl;
start = clock();
CTNT = TNT::matmult(ATNT, BTNT);
end = clock();
std::cerr
<< "TNT: "
<< (float) (end - start) / CLOCKS_PER_SEC
<< "s"
<< std::endl;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) {
assert(C[i * N + j] == N);
assert(CTNT[i][j] == N);
}
delete [] A;
delete [] B;
delete [] C;
}
g++ -O3 -o foo -I/tmp/tnt foo.cpp -lcblas -latlas
So - C++ almost two orders of magnitude slower (and that's typical, in my experience).
ATLAS: 0.22s
TNT: 17.64s
Writing kernel modules in Haskell
template linear algebra library (http://eigen.tuxfamily.org). It seems to
hold up pretty well against Atlas (on Thinkpad T60, compiled with -msse2
flag):
TNT: 32.25s
Eigen: 0.76s
--
MatrixXf Aeig(N,N), Beig(N,N), Ceig(N,N);
Aeig.setOnes(); // or Aeig = MatrixXf::Ones(N,N);
Beig.setOnes();
Ceig.setZero();
--
Ceig = Aeig * Beig;
--
assert(Ceig(i,j) == N);
Writing kernel modules in Haskell
http://eigen.tuxfamily.org/index.php?title=Benchmark
http://eigen.tuxfamily.org/index.php?title=Benchmark-Augu...
EIGEN_TUNE_FOR_CPU_CACHE_SIZE, see in the file Macros.h.
Writing kernel modules in Haskell
packages for everything. This was on my laptop, and I only bother to tune
for production runs; those are not on my laptop :)
problem space that's dominated by dinosaurs --- I've meant to look into it
for a while, but not enough time and all that, and last time I checked it
didn't have sparse matrix support (I see it does now, although
experimental).
Writing kernel modules in Haskell
anyway thanks for the kind words. Yes, there are a lot of dinosaurs in this area and we're sort of the small mammals in comparison.
Writing kernel modules in Haskell
ATLAS: 0.69s
TNT: 21.93s
Eigen: 0.56s
Matrix Libraries
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/bindings/atlas/cblas.hpp>
#include <boost/numeric/bindings/traits/ublas_matrix.hpp>
...
namespace ublas = boost::numeric::ublas;
namespace atlas = boost::numeric::bindings::atlas;
...
atlas::gemm(CblasNoTrans, CblasNoTrans, 1.0,
Aublas, Bublas, 0.0, Cublas);
...
g++ -O3 -o mat mat.c++ -I/tmp/boost-numeric-bindings -L /usr/lib64/atlas -latlas -lcblas -DNDEBUG
uBLAS: 0.16s
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Look at smalltalk80 .-)=====
Writing kernel modules in Haskell
booting in qemu and on real hardware.
Writing kernel modules in Haskell
Writing kernel modules in Haskell
lock but I don't think there's any other lock when Ocaml is run natively.
hurd shows it was meant as a joke :)
(It was just students having fun building an OS from scratch)
Writing kernel modules in Haskell
assignment-free garbage-collected data processing considered no substitute for cache locality
Writing kernel modules in Haskell
<a href="http://www.shlomifish.org/humour/fortunes/shlomif.html#sh...">this IRC conversation on my page should be instructive</a> (I am "rindolf" there). Essentially, even an elegant dinky "log analyser" that people showed me how to write properly using ghc segfaulted. And I don't mean thrown an exception - it segfaulted. As much as I like Haskell, I still think the language has many inherent limitations due to its restrictive design decisions, and ghc still has many bugs, and is a huge memory hog (possibly due to a good reason). Haskell and ghc are still fine to play with and highly enlightening, but I'd never use them in anything "industrial strength", that I want to depend on.
</p>
Someone I talked with on IRC, said he'd like to create an alternative operating system written in Haskell, that would be incompatible with Linux. Then when I said <a href="http://www.joelonsoftware.com/articles/fog0000000054.html">no one will use it because it won't run any UNIX (or Windows for that matter) applications</a>, he said that "fine, we can implement a nice POSIX emulation subsystem in a jail.". The reason GNU/Linux was successful was because the GNU run-time and other open-source UNIX/POSIX programs were ported to it easily, and in time it also proved attractive to vendors of commercial and/or non-FOSS software. If the Linux kernel was incompatible with anything else, it would have faded into obscurity.
</p>
So I don't see why I should use the new OS with a POSIX-compatible system that will run everything I'm using now more slowly, less natively and less reliably. Granted, the C/UNIX/TCP/IP system is not without its inherent philosophical problems, but everything today relies on it too much. In <a href="http://www.shlomifish.org/humour/Star-Trek/We-the-Living-...">a Star Trek screenplay I started writing (a fan-fiction of sorts)</a> I whimsically contemplated that their tricorder still runs a UNIX-based OS, and can be operated in X mode from the command line. I'm not sure UNIX (whether Linux, BSD or a different kernel) will still be prevalent 300 years from now, but we cannot rule it out.
</p>
My experience told me that such grand re-inventing everything from scratch schemes tend to amount to very little of promise. (And yes - I've tried some of them myself). Inertia is important and like it or not, reality needs to be obeyed in order to be conquered.
</p>
In short - nice hack, but not terribly useful. The kernel developers are likely to reject Haskell modules, and I would too in their shoes. Now, it's time for Perl, Python, Ruby, Lua, Tcl, PHP, etc. to reciprocate... ;-)
</p>
Writing kernel modules in Haskell
Writing kernel modules in Haskell
Writing kernel modules in Haskell
import System.Environment
import Data.List
main = do [infile,outfile] <- System.Environment.getArgs
text <- readFile infile
writeFile outfile . unlines . map (\xs -> (show (length xs)) ++ "\t" ++ head xs) . group . sort . words $ text
#!/usr/bin/perl
use strict;
use warnings;
my %hash;
open my $in, "<", "FreeNode-#perlcafe.log"
or die "Could not open - $!";
while (my $l = <$in>)
{
chomp($l);
foreach my $word (split (/ +/, $l))
{
$hash{$word}++;
}
}
close($in);
open my $out, ">", "analysis-perl.txt"
or die "Could not open for writing - $!";
while (my ($word, $occurs) = each(%hash))
{
print {$out} "$occurs\t$word\n";
}
close($out);
$ wc FreeNode-#perlcafe.log
383760 3773752 22564515 FreeNode-#perlcafe.log
As much as I like Haskell, I still think the language has many inherent limitations due to its restrictive design decisions
Writing kernel modules in Haskell
Your algorithms for these two program are entirely different. Your Perl program will take one word, modify a map of counters, and then process the next word - a constant space algorithm. This is entirely doable in Haskell but you have decided not to. Instead, you read in the entire file, sort the words, group them, and count the resulting list lengths, requiring O(n) memory (actually more, given that you are sorting).
Anyone serious about time and space would be using packed strings, from the bytestring package.