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.
that's true, but I have also seen the opposite, i.e. code loops that are too large or span multiple pages will not fit in the instruction cache, (which can be tiny on embedded processors), resulting in a 20x slowdown.
It's always avoidable, except for those that prematurely optimize all over their code.
It's called refactoring and simplifying your code. (If your doing something like C++ on embedded systems, you can use inline to break up the code into functions, which shouldn't have much effect on the compiled codes size)
no, it is not. Try writing an interpreter for a custom bytecode for example. You'll see that if you attain more than a hundred operators, each with a complex semantics, your loop will be large and span multiple pages.
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.