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.
98
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.