24

I'm looking for resources (ideally a book) that will help me gain an in-depth understanding of C++ performance. Here's a little more background:

I write server software with very high throughput requirements and/or low latency requirements. We write in C++; it's not really up for debate at this time. Most of my colleagues seem to have a much better understanding of C++ performance. They have better mental models, so they can tell when a certain bit of code will perform poorly at scale. I lack this understanding, and so I'm looking to improve my mental model.

I am specifically interested in:

  • Understanding cache effects, and how cache locality due to object layout affects my code's performance. This is the number one issue that seems to be brought up by other members of my team.
  • Understanding how memory allocation otherwise affects performance. Should I be using TCMalloc (or other mallocs), and how should I know? How should I tune the various allocation and deallocation parameters?
  • How do I know when the overhead from object copying will matter (and therefore should switch to pointers, for example)?
  • I'm also generally interested in "optimizations" as long as I have the knowledge as to when to use them.

Things I'm not really interested in:

  • "High Performance Computing," a term which seems indicate more math/simulation-oriented applications.
  • Discussions of C++ performance relative to other languages, since I'm stuck with C++.

As a starting point, anyone know if this book, Efficient C++, would fit the bill?

Nels Beckman
  • 20,508
  • 3
  • 24
  • 28
  • Do you understand assembler and are able to produce assembly listings? That might be too much for newbies, but I've used that to increase my understanding of what C++ does under the covers. – Jonathan Wood Sep 10 '12 at 17:21
  • Regarding "How do I know when the overhead from object copying will matter": you need to profile your app. You need a test scenario and a profiler. – piokuc Sep 10 '12 at 17:23
  • 1
    I was going to suggest the C++ Performance TR, ISO 18015, but even from the ANSI store, it costs far too much ($285). – Pete Becker Sep 10 '12 at 17:28
  • You can see 1)Inside the C++ Object Model by Stanley B. Lippman http://www.amazon.com/Inside-Object-Model-Stanley-Lippman/dp/0201834545 and 2)Code Optimization: Effective Memory Usage by Kris Kaspersky (Not exactly C++ but good discussion of cache and related things) http://www.amazon.com/Code-Optimization-Effective-Memory-Usage/dp/1931769249 – Tanmoy Bandyopadhyay Sep 10 '12 at 17:37
  • 3
    @PeteBecker - Here is a free draft: http://www.open-std.org/JTC1/SC22/WG21/docs/TR18015.pdf. This might be good enough. – emsr Sep 10 '12 at 17:40
  • 1
    Just be aware that not always theory has direct results in practice (I'm writing from my own experience). Always profile your code when you want to improve performance. Not always good advises from books in real world project will give you improvement... :( – PiotrNycz Sep 10 '12 at 18:02
  • 1
    A good place to start with cache effects is this textbook example: [Why does the order of the loops affect performance when iterating over a 2D array?](http://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra) – Mysticial Sep 10 '12 at 18:37
  • Efficient C++ would fit the bill--it's quite insightful and a quick read. – Drew Hall Sep 10 '12 at 18:54
  • The Performance TR is freely available via the WG21 site. Quick search, top hits including PDF, HTML, and some announcements at the time: http://www.bing.com/search?q=C%2B%2B+performance+TR – Herb Sutter Sep 10 '12 at 19:36
  • @DrewHall: It's also the weakest book in the _E... C++_ "series". – sbi Sep 10 '12 at 19:50
  • @sbi: It's never been clear to me that it's actually in the E... C++ series (it doesn't have the same look & feel). Nonetheless, if it is, I agree with you, but it's also the only one that directly addresses the question. – Drew Hall Sep 12 '12 at 11:00
  • @DrewHall: It's not officially in the series, but it rides on the good name. – sbi Sep 12 '12 at 12:03

4 Answers4

30

Let me split my recommendations into several sections.

C++ Optimization

As a starting point, I would highly recommend Agner Fog's Optimizing software in C++. This manual gives an excellent overview of the common C++ optimization topics.

Understanding Hardware in General

To have a good mental model of the C++ performance, you also need to understand the underlying hardware. Consider this statement:

a[7] = 5;

On the C++ language side, the line of code is boring from the performance perspective: it's just one memory write. But, on real hardware, the performance of that memory write can vary by orders of magnitude. To understand what's going on at that level, you need to learn about concepts such as caches, processor pipeline, TLB, branch prediction, and so on.

As a quick introduction to processor caches, I'd recommend my article Gallery of Processor Cache Effects. A much deeper and longer (>100 pages) discussion of caches and computer memory is What Every Programmer Should Know About Memory.

To get an overall understanding of modern computer hardware, Computer Architecture: A Quantitative Approach is the commonly recommended book. I didn't read the book myself, but instead learned by reading blogs and experimentation. However, others have apparently found the book to be very useful.

Understanding Specific Processors

At one point in your journey to improve your optimization skills, you'll find it useful to recognize specifics of different processors. As one example of many, different Intel and AMD processors have very different penalties for using unaligned SSE instructions, such as the _mm_storeu_ps C++ intrinsic.

To learn the specifics of different processors, I'd recommend The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers. In fact, I'm just going to go ahead and recommend all of the optimization manuals from Agner Fog. Also, hardware vendors provide documentation for their particular hardware.

Learning to Use Tools

Having a good mental model of C++ and hardware performance is very useful when optimizing code. But, learning to use the right tools is at least as useful. Arguably the best advice for optimization is "Measure first!". It is extremely difficult to understand the performance of even a simple block of code just by thinking about it. You'll gain a lot of information by running the code and measuring it in various ways.

These are some of the common useful measurements:

  • Timing: just run the code and measure the time
  • Sampling profilers
  • Instrumentation profilers
  • Processor counters

I won't get into recommendations for specific tools, since I am arguably getting out of scope of your original question. And, tooling is a big topic by itself: tools vary for different hardware platforms, software platforms, and by cost (some are free, some are expensive).

But, you certainly need to be aware that to optimize C++ code, you need to know and use appropriate tools.

Igor ostrovsky
  • 7,282
  • 2
  • 29
  • 28
  • I'd say learning the tools and how to measure is actually much more important, because that way you can see how your optimizations behave and learn as you go. The hardware/os/compiler stuff changes fast under your feet, but learning how to measure/profile code and apps is constantly useful. – Macke Sep 11 '12 at 07:38
  • Learning to use appropriate tools is a very worthwhile investment. You still need to understand the compiler and the hardware to be able to use the tools effectively to optimize code in practice. For example, you need to know what a "cache line" is if you want to fix a false cache line sharing issue. – Igor ostrovsky Sep 11 '12 at 17:27
  • Mostly I've found that just knowing where CPU goes, I can optimize it sufficiently (i.e. do less work, choose better data structures, etc.) .. but yeah, if you need to get your stuff working faster as is, then you need to know more about the hardware. It's just that I've found that optimization, like most things, begins at a much higher level than one expects. (Especially for beginners. I think the OP knows enough, but your answer will be read by newbies too. :) – Macke Sep 11 '12 at 17:58
11

Valgrind should be your first tool.

Valgrind has a lot of tools, but cachegrind is a great way to see whether your algorithm has good data locality. This will identify memory bottlenecks. Callgrind is another valgrind module that will help you identify processing bottlenecks.

References:

Cachegrind: http://valgrind.org/docs/manual/cg-manual.html

Callgrind: http://valgrind.org/docs/manual/cl-manual.html

guyrt
  • 927
  • 7
  • 12
1

Previous responses gave the most important thinks.

Just one warning : do some profiling (valgrind), that's where you'll get the quick win. After that, trying to get cache optimizations, looking at SSE… will require a lot more effort, for (at least at the begining) little improvement.

Also, C++ is a huge language, and the compilers does magic. Templates, inlining, and so forth allow the compiler to do great optimisations that are not possible in other languages like C. So be very carefull when thinking about using lowlevel data structures. It might result in a loss of performances (and more bugs and more headaches in memory management).

Using the STL and BOOST will probably help avoiding some mistakes.

Tristram Gräbener
  • 9,601
  • 3
  • 34
  • 50
1

To understand what's going on at that level, you need to learn about concepts such as caches, processor pipeline, TLB, branch prediction, and so on.

I would like to discuss these further in a very casual manner.

  1. Cache - Basically, if you can try to fit your work set inside of cache, your application can see enormous speed gains.
  2. Branches - Branches take a VERY long time because they require a block on a memory read. For instance, x=1 can be faster than if (needWrite) x=1; even if you end up doing unnecessary writes.
  3. branch prediction - Because of the previous, the CPU attempts to try to 'guess' what the result of a branch is using pattern matching algorithms. Making this trival to guess can give you speed gains.
  4. As far as processor pipelines, Instruction Level Parallelism, superscalars, register renaming and others - These mostly have to be optimized by the compiler, I think.
user606723
  • 4,918
  • 2
  • 27
  • 34