News for hackers. Stuff that matters.
Re:You're Doing It Wrong: CS in the real world by stcredzero on Saturday June 12, 2010 @02:30PM (#1426319)
this article is great. He gives a specific example based on real-world performance, showing that you can't always rely on theory assuming a general case. For many intensive applications, memory is so precious, you CAN'T effectively ignore VM. Some thought about the relative latency of memory is useful in more than just parallel applications on NUMA hardware.

(Git and Mercurial are designed with an eye towards optimizations based on disk latencies. Python is optimized with regard to CPU cache. We're back to "Abstractions Leak.")

Re:You're Doing It Wrong: CS in the real world by _delirium on Saturday June 12, 2010 @03:42PM (#1426418)
One problem is that the article seems to incorrectly assume that "theory" always ignores memory hierarchies. That was true in, say, 1975, but the past 20 years of algorithms theory pays a lot of attention to memory hierarchies. You can even get all sorts of off-the-shelf algorithms designed to perform well on typical modern memory configurations.

I mean, he's basically arguing that CS hasn't revisited heaps since 1961, and hasn't noticed that things like caches or VM pressure might change what the optimal algorithm looks like. But that's of course not the case.

Re:You're Doing It Wrong: CS in the real world by jemfinch on Saturday June 12, 2010 @05:07PM (#1426520)
> I mean, he's basically arguing that CS hasn't revisited heaps since 1961...But that's of course not the case.

Then kindly link me to the paper which describes his B-heaps; I'd love to read it.

Re:You're Doing It Wrong: CS in the real world by _delirium on Saturday June 12, 2010 @05:34PM (#1426571)
His specific B-heaps might indeed be novel; I'm not claiming he makes no contribution. I'm just objecting to the portion of his paper that claims that nobody in CS has ever thought of the idea of optimizing heaps for the properties of a modern computer's memory hierarchy. He seems to really believe Knuth's 1961 paper is the last word on the subject, or at least says so.

Fwiw, here's a widely cited 1996 paper that describes a different variety of block-aggregated heaps, "d-heaps", aimed mainly at cache-aware performance: http://lamarca.org/anthony/pubs/heaps.pdf

It's quite possible that no existing heap layouts solve his specific problem, but he could've at least acknowledged that there exist heaps newer than Knuth's, and that many of them specifically look at the influence of the memory hierarchy on performance.

Re:You're Doing It Wrong: CS in the real world by jemfinch on Saturday June 12, 2010 @11:41PM (#1426923)
That's a great paper, thanks for the reference.
Re:You're Doing It Wrong: CS in the real world by gaius on Saturday June 12, 2010 @05:34PM (#1426570)
Undergraduate CS education certainly hasn't.
Re:You're Doing It Wrong: CS in the real world by _delirium on Saturday June 12, 2010 @06:29PM (#1426640)
Hmm, my undergrad algorithms class at least mentioned the existence of cache effects, though it didn't really go into any detail. It had a bit of disclaimer along the lines of: for simplicity, we don't take into account caches in this class, but more modern models of computation do, and for real-world applications you might want to look up cache-aware algorithms.
Re:You're Doing It Wrong: CS in the real world by stcredzero on Saturday June 12, 2010 @07:38PM (#1426709)
Hmm, my undergrad algorithms class at least mentioned the existence of cache effects, though it didn't really go into any detail.

There should at least be exposure on the level of a walkthrough of the optimization of a real-world server. There was a concurrency optimization video posted to HN a couple of weeks ago.

Re:You're Doing It Wrong: CS in the real world by gaius on Sunday June 13, 2010 @04:05AM (#1427151)
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.
Re:You're Doing It Wrong: CS in the real world by acqq on Saturday June 12, 2010 @03:20PM (#1426394)
The article is really poorly written. The specific example is very specific, the claims that "nobody else gets it" are in fact unsubstantiated. All the effects he mentions are very known among right professionals. And the title text is not about "relative latency" you mention but about the cost of paging, once something gets paged out.
Re:You're Doing It Wrong: CS in the real world by stcredzero on Saturday June 12, 2010 @03:48PM (#1426425)
The specific example is very specific

Sounds good to me.

the claims that "nobody else gets it" are in fact unsubstantiated

I'm pretty sure that the entire shop at my last consulting job would all claim it was news to them. Most people don't have to deal with issues like the ones discussed in the article, so it's perfectly understandable that it would be news to them. I don't have to deal with such issues on a daily basis, though I think I would have been able to do the same analysis if I had his job.

And the title text is not about "relative latency" you mention but about the cost of paging

I didn't know "relative" was so associated with memory and paging that you could jump to a conclusion about my specific meaning. (And actually, I meant to be quite general.) AFAIK, the cost of paging has something to do with the latency of resident memory vs. latency memory that was paged out.

Re:You're Doing It Wrong: CS in the real world by Confusion on Sunday June 13, 2010 @08:50AM (#1427368)

  I'm pretty sure that the entire shop at my last consulting
  job would all claim it was news to them
On the other hand, I'm pretty sure that the same doesn't hold for the actual target audience of this article.
Re:You're Doing It Wrong: CS in the real world by mfukar on Sunday July 11, 2010 @02:25PM (#1505892)
I'm willing to forgive his "poor" writing on account that he's right - most CS students and graduates don't have any clue about cache effects on algorithm implementations, and that's just wrong.