Ohh, dear, another forum to keep an eye on :-) First: congratulations, the level of discussion here is a fair bit above what I have seen so far on reddit and s

Ohh, dear, another forum to keep an eye on :-) First: congratulations, the level of discussion here is a fair bit above what I have seen so far on reddit and slashdot. Second: A sense a number of bruised egos. Good. That is often a sound indication that a sore point successfully poked. Third: user "gaius" hits the problem spot on: "In mine, we learnt about the hardware, the cache hierarchy and so on, completely separately from the algorithms and complexity theory. Two different classes, two professors. Probably they both knew it themselves, but it never occurred to them to cross-pollinate their course materials." If I can get those two professors to talk to each other, my article will have been worth the effort. Hopefully the HW-prof will tease the algorithm-prof with my article and some fruitfull cooperation ensue. The important point in my article is not the B-heap, that took me all of an hour to figure out and I'm sure most of you could have done the same thing, had your thoughts been wandering in that direction. No, the important point is that most CS educations don't even mention that actual computers have Virtual Memory, Write buffers, multilevel caches and so on, and if they do, the certainly don't mention that the O() function depends on 13+ more or less stochastic variables extracted therefrom. Several people here, and elsewhere, seem to make the sign of the cross at there mere mention of virtual memory and RAM overcommit. That is understandable, in particular if nobody ever taught them how to properly use those facilities. Getting into a fight with the kernels VM bits is a sure-fire recipe for lousy performance, and after one or two such experiences, becoming a bit sceptical is fair. But the facts are, that by intelligently using the those VM bits you save a lot of complex code, and get as good performance as you can hope for. But you have to know what you are doing, and for most of us, that means that the professor should have told us. Poul-Henning