Galleries
Search
Powered by Squarespace

Entries in Optimization (1)

Friday
Sep192014

Implement First, Optimize Second

I've started participating on stackoverflow, mostly by trying to answer questions.  This has made we really want to write some longer articles about programming and programming practices that are generally too long and ranty to be helpful answers.  There are issues that I see brought up over and over again on SA and the advice I want to give does not answer the question because the asker is asking the wrong question.  For my first piece I am going to discuss why worrying about performance before your program is working is a bad idea.

The type of question that motivated me to write this article is some permutation of

I am planning on writing a program to do X.  It needs to be a fast as possible.  What optimizations should I use when I write my code?

You'll see lots of comments (including a few from me) saying effectively

Don't try to optimizate your code until is working and you can profile/benchmark it

or as I like to put it "implement first, optimize second".  I hope this article will explain why this is the correct approach.  There are many reasons why you should implement first and optimize second.  I will order the arguments for this approach in what I consider the most to least compelling arguments. Opinions may vary.

1. Correctness

The hardest, most resource consuming part of programming is writing correct code.  It is really easy to write code, but making sure it is correct is hard.  Now when I say correct, I mean correct in an industrial, deliver to paying customers sense of correct, not the much weaker did my TA happen to catch any bugs sense (a topic for another day...).  The best way to verify correctness is to test.  However you can't test without code to run.  Thus you should attempt to reach a point where you can test your program as soon as possible.  (For a more information on testing and coding, I suggest looking at Test Driven Development).

The fastest way to get correct code?  Write it as simple as possible.  Don't be clever.  Don't use tricks.  Just make it work.  The faster you can get it working the better, even if this means making sub-optimal decisions.  If you've got slow but reliable data structures, use those instead of writing faster ones.  Even if you know they are going to be too slow, use them.  Get your code working first.  Then write tests to verify the correctness of your program, then check to see if your program is too slow.  You may run into performance issues during testing.  That's ok.  You want examples to prove your code is too slow, before you optimize.  If you can't find any, maybe your code is just fine without the optimizations (see below).

Now is the time to start benchmarking, profiling then optimizing.  Lucky for you have good tests to make sure that the optimizations you try don't change the program's behaviour.  This means that as you try different optimizations you can verify that the program still works.  Benchmarking and profiling a program that does not work is a bad idea.  If your change doesn't work, you can always compare the optimized with the unoptimized code (you are using a source code management tool, right?) to isolate the problem.  It is much easier to debug when you know exactly what change broke the behaviour.  Nothing wastes time like debugging the wrong code.

One objection I see raised to this is that is seems like you'll end up coding twice, once the slow way and once that fast way.  Isn't it faster to just write the code once?  No, it is not.  Most programmers spend more time debugging then actually writing code.  Correctness is hard, writing code is not.  Debugging optimized code is harder that debugging simple code.  Debugging isolated changes (a particular optimization) is easier than debugging a whole program (bug could be anywhere).  You will save time by making the debugger easier.

2. 90/10 Rule

There are a million variations on the 90/10 rule, but the one I am talking about is

90% of your program's time is spent in 10% of its code

Basically only a small part of your code is probably performance critical and it may not be the part you think it is.  So how do you determine what is the important code?  Profiling.  Ideally using profiling tools to instrument your code so you can actually see which code matters.  Optimizing the 90% of your code that doesn't matter is a waste of time.  If you try to optimize while you implement, the odds are pretty good you will spend time optimizing code (and debugging that optimized code) when it does not matter.

3. Compilers are smart and do crazy shit

I was going to say that this point only applies to developers of compiled languages like C/C++, however most interpreted languages are moving towards using just in time compilers so it does still apply to you python/ruby types as well.  Compilers probably know way more about your hardware than you do.  Unless you happen to be a compiler developer, just accept this as a fact.  The compiler will make all sorts of optimizations.  You won't be able to predict what the compiler will do to your code.  Thus you really can't know if the code you think you need to optimize will be handled just fine by the compiler or not.  So wait until the code is written and the compiler has had a chance to do its magic before deciding if you need to step in.

I also suspect (although I am not a compiler developer) that compilers do better with code that is, well, simple.  It is easier for the compiler to optimize straight forward code.  Complex code with weird tricks may actually impede the compiler's ability to optimize your code.  As the compiler is probably better at optimizing your code that you are, don't second guess until you know you need to do better.

4.  Stuff changes when you start implementing

When you start implementing your program, you'll discover that your plans won't work and you'll need to do something different.  Often this means going back and changing code you've already written.  Spending time on a piece of code only to discover that you don't need it sucks.  If you've also debugged the optimized version of that code, it sucks twice as hard.  So don't spend time optimizing until you're done.

5.  The simple code may work just fine

Many programs are not performance critical.  Many programs don't need to be as fast as possible, they just need to be fast enough.  It may well be that the optimizations you are planning are totally unnecessary.  Your program might be just fine with the simple code.  A program that is fast enough with simple clear code will be much easier to maintain, especially if someone else may be maintaining it in the future.