Friday, September 23, 2016

C++ Optimization Bibliography

I wrote a wonderful book on performance tuning in C++. Plug, plug, plug. Buy it now!

The web is full of free optimization advice. The best of these references support their findings with timing benchmarks. Intermediate in quality are references that speak to the behavior of specific processors, but don't contain timing data to allow the reader to reason about the size of the performance speedup. Least interesting are simple lists of recommendations presented without evidence. These are a few frequently-cited references I found useful.

Most people think of code tweaks when they write about optimization. The performance improvement from statement-level optimization is unlikely to make much difference unless it is magnified by being frequently executed, in a loop or frequently called function, so these tweaks are of uncertain value.

Free Resources on the Web 

Here is a free taste of the optimization drug, to whet your appetite and make you want to read my book, or to get you over those two days of the shakes while Amazon delivers your paper copy.

Short Notes

Tips for Optimizing C/C++ Code (PDF)
This short note contains two dozen short thought-mantras about optimizing code. Explanations are necessarily brief. It can serve as an, "I didn't know that!" kind of checklist.

Optimizing C and C++ Code (HTML)
Two dozen short thought-mantras on code optimization from game developers.

Optimization in C and C++: good practices, pitfalls, by Sébastien Binet (PDF)
Optimization advice on PowerPoint slides. Covers a lot of ground, focuses on linked structures, great graphics.

Programming Optimization (HTML), by Paul Hsieh
An interesting mix of general advice, plus brief specific low-level advice for optimizing statements and expressions.

Performance Optimization (HTML)
This is chapter 25 of the book Object Oriented System Design. It is notable for providing language-independent descriptions of design-time optimization techniques. It uses a dense and somewhat obsolete jargon defined elsewhere in the book, that can be a little hard to read. 

Three Optimization Tips for C++, Andrei Alexandrescu (HTML)
Anything Alexandrescu says is worth reading. This is more of a case study than a general advice piece, and contains many more than three tips. It features reduction in strength, reduction in array writing, and memoization.

This link has commentary and more measurements on the counting digits example Alexandrescu uses in his article.

Efficient C/C++ Coding Techniques, by Darren G. Moss (PDF)
This is a performance analysis of how several compilers available in 2001 generate code for common flow-of-control constructs, loops that index tables, and methods of structure composition. The findings are unsurprising; that switch is often better than if-elseif-else, that pointers are efficient in loops, and that a class with virtual multiple inheritance is expensive (if that wasn't obvious).

Writing Efficient C and C Code Optimization, Koushik Ghosh (HTML)
A grab-bag of statement- and expression-level optimization techniques, provided without supporting evidence for its effectiveness. Compilers may do some of these optimizations.

Techniques for Scientific C++, by Todd Veldhuizen (PDF)
A somewhat older, but interesting article with a grab-bag of optimization advice. Covers optimizing compile time, eliminating virtual functions, how aliasing interferes with optimization, expression templates,

C++ Optimization Strategies and Techniques (HTML) by Pete Isensee
Isensee really knows his stuff. This web page represents the state of the art in optimization circa 1999 (as he notes himself). It is slightly dated now, but still very relevant. The advice is well supported with timing measurements and examples.

Faster C++ (HTML)
Another grab-bag of statement-level optimizations, plus discussion of profiling, compiler flags, and cache issues. Good bibliography at the end.

FastC++: Coding Cpp Efficiently blog (HTML)
I haven't explored this blog extensively, but he seems to know a lot about getting the C++ compiler to use SSE extensions.

The Top 10 Myths of Video Game Optimization, Eric Preisz (HTML)
Interesting viewpoint on several well-loved optimizations. Of particular interest to me, that LUT-based algorithms may be a lose if they have reduced cache performance, since a cache miss is slower than the slowest instruction. The moral would be that small LUTs are good, but big ones can be problematical.

Mentor low Latency C or C++ code (HTML)
This is an article on verifying that programs meet their latency goals, not on optimizing C++ per se, But it has a bunch of good rules about memory allocation, and a couple of other optimization topics, covered without supporting evidence.
Performance of a Circular Buffer vs. Vector, Deque, and List (HTML)
This article reviews the performance measurements from chapter 10 of my book Optimized C++, plus a new type of container, the circular buffer, that is a candidate for inclusion in C++20.

Longer Works

Technical Report on C++ Performance ISO/IEC TR 18015:2004 (PDF)
This is a definitive 202 page report on performance-related issues in C++03 by the ISO C++ Committee, fully supported with extensive timing evidence. At the time this TR was written, C++ was under an unjustified attack for being inefficient compared to C. TR 18015 is amazing, offering a mature look at C++ which includes much of the optimization advice in Optimized C++, albeit in a compressed form. I was aware of TR 18015 before I began writing my book,  then forgot about it until the book was in production.It's a gem.

TR 18015 covers all of the following:
  • Types of programs (embedded programs on small devices, servers running flat out) with performance issues
  • Costs of various C++ features: namespaces, type conversion and casting, classes and member function calls, exception handling, and templates, all supported with run time measurements.
  • Two methods of exception handling (code, table). This discussion also contains a list of alternative error handling mechanisms.
  • Ways to make the standard I/O functions faster by fiddling with locales.
  • A hardware interface using atomic and volatile. 

TR 18015 spawned some articles in the embedded systems press. Some of these articles offer a much less mature “C++ is less efficient than C” viewpoint.

Efficient C/C++ Coding Techniques, Moss, 2000
"Explains" that C++ is less efficient than C if you use virtual multiple inheritance when simple containment will do. Some comparisons of control flow choices also motivated by poor understanding about what’s good about C++. Great diagrams on virtual functions and virtual inheritance, though.
Using C++ Efficiently In Embedded Applications, Quiroz, 1998
"Explains" that C++ exception handling is expensive because you don’t really need to destroy objects as you exit each stack frame, which is fine if resource leaks are OK with you. Paper talks about some C++ features and categorizes them into cheap, maybe-cheap, and expensive categories.
Reducing Run-Time Overhead in C++ Programs, Saks, 2002
A paper on optimizing C++. It has great 90/10 law quotes, and covers implicit copying and custom new and delete. It cites Bulka and Mayhew in its bibliography.
Representing and Manipulating Hardware in Standard C and C++, Saks
A paper on how hardware registers may be represented in C++.

Optimizing Software in C++: Agner Fog (PDF)
This is a long (150 page) treatment of statement and expression-level optimization in C++. The material is informed by deep knowledge of the x86 architecture, and makes reference to architectural details. It is only partially translatable to other platforms. Agner Fog actively maintains this document, so its content changes from time to time. If you find it useful, it may be worth caching a copy for your own use, lest the material change out from under you.

Optimizing C++: A book about improving C++ performance (Wikipedia | PDF)
There is some useful information in this small collection of Wikipedia entries, though not enough to call it a book. Good things about this wikibook include:
  • It evolved substantially during the time I was writing Optimized C++, growing to cover more material better.
  • It has a bibliography, including free on-line references, and some books that were new to me.
There are several problems with it, though:
  • No topic is covered exhaustively. There are, for instance, a few algorithmic techniques, but not a complete or even extensive catalog.
  • Most optimization advice is supported only by hand-waving arguments about how a compiler might behave.

Books

Efficient C++, Dov Bulka and David Mayhew (Amazon link) 1999, Addison Wesley, ISBN: 0-201-37950-3
Meticulously researched, but now slightly dated. I have tremendous respect for this work.

The Software Optimization Cookbook, Gerber, Bik, Smith, Tian (PDF table of contents)
I have not read this book, but it appears to be a useful source of information on processor-dependent optimization for the IA-32 (Intel 32-bit) architecture.

Optimizing C++, Steve Heller (HTML), 1999, Prentice-Hall, ISBN: 0-13-977430-0
Warning: not about performance tuning in C++ at all, but rather about optimizing an ISAM database. You can view it for free on the web.

Optimized C++, Kurt Guntheroth (Amazon link), 2016, O'Reilly Media, ISBN: 978-1491922064
My book, the best of everything, of course.

Other Notes

Microsoft Visual C++ Tips and Tricks has all sorts of debugger tricks. Not about optimization, but interesting.