Skip to main content
Software Engineering

Return to Answer

added 950 characters in body
Source Link
Damon
Damon
  • 253
  • 1
  • 3

To put the previous paragraph into perspective, consider what the different things that you can do cost you. Executing something like a+b takes (if not optimized out) one or two cycles, but the CPU can usually start several instructions per cycle, and can pipeline non-dependent instructions so more realistically it only costs you something around half a cycle or less. Ideally, if the compiler is good at scheduling, and depending on the situation, it might cost zero.
Fetching data ("memory") costs you either 4-5 cycles if you're lucky and it's in L1, and around 15 cycles if you are not so lucky (L2 hit). If the data isn't in the cache at all, it takes several hundred cycles. If your haphazard access pattern exceeds the TLB's capabilities (easy to do with only ~50 entries), add another few hundred cycles. If your haphazard access pattern actually causes a page fault, it costs you a few ten thousand cycles in the best case, and several million in the worst.
Now think about it, what's the thing you want to avoid most urgently?

To put the previous paragraph into perspective, consider what the different things that you can do cost you. Executing something like a+b takes (if not optimized out) one or two cycles, but the CPU can usually start several instructions per cycle, and can pipeline non-dependent instructions so more realistically it only costs you something around half a cycle or less. Ideally, if the compiler is good at scheduling, and depending on the situation, it might cost zero.
Fetching data ("memory") costs you either 4-5 cycles if you're lucky and it's in L1, and around 15 cycles if you are not so lucky (L2 hit). If the data isn't in the cache at all, it takes several hundred cycles. If your haphazard access pattern exceeds the TLB's capabilities (easy to do with only ~50 entries), add another few hundred cycles. If your haphazard access pattern actually causes a page fault, it costs you a few ten thousand cycles in the best case, and several million in the worst.
Now think about it, what's the thing you want to avoid most urgently?

Source Link
Damon
Damon
  • 253
  • 1
  • 3

Your question should have been: "Do I need to optimize this at all?".

Version A and B differ in one important detail that makes A preferrable, but it is unrelated to optimization: You do not repeat code.

The actual "optimization" is called common subexpression elimination, which is what pretty much every compiler does. Some do this basic optimization even when optimizations are turned off. So that isn't truly an optimization (the generated code will almost certainly be exactly the same in every case).

But if it isn't an optimization, then why is it preferrable? Alright, you don't repeat code, who cares!

Well first of all, you do not have the risk of accidentially getting half of the conditional clause wrong. But more importantly, someone reading this code can grok immediately what you're trying to do, instead of a if((((wtf||is||this||longexpression)))) experience. What the reader gets to see is if(one || theother), which is a good thing. Not rarely, I happens that you are that other person reading your own code three years later and thinking "WTF does this mean?". In that case it's always helpful if your code immediately communicates what the intent was. With a common subexpression being named properly, that's the case.
Also, if at any time in the future, you decide that e.g. you need to change a+b to a-b, you have to change one location, not two. And there's no risk of (again) getting the second one wrong by accident.

About your actual question, what you should optimize for, first of all your code should be correct. This is the absolutely most important thing. Code that isn't correct is bad code, even moreso if despite being incorrect it "works fine", or at least it looks like it works fine. After that, code should be readable (readable by someone unfamiliar with it).
As for optimizing... one certainly shouldn't deliberately write anti-optimized code, and certainly I'm not saying you shouldn't spend a thought on the design before you start out (such as choosing the right algorithm for the problem, not the least efficient one).

But for most applications, most of the time, the performance that you get after running correct, readable code using a reasonable algorithm through an optimizing compiler is just fine, there's no real need to worry.

If that isn't the case, i.e. if the application's performance indeed doesn't meet the requirements, and only then, you should worry about doing such local optimizations as the one you attempted. Preferrably, though, you would reconsider the top-level algorithm. If you call a function 500 times instead of 50,000 times because of a better algorithm, this has larger impact than saving three clock cycles on a micro-optimization. If you don't stall for several hundred cycles on a random memory access all the time, this has a larger impact than doing a few cheap calculations extra, etc etc.

Optimization is a difficult matter (you can write entire books about that and get to no end), and spending time on blindly optimizting some particular spot (without even knowing whether that's the bottleneck at all!) is usually wasted time. Without profiling, optimization is very hard to get right.

But as a rule of thumb, when you're flying blind and just need/want to do something, or as a general default strategy, I would suggest to optimize for "memory".
Optimizing for "memory" (in particular spatial locality and access patterns) usually yields a benefit because unlike once upon a time when everything was "kinda the same", nowadays accessing RAM is among the most expensive things (short of reading from disk!) that you can in principle do. Whereas ALU, on the other hand, is cheap and getting faster every week. Memory bandwidth and latency doesn't improve nearly as fast. Good locality and good access patterns can easily make a 5x difference (20x in extreme, contrieved examples) in runtime compared to bad access patterns in data-heavy applications. Be nice to your caches, and you will be a happy person.