3 ms·

The 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

The 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 ago
IIRC, 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 ago
  This is the most fascinating thing I've read all day. Thanks for the information!

zvrba 7y ago

IIRC, 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 ago
This is the most fascinating thing I've read all day. Thanks for the information!