How much should scientific software be optimized?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.