Ask HN: Is the “The Art of Computer Programming” Worth the Investment?
Reading through and taking in "The Art of Computer Programming" seems to require massive amounts of time investment. In your opinion is the gems inside the text worth it?
But.
If you want to learn _other_ things, these books are incredible. Maybe you want to learn deeply the combinatorial ideas behind data structures, or general techniques for squeezing small optimizations out of low level code. Or even maybe you want to see simple data structures used every-which-way to efficiently solve a huge range of mathematical problems. None of this is normal programming per se. I treat these as math books, and love them for it.
Like much of mathematics, it will make you a better programmer, but only accidentally.
That said, I think its worth having this for the humbling experience it provides. This experience is very much needed for every engineer, and specifically software engineers, because after a while of reapplying same old tropes to churn out solutions to problems, there creeps a feeling that we are at the top of our game, and "experts", when in reality most of us are only "experts" in a specific insipid framework or technology which are as permanent as the latest fashion trends. This series of books makes us feel worthless and keenly introspect. It makes us see that there is a vast array of knowledge that we severely lack. It builds personality and keeps us grounded. It separates true musicians from college band guitarists who shred the neck to cheering crowds.
I have Combinatorial Algorithms Part 1 Volume 4A and it makes me cry every time I peruse it.
But Corman himself is also kind of a pretentious tool, so that doesn't help - he was certainly an abysmal freshman advisor.
I think the same course could have been much more useful and even fun if you had to turn in working C code in addition to all the pen-and-paper work.
I have been watching Steven Skiena's lectures and reading his book, and I like both of them, but the lectures most of all because of his relaxed and practical approach. Skiena himself says that CLRS is a "better" book than his (and also more up to date) but I like the Skiena learning curve better.
In contrast, Tim Roughgarden's lectures and books are more mathematical, but his proofs seem reasonably well-motivated and clearly explained to me at least.
I also like how both of these guys point out that coming up with new algorithms or proofs from scratch is incredibly hard and you shouldn't expect (yourself or anyone) to be able to do so quickly or on the fly. Success with algorithm puzzle exams, algorithm puzzle "programming" contests, and algorithm puzzle "technical" interviews is largely based on familiarity with a large body of pre-existing algorithms and data structures and experience applying them to a wide range of problems. That sort of knowledge and experience greatly improves your odds of guessing the (often sneaky and non-obvious) trick required to solve a particular, usually weirdly stated, algorithm puzzle.
They may be extremely dense and hard to read, but I feel like you are hanging a lot of emotional baggage on a set of reference books.
Is that a recommendation or anti-recommendation? Or both?
- Reflections on a year of reading Knuth https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...
- Reflections on another year of reading Knuth https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...
- Reflections on Three Years of Reading Knuth https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...
BTW, commandlinefan, your page:
https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...
has the right pane text overlapping the left pane (main body of post), at least when I increase the font a bit with Ctrl=+. (Chrome, Windows). Please check and fix if can.
It happens for the other two posts about reading Knuth too. But not for your About page. FYI.
(In particular I love why numbers with lower initial digits are more ‘common’ than others, and tests for randomness.)
> Quicksort is O(log n)
Should be
> Quicksort is O(n log n)
Reverence for it is religious/romantic in nature, and neither based on practical nor pedagogical means.
If you want to build practical skills and experience with algorithms, choose a problem domain involving them and dive straight into it.
If you want to expand your mind/skills, choose a programming language from a paradigm and do everything in it for a few years. Then once you've got it all figured out, choose a deliberately different paradigm and do the same thing. Repeat for 3-5 rounds.
Sure, there's nothing technically or factually wrong with the book. I had to look up some algorithms in it once for a reference and implemented it from that source, and Knuth writes clearly enough, but if someone wanted to learn english, or wanted to know how to improve their english, i similarly wouldn't direct them to read an old dictionary.
Edit 1: If i had to recommend books, aside from the observation that there's relatively few that i'd actually recommend with the goal of making one a better programmer explicitly, I've learnt more from lisp books and/or trying to apply languages to project euler or personal projects than I've ever picked up from TAOCP...
Edit 2: oh, and trying to improve and implement all the things that people tell you not to bother trying to improve and/or implement...
That said, you didn’t really set any goals; you just asked if it’s “worth the investment”. That’s very abstract, and to that I would say “yes”, but also “it’s very likely that you’re not at a point in your life that reading the series, especially cover to cover, is the best use of your time”.
Hope that helps.
Genuinely curious, when would it be the best use of my time? Is there any scenario where "Read TAOCP and gain X superpowers" would hold true? I have been wanting to get into this for some time now because I like the idea of intellectual pursuit but I also hoped that some benefits, however incidental, would carry over into my career.
The benefits of understanding how computers work at low levels, how algorithms work and are built/studied/compared, and how data structures can change how you think about programs and processes (to call out a few barrel-sized buckets) are likely to be helpful over the long term, while the likelihood that you happen upon the key thing that you need today (or this month) at just the right time is pretty low.
For example, 7.2.1.2 on generating all permutations (http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf) has a lot of cool mathematics, some low-language programs, some alphametic puzzles, .... Or 7.1.4 on Binary Decision Diagrams (http://www.cs.utsa.edu/~wagner/knuth/fasc1b.pdf) is on a little-known (IMO) data-structure presented in Knuth's unique way, which can solve many counting problems.
Stepping back a little, there are two ways you could read this book:
• Try to engage with the mathematics, try each exercise for at least half an hour before giving up and looking at the solution, etc. (Doing it this way can definitely be a massive time investment.) If you'd like to do this, and find the mathematics difficult, you should read Concrete Mathematics which Knuth co-wrote with Ron Graham and Oren Patashnik, which is a highly enjoyable book in itself.
• As mentioned in a recent post (https://nickdrozd.github.io/2019/05/17/knuth-check.html):
> By the way, if you’ve ever thought about reading TAOCP, give it a try. A lot of people will tell you that it’s a reference work, and it’s not meant to be read straight through, but that isn’t true. The author has a clear point of view and a narrative and an idiosyncratic style, and the only thing that inhibits readability is the difficulty of the math. There’s an easy solution to that though: read until you get to math you don’t understand, then skip it and find the next section you can understand. Reading this way, I skip at least 80% of the book, but the remaining 20% is great!
You could even do the latter first, then the former. It's really up to you, and diving in and trying a chapter or two is the best way you can judge whether you'll find it an enriching experience. (BTW: Knuth mentions in some interview that he wanted to call the books “mathematical analysis of algorithms”... if you're thinking that the books are trying to define the art of computer programming and will make you a better programmer at the kind of programming tasks you're likely to encounter in a professional career, then it's probably not the best use of your time... which is why I mention reading it for yourself and seeing if you like it; IMO the books are really enjoyable and full of clarity and grace and humour and depth.)
However, they are a well of ideas as well as extensive treaties on "esoteric" topics (e.g., testing sequences for randomness, derivation of FFT, sorting networks, external sorting...)
Knuth has written that he plans to remove the section on external sorting from the next edition of vol 3 (if _that_ ever happens)… though think about the cache effects on modern CPUs: could we sort faster by thinking of the cache as "internal memory" and of RAM as a "tape or disk drive" and applying a decades old external sorting algorithm?
Similarly, most sorting routines rely only on less-than, but often your comparison routine returns -1, 0 or 1. I implemented string sorting in C++ using 3-way comparison (instead of just less-than) and it was actually faster!
The exercises and their answers are source of gems as well, even if you just look up the answer to use the result.
Also, I never read them cover-to cover. When I'm bored, I take one volume, pick a chapter/section and read it and skim through exercises, at the same time thinking of what that could be applied to.
This is provably false for common DDR4 RAM! Linear access to RAM is significantly faster, maybe 2x to 3x faster than random access in practice... maybe 10x faster in a theoretical micro-benchmark.
This is partially due to pre-fetchers: modern CPUs will detect that you're accessing memory linearly, and then it will "prefetch" the data to the cache before your code even reads a location.
Another aspect: any "Open Row" of RAM (roughly 1024-bytes worth) is accessed through a "Column Read", which is 2x faster than a "Row Read + Column Read", and maybe 3x faster than a "Precharge + Row Read + Column Read" (this last case is how random-access works).
So a read to an already-open row is 2x to 3x faster at the DDR4 protocol level. The prefetcher increases gains to roughly 10x faster in special cases (but the prefetcher is "arguably cheating", even if it is quite reliable in sequential cases).
Just using round numbers, but... yeah... random access should be between 2x to 3x slower if you test it. Its very simple to test too: just rand() across a big 2GB array that you malloc() and you'll see that the rand() traversal is SIGNIFICANTLY slower than an iterative traversal.
------------
If you can "cheat" your algorithm to traverse memory sequentially, you'll find absolutely crazy gains. Bonus points: a linear / sequential algorithm can often be converted into SIMD-style code (possibly by the autovectorizer of the compiler).
Sequential-access of RAM is one of those surprising micro-optimizations on modern computers. 1000% faster memory reads in some cases, I'm serious!
-----------
The L1 cache seems fully random to me in my tests. But the hardware prefetcher works even on L2 and L3 cache, so I'd expect sequential gains even if your data fits inside of L2 or L3.
Oh, and don't get me started on the TLB. If you're on Windows or Linux (which use virtual memory, not physical memory), all pointer-dereferences goes through the Translation-Lookaside Buffer. If you have 4GB to 8GB of data on 4kB pages... random access would destroy your TLB and you'll suffer dramatic slowdowns as the OS will "pagewalk" the virtual memory directory on every dereference.
Yeah... memory optimization favors sequential access in a huge variety of situations.
TAOCP is no howto, no tutorial. For the subjects it covers, it is a meditational bible.
Be it ever so humble, it will be yours and it will grow in leverage the more you test, update, organize, and refine it.
A good way to start is to write down things you've already learned about computer programming. Then get ready to start organizing and updating this information over time.
Pretty soon you'll find that you start on new projects faster and save lots of time and energy.
Actually I usually just do the cheap hack anyway but it is reassuring to know that it is there.
There is also the benefits of learning direct programming of hardware, for example MIXAL, used in the first 3 volumes (replaced by MMIXAL) is meant to be run without an operating system. Maybe you want to play around with direct control of a RISC-V chip or fpga or understand the quantum abstract machine Rigetti built and it's instruction language.
Reading it from start to end IMO is overkill, unless you want to be algorithm encyclopedia.
Though most developers can just skip it, because they won't need to implement any complex algorithm ever.
That being said, I think you CAN put all that you learn in those books into practice, even if it won't be in your job - try out competitive programming. Try TopCoder or CodeForces, or Google's Code Jam. I think Hackerrank is similar and heavily used for weeding out programmers during the early stages of interviews. As this article states: https://glenmccallum.com/2019/05/14/senior-developers-reject... this sort of "testing" could actually become even more common place for job applications because of how handy it is for recruiters.
But yeah, if you enjoy being competitive in general, consuming books like CLRS or TAOCP and then joining competitions will actually give you a good feel for a programming world very different from the usual, day to day development you'll do at your job.
In the monetary sense? Depends highly on your particular specialization.
In the intellectual sense? I own a copy, have read selected chapters. Perhaps. Are you planning on doing all the exercises, as if in a class?
This wouldn't be mentioned by Bill Gates “If you think you’re a really good programmer… read Art of Computer Programming… You should definitely send me a résumé if you can read the whole thing.”
Currently most of engineers have to do application development where you rarely come across of any need to use this knowledge. But for being computer engineer and if you think all these coding challenges, the concept of these books is still relevant. Books on competitive coding take excerpt from that book only.
It is a daunting task to complete but it will show its worth over time.
I don't think Bill meant it seriously....he never responded when I sent him my resume 20 years ago :-)
if you want to learn in general more about computer programming ,go for it, its good. if you want to learn specific sub topics within computer programming, of which there are many, consider getting a more specialised book.
as example. for me i like to go low level and code in C on some hobby operating system. most information in most programming books is rubbish for that. but specific books targeting intel/amd execution environments, architecture and assembly basics have helped me ALOT. - other books still help me out, and teach me things, but specific books help me directly implement things into my current project which is to me more useful.
I would not recommend it for studying, though.
I'll read it again when I have the time. The other stuff is admittedly too difficult for me.
Yes, I am jokingly referring to the Bill Gates blurb about the book on the cover of later editions of TAOCP.