Slashdot Mirror

← Back to Stories (view on slashdot.org)

Knuth Got It Wrong

Posted by kdawson on from the to-be-or-not-to-be-heap dept.

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."

12 of 298 comments (clear)

  1. as Knuth told me when I was at his house by commodoresloat · · Score: 5, Funny

    "Who the hell are you and what are you doing in my house?"

    1. Re:as Knuth told me when I was at his house by TheGratefulNet · · 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.

      --

      --
      "It is now safe to switch off your computer."
  2. Nope, he didn't by siddesu · · Score: 5, Informative

    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.

    1. Re:Nope, he didn't by SashaMan · · 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/

    2. Re:Nope, he didn't by yuhong · · Score: 5, Insightful

      Especially when virtual memory did not exist 46 years ago.

  3. Re:Crank it to 11 by PatPending · · 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.

    --
    What one fool can do, another can. (Ancient Simian Proverb)
  4. Credit where credit is due... by Anonymous Coward · · Score: 5, Informative

    link

  5. Re:Crank it to 11 by Nadaka · · Score: 5, Funny

    That has to be the one of the better binary jokes around.

  6. Agreed by eldavojohn · · 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."

    --
    My work here is dung.
  7. Knuth didn't get anything wrong by jfengel · · 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.

  8. Re:Theoretical performance vs real-world performan by DragonWriter · · Score: 5, Informative

    Yes it's true. In some real-world applications an algorithm encounters it's worst case running time more than the predicted theoretical average case running time.

    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.

  9. Re:Knuth didn't get it wrong by ImABanker · · Score: 5, Informative

    How does one get from, "I have not found a systematic flaw in the quality of Knuth et al.'s reasoning" to "Knuth Got it Wrong"?