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. Also garbage-collected languages like Java are likely to be impacted. The way I like to put it is “memory is cheap, but accessing memory is expensive”. The first part has been true since about the 1980s, but the ever-greater emphasis on caches for performance on current architectures, particularly in this century, has brought the second part into sharper relief.