Knuth Got It Wrong

davecb writes "Think you've mastered the art of server performance? Think again. Poul-Henning Kamp, in an article at ACM Queue, finds an off-by-ten error in btrees, because they fail to take virtual memory into account. And he solves the problem in the open source 'Varnish' HTTP accelerator, for all of us to see and use."

Comments

Why trust the OS?

[michaelmalak]

I'm not sure what the advantages are of dancing around with the OS's virtual memory system. If it were me, I would detect the amount of physical memory available, allocate 80% of it, lock it into physical memory and manage the paging myself. It would be portable, not subject to changes in the VM algorithm by the OS authors, and easier to directly monitor and improve performance. But that's just me.

Alas, no more

[l00sr]

Unfortunately, he no longer gives out reward checks for finding bugs in his texts. This seems to be mostly because proud bug-finders inevitably post images of the checks online, which of course, contain Knuth's bank account numbers. More discussion here.

Re:as Knuth told me when I was at his house

[jschrod]

That's not quite right.

He uses email; his secretary prints them out (after some selection) and forwards them. And he reacts to them. Well, at least, to some, if he knows you. Don is the most humble genius that I know, and I have always found him approachable in a way that is rare for other famous people.

He also uses email (typically via his secretary, again) to organize trips. I also have direct emails from him when some new TeX developments irks him.

Re:Agreed

[jonadab]

I think "got it wrong" in the past tense is a little harsh, but I would say that a LOT of stuff in Knuth is wrong today, or at least terribly obsolete. It's not useless to be aware of, but you don't want to assume that everything is today still exactly the way Knuth described it in the digital stone age.

I mean, just for example, Knuth spends whole chapters talking about sorting algorithms. Almost all modern programmers don't have any use for that stuff, because re-implementing sort in your application code is pointless and counterproductive. The built-in sort provided by any modern language is optimized at a lower level and will handily beat the pants off anything you can do. Heck, even the Schwartzian Transform is built in to most modern languages these days.

Okay, sure, the guys who build low-level tools (compilers and system libraries and such) still need to know about sorting routines. What percentage of the programmer population is that? 0.1%? And even there, Knuth is somewhat obsolete, because (among other things) the stuff you're sorting is almost certainly stored in high-level cross-platform data structures, not some flat array of machine integers. I mean, it's still true that you probably don't want to code a bubble sort, but that's not exactly a profound revelation.