Writing high performance code

During Scott Hanselman’s podcast we briefly discussed managed code performance.  Here are a few of my thoughts about writing high performance code. In the spirit of a cheesy business book (or motivational speaker), I will give away my main points in the form of controversial-sounding statements before proceeding to flog them to death:

    • Don’t trust anyone.
    • Managed is better.

Some background: before I came to Microsoft I built solvers for both discrete and continuous optimization problems, primarily in C/C++, with a bit of Fortran thrown in.  Back in 2002 when I was on the Project Server team we were faced with the decision of whether to rebuild our scheduling engine in C++ or C#.  For the past year or so I have worked on the Solver Foundation team, which is pure C#.  We build solvers that solve a range of large-scale optimization problems, and they are “industrial grade”:  tens or hundreds of thousands of constraints are not uncommon.

Don’t trust anyone.  Rico Mariani says the first rule of performance is to measure.  Listen to Rico.  There are many reasons for this. The first is that nobody has ever written code that is doing exactly what you are trying to do.  Otherwise (being a smart programmer) you should just call their code or (being a smart business person) you should just buy their code, try to do it better, or do something different entirely (perhaps mixed martial arts).  So you should seek to understand how the code behaves, otherwise you will never find out – until it is too late.

The second is that you know your scenarios and priorities better than others do.  You should already have an idea of how fast the code is supposed to be. Now sometimes the requirement truly is “make it as fast as possible”.  For numerical libraries this is often the case because many problems can be made to be arbitrarily complicated.  For example, if you are modeling fluid dynamics you could use tighter meshes and get more accurate results.  In most other cases (perhaps in a user interface) you have a hard number you need to hit. Of course, there are some simple guidelines that may apply in most situations.  If you never go to the database, your server app will be fast. If you never allocate memory, your numeric code will fly. True or false? Well…measure.

The third is that even if someone else has measured code that seems to be similar to yours, their results may be misleading.  For example, you depend on different collection classes, or you are running on a different processor.  Or your input data is different in some subtle way.  To take a very simple example, suppose you want to sort lists of 1 million integers, and somebody says, “hey, I measured different sorting algorithms on arrays of 1 million integers and quicksort is best.”  And they hand over the code and all of their results.  Well, what do those arrays look like?  Because if the data is mostly sorted then something like insertion sort may work better.

If you follow this advice you may end up with more questions: doesn’t this take a lot of time and effort? How do I know when to stop measuring, or stop optimizing my code?  If you start profiling at the very start of development, and build some simple skills, it’s not too bad (and you learn a lot).  If, for example, you are considering whether to use managed or unmanaged code for a project, prototype a couple of key sections in C++ and C# and measure.  I did this on the Project Server team and that was the best way to settle the argument.  These things often get way too philosophical – just try it and see.  I did standard critical path scheduling in both C# and C++ and found that the C# version was only 10-15% slower.  We went with C# and in the course of development we were able to find algorithmic improvements that resulted in a faster implementation that the original C++ codebase. Get good at writing simple programs that answer one specific performance question.  For example: should I use a list or an array?  How should I read this data set?  Be a scientist and seek to answer specific questions by controlling the conditions and varying only one thing at a time.  And pick the right thing based on your knowledge of the customer scenario.

Managed or unmanaged? My blunt opinion is: unless your computation is dominated by BLAS-style computations you are better off using C# because of productivity, stability, and maintainability concerns.

Here are a couple of “pros” for C#:

  • There are clear performance differences, but in many cases when you look at the overall system performance they can be washed away due to other factors: I/O, a webservice call, DB access, etc.
  • Many programmers (myself included) are much more productive writing C# code.  This gives me more time to investigate possible algorithmic improvements, write good unit tests, etc. There are opportunity costs!
  • I think it is easier to make use of multiple cores. For example, the parallel extensions available for .Net 3.5 (and built into 4.0) are very easy to use.

There are also some clear downsides:

  • It is easy to get lazy, or to unintentionally use constructs that are not efficient.  People start using List<> and Dictionary<> when a good ol’ array will do.  It’s also easy to miss unnecessary memory allocations, because everything is garbage collected.  So you need to be vigilant about profiling the code.
  • There is a lot of unnecessary array bounds checking that slows things down.  In particular, with LAPACK-style routines with tight, nested loops.
  • As far as I know, the managed code compilers do not make use of SSE2 instructions.

Others have different opinions and I’m not saying they’re wrong – so long as they have measured.  Otherwise they are bullshitting you.

Author: natebrix

Follow me on twitter at @natebrix.

2 thoughts on “Writing high performance code”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s