Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I work in computational science, and as a result, I spend a non-trivial amount of my time trying to increase the scientific throughput of many codes, as well as understanding the efficiency of these codes.

Let's assume I have evaluated the performance vs. readability/reusability/maintainability tradeoff of the software I am working on, and I have decided that it's time to go for performance. Let's also assume that I know I don't have a better algorithm for my problem (in terms of flop/s and memory bandwidth). You can also assume my code base is in a low-level language like C, C++, or Fortran. Finally, let's assume that there is no parallelism to be had in the code, or that we're only interested in performance on a single core.

What are the most important things to try first? How do I know how much performance I can get?

share|improve this question
add comment

8 Answers

up vote 35 down vote accepted

First of all, as skillman and Dan have pointed out, profiling is essential. I personally use Intel's VTune Amplifier on Linux as it gives me a very fine-grained overview of where time was spent doing what.

If you're not going to change the algorithm (i.e. if there will be no major changes that will turn all your optimizations obsolete), then I'd suggest looking for some common implementation details that can make a big difference:

  • Memory locality: is data that is read/used together also stored together, or are you picking up bits and pieces here and there?

  • Memory alignment: are your doubles actually aligned to 4 bytes? How did you pack your structs? To be pedantic, use posix_memalign instead of malloc.

  • Cache efficiency: Locality takes care of most cache efficiency issues, but if you have some small data structures that you read/write often, it helps if they are an integer multiple or fraction of a cache line (usually 64 bytes). It also helps if your data is aligned to the size of a cache line. This can drastically reduce the number of reads necessary to load a piece of data.

  • Vectorization: No, don't go mental with hand-coded assembler. gcc offers vector types that get translated to SSE/AltiVec/whatever instructions automagically.

  • Instruction-Level Parallelism: The bastard son of vectorization. If some often-repeated computation does not vectorize well, you can try accumulating input values and computing several values at once. It's kind of like loop unrolling. What you're exploiting here is that your CPU will usually have more than one floating-point unit per core.

  • Arithmetic precision: Do you really need double-precision arithmetic in everything you do? E.g. if you're computing a correction in a Newton iteration, you usually don't need all the digits you're computing. For a more in-depth discussion, see this paper.

Some of these tricks are used in the daxpy_cvec this thread. Having said that, if you're using Fortran (not a low-level language in my books), you will have very little control over most of these "tricks".

If you're running on some dedicated hardware, e.g. a cluster you use for all your production runs, you may also want to read-up on the specifics of the CPUs used. Not that you should write stuff in assembler directly for that architecture, but it might inspire you to find some other optimizations that you may have missed. Knowing about a feature is a necessary first step to writing code that can exploit it.

Update

It's been a while since I wrote this and I hadn't noticed that it had become such a popular answer. For this reason, I'd like to add one important point:

  • Talk to your local Computer Scientist: Wouldn't it be cool if there were a discipline which dealt exclusively with making algorithms and/or computations more efficient/elegant/parallel, and we could all go ask them for advice? Well, good news, that discipline exists: Computer Science. Chances are, your institution even has a whole department dedicated to it. Talk to these guys.

I'm sure to a number of non-Computer Scientists this will bring back memories of frustrating discussions with said discipline that led to nothing, or memories of other people's anecdotes thereof. Don't be discouraged. Interdisciplinary collaboration is a tricky thing, and it takes a bit of work, but the rewards can be massive.

In my experience, as a Computer Scientist (CS), the trick is in getting both the expectations and the communication right.

Expectation-wise, a CS will only help you if he/she thinks your problem is interesting. This pretty much excludes trying to optimize/vectorize/parallelize a piece of code you've written, but not really commented, for a problem they don't understand. CSs are usually more interested in the underlying problem, e.g. the algorithms used to solve it. Don't give them your solution, give them your problem.

Also, be prepared for the CS to say "this problem has already been solved", and just give you a reference to a paper. A word of advice: Read that paper and, if it really does apply to your problem, implement whatever algorithm it suggests. This is not a CS being smug, it's a CS that just helped you. Don't be offended, remember: If the problem is not computationally interesting, i.e. it has already been solved and the solution shown to be optimal, they won't work on it, much less code it up for you.

Communication-wise, remember that most CSs are not experts in your field, and explain the problem in terms of what you are doing, as opposed to how and why. We usually really don't care about the why, and the how is, well, what we do best.

For example, I'm currently working with a bunch of Computational Cosmologists on writing a better version of their simulation code, based on SPH and Multipoles. It took about three meetings to stop talking in terms of dark matter and galaxy haloes (huh?) and to drill down to the core of the computation, i.e. that they need to find all the neighbours within a given radius of each particle, compute some quantity over them, and then run over all said neighbours again and apply that quantity in some other computation. Then move the particles, or at least some of them, and do it all again. You see, while the former may be incredibly interesting (it is!), the latter is what I need to understand to start thinking about algorithms.

But I'm diverging from the main point: If you're really interested in making your computation fast, and you're not a Computer Scientist yourself, go talk to one.

share|improve this answer
3  
as profiling tools go, I wouldn't forget about valgrind. –  GertVdE May 11 '12 at 12:37
    
I'm agreeing with you Pedro, when the program being optimized is like a F1 race car, close to optimal already. The programs I see in practice, scientific and not, often are more like Cadillac Coupe DeVilles. To get real performance, tons of fat can be cut away. After that, the cycle-shaving starts to hit its stride. –  Mike Dunlavey Oct 5 '12 at 2:14
    
@MikeDunlavey: Completely agree. I've added an update to my answer to address more algorithmically related issues. –  Pedro Oct 8 '12 at 12:55
    
@Pedro: I wish I shared your faith in CS folks. The ones in academia are still selling gprof :) –  Mike Dunlavey Oct 8 '12 at 14:46
    
@MikeDunlavey, I am CS folk :) –  Pedro Oct 8 '12 at 15:06
show 3 more comments

Scientific software is not that much different from other software, as far as how to know what needs tuning.

The method I use is random pausing. Here are some of the speedups it has found for me:

If a large fraction of time is spent in functions like log and exp, I can see what the arguments to those functions are, as a function of the points they are being called from. Often they are being called repeatedly with the same argument. If so, memoizing produces a massive speedup factor.

If I'm using BLAS or LAPACK functions, I may find that a large fraction of time is spent in routines to copy arrays, multiply matrices, choleski transform, etc.

  • The routine to copy arrays is not there for speed, it is there for convenience. You may find there is a less convenient, but faster, way to do it.

  • Routines to multiply or invert matrices, or take choleski transforms, tend to have character arguments specifying options, such as 'U' or 'L' for upper or lower triangle. Again, those are there for convenience. What I found was, since my matrices were not very big, the routines were spending more than half their time calling the subroutine for comparing characters just to decipher the options. Writing special-purpose versions of the most costly math routines produced massive speedup.

If I can just expand on the latter: matrix-multiply routine DGEMM calls LSAME to decode its character arguments. Looking at inclusive percent time (the only statistic worth looking at) profilers regarded as "good" could show DGEMM using some percent of total time, like 80%, and LSAME using some percent of total time, like 50%. Looking at the former, you would be tempted to say "well it must be heavily optimized, so not much I can do about that". Looking at the latter, you would be tempted to say "Huh? What's that all about? That's just a teeny little routine. This profiler must be wrong!"

It's not wrong, it's just not telling you what you need to know. What random pausing shows you is that DGEMM is on 80% of stack samples, and LSAME is on 50%. (You don't need a lot of samples to detect that. 10 is usually plenty.) What's more, on many of those samples, DGEMM is in the process of calling LSAME from a couple different lines of code.

So now you know why both routines are taking so much inclusive time. You also know where in your code they are being called from to spend all this time. That's why I use random pausing and take a jaundiced view of profilers, no matter how well-made they are. They're more interested in getting measurements than in telling you what's going on.

It's easy to assume the math library routines have been optimized to the nth degree, but in fact they have been optimized to be usable for a wide range of purposes. You need to see what's really going on, not what is easy to assume.

ADDED: So to answer your last two questions:

What are the most important things to try first?

Take 10-20 stack samples, and don't just summarize them, understand what each one is telling you. Do this first, last, and in-between. (There is no "try", young Skywalker.)

How do I know how much performance I can get?

The stack samples will give you a very rough estimate of what fraction $x$ of time will be saved. (It follows a $\beta(s+1,(n-s)+1)$ distribution, where $s$ is the number of samples that displayed what you are going to fix, and $n$ is the total number of samples. That doesn't count the cost of the code that you used to replace it, which will hopefully be small.) Then the speedup ratio is $1/(1-x)$ which can be large. Notice how this behaves mathematically. If $n=10$, and $s=5$, the mean and mode of $x$ is 0.5, for a speedup ratio of 2. Here's the distribution:
enter image description here
If you are risk-averse then, yes, there is a small probability (.03%) that $x$ is less than 0.1, for a speedup of less than 11%. But balancing that is an equal probability that $x$ is greater than 0.9, for a speedup ratio of greater than 10! If you're getting money in proportion to program speed, that's not bad odds.

As I've pointed out to you before, you can repeat the whole procedure until you can't any more, and the compounded speedup ratio can be quite large.

ADDED: In response to Pedro's concern about false positives, let me try to construct an example where they might be expected to occur. We never act on a potential problem unless we see it two or more times, so we would expect false positives to occur when we see a problem the fewest possible times, especially when the total number of samples is large. Suppose we take 20 samples and see it twice. That estimates its cost is 10% of total execution time, the mode of its distribution. (The mean of the distribution is higher - it is $(s+1)/(n+2)=3/22=13.6\%$.) The lower curve in the following graph is its distribution:

enter image description here

Consider if we took as many as 40 samples (more than I ever have at one time) and only saw a problem on two of them. The estimated cost (mode) of that problem is 5%, as shown on the taller curve.

What is a "false positive"? It is that if you fix a problem you realize such a smaller gain than expected, that you regret having fixed it. The curves show (if the problem is "small") that, while the gain could be less than the fraction of samples showing it, on average it will be larger.

There is a far more serious risk - a "false negative". That is when there is a problem, but it is not found. (Contributing to this is "confirmation bias", where absence of evidence tends to be treated as evidence of absence.)

What you get with a profiler (a good one) is you get much more precise measurement (thus less chance of false positives), at the expense of much less precise information about what the problem actually is (thus less chance of finding it and getting any gain). That limits the overall speedup that can be achieved.

I would encourage users of profilers to report the speedup factors they actually get in practice.


There's another point to be made re. Pedro's question about false positives.

He mentioned there could be a difficulty when getting down to small problems in highly optimized code. (To me, a small problem is one that accounts for 5% or less of total time.)

Since it is entirely possible to construct a program that is totally optimal except for 5%, this point can only be addressed empirically, as in this answer. To generalize from empirical experience, it goes like this:

A program, as written, typically contains several opportunities for optimization. (We can call them "problems" but they are often perfectly good code, simply capable of considerable improvement.) This diagram illustrates an artificial program taking some length of time (100s, say), and it contains problems A, B, C, ... that, when found and fixed, save 30%, 21%, etc. of the original 100s.

enter image description here

Notice that problem F costs 5% of the original time, so it is "small", and difficult to find without 40 or more samples.

However, the first 10 samples easily find problem A.** When that is fixed, the program takes only 70s, for a speedup of 100/70 = 1.43x. That not only makes the program faster, it magnifies, by that ratio, the percentages taken by the remaining problems. For example, problem B originally took 21s which was 21% of the total, but after removing A, B takes 21s out of 70s, or 30%, so it is easier to find when the entire process is repeated.

Once the process is repeated five times, now the execution time is 16.8s, out of which problem F is 30%, not 5%, so 10 samples find it easily.

So that's the point. Empirically, programs contain a series of problems having a distribution of sizes, and any problem found and fixed makes it easier to find the remaining ones. In order to accomplish this, none of the problems can be skipped because, if they are, they sit there taking time, limiting the total speedup, and failing to magnify the remaining problems.

If problems A through F are found and fixed, the speedup is 100/11.8 = 8.5x. If one of them is missed, for example D, then the speedup is only 100/(11.8+10.3) = 4.5x. That's the price paid for false negatives.

So, when the profiler says "there doesn't seem to be any significant problem here", maybe it's right, and maybe it's not. (A false negative.) You don't know for sure if there are more problems to fix, for higher speedup, unless you try another profiling method and discover that there are. In my experience, the profiling method does not need a large number of samples, summarized, but a small number of samples, where each sample is understood thoroughly enough to recognize any opportunity for optimization.

** It takes a minimum of 2 hits on a problem to find it, unless one has prior knowledge that there is a (near) infinite loop. (The red tick marks represent 10 random samples); The average number of samples needed to get 2 or more hits, when the problem is 30%, is $2/0.3=6.67$ (negative binomial distribution). 10 samples find it with 85% probability, 20 samples - 99.2% (binomial distribution). To get the probability of finding the problem, in R, evaluate 1 - pbinom(1, numberOfSamples, sizeOfProblem), for example: 1 - pbinom(1, 20, 0.3) = 0.9923627.

ADDED: The fraction of time saved, $x$, follows a Beta distribution $\beta(s+1,(n-s)+1)$, where $n$ is the number of samples, and $s$ is the number that display the problem. However, the speedup ratio $y$ equals $1/(1-x)$ (assuming all of $x$ is saved), and it would be interesting to understand the distribution of $y$. It turns out $y-1$ follows a BetaPrime distribution. I simulated it with 2 million samples, arriving at this behavior:

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

The first two columns give the 90% confidence interval for the speedup ratio. The mean speedup ratio equals $(n+1)/(n-s)$ except for the case where $s=n$. In that case it is undefined and, indeed, as I increase the number of simulated $y$ values, the empirical mean increases.

This is a plot of the distribution of the speedup factors, and their means, for 2 hits out of 5, 4, 3, and 2 samples. For example, if 3 samples are taken, and 2 of them are hits on a problem, and that problem can be removed, the average speedup factor would be 4x. If the 2 hits are seen in only 2 samples, the average speedup is undefined - conceptually because programs with infinite loops exist with non-zero probability!

enter image description here

share|improve this answer
    
Uhm... Don't you get exactly this information looking at profiler call graphs or "bottom-up" type summaries as provided by VTune? –  Pedro Jul 9 '12 at 13:40
    
@Pedro: If Only. In a stack sample (& related variables) is encoded the entire reason that increment of time is being spent. You can't get rid of it unless you know why it's being spent. Some problems can be found with limited information, but not every one. If you only get some of them, but not every one, then the problems you don't get end up blocking you from further speedups. Check here and here. –  Mike Dunlavey Jul 9 '12 at 14:18
    
Arguably, you're comparing your method to bad profiling... You could also go through the profile for each routine, independent of its contribution to the total execution time, and look for improvements, with the same effect. What I'm worried about in your approach is the increasing number of false positives you'll end up tracking down as the "hotspots" in your code get smaller and smaller. –  Pedro Jul 9 '12 at 14:27
    
@Pedro: Just keep taking samples until you see something you can fix on more than one sample. The beta distr tells how much it can save, if you care, but if you're afraid of getting less speedup than it shows, be aware that you're throwing away the chance that it could also be more (and it's right-skewed). The larger danger, with summarizing profilers, is false negatives. There can be a problem, but you're just hoping your intuition will sniff it out when the profiler is being very un-specific about where it could be. –  Mike Dunlavey Jul 9 '12 at 14:37
    
@Pedro: The only weakness I know of is when, looking at a snapshot it time, you can't figure out why that time is being spent, such as if it's simply processing asynchronous events where the requester is hiding, or asynchronous protocols. For more "normal" code, show me a "good" profiler and I'll show you a problem it has trouble with or simply cannot find (making you fall back on your fallible smarts). Generally the way to construct such a problem is to make sure that the purpose being served cannot be deciphered locally. And such problems abound in software. –  Mike Dunlavey Jul 9 '12 at 14:54
show 7 more comments

Not only do you have to have intimate knowledge of your compiler, you also have intimate knowledge of your target architecture.

If you want to squeeze every last ounce of performance, then every time you change your target architecture, you will have to tweak and re-optimise your code. Something which was an optimisation with one CPU may become sub-optimal in the very next revision of that same CPU.

An excellent example of this would be CPU cache's. Move your program from a CPU with a fast small cache to one with a slightly slower, slightly larger cache and your profiling could change significantly.

This is why, when you are developing highly optimised code, you need to keep it modular and make it easy to swap different versions of the same algorithm in and out, possibly even selecting the specific version used at run time, depending on the resources available and the size/complexity of data to be processed.

Modularity also means being able to use the same test suite on all of your optimised and unoptimised versions, allowing you to verify that they all behave the same and profile each one quickly in a like-for-like comparison. I go into a little more detail in my answer to How to document and teach others “optimized beyond recognition” computationally intensive code?.

In addition, I would highly recommend taking a look at Ulrich Drepper's excellent paper What Every Programmer Should Know About Memory, whose title is an homage to David Goldberg’s equally fantastic What Every Computer Scientist Should Know About Floating-Point Arithmetic.

Remember every optimisation has the potential to become a future anti-optimisation, so should be considered a possible code smell, to be kept to a minimum. My answer to Is micro-optimisation important when coding? provides a concrete example of this from personal experience.

share|improve this answer
add comment

I think you phrase the question too narrowly. In my view, a useful attitude is to live under the assumption that only changes to the data structures and algorithms can yield significant performance gains on codes that are more than a few 100 lines, and I believe that I have yet to find a counterexample to this claim.

share|improve this answer
2  
Agreed in principle, but one should not underestimate the interplay between the performance of an algorithm/data-structure and the details of the underlying hardware. E.g. balanced binary trees are great for searching/storing data, but depending on the latency of the global memory, a hash-table may be better. –  Pedro May 17 '12 at 10:03
1  
Agreed. Algorithms and data structure can provide O(10) to O(100) improvements. However, for a few compute bounded problems (as in molecular dynamics calculations, astrophysics, real-time image and video processing, finance) a highly tuned critical loop can mean a 3x to 10x faster overall application runtime. –  fcruz May 17 '12 at 10:44
    
I've seen badly ordered nested loops in "production" codes of substantial size. Other than that I think you're right. –  dmckee Jul 6 '12 at 20:46
add comment

The very first thing you should do is profile your code. You want to find out which parts of your program are slowing you down before you begin to optimize, otherwise you could end up optimizing a part of your code that wasn't eating up much of the execution time anyway.

Linux

gprof is pretty good, but it only tells you how much time is taken by each function rather than each line.

Apple OS X

You might want to try out Shark. It is available in Apple Developer site under Downloads > Developer Tools > CHUD 4.6.2, the older version here. CHUD also contains other profiling tools such as BigTop frontend, PMC Index search tool, Saturn function-level profiler and a lot of other commands. Shark will come with a commandline version.

share|improve this answer
    
+1 Profile? Yes, in a way... It's far better than guessing, but here is a list of issues that apply especially to gprof, and to many other profilers. –  Mike Dunlavey Jul 12 '12 at 16:44
    
Is Shark an old command in OS X? More here. With Mountain Lion, should I use Instruments? –  hhh May 21 '13 at 0:17
    
@hhh: It was a GUI profiler for macs, though it looks like it isn't being maintained anymore. I haven't programmed on an apple machine since I wrote this answer, so I can't help you much. –  Dan May 21 '13 at 0:21
1  
It is available in Apple Developer site under Downloads > Developer Tools > CHUD 4.6.2. The older version here and it contains all kind of profiling things -- unfortunately this installation is not succeeding: "Contact the manufacturer", no idea about the bug. Shark was taken out of the Xcode apparently after Lion and later put back to Apple Dev site after being free tool in MacUpdate. –  hhh May 21 '13 at 0:46
    
@hhh: You seem more qualified to answer this than I am. Feel free to edit my answer to update it, or write your own. –  Dan May 21 '13 at 3:03
show 1 more comment

As for how much performance you can get, take the results from the profiling of your code and let's say you identify a piece that takes "p" fraction of the time. If you were to improve the performance of that piece only by a factor of "s", your overall speedup will be 1/((1-p) + p/s). Therefore you can maximally increase your speed by a factor of 1/(1-p). Hopefully you have areas of high p! This is the equivalent of Amdahl's Law for serial optimization.

share|improve this answer
add comment

I am not a computational scientist as many others here (so I could be wrong :)) but these days there is little point in spending too much time on serial performance as long as we use standard libs. It might be more worthwhile to spend any additional time/effort on making the code more scalable.

In any case here are two examples (if you havent already read them) on how performance was improved (for unstructured FE problems).

Serial: See 2nd half of abstract and related text.

Parallel: Specially the initialization phase, in sec 4.2.

share|improve this answer
add comment

This is perhaps more of a meta-answer than an answer ...

You must develop an intimate familiarity with your compiler. You can most efficiently acquire this by reading the manual and experimenting with the options.

Much of the good advice that @Pedro dispenses can be implemented by adjusting the compilation rather than the program.

share|improve this answer
    
I disagree with the last point. Knowing what your compiler can do is one thing, but writing your code so that your compiler can actually do something with it is a whole different problem. There are no compiler flags that will sort your data for you, use lower precision when required or re-write your innermost loops such that they have few or no branches. Knowing your compiler is a good thing, but it will only help you write better code, it won't make your code better per se. –  Pedro May 11 '12 at 12:47
add comment

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.