Knuth Got It Wrong 298
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."
as Knuth told me when I was at his house (Score:5, Funny)
"Who the hell are you and what are you doing in my house?"
Re:as Knuth told me when I was at his house (Score:5, Funny)
Re: (Score:3, Funny)
Next time, don't title your e-mail "buY h3rb@L c1aL 1s today!!"
Re: (Score:3, Interesting)
I wrote Knuth an email once. He never wrote me back.
As with the xkdc.org reference in the grandparent, this is something of an in joke. Don doesn't do email. B-)
Re:as Knuth told me when I was at his house (Score:4, Interesting)
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:as Knuth told me when I was at his house (Score:5, Funny)
I called Wirth, once. but I think I called him by name and not by value.
perhaps I made the wrong judgement call; my phone overflowed.
Re: (Score:3, Funny)
"Who the hell are you and what are you doing in my house?"
Get off my lawn.
Credit where credit is due... (Score:5, Informative)
link [xkcd.org]
You can quote xkcd... (Score:2)
Crank it to 11 (Score:5, Funny)
10 times faster? Yawn. Wake me up when it's 11 times faster.
Re:Crank it to 11 (Score:5, Funny)
10 times faster? Yawn. Wake me up when it's 11 times faster.
And wake me up when it's 1010 times faster.
Re:Crank it to 11 (Score:5, Funny)
That has to be the one of the better binary jokes around.
Re: (Score:2)
1010 = 12 in binary
Sadly, no.
Re: (Score:2)
1010 = 10 in binary
Re: (Score:2)
1010 = 12 in binary
Somebody doesn't understand binary...
Re: (Score:3, Informative)
Re:Crank it to 11 (Score:4, Funny)
I think they mean
00
01
10
11
It represents 4 states the same way that 10 (decimal) represents 100 states. In other words, not at all (except for having 2 digits).
Re: (Score:3, Funny)
I give that post an 0xA!
Nope, he didn't (Score:5, Informative)
Agreed (Score:5, Insightful)
Knuth's analysis is valid in the framework of his assumptions, and what is described in the linked article has been known as "cache oblivious b-tree" for not so short time.
Yeah, using this logic, once quantum computers get to the point of solving general problems there's going to be an awful lot of people who "got it wrong" because their algorithms do not apply in a quantum computer. Advancements in technology causing algorithms & data structures to be tweaked means the original person who thought them up "got it wrong"? Ridiculous.
"Oh, RSA was brilliant. But they got it wrong. You see, they failed to account for xanxinglydiumapping in 2056 computers. Poor stupid wrong bastards."
Re: (Score:3, Interesting)
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 cod
Re:Nope, he didn't (Score:5, Insightful)
Mod parent up. There was a comment on the article that referenced cache oblivious algorithms, which was a new concept to me and very interesting. Basically, this set of algorithms assumes a memory hierarchy (e.g. fast ram vs slow disk) that is optimized to limit the number of times the slower memory is accessed. Importantly, cache oblivious algorithms are optimal REGARDLESS of the size of the cache. That's opposed to a cache aware algorithm, like a normal b-tree, where the size of each node is set according to the page size of the machine.
A very helpful overview here from MIT Opencourseware: http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-fourteen/ [catonmat.net]
Re: (Score:3, Interesting)
For instance if the b-tree node is roughly the size of a page, the entire node must be read into memory at once from disk. Even reading a single byte of the record may necessitate reading the entire page. However this size will likely be much larger than a cache line. So you could have quite a lot of variance in performance based on how much of the structure you access; say scanning through the wh
Re: (Score:3, Interesting)
Instead I had to read a bunch of text and timing charts before he simply showed what his improvement was. Yes, cache oblivious is worse, but that wasn't the problem Knuth was trying to solve. You could make further arguments that the paging system should group links by location AND popularity. You could move more popular links to the top of the tree so y
Many servers (Score:5, Informative)
Unless you have many servers
The article does in fact mention many servers, specifically replacing twelve Squid servers with three Varnish servers.
it is cheaper to throw money at the problem in the form of physical RAM before you start thinking about problems like this.
No matter how much physical RAM you have, you're still limited by the speed of the interface between RAM and the CPU. If a set of closely related nodes can fit in a cache line, this improves locality so that the CPU can do more work instead of twiddling its thumbs.
Re:Nope, he didn't (Score:5, Insightful)
For instance, it is common with sorting algorithms to measure (in Big-Oh notation) how many comparison operations there are. However these may not necessarily be very expensive relative to other operations; such as the cost of swapping two elements. If the elements are large structures and the comparison keys are integers, then you should be concerned about the number of copies. But if the elements are pointers to structures and the keys are long strings, then the concern will be with the number of comparisons.
Almost every text book on algorithms you see is going to assume some sort of idealized computing device. In the real world there are multiple levels of memory speeds; caches up to virtual memory to disk. There are also other external factors that must be taken into account as well; for instance if you don't have enough memory, virtual or not, to hold all the data at once. Say you're sorting a database selection; or you're on a mainframe with limited memory space but reading customer data from tapes.
Re: (Score:3, Insightful)
No, and no. The data structure described by Henning-Kamp is not a B-tree, but a heap. Additionally, it's cache-aware, not cache-oblivious.
Re:Nope, he didn't (Score:4, Insightful)
Does it work : Yes
Is there a better way : Yes
Did it take 46 *years* for anyone to find a better way : yes
If Knuth's mistakes take this long to spot then I still rate his code over most peoples
Re:Nope, he didn't (Score:5, Insightful)
Re: (Score:2)
Knuth didn't get it wrong (Score:5, Insightful)
Re:Knuth didn't get it wrong (Score:5, Informative)
Re:Knuth didn't get it wrong (Score:5, Funny)
Laziness?
Come on, it's Slashdot!
Re: (Score:2)
But then the post wouldn't be sensational, wouldn't get as many views, and would leave you with a positive view of Slashdot editors.
don't use swap, doofs (Score:4, Insightful)
article summary:
"disk is slower than RAM. some doofs don't realize their system is swapping. ergo algorithm is bad."
throw in 'Knuth is wrong' to generate page hits.
???
profit.
non-sensationalized takeaway: "remember swap is slow; try not to use it."
Are you serious? Do you even know who phk is? (Score:3, Informative)
Poul-Henning is definitely not a "doof". He's single-handedly responsible for a huge amount of the FreeBSD kernel. Yes, this is the same FreeBSD that powers Yahoo!, that provided a significant portion of Mac OS X, and runs hundreds of thousands of businesses world-wide.
To suggest that phk doesn't know what he's talking about is absurd. He's one of the top three UNIX gurus in the entire world. In fact, the Internet today is what it is thanks to his hard work and dedication.
Re:Are you serious? Do you even know who phk is? (Score:4, Insightful)
I don't think anyone accused him of not knowing what he's talking about. He's been accused of using an extremely hyperbolic headline to draw readers. Besides, what he's saying isn't exactly brand new.
Re: (Score:2)
That's PHK. You should have seen him 15 years ago in the FreeBSD core. He's a very smart developer but even more so he's very adept at blowing his own horn.
Re: (Score:2)
It's not hyperbolic at all. phk is 100% correct, like usual. Knuth's estimates have been shown to be incorrect. In case you didn't catch it, that's what science is all about. Knuth posed his theory and his conclusions, and phk showed how they were wrong.
Actually, Knuth posted his assumptions, theory and conclusions, and phk showed that some of the assumptions no longer hold true for physical hardware.
Re:Are you serious? Do you even know who phk is? (Score:5, Insightful)
To place algorithm theory in the same space as implementation is just plain wrong... and the article does say that in a better way than kdawson's sensationalist header.
The implementation of a particular algorithm on specific hardware is more inline with resource economy than anything else and to subject comparison to the theoretical implementation is just ludicrous.
For instance one could with simple means device a unit where only bubble-sort would be possible because of the massive overhead of qsort on said machine. This is trivial... for instance Casio Fx180 calculator.
Re: (Score:2)
Hey, blame me, not kdawson! We both know who phk is.
--dave (with tongue firmly in cheek) c-b
Yes, but... (Score:3, Funny)
He's one of the top three UNIX gurus in the entire world. In fact, the Internet today is what it is thanks to his hard work and dedication.
Still, I'd trust Don Knuth over Poul-Henning any day--at least Knuth can spell his own first name correctly.
Re: (Score:2)
non-sensationalized takeaway: "remember swap is slow; try not to use it."
Not really. Closer to "Remember, swap is slow. Think about how you use it."
Re: (Score:3, Funny)
non-sensationalized takeaway: "remember swap is slow; try not to use it."
Not really. Closer to "Remember, swap is slow. Think about how you use it."
"Your response has exactly the same length as the parent's quote. Interesting"
Re: (Score:3, Insightful)
Re: (Score:2)
Instead store multiple levels of the tree in a contiguous mem/disk page.
I seem to recall a chapter in a programming book that I read maybe 15 years ago, talking about 'locality of reference' for optimisation. It was the same concept as this: Structure your memory usage to keep data that are accessed together, stored together. Then, whatever caching mechanism is in place will be able to spend less time paging (or spread the paging out over a larger number of CPU cycles) and thus have better throughput.
Re: (Score:2)
I've programmed app-level caches, and am very aware of the memory/disk trade-offs, so I completely understand where he's coming from (even though I don't know the details of his tool).
What I thi
Re: (Score:2)
More like: swap is slow. When you are using it try to make things you need to access at the same time closer together to minimize reads.
Re: (Score:2)
"doofs"? You should look up some information on the author :)
Re: (Score:3, Informative)
In no way whatsoever did he say 'remember swap is slow; try not to use it.'
That's as wrong as the idiotic summary.
Here's a relevant quote:
A 300-GB backing store, memory mapped on a machine with no more than 16 GB of RAM, is quite typical. The user paid for 64 bits of address space, and I am not afraid to use it.
The article is about redesigning binary heaps to account for non-linear access times between nodes due to swap. This point is critical. He's NOT avoiding swap, he's planning for it.
already proposed 40 years ago... (Score:2)
You mean people are implementing heap like that ?
That would indeed be stupid. People have been using B-tree http://en.wikipedia.org/wiki/B-tree [wikipedia.org] instead of Binary search trees for the cache access (or sequential disk IO) reason forever.
More recently we have been talking about cache oblivious and cache aware algorithm : http://en.wikipedia.org/wiki/Cache-oblivious_algorithm [wikipedia.org]
I should write an article about Z-order and be on the first page of slashdot...
Theoretical performance vs real-world performance (Score:3, Insightful)
Knuth never claimed the algorithm was the best choice in YOUR particular case. Don't drag his name through your sensational mud for the sake of your slashvertisement.
Re:Theoretical performance vs real-world performan (Score:5, Informative)
That's actually not the issue.
The issue is that in the real world, the assumptions underlying the calculation of algorithmic complexity may not hold. For instance, Knuth's analysis that the author of the article here holds to be misleading (not, as the Slashdot title suggests, "wrong") calculates the complexity based on the assumption of ideal random access memory, that is, memory for which all accesses are equal cost.
In real-world computers using caches (as pretty much all real-world computers do, often at many different levels) that assumption does not hold -- access to some parts of the memory address space are much more expensive than accesses to other parts of the address space, and which parts of the address space are expensive changes over time (and how it changes over time potentially depends on the caching strategy used at every level lower than the level at which the algorithm is implemented.)
This means that algorithms in the real world can scale worse than their theoretical "worst-case", if that theoretical worst-case scaling is based on the assumption of constant memory access cost, since that assumption does not hold in the real world.
Re:Theoretical performance vs real-world performan (Score:4, Insightful)
Compare g gravity vs. G gravity (Score:2)
He was writing a text book for students, and simplified a complicated problem to the point where it can be studied and analyzed more easily. Similar to teaching students Newtonian physics.
I don't find it all that similar. Newtonian mechanics describes behavior of the objects that people see within their daily lives to within measurable noise level. Ideal random-access memory does not. It's as if aerospace engineers were taught the version of gravity with g (Earth sea level acceleration) instead of the version with G*m/(r + h)^2 (acceleration given arbitrary planetary mass, planetary radius, and altitude). g works for land vehicles but not spacecraft, and as a lead-in to discussion of G*m/(r
Careful there... (Score:3, Informative)
I agree with all of your post except this part. Algorithmic complexity theory is about orders of magnitude, not about precise numbers. That's why we have O(n) as a complexity class but not O(2n), O(3n) as separate classes; saying that an algorithm has O(n) wor
Re:Careful there... (Score:5, Informative)
No, you're missing the point. And wrong. And also missing a lot knowledge about what O() means.
It doesn't matter how many orders of magnitude slower an operation is. O() is about SCALING for input size n. That's all. Constant factors do not matter. The GP already said this, please pay bloody attention next time. The running time of each operation is just a constant and has no impact on the O() performance. An order of magnitude or fifty is all the same. You talk about 1/100 speed and compare n to n^2. Hahahaha. Take n = 1000000. You know what the difference between n and n^2 is then? 1000000. Your puny factor of 100 is irrelevant against six orders of magnitude performance difference.
The worst case performance does not change. It's still O(n) or O (n^2). In fact it's quite possible for an O(n^2) algorithm to be faster than an O(log(n)) algorithm for small n under certain conditions. O is all about n being so bloody large that constant factors don't matter anymore.
This is all basic introductory algorithms stuff, please read up on it before trying to chime in on any arguments related it it in the future, okay?
Re: (Score:3, Informative)
Sigh. No, the GP doesn't know what he's talking about. And apparently neither do you. If he did he would not mention something as idiotic as cache making the algorithm go from O(n) to O(n^2). It makes it go from O(x*n) to O(100*x*n), both of which are O(n). But if n is 50, O(x*n^2) would come out faster.
You're both confusing the very real issue of the constant running time of operations and O algorithm scaling. The algorithm is still O(n) however for the data sets in question it's slower than an O(n^2) algo
Re: (Score:3, Insightful)
Where, n is the number of items stored, the lookup time is given by log(n)*COMPARRISON_COST + log(n)*MEMORY_ACCESS_COST.
That gives O(logn) only if COMPARRISON_COST and MEMORY_ACCESS_COST are *constant* - the entire point of the article is that MEMORY_ACCESS_COST is not constant, but increases as n increases.
Re: (Score:3, Insightful)
Except it's a bounded increase. That's my whole point. There is nothing slower than the hard drive to cache from. You can assume every operation has the worst possible access time and you'd still end up with the same O() running time.
log(n)*COMPARRISON_COST + log(n)*MEMORY_ACCESS_COST log(n)*COMPARRISON_COST + log(n)*MEMORY_ACCESS_COST_MAX CONSTANT*log(n)
Re: (Score:3, Informative)
Knuth didn't get anything wrong (Score:5, Insightful)
There isn't any "off by ten error", and this isn't telling us anything we don't already know (in CS terms): implementation on an actual computer can be different in performance from an abstract machine.
What the author is saying (quite well) is that the virtual memory performance amounts to cache misses, which cause extra performance overhead. He found a case where it was significant and got a 10x speedup in his particular application.
The article is a little over-zealous its characterization, though it's careful to note that this is not actually a theoretical novelty. The summary, on the other hand, bastardizes and exaggerates it.
The article is interesting, and worth reading, but if you RTFS without RTFA you'll be dumber than you were before. Thanks, kdawson.
Re: (Score:2)
What's troubling to me about this article is it reads like this guy hasn't been paying attention for quite a while.
Squid is his use case to beat? Has he been in any high performance app stack in the past five years?
Squid... really?
Re: (Score:3, Interesting)
Squid is his use case to beat? Has he been in any high performance app stack in the past five years?
Squid... really?
Considering Varnish was written due primarily to the lacking performance of Squid, I don't see why this is so bad?
Re: (Score:3, Interesting)
Other then varnish and squid what caching reverse proxy software is there? It looks like Nginx added caching to their core recently, although I'm not exactly sure if its intended to act in the same capacity as squid and varnish or to be more like mod_cache for lighttpd. I guess you could use apache and mod_proxy but that's not exactly high performance. I know my employer looked at the various offerings and we ended up writing our own on top of a webserver called OKWS.
Re: (Score:2)
My favorite quotes from the article:
Cache behavior is hard and not portable (Score:2)
I am sympathetic with his argument, but trying to figure out the best algorithm for a given OS and hardware combo is very difficult and usually not portable.
Re: (Score:2)
Assuming that the number of actual caching strategies is smaller than the number of hardware and OS combos (which it would seem likely to be, since at least some of those should share caching strategies), what is really needed is analysis of the determinants of algorithm performance that take into account different caching strategies. That's still diffi
Re: (Score:2)
If you make sure that you require less pages to do something, you will generate less page faults. I would think that this fact is rather universal. Of course, you can go further by tweaking the parameters in such a way that they run well on a specific processor.
Re: (Score:2)
I suppose, but have all modern OS's finally agreed on a universal LRU algorithm, or do we still have "clever" algorithms that try to figure out if the application is user-centric or server-centric then changes the page expiry accordingly?
news at 11 (Score:3, Insightful)
Algorithm revised in light of real-world performance constraints! Read all about it!
Seriously, we just rewrote a tree (that runs in a high traffic serving environment) this month at work because it wasn't streamlined just right to take full advantage of the underlying architecture. No one will write a paper about it.
Also, hey kids, profile your code.
Why trust the OS? (Score:5, Interesting)
Re: (Score:2, Insightful)
Don't Trust the OS! (Score:2)
In a virtual world it lies: I suspect that most Operating Systems lie about what physical hardware:
VMware allows for over-commitment of most hardware. (CPU, Memory, and Hard Disk). Windows allows for over-commitment of Memory
Since this is making assumptions about memory management: (Flash: Various algorithms may be tuned for optimized use in your specific use-case).
In your case of grabbing 80% of memory: This works if you really need the memory - in which case you have to have it: If this forces Windows (li
Re: (Score:2)
In Windows, the API to allocate physical memory is VirtualAlloc [microsoft.com].
Good point about VMWare. I hadn't thought about that.
I just used 80% as an example. Obviously one would provide command-line switches or config options for either X% of memory or Y MB of memory.
Re: (Score:2, Interesting)
Why is this funny? Almost all DBMS kernels do it -- they manage physical memory and disk blocks themselves. More to the point, Dr. Kamp is glossing over the fact that one doesn't use in-memory data structures where data my reside on disk.
In this case, the suitable data structure is any variation of B+Tree, which actually contains children of a node in one memory page and when there is no more room in that page a page split happens. He used the wrong D/S to begin with, concludes Knuth was wrong and finally e
Re: (Score:2)
Very simply, because the OS developers are usually pretty smart and when you try to outsmart them and fail you look like a tool. And you're going to fail. If I knew that everyone who I posted a response like this would pay up, I'd bet you $1k that you'd fail and make mad cash.
Re: (Score:3, Insightful)
well (Score:2, Informative)
This deserves a beer. (Score:4, Funny)
If you meet him some day, and you think this stuff is worth it, buy him a beer.
Stupid headline (Score:4, Insightful)
Good article (increase your locality to get fewer page faults). Stupidly wrong Slashdot headline and summary. "Off by ten error?" Please!
kdawson, next time, RTFA before you post someone's lame summary.
Summary is wrong - btrees != binary trees (Score:4, Informative)
The summary is wrong when it talks about "an off by ten error in btrees". In fact, the article talks about how normal binary heap implementations are slow when virtual memory is taken into account.
In fact, b-trees ARE cache aware and ARE optimized to limit paging on disk. PHK's algorithm is essentially a cache-aware version of a binary heap.
That is, binary tree is to b-tree as binary heap is to PHK's b-heap.
This headline is silly (Score:5, Informative)
The RAM resident stuff is still useful, both at a lower level, but also for those of us creating applications that can live entirely in memory. A web site I did recently is careful to ensure that the entire primary data set can fit in memory, and for that site everything he wrote is still perfectly valid.
In fact, for very high performing websites you try to ensure that at least most of your requests come from memory rather than disk, which makes Knuth's stuff more important than ever. If you can't do it in RAM then you'd better have a lot of spindles!
Re: (Score:2)
CPU cache.
Timer wheels (Score:2)
Continuing a discussion...
Seems to be that this bheap just reduces the number of pages probably needed from log(n) to log(n)/C where C is the number of levels that are stored in the same page. And for removing a node it may need to access log(n)/C random pages. So this is just a constant factor improvement... it's just that the constant is number of pages so has a large real world cost.
I'd like to get people's thoughts on using timer wheels [lkml.org] instead, like the linux kernel uses for timers. Say you take say
Re: (Score:3, Informative)
The main reason they are using the buckets is to delay sorting costs as far as possible into the future so that there is less cost for most timers (as most timers are apparently deleted far before expiring). I'd suggest that the major performance gain is due to this lazy sorting, and not because their data structure avoids page faults. (Well, it does avoid page faults that the old linked list algorithm would have caused, but these page faults are due to the sorting going on in the original code which is a
Don Knuth pays people who find errors (Score:3, Interesting)
Re: (Score:3, Funny)
I forget the exact amount, but it was like PI or E dollars for every typo. I am not sure what the payment is for an algorithmic error.
I think it's e ^i(pi/2) [wikipedia.org]
Seymour Cray on virtual memory (Score:4, Insightful)
"Virtual memory leads to virtual performance."
Just what I always wanted, a B-tree implementation that is guaranteed to swap.
"Knuth got it wrong" (Score:2)
Next news headline (Score:2)
GOTO Successfully Used Without Harm!
Does he get a check? (Score:2)
I'm interested to see if this counts as a true error and thus deserving a check.
Nothing new.. please move along (Score:4, Informative)
This really isn't anything new. Knuth didn't get it "wrong". He based his analysis of the algorithms assuming a system that had dedicated memory and where each instruction of code ran uninterrupted and in a consistent fashion.
Certain memory access patterns are "bad" under a system that uses virtual memory, especially when the base system is memory constrained. This has been a well known fact for decades. In fact one of the maybe lost arts of programming was ensuring reference locality, not only of data, but also of code. It was a common practice to ensure that often called subroutines or functions where either located in same page of memory as the calling code, or to group all the often called functions into as few pages of memory as possible.
Basically, every address space has what is sometimes called a working set, a set of pages that have been recently referenced. There are three things that can happen with a working set. It can remain the same size, it can grow and it can shrink. If it remains the same, there is no additional load to the operating system. If it shrinks, there is no additional load to the operating system, in fact this can help a memory constrained system. A growing working set however an lead to a thrashing system. Some operating systems will monitor working set sizes and can adjust dispatch priorities and execution classes depending on what the recent working set size history is. An application with a growing working set may very will find itself at the end of the queue way behind applications that have a static working set size.
Take for an example the following very simple program
Here the working set of this program will be very small. Ignoring the file i/o routines, all the code and data references will be limited to basically a fixed section of memory. From a virtual memory stand point, this is a "well behaved" application.
Now take the following
Functionally the same program, however the data reference pattern here is all over the place. The working set will be large, since many of the buffer pages will be referenced. The program never stays long on the same memory location.
Finally take the following example
Here there will be an initially huge working set as the data is read in. However, the working set will shrink to a reasonable size once the numbercrunching phase starts since the data references will all be localized to a small block of memory.
The smell of slashdot in the morning... (Score:5, Informative)
What a misleading title, it is not even in the same continent as the article.
A large number of people obviously didn't read the actual article.
And I guess Knuth has quite a fanboi community on slashdot. I wonder if he really appreciates that ?
Some of those who did read the article, does not seem to know the difference between a binary heap and a binary tree, and even the pretty strong clue to the difference in the text, did not make them go check wikipedia. 10 out of 10 for selfesteem, but 0 out of 10 for clue.
Those who think CS should be unsullied by actual computers should make sure to note this belief on their resume. (Trust me, everybody you send your resume to will appreciate that.)
Those who advocate getting rid of Virtual Memory must have much more money for RAM than is sensible. I wish I could afford that.
About five comments tries, in vain it seems, to explain the point of my article to the unwashed masses (kudos!, but really, what are you doing here ?)
Not one comment rises to a level where I feel a need to answer it specifically. On Reddit over the weekend there were about a handful.
Is that really par for the course on slashdot these days ?
Sic transit gloria mundi...
Poul-Henning
Re: (Score:2, Interesting)
Re: (Score:2)
Don't Journaled filesystems themselves use b-trees?
File systems that use b-trees use b-trees; file systems that don't use b-trees don't use b-trees. Both types of file systems can be journaled or not journaled.
Re: (Score:3, Funny)
What is this? The freaking tautology hour?
Alas, no more (Score:5, Interesting)
Unfortunately, he no longer gives out reward checks [wikipedia.org] 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 [stanford.edu].
He is old, but... (Score:2)
...not dead yet, to quote Monty Python.
Re: (Score:2)