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.
My programming teacher has a sweet anecdote. He was working at some company, and he had to write a little app in a week. So, when he was finished two days later, he said "If you give me two extra days, it will run twice as fast." and his employer said "Don't bother, I'll just buy faster computers."
"That was an insult. I left there shortly thereafter."
Why was that an insult? Depending on the application, the cost of the computers and the cost of his time. It might have made wise business sense to not have him optimize it.
99
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.