Re:Computer Scientists’ Trivia
by andreareina on Thursday February 02, 2017 @05:48AM
(#13549596)
This is precisely the sort of thing you let the compiler worry about. Using godbolt.org I see that a constant multiplication by 30 is compiled to an `imul` in x86-64 (both clang and gcc) and `lsl`, `sub`, `lsl` in ARM64 (gcc).
> The costly operation in the example is accessing a large 2D array along the non-dense axis. For big enough arrays, that's a cache miss every time.
I half-remember hearing about memory-prefetchers smart enough to detect this kind of strided access and fill the cache accordingly.
Then it turns from a cache miss problem to a memory bandwidth problem. If you are only using a small proportion of the cache line in your calculation, then you effectively multiply the data transferred to the CPU.
This is usually not worth it on modern superscalar processors, where multiply is fast and pipelined. It's a win mostly on Arduino-class CPUs. If you need more than one operation to replace a multiply, such as an add and shift or a bit operation, the replacement is probably slower.
The costly operation in the example is accessing a large 2D array along the non-dense axis. For big enough arrays, that's a cache miss every time.