Approaches against code base becoming uniformly slow

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.)