13
$\begingroup$

For applications requiring significant computational resources, high performance can be a critical factor when it comes to delivering scientific results or achieving "break-throughs" in reasonable time.

How much should time and effort should software developers invest in optimizing an application? What are the key criteria used?

$\endgroup$
  • $\begingroup$ Programs that scientists write often run for a very long time (e.g. simulations). Programmer time and computer running time might be comparable. This is very different from today's "usual" programmer work. Like in the early days of computing, it's often worth investing some effort (and programmer time) to make the simulation faster and finish more quickly, and get the job done faster. $\endgroup$ – Szabolcs Feb 15 '12 at 12:13
15
$\begingroup$

In the vast majority of cases, improvements in algorithms make a bigger difference than improvement in optimization. Algorithms are also more portable than low-level optimizations. My advice is to follow general best practices with respect to memory layout for cache reuse, avoiding excessive copies or communication, treating the file system in a sane way, and making floating point kernels have sufficient granularity for vectorization. Sometimes this is enough to reach an acceptably high fraction of "peak" (for this operation).

Always sketch a performance model for operations that you think are important (or that you discover are important by profiling). Then you can use the performance model to estimate what a highly tuned implementation could deliver. If you decide that speedup is worth it (relative to the other things you could be doing), then make the optimization.

Perhaps the hardest challenge is designing high-level, important (in the sense that a lot of code will depend on these choices) interfaces and data structures so that you can optimize later without needing to change the API. In contrast to specific optimizations and general guidelines, I don't know how to teach this except through experience. Working with performance-sensitive open source software helps. As with any API decision, it's important to understand the problem space.

$\endgroup$
  • $\begingroup$ Just recently I got a factor of 10,000 (for our biggest events) improvement in the run time of a limiting step of our analysis just be replacing a algorithm that was O(n^2) in time and space with one O(n log n) in both. Mind you it meant another dependency and some added complexity, but sometimes it's worth it... $\endgroup$ – dmckee Feb 9 '12 at 1:30
  • 1
    $\begingroup$ Speedup factors (which are relative to something) are not much worth out a clear reference to what you have compared to. If you compare to a bad implementation based on an inappropriate algorithm and then change then it would obviously not be unreasonable to expect large relative gains. $\endgroup$ – Allan P. Engsig-Karup Feb 9 '12 at 6:45
  • 1
    $\begingroup$ @Allan: It there was a factor of 10,000 to get from a single change then obviously it was an ill-chosen implementation. The previous code was hurt as much by the unnecessary space as by the time complexity: the caching performance was abysmal. But that's the point isn't it? $\endgroup$ – dmckee Feb 9 '12 at 17:31
8
$\begingroup$

How would you define "optimize"? There's an entire spectrum from the development of better algorithms or computational models down to using hand-tuned assembler.

In my opinion and experience, the low-hanging fruit is somewhere in the middle, e.g. choosing an algorithm that is best suited for the underlying computer architecture. The algorithm doesn't necessarily have to be novel and your understanding of the underlying architecture doesn't necessarily have to be very specific, e.g.

  • If you know that your architecture supports SIMD, re-structure the calculation such that your operations can be written in terms of short vectors,
  • If you know you're architecture is a multi-core computer, try to break-down your computational task into individual sub-tasks that don't interfere with each other and run them in parallel (think a DAG of your sub-tasks),
  • If your underlying architecture has a GPU, think of ways you can re-formulate your computation as a group of threads marching through the data in lock-step,
  • etc...

All of the above features, e.g. SIMD, parallelism and GPUs, can be accessed without to much low-level knowledge, but only really offer an advantage in algorithms that can readily exploit them.

$\endgroup$
4
$\begingroup$

I agree with all the answers already put forth thus far... I just want to address one more overlooked aspect of code optimization: quality expectation.

The issue of code optimization typically arises when the user tries to solve larger and larger problems and the code is insufficient to meet the user's needs/expectations. The amount of time that one should invest in code optimization depends on the demand to meet this expectation. It is certainly worth investing significant time if there is a critical need for a competitive advantage (e.g. finishing & publishing your research on a hot topic before others).

Of course, how much time should be invested depends upon how fast you need it to be, and how portable you want the code to be. Often, these two needs are in conflict with each other, and you have to decide which is more important before you begin optimization. The more portable you want it, the more you have to rely on high level design changes to the code (algorithm/data structure). The faster you want the code to perform, it must be tuned with low level optimizations specific to a particular machine (e.g. code/compiler/runtime optimizations).

$\endgroup$
4
$\begingroup$

You'll have to make the (cost) analysis of spending so many man-months (and those are always mythical :-) ) on gaining execution speed. You'll have to figure out how many times this piece of software will be used and by how many people so you can estimate the gain.

The rule of thumb, as always, is the famous 80/20 rule. At some moment it just doesn't add up any more to spend more and more time in gaining few percentages (or less) of running time. But you'll have to analyze.

And I sincerely agree with the above posters: make sure your API is well thought out so it doesn't need many changes and make sure the code is portable and maintainable (think about having to re-analyze an algorithm you wrote and nitty-gritty optimized ten years ago). And make sure that you use good programming practice and standard libraries. Chances are reasonable somebody already thought about the most efficient algorithm for your application.

To cite Donald Knuth: "premature optimization is the root of all evil". So profile your code, but not too soon.

$\endgroup$
  • $\begingroup$ Are you referring to the Pareto Principle (80/20) rule? If so, do you mean that we should focus optimization efforts on the 20% of the code that produces 80% of the slow-down? Or do you mean that if you can expect only 20% speedup, then it's just not worth optimizing? $\endgroup$ – Paul Feb 9 '12 at 15:33
  • $\begingroup$ No, I only used it as a kind of principle, not exactly 80/20. At some moment in time, you will spend so much effort on gaining only a few percentages that it's not worth the effort any more. $\endgroup$ – GertVdE Feb 9 '12 at 17:30
3
$\begingroup$

Some additional advice:

  1. Before doing any optimization of a working program, make sure you have a good set of test cases that help maintain the integrity of the code. There's no point in getting wrong results faster.
  2. If your optimization makes the code less readable, keep the original version around, at least in the form of a comment, but better as an alternative version to be selected at compile time and run time. Your optimization needs may change as your problems and your machines evolve, and the original code may be a better starting point for the optimization you will do five years from now.
  3. If your optimized version turns out to be of minimal impact, but makes the code less readable, less universal, or less stable, go back to the original version. You lose more than you gain.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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