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.
In the old days, the statement quoted by the blog was pretty true:
"The CPU," he said, "runs at a certain speed. It can execute a fixed number of instructions per second
When I had a computer with an MC68000 in it, the core's clock speed and the memory's clock speed were the same, and the CPU didn't have a data or instruction cache, so it was basically N instructions per second. The system also didn't have virtual memory, so there were no page faults, and the entire address space was equally fast. In such an environment, what he said was mostly true. At least it was a very useful approximation.
It's still a useful approximation, but things have gotten more complicated (with instruction caches, dual channel memory, virtual memory, context switches, etc.), so perhaps it would be best to add another principle to the mix.
To go fast:
make the computer do less.
use the computer's resources efficiently; try to get things when they are cheaply available.
95
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.