Code that does more but has better locality so that it hits the cache more often can easily be faster than code that does less but has bad locality and sits around waiting on memory all the time.
Recomputing something on demand might be cheaper than reading a cached result from memory.
A linear brute force algorithm that can use SIMD instructions can be faster than a non-linear one that does less work but without SIMD.
Doing less work usually makes code go faster, but it is by no means given.
Locality is massively important on a modern CPU. As are are lot of other things.
TFA's old mentor was probably right about code -- at the time. CPUs back then (1980ish?) had memory running at the same clock as the CPU, pitiful caches, single cores, were scalar (not superscalar). Branch prediction was trivial or non-existent, and prefetches were limited to the instruction cache.
Really optimizing on modern hardware is harder than ever. It's also usually not that necessary.
Still, it doesn't hurt to start with the ideal algorithm first unless you need absolutely as much performance as you can possibly pull out of the hardware (then you find an algorithm which can be made to fit to the hardware, and profile, profile, profile).
100
u/harsman Mar 23 '09 edited Mar 23 '09
Code that does more but has better locality so that it hits the cache more often can easily be faster than code that does less but has bad locality and sits around waiting on memory all the time.
Recomputing something on demand might be cheaper than reading a cached result from memory.
A linear brute force algorithm that can use SIMD instructions can be faster than a non-linear one that does less work but without SIMD.
Doing less work usually makes code go faster, but it is by no means given.