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