Ask HN: Is Knuth's TAOCP worth the time and effort?
I excitedly started delving into it last night but after an hour or two of reading and exercises I started getting the sinking feeling that I'd just wasted $178.08. It seems quite mired in 1960's-era academic minutiae and tedious mathematical formalism that doesn't seem very relevant to a modern practicing programmer.
For all its focus on algorithmic performance I found no mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc. which are all very fundamental aspects of good performance on modern hardware.
So for those who are practical programmers and have gone down the Knuth TAOCP rabbit hole I ask - was it worth it? Did it give you knowledge and skills applicable to your programming work or was it mostly academic / intellectual entertainment?
140 comments
[ 3.1 ms ] story [ 164 ms ] thread> For all its focus on algorithmic performance I found no mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc. which are all very fundamental aspects of good performance on modern hardware
Yes, but pure computer science is not worried about that (maybe about multithreading)
But yeah, for a more practical/specific work there are better options (but it's going to be specific to an area)
If you're interested in modern architecture details, I'd recommend Agner Fog's marvelous reference books (http://www.agner.org/optimize/).
He writes in that made up assembly language specifically to consider efficiency and implementation concerns:
"Expressing basic methods like algorithms for sorting and searching in machine language makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes."
Whether he achieves that is another matter.
There is a note from Bill Gates in the back that says if you can read it all and understand it, contact him for a job.
Edit: read the comment by @geff82 in this thread. This is perfect.
Computer science and software development are usually thought to be the same by non computer scientists, but in reality computer science is basically applied mathematics. Expect a lot of it.
When you prefix it with "computer" you're specifying the domain, namely all instructions that will allow a computer to do something. Like you correctly mentioned, when prefixed with "dynamic" you're specifying the set of instructions that have a common approach (to break problems into subproblems, etc etc). Similarly, when saying "linear" before "programming" you're specifying that the instructions involving this set use linear variable constrains.
Source: https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...
My first thought was, there sure are different definitions of what "dynamic programming" is, as I've only seen it as related to the Bellman equation (motivation for the name being that it would sound appealing to Bellman's superiors at RAND who had a distaste for mathematical theory).
But then, solving the damn thing is all about identifying and avoiding re-computing overlapping sub-problems, so I guess that is exactly what you meant (even though I have no idea what "memoization" is) :)
A while back, I was joking with some friends that TAoCP is to the programming world what Finnegans Wake is to English literature: you're not supposed to read it, nobody's ever actually read it. We all just say we've read it, talk about how brilliant it is, and place it prominently on our office bookshelves to silently humblebrag to anyone who drops by. Sorry you had to spend $178.08 on that lesson, mate.
Short answer, is the book easy? Of course not. Is it dated in approach? Yes. Sorta. What would make it better? A modern language? Why?
Consider, just yesterday there was someone designing an elevator system using python. That is literally one of the first examples in TAoCP.
Not long ago, there was an article about how linear search with sentinel values is actually faster than binary search for many data sets. This is, again, one of the first treatments of searches in this text.
I'm waiting for someone to rediscover that you can make a tree for depth first traversal, such that you do not need to use a stack. Again, one of the early topics in these books. Curious about different characteristics of Tries/Trees/Lists/Hashes?...
Is it worth the time to read end to end? Almost certainly not. The math heavy sections are definitely going to scare off a lot of people. Myself included. This mainly means to skim the exercises.
But, there is a lot to offer in the industry of programming. Knuth picked an order to offer this information and is going in that order. The latest topics he is just now getting to are hugely relevant in many endeavors and I recommend people at least be aware of them.
Perhaps it's sacrilege, but I've always considered it kind of weird to take on a project like TAOCP in a field that's growing far faster than it can be documented by one person.
Is it though?
Hash tables - 1953, Red-Black trees 1972, Quicksort 1959, etc...
I don't mean to take away from the books - they're beautiful and full of a lot of timeless knowledge. There's just something that seems a bit ... I can't even find a word for it ... about the endeavor.
> faster than can be documented.
By one person, I wrote.
Here's one that I think is interesting, difficult and evolving: distributed systems. This shows interesting work happening with version vectors, for instance, over the past 15 years: https://en.wikipedia.org/wiki/Version_vector
I wish him the best of lucky and sincerely hope he pulls it off.
TAOCP is not only hyper-focused, obsessive, bloated, difficult, and outdated, but also genius and foundational and connected to everything.
Kind of like TeX and Metafont.
You've yet to make the case that the fundamentals of computing science are changing so much that documenting them is not a worthy task.
Again, basic algorithms and data structures simply have not changed. Their performance characteristics, methods for optimal implementation, etc, certainly have as computer architectures have evolved (think reordering CPUs, multi-level caches, changes to data storage technology, etc). But the basic algorithms remain the same. Quicksort is still quicksort.
It's true that over the last decade some new concepts have reached a new prominence (e.g., lock-free data structures), but those are additions to the field. They certainly don't invalidate the basics.
These are computer science books, not software engineering books.
Woah there! No one ever said anything about 'not worthy'. I have tremendous admiration and respect for Knuth and his work, and like you say, a lot what he's written is timeless.
[0] https://en.wikipedia.org/wiki/Equivalence_relation
Also (you probably know): "The unreasonable man ..." - Shaw (GBS)
https://en.m.wikiquote.org/wiki/George_Bernard_Shaw
Especially without those math courses, I imagine it will be a tougher read, certainly for those grown up with multi-mega or multi-gigabyte machines who expect it to be on programming, not computer science.
And it isn't 60's era formalism, it is low-level computer science.
And to the original question, I consider TAOCP probably not worth the time and effort to read in detail. It has a lot of interesting stuff if you have infinite time, but very little that I've found practical to me. I've read enough of TAOCP to get two Knuth reward checks but can't motivate myself to read more than a fraction of it.
https://ebooks.adelaide.edu.au/j/joyce/james/j8f/complete.ht...
The explanation is golden:
https://en.wikipedia.org/wiki/Finnegans_Wake
"Despite the obstacles, readers and commentators have reached a broad consensus about the book's central cast of characters and, to a lesser degree, its plot. However, a number of key details remain elusive.[6][7]"
That said, if you can convince people to house rule it as a word-source for a Scrabble game, you can terrify people who want to challenge.
Some examples from the first chapter "oystrygods gaggin fishy-gods" - ok, that's clever turning Ostrogoths and Visigoths into seafood gods. The Willingdone Museyroom section was entertaining enough with "Willingdone" and "Lipoleum" for Wellington and Napoleon. "And a barrowload of guenesis hoer his head" - Guinness the beer and Genesis the book of the bible, clever enough.
I've read a few comments before saying that FW is hilarious. Maybe it's pointless to try to dissect humor, but I'm just not seeing it.
I personally think this passage is one of the funniest things I've ever read. First of all, it rolls off the tongue in the most ridiculous way ever (you have to read it out loud) and second of all he manages to write entirely about food while making you think entirely about naughty things.
In the passage cited below by jhedwards, I find the way Joyce suggests Shem's Greek-Jewish heritage explains his taste in cheap prostitutes very funny (as well as his skewering the sanctimoniousness of it all, "you like prostitutes but only the cheap ones"). Also, that he gives the address of the whore house, like it is an advertisement is also funny.
You mention the first chapter, so I started reading from the online link given earlier in the thread. In the second paragraph, I found it funny the way he says that topsawyer (Tom Sawyer?) had not exaggerated the size of his balls when they were "doublin their mumper all the time."
It's all about the wordplay and frankly being ridiculous. Obviously if you read these things in the context of a forum, you are probably not going to find it funny. Context is very important: http://www.cc.com/video-clips/0i0fy2/stand-up-hannibal-bures...
As jhedwards suggests, if you read it aloud you will hear the jokes.
> "You're full of shit," Knuth responded.
(http://www.folklore.org/StoryView.py?story=Close_Encounters_...)
Yes, now we know that this never happened, but I like to think it did.
In every full set of TAOCP, there is a sentence that reads "If you have read this far, mail this string to the author to collect $25." The sentence is followed by a 10 character alphanumeric string. The string and placement of this sentence is randomized: different in every set.
To this day only 3 people have collected their checks. All three have them framed on their walls.
My parent post was a (badly executed) joke, riffing on a) the famous bug reward checks and b) the running joke (mentioned in other comments) that a lot more people own TAOCP than have actually read it. EDIT: and c) the urban legends of students putting such a "test" sentence in papers they hand in to inattentive professors.
There is no better way to kill a joke than explain it, but mine was DOA anyway...
Those are issues for a subset of computer hardware. Embedded computing is still huge and has drastically different performance requirements. TAOCP is designed to stand the test of time, not focus on micro-optimizations that generally have limited performance impact and are a waste of time 99% of the time.
Even chips as small Cortex-M4 has a write buffer, 3-stage pipeline and branch speculation. And real embedded computing is more and more utilizing hardware similar to desktop/mobile/server. You can't run self-driving car / neural networks / image processing on a single threaded CPU with no cache or branch prediction.
As to the rest of it. It's much cheaper to use a GPU style massive array of dumb cores vs. a few faster cores. Don't forget car companies are spending billions on these chips so spending a little more on software to save a lot on hardware is a good tradeoff.
Hmmm. My edition of "Sorting and Searching" has a section devoted to tape-sorting.
The point isn't learning the answer; it's learning how to get to the answer.
Depends what you want from it. I used the first book to study for my Bachelor's degree final state examinations, and it served me well :-)
In other words, yes it is very academical, in the truest sense of the word.
From what you say, that you want it to "mention of pipeline stalls, designing for cache performance, branch prediction, multithreading, etc.", you might find better use of Andrew S. Tanenbaum books. I have only read his Computer Networks [1], but it has saved me at least 14 hours of boring lectures at uni, and helped me with some protocols work. He still does research in distributed OS-es, so would hope, that rest of his books would have same amount of readability and usefulness as the one I have read :)
Back to Knuth, if think you have no use in mathematical formalism, or college math in general, you will probably find it little more than intellectual entertainment.
There are of course areas where having formal theory of a thing is beneficial when programming, even if you yourself don't apply it (i.e. the chapter on random numbers seems like something everybody touching any code related to security should read, i.m.o)
But even then, if you suddenly need to learn more math theory, there are probably better sources than Knuth.
As somebody who finished my Msc already, I like it as my intellectual entertainment just fine :)
[1] http://www.mypearsonstore.com/bookstore/computer-networks-97...
Sounds like what you want is a prescriptive tutorial addressing a set of specific computing problems. That's not what TAOCP is.
If you want to scratch that itch, a better way would be Cormen, Leiserson, Rivest, and Stein's Intro to Algorithms (https://mitpress.mit.edu/books/introduction-algorithms).
I'm not aware of such a universal reference for the interaction between algorithms and architecture ("...pipeline stalls, cache performance, ...").
Until that day comes...TAOCP sure looks nice on the bookshelf.
I got a set when a coworker jumped ship with no forwarding address and left all his books. It seems useful for people implementing languages and standard libraries, less useful for people using them.
I keep volumes 1 and 2 on my desk in case I ever need to refer to them for information about a specific topic, but I have yet to actually open them.
If you're in the Toronto region, I actually run a reading group for these books: http://www.meetup.com/Knuth-Reading-Group-Art-of-Computer-Pr.... We get together about once a month and go through the problems together. Just last night we had a 2.5-hour session about only section 2.3.4.1. I doubt you'd be able to get this much content from a sub-sub-sub-section of CLRS.
I would argue the opposite... When I needed to read about the different approaches on how to shuffle a deck for a card game TAOCP was there for me. When I needed to investigate different approaches for string comparison algorithms, TAOCP was there for me. When I didn't understand what was the deal and why was so hard to implement a random number generator, TAOCP was there too.
Anytime that I needed a reference for a core CS algorithm or data structure, TAOCP worked very well as a reference for me. It feels like the Britannica Encyclopedia for CS.
Knuth has spent 50 years creating computer science that we can take for granted. But in the end TAoCP is a "little book on compilers" and if that's not relevant to one's vocation and the topic isn't intellectually interesting in and of itself then it's probably not the right book for a person.
Knuth always reminds me how hard this stuff really is.
Good luck.
[1]: edit. The First Edition has a centerfold showing the sequences of different society's executions across multiple tape drives.
I did not learn much of practical use for my day-to-day programming. Sadly, I will probably never read the other two volumes in my boxed set. They look great on the shelf.
The MIX assembly language was my least favorite aspect of the book - and I ENJOY creating and tinkering with toy virtual machines.
MMIX (MIX's modern RISC successor) will probably be a lot nicer.
Perhaps assembly languages are essential to demonstrate the concepts properly. And I understand the arguments against using a popular low-level language such as C. But it sure would have been nice to have a simple and readable pseudo-language for the examples rather than MIX!
Early in my career, I got the first three volumes.
The volume on sorting and searching was the most useful, and there the most useful was AVL trees. Next, heap sort and the Gleason bound. Sort-merge? I'd known that already, but if don't then can learn it there. Radix sort? That's what the old punched card machines did; in some cases it's faster than heap sort (doesn't contradict the Gleason bound because that bound assumes that the sorting is from comparing pars, and radix sort doesn't do that). Radix sort could be still be useful in special cases. Lists, queues? Obvious.
The fast Fourier transform remains important, and some of what Knuth writes about it is good and tough to find elsewhere.
Somewhere in those first three volumes are some really good summaries of combinatorial formulas, with some results not easy to find elsewhere.
The volumes give some good examples of how to do the math to evaluate the performance of an algorithm -- might need to do that sometime, e.g., for some guaranteed performance in some embedded system -- and if need to do that then it's far easier to read at least the start on how from Knuth than reinvent it yourself and likely easier than from other sources.
The level of clarity, precision, and quality in Knuth is about as high as those go and a great example for others.
That's most of what I got from those three volumes.
For the later volumes, right, I didn't bother. But, if I have a question that might have an answer in one of those volumes, then, sure, I will eagerly look.