On Tue, Nov 16, 2021 at 12:50:40PM +1300, Lawrence D'Oliveiro wrote:
On Tue, 16 Nov 2021 12:28:01 +1300, Michael Cree wrote:
It's that 100ns for a main memory reference (i.e. a random access to memory that is not in cache) compared to the L1 (or even L2) cache reference of 0.5ns (or 7ns) that is really significant to one of the most important algorithms to modern computing, namely the discrete Fourier transform (and its variants such as the FFT and the DCT).
I suspect (but haven’t checked) that it also renders old techniques like binary search of an ordered array worthless, or at least of very limited use -- probably faster (and easier) to do a sequential search of an unordered array in many cases.
Excepting that binary search turns a sequential O(n) search into a O(log n) search, and the memory access timings don't change that fact, so for a sufficiently large array a binary search will always outperform a linear search even if access time is much worse for individual accesses in the binary search.
The way I like to put it is “memory is cheap, but accessing memory is expensive”.
It is better to consider modern "random access memory" (or RAM) is grossly misnamed. It should be called "streaming memory". It is extremely efficient to stream sequential memory locations into the CPU but it is very inefficient (100s of CPU clock cycles) to do a single random access to memory. Cheers Michael.