General C++ Performance Improvement Tips

Could someone point me to an article, or write some tips right here about some C++ programming habits that are generally valid (no real drawbacks) and improves performance? I do not mean programming patterns and algorithm complexity - I need small things like how you define your functions, things to do/to avoid in loops, what to allocate on the stack, what on the heap, and so on.

It's not about making a particular software faster, also it's not about how to create a clean software design, but rather programming habits that - if you always apply them, you will make your code rather a little bit faster than a little bit slower.

A number of the tips in http://www.amazon.com/Effective-Specific-Addison-Wesley-Professional-Computing/dp/0201924889">Effective C++, http://www.amazon.com/More-Effective-Improve-Programs-Designs/dp/020163371X">More Effective C++, http://www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629">Effective STL and http://www.amazon.com/Coding-Standards-Rules-Guidelines-Practices/dp/0321113586">C++ Coding Standards are along this line.

A simple example of such a tip: use preincrement (++i) rather than postincrement (i++) when possible. This is especially important with iterators, as postincrement involves copying the iterator. You optimizer may be able to undo this, but it isn't any extra work to write preincrement instead, so why take the risk?

If I understand you correctly, you're asking about avoiding Premature Pessimization, a good complement to avoiding Premature Optimization. The #1 thing to avoid, based on my experience, is to not copy large objects whenever possible. This includes:

• pass objects by (const) reference to functions
• return objects by (const) reference whenever practical
• make sure you declare a reference variable when you need it

This last bullet requires some explanation. I can't tell you how many times I've seen this:

class Foo
{
    const BigObject & bar();
};

// ... somewhere in code ...
BigObject obj = foo.bar();  // OOPS!  This creates a copy!

The right way is:

const BigOject &obj = foo.bar();  // does not create a copy

These guidelines apply to anything larger than a smart pointer or a built-in type. Also, I highly recommend investing time learning to profile your code. A good profiling tool will help catch wasteful operations.

A few of my pet peeves:

1. Don't declare (actually, define) object variables before their use/initialization (as in C). This necessitates that the constructor AND assigment operator functions will run, and for complex objects, could be costly.
2. Prefer pre-increment to post-increment. This will only matter for iterators and user-defined types with overloaded operators.
3. Use the smallest primitive types possible. Don't use a long int to store a value in the range 0..5. This will reduce overall memory usage, improving locality and thus overall performance.
4. Use heap memory (dynamic allocation) only when necessary. Many C++ programmers use the heap by default. Dynamic allocations and deallocations are expensive.
5. Minimize the use of temporaries (particularly with string-based processing). Stroustrup presents a good technique for defining the logical equivalent of ternary and higher-order arithmetic operators in "The C++ Programming Language."
6. Know your compiler/linker options. Also know which ones cause non-standard behavior. These dramatically affect runtime performance.
7. Know the performance/functionality tradeoffs of the STL containers (e.g., don't frequently insert into a vector, use a list).
8. Don't initialize variables, objects, containers, etc., when they are going to be unconditionally assigned to.
9. Consider the order of evaluation of compound conditionals. E.g., given if (a && b), if b is more likely to be false, place it first to save the evaluation of a.

There are many other "bad habits" which I won't mention, because in practice, modern compilers/optimizers will eliminate the ill effects (for example, return value optimization vs. pass-by-reference, loop unwinding, etc.).

One of the good starting points is the Sutter's Guru of the week series, and the Exceptional C++ books that grew out of that.

The "Optimizing Software in C++" by Agner Fog is generally one of the best references for optimization techniques both simple, but definitely also more advanced. One other great advantage is that it is free to read on his website. (See link in his name for his website, and link on paper title for pdf).

Edit: Also remember that 90% (or more) of the time is spent in 10% (or less) of the code. So in general optimizing code is really about pinpointing your bottlenecks. Further more it is important and useful to know that modern compilers will do optimzation much better than most coders, especially micro optimizations such as delaying initialization of variables, etc. The compilers are often extremely good at optimizing, so spend your time writing stable, reliable and simple code.

I'd argue that it pays to focus more on the choice of algorithm than on micro optimizations, at least for the most part.

Use functors (classes with operator() implemented) instead of function pointers. The compiler has an easier job inlining the former. That's why C++'s std::sort tends to perform better (when given a functor) than C's qsort.

It seems from your question that you already know about the "premature optimization is evil" philosophy, so I won't preach about that. :)

Modern compilers are already pretty smart at micro-optimizing things for you. If you try too hard, you can often make things slower than the original straight-forward code.

For small "optimizations" you can do safely without thinking, and which doesn't affect much the readability/maintability of the code, check out the "Premature Pessimization" section of the book C++ Coding Standards by Sutter & Alexandrescu.

For more optimization techniques, check out Efficient C++ by Bulka & Mayhew. Only use when justified by profiling!

For good general C++ programming practices, check out:

• C++ Coding Standards by Sutter & Alexandrescu (must have, IMHO)
• Effective C++/STL series by Scott Meyers
• Exceptional C++ series by Herb Sutter

Off the top of my head, one good general performance practice is to pass heavyweight objects by reference, instead of by copy. For example:

// Not a good idea, a whole other temporary copy of the (potentially big) vector will be created.
int sum(std::vector<int> v)
{
   // sum all values of v
   return sum;
}

// Better, vector is passed by constant reference
int sum(const std::vector<int>& v)
{
   // v is immutable ("read-only") in this context
   // sum all values of v.
   return sum;
}

For a small object like a complex number or 2-dimensional (x, y) point, the function will likely run faster with the object passed by copy.

When it comes to fixed-size, medium-weight objects, it's not so clear if the function will run faster with a copy or a reference to the object. Only profiling will tell. I usually just pass by const reference (if the function doesn't need a local copy) and only worry about it if profiling tells me to.

Some will say that you can inline small class methods without thinking. This may give you a runtime performance boost, but it may also lengthen your compile time if there is a heavy amount of inlining. If a class method is part of a library API, it might be better not to inline it, no matter how small it is. This is because the implementation of inline functions has to be visible to other modules/classes. If you change something in that inline function/method, then other modules that reference it need to be re-compiled.

When I first started to program, I would try to micro-optimize everything (that was the electrical engineer in me). What a waste of time!

If you're into embedded systems, then things change and you can't take memory for granted. But that's another whole can of worms.

Here is a nice article on the topic: How To Go Slow

Unless youre really sure another container type is better, use ´std::vector´. Even if ´std::deque, ´std::list´, ´std::map´ etc seems like more conveniant choices, a vector outperformes them both in memory usage and element access\iteration times.

Also, prefer using a containers member algorithm (ie ´map.equal_range(...)´) instead of thier global counterparts (´std::equal_range(begin(), end()...)´)

I like this question because it is asking for some "good habits". I have found that certain things that are desirable in programming are initially a chore, but become acceptable and even easy once they become habits.

One example is always using smart pointers instead of raw pointers to control heap memory lifetime. Another, related of course, is developing the habit of always using RAII for resource acquisition and release. Another is always using exceptions for error handling. These three tend to simplify code, thereby making it smaller and so faster, as well as easier to understand.

You could also make getters and setters implicitly inline; always make full use of initializer lists in constructors; and always use the find and other related functions that are provided in the std library, instead of crafting your own loops.

Not specifically C++, but it is often worthwhile to avoid data copying. In long-running programs with a lot of memory allocation it can be worthwhile to consider memory allocation as a major part of the design, so that the memory you use comes from pools that are reused, although this is not necessarily a common enough thing to be considered worthy of forming a habit.

One more thing - do not copy code from one place to another if you need the functionality - use a function. This keeps code size small and makes it easier to optimize all the places that use this functionality.

Use the right container

Sequence containers

• Do not use vector for data of unknown size if you are going to keep adding data to it. If you are going to repeatedly call push_back(), either use reserve() or use a deque instead.
• If you are going to be adding/removing data in the middle of the container, list is probably the right choice.
• If you are going to be adding/removing data from both ends of the container, deque is probably the right choice.
• If you need to access the nth element of the container, list is probably the wrong choice.
• If you need to both access the nth element of the container and add/remove elements in the middle, benchmark all three containers.
• If you have C++0x capability and are using a list but you never move backwards through the list, you may find forward_list more to your liking. It won't be faster but it will take up less space.

Note that this advice becomes more applicable the larger the container. For smaller containers, vector may always be the right choice simply because of the lower constant factors. When in doubt, benchmark.

Associative containers

• If you do not have TR1, C++0x, or a vendor-specific unordered_foo/hash_foo, there isn't a ton of choice. Use whichever of the four containers is appropriate to your needs.
• If you do have an unordered_foo, use it instead of the ordered version if you do not care about the order of the elements and you have a good hash function for the type.

Use exceptions judiciously

• Don't use exceptions in your normal code path. Save them for when you actually have an exceptional circumstance.

Love templates

• Templates will cost you at compile time and space-wise, but the performance gains can be amazing if you have calculations that would otherwise be performed at run-time; sometimes even something so subtle as a downcast.

Avoid dynamic_cast

• dynamic_cast is sometimes the only choice for doing something, but oftentimes the use of dynamic_cast can be eliminated by improving design.
• Don't replace dynamic_cast with a typeid followed by a static_cast either.

Templates! Using templates can reduce the amount of code because you can have a class or function/method that can be reusable with many datatypes.

Consider the following:

#include <string>
using std::basic_string;

template <class T>
	void CreateString(basic_string<T> s)
	{
		//...
	}

The basic_string could be composed of char, wchar_t, unsigned char or unsigned wchar_t.

Templates could also be used for a panoply of different things such as traits, class specialization or even used to pass a int value to a class!

Avoid iterating over the same dataset multiple times as much as possible.

This page sum up all you have to know about optimization in C++ (be it while or after writing software). It's really good advice and is very lear -- and can be used as a useful reminder in optimization phase on a project.

It's a bit old so you also have to know wich optimizations are already done by your compiler (like NRVO).

Other than that, reading the Effective C++, More Effective C++, Effective STL and C++ Coding Standards that have already been cited is important too, because it explains a lot of things about what occurs in the language and in the STL, allowing you to better optimize your specific case by using a better understanding of what's happening exactly.

Here's a list I've referred to in the past - http://www.devx.com/cplus/Article/16328/0/page/1. Beyond that, Googling c++ performance tips yields quite a bit.

I took the habit to prefer writing ++i rather than i++ not that it brings any performance boost when i is an int but things are different when i is an iterator which might have a complex implementation.

Then let's say you come from the C programming language, lose your habit to declare all your variables at the beginning on the function: declare your variables when they are needed in the function flow since the function might contain early return statements before some variables that were initialized at the beginning are effectively used.

Apart from that, another resource is C++ Coding Standards: 101 Rules, Guidelines, and Best Practices by Herb Sutter (him again) and Alexei Alexandrescu.

There is also a more recent edition of Scott Meyers' Effective C++: Effective C++: 55 specific ways to improve your programs and designs.

Finally, I would like to mention Tony Albrecht's Pitfalls of Object Oriented Programming presentation: not that it contains rules of thumb you can follow blindly but it's a very interesting read.

I would suggest to read chapter II ("Performance") of "Programming Pearls" from Jon Bentley. It's not C++ specific, but those techniques can be applied in C or C++ as well. The website contains just parts from the book, I recommend to read the book.

Lots of good suggestions here already.

One of the best ways to get into good habits is to force them on yourself. For this I love PC-Lint. PC-Lint will actually enforce Scott Meyer's Effective C++ & More Effective C++ rules. Also obeying Lint rules tends to lead to easier to maintain, less error-prone, and cleaner code. Just don't go too crazy when you realize lint will often generate more output than you have source code; I once worked on a project with 150MB of source code and 1.8GB of Lint messages.

1. Avoid memory fragmentation.
2. Aligned memory.
3. SIMD instructions.
4. Lockless multithreading.
5. Use proper acceleration trees, such as kd-tree, cover tree, octree, quadtree, etc. 5a. Define these in ways that allow for the first three (ie make nodes all in one block)
6. inlining. The lowest hanging but quite delicious fruit.

The performance boosts you can get this way are astonishing. For me 1500 times for a computation heavy app. Not over brute fore, but over similar data structures written in a major software package.

I'd not bother with stuck like preincrement over post. That only gives savings in certains (unimportant) cases and most of what's mentioned is similar stuff that might scrape out an extra 1% here and there once in a while but usually isn't worth the bother.

This one will have very good Techniques for general c++ Optimization:

http://www.tantalon.com/pete/cppopt/main.htm

Use the profiler to see what part of application running slowly and then use the optimizing techniques.

I used the valgrind with callgrind tool for the profiling purpose and it will give you which lines cost how much.

valgrind --tool=callgrind

The best way to improve these skills is reading books and articles, but I can help you with some tips:

• 1- Accept Objects by reference and Primitive or Pointer Types by value but use object pointer if a function stores a reference or a pointer to the object.
• 2- Don't use MACROS to declare constants -> use static const.
• 3- Always implement a virtual destructor if your class may be subclassed.

• Avoid multiple inheritance.
• Use virtuals when they are necessary, not just for fun
• Use templated collection classes only when it's a pain not to

Why nobody mentioned it so far? Why is everyone into poor little ++i?

One of the best little things you can easily do, to not pessimize your code:

Effective C++ by Scott Meyers, Item 20:

Prefer pass-by-reference-to-const to pass-by value

Example:

// this is a better option
void some_function(const std::string &str);
// than this:
void some_function(std::string str);

In case of short std::string you might not win much, but passing big objects like that, can save you quite a lot of computing power as you avoid redundant copying. And can also save you from a bug or two if you forgot to implement your copy constructor.