Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

We are working on a moderately-sized C++ code base (10Mloc) which through our optimization efforts is becoming uniformly slow.

This code base is a set of libraries which we combine to put them to work. When the general framework of how these libraries communicate was developed there was some emphasis on performance and later on, when more parts where added, the general framework wasn't changed much. Optimization was done when needed and as our hardware evolved. This made expensive early decision apparent only much later. We are now at a point where further optimizations are much more expensive since they would require rewriting large parts of the code base. We find ourselves approaching an undesirable local minimum since we know that in principle the code should be able to run much faster.

Are there any successful methodologies which help to decide what turns to take over the evolution of a code base towards a globally optimally performing solution which aren't easily confused by easy optimization opportunities?

EDIT

To answer the question how we currently profile:

We really only have 2 different scenarios how this code can be used, both embarrassingly parallel. Profiling is done both with wall clock time averaged over a large sample of inputs and more detailed runs (instruction costs, branch mispredictions and caching issues). This works well since we run exclusively on our extremely homogeneous machines (a cluster of a couple thousand identical machines). Since we usually keep all our machines busy most of the time running faster means we can look at additional new stuff. The issue is of course that when new input variations show up, they might get a late-comer penalty since we removed most obvious micro-inefficiencies for the other use cases, thus possibly narrowing down the number of "optimally running" scenarios. The current answers rightly suggest to separate data and algorithms so this becomes easier to adjust.

share|improve this question
10  
10Mloc is actually huge project –  BЈовић Jan 23 '12 at 19:41
1  
It's 10 million loc (SI prefix) as counted by sloc. I called it "moderately sized" because I have no idea what is considered "big" here. –  Benjamin Bannier Jan 23 '12 at 19:54
4  
pretty sure 10 million is at least big everywhere and probably huge most places. –  Ryathal Jan 23 '12 at 20:52
    
First thing is how are you measuring, what profiling techniques are you using? I usually find a mix of different measurements is invaluable, only measuring one way is prone to blindness. Second thing is how are you defining "slow." Is it possible that 10M LOC are running as fast as they possibly can and it just takes that long to get something done? Have the individual libraries been optimized internally versus simulated data flows and calls? –  Patrick Hughes Jan 27 '12 at 0:23
1  
Awesome, thanks @honk For 10M LOC it sounds like you're optimizing at a very low, almost at the hardware level? Traditional OOP (AOS "array of structures") is horribly inefficient on caches, have you tried rearranging your classes to be SOA (structure of arrays) so the data points your code is working on is coherent in memory? With that many machines are you running into communications blockages or synchronization eating up time? Final question, are you dealing with high volumes of streaming data or is this mostly a problem of complex operations on your data sets? –  Patrick Hughes Jan 27 '12 at 1:12

4 Answers 4

I do not know of a general-purpose approach to this problem, but two somewhat related approaches worked well for me in the past: for lack of better terms, I called them bunching and horizontal optimization.

Bunching approach is an attempt at replacing a large number of short, fast operations with a single, slower-running, highly specialized operation that ultimately produces the same result.

Example: After profiling one particularly slow operation of our visual rule editor we discovered no "low hanging fruit": there was not a single operation that was taking more than 2% of the execution time, yet the operation as a whole felt sluggish. However, we discovered that the editor was sending a large number of small requests to the server. Even though the editor was quickly processing the individual replies, the number of request/response interactions had a multiplicative effect, so the overall time the operation took was several seconds. After carefully cataloging the interactions of the editor during that long-running operation, we added a new command to the server interface. The additional command was more specialized, as it accepted the data required to perform a subset of short operations, explored data dependencies to figure out the final set of data to return, and provided a response containing the information needed to complete all the individual small operations in a single trip to the server. This did not reduce the processing time in our code, but it cut a very significant amount of latency due to removing multiple expensive client-server round trips.

Horizontal optimization is a related technique when you eliminate the "slowness" that is thinly distributed among multiple components of your system using a particular feature of your execution environment.

Example: After profiling a long-running operation we discovered that we make a lot of calls across the application domain boundary (this is highly specific to .NET). We could not eliminate any of the calls, and we could not bunch them together: they were coming at different times from widely different sections of our system, and the things they requested were dependent on the results returned from prior requests. Each call required serialization and deserialization of a relatively small amount of data. Again, the individual calls were short in duration, but very large in number. We ended up designing a scheme that avoided serialization almost entirely, replacing it with passing a pointer across the app domain boundary. This was a big win, because many requests from entirely unrelated classes instantly became much faster as a result of applying a single horizontal solution.

share|improve this answer
    
Thanks for sharing your experience, these are useful optimizations to keep in mind. Also, since they lift problematic parts to a distinct place they will be much better to control in the future. In a sense they put into place what should have happened in the first place, now only back by hard data. –  Benjamin Bannier Jan 23 '12 at 22:18

This made expensive early decision apparent only much later. We are now at a point where further optimizations are much more expensive since they would require rewriting large parts of the code base.

When you start this rewrite you have to do several things differently.

First. And most important. Stop "optimizing". "Optimization" doesn't matter very much at all. As you've seen, only wholesale rewrite matters.

Therefore.

Second. Understand the implications of every data structure and algorithm choice.

Third. Make the actual choice of data structure and algorithm a matter of "late binding". Design interfaces which can have any one of several implementations used behind the interface.

What you're doing now (rewriting) should be much, much less painful if you've got a set of interfaces defined that allows you to make a wholesale change to data structure or algorithm.

share|improve this answer
1  
Thanks for your answer. While we still need to optimize (which falls under 1. and 2. for me) I really like the organized thinking behind 3. By making data structure, algorithm & access defined late and explicit, one should be able to get a handle on many problems we are facing. Thanks for putting it into a coherent language. –  Benjamin Bannier Jan 23 '12 at 22:15
    
You actually don't need to optimize. Once you have the correct data structure, optimization will be shown to be a waste of effort. Profiling will show where you have wrong data structure and wrong algorithm. Fooling around with the performance difference between ++ and +=1 will be irrelevant and almost unmeasurable. It's the thing you to last. –  S.Lott Jan 23 '12 at 22:56
1  
Not all bad algorithms can be found by pure reasoning. Once in a while one needs to sit down and profile. This is the only way to find out if the initial guess was right. That's the only way to estimate the real cost (BigO + const). –  Benjamin Bannier Jan 23 '12 at 23:00
    
Profiling will reveal bad algorithms. Totally correct. That's still not "optimization". That's still correction of a fundamental design flaw my making a design change. Optimization (tweaking, fine-tuning, etc.) will rarely be visible to profiling. –  S.Lott Jan 24 '12 at 0:32

A nice practical trick is to use your unit test suite as a performance test suite.

The following approach worked well in my code bases:

  1. Ensure your unit test coverage is good (you did this already, right?)
  2. Make sure your test running framework reports runtime on each individual test. This is important because you want to find where slow performance is happening.
  3. If a test is running slowly, use this as a way to dive in and target optimisation at this area. Optimising before identifying a performance issue might be considered premature, so the great thing about this approach is that you get concrete evidence of poor performance first. If needed, break the test into smaller tests that benchmark different aspects so you can identify where the root problem is.
  4. If a test runs extremely fast that's usually good, although you might then consider running the test in a loop with different parameters. This makes it into a better performance test and also increases your test coverage of the parameter space.
  5. Write a few extra test that specifically target performance, e.g. end-to-end transaction times or time to complete 1,000 rule applications. If you have specific non-functional performance requirements (e.g. <300ms response time), then make the test fail if it takes too long.

If you keep doing all this, then over time the average performance of your code base should organically improve.

It would also be possible to track historical test times and draw performance charts and spot regressions over time in average performance. I never bothered with this mainly because it's a bit tricky to ensure you are comparing like with like as you change and add new tests, but it could be an interesting exercise if performance is sufficiently important to you.

share|improve this answer
    
i like the technique - clever - howevre, this is micro optimisation and will improve to a local minimum - it won't solve architectural problems that allow you to hit global minimums –  jasonk Mar 15 '12 at 13:49
    
@jasonk - you are absolutely right. Though I would add that it can sometimes give you the evidence you need to demonstrate why a particular architectural change is justified..... –  mikera Mar 15 '12 at 15:07

The answer by @dasblinkenlight points out a very common issue, especially with large code bases (in my experience). There may be serious performance problems, but they are not localized. If you run a profiler, there are no routines taking enough time, by themselves, to draw attention. (Assuming you look at inclusive time percentage that includes callees. Don't even bother with "self time".)

In fact, in that case, the actual problem was not found by profiling, but by lucky insight.

I've got a case study, for which there's a brief PDF slide show, illustrating this issue in detail and how to handle it. The basic point is, since the code is much slower than it could be, that means (by definition) the excess time is spent doing something that could be removed.

If you were to look at some random-time samples of the program's state, you would just see it doing the removable activity, because of the percent of time it takes. It is quite possible the removable activity is not confined to one function, or even many functions. It doesn't localize that way.

It's not a "hot spot".

It's a description you make of what you see, that happens to be true a large percent of time. That makes it simple to discover, but whether it is easy to fix depends on how much re-writing it requires.

(There's a critique often made of this approach, that the number of samples is too small for statistical validity. That is answered on slide 13 of the PDF. Briefly - yes, there is high uncertainty in the "measurement" of potential savings, but 1) the expected value of that potential savings is essentially unaffected, and 2) when the potential savings $x$ is translated into speedup ratio by $1/(1-x)$, it is strongly skewed toward high (beneficial) factors.)

share|improve this answer
    
Thanks for your answer. We don't believe in statistical sampling and use instrumentation with valgrind. This gives us good estimates of both the "self" and "inclusive" cost of most stuff we do. –  Benjamin Bannier Jan 27 '12 at 22:06
    
@honk: Right. But sadly, instrumentation still carries the idea that performance problems are localized & so can be found by measuring fraction of time spent in routines, etc. You can certainly run valgrind etc., but if you want real insight into performance check out that slide show. –  Mike Dunlavey Jan 28 '12 at 0:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.