4 ms·
Depends on your goals. For example, when writing a real-world application today, the standard library provides you with a "good enough" sorting and searching al
by zvrba 7y ago
Depends on your goals. For example, when writing a real-world application today, the standard library provides you with a "good enough" sorting and searching algorithms and dictionary structures. The whole 600+ pages of volume 3 are dedicated just to these topics. You aren't going to be a better "everyday" programmer after studying that book. (Though I'm not aware of any language that has radix sort in its stdlib :-))
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.
- KingMob 7y agoThe issue with thinking of RAM as a "tape or disk drive" is that a tape has linearly increasing access times, but RAM takes the same time to access any part, so this algorithm wouldn't be ideal. Even most of our external storage these days (flash, etc) is random-access. True O(n) access media are becoming more and more scarce, so I'm not surprised Knuth is removing it.
- zvrba 7y agoIIRC, these algorithms are based on merging, i.e., reading sequentially as much as possible. Therefore I wonder...
- dragontamer 7y ago> but RAM takes the same time to access any part 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.
- Breza 7y agoThis is the most fascinating thing I've read all day. Thanks for the information!