What are the best books on how to optimize C++ code?
+19
A:
rahul
2009-10-22 05:34:22
+1: Agner Fog's work is amazing.
RaphaelSP
2009-10-23 17:35:39
@RaphaelSP: Yes, assuming you want maximum performance, potentially at the cost of other things. Good stuff, but don't apply it blindly.
David Thornley
2009-10-30 15:56:06
+11
A:
Depends on the scale/granularity you have in mind -- for large scale, where it matters most, my favorite is still Lakos' grand old book, dated tho it may be I don't think it's been surpassed.
Alex Martelli
2009-10-22 05:34:33
graham.reeds
2009-10-22 13:17:26
graham - doesn't seem fair that you guys in the UK have to wait 2 years longer than the folks in the US - http://www.amazon.com/gp/product/0201717069 (Dec. 2009)Of course, all these dates are ephemeral anyway....
Dan
2009-10-22 13:29:21
That's a great book... but I don't remember anything about optimization. I suppose you can consider it to be optimizing the maintenance complexity, but Lako's book is more about sanity in a large project, not efficiency.
Tom
2009-10-25 15:57:31
+1
A:
Probably starting using an profiler to point you to the location that really needs speedup. I think a lot of people spend a lot of time in optimizing their code by guessing what eats up the time while normally the C++ optimizer of the compiler does a quiet well job.
So first identitify the bottleneck by use of a profiler. Then think about speeding up your code.
Totonga
2009-10-22 06:17:17
If you think so. I already spend some time with code that was "optimized" because of no need. Make the design and if its really a bottleneck think about code optimization.I do not think that the one who asked wanted to write an C++ optimizer.
Totonga
2009-10-22 08:51:54
@Totonga, Justicle may be a bit terse (and comes off as rude), but he's correct. Your advice is good advice, but still it is very basic when it comes to optimization techniques. The profiler will help identify the low hanging fruit.
Scottie T
2009-10-23 17:28:18
I completely agree that the profiler will somehow identify the low hanging fruits. So if your design and your complete setup is really bad fro performance the profiler will not help. But men, I am not sure if I could coun't the hours discussing on why this code is slow and when we did a little profiling, we determined that the time was eaten by something else.I still stay with my thoughts.Try to write good code and focus on a good design that is maintainable.If there is really a bottleneck. Go for it.
Totonga
2009-10-24 17:57:42
Sorry for appearing rude, I thought it better than a random downvote with no explanation. Totonga, useful advice, but better suited for the comments under the question, than an actual answer. Think of the votes being for "how well the *question* is answered" not "how useful is the answer".
Justicle
2009-10-25 01:33:00
Hello Justicle, it no problem. Thats how stackoverflow works, and I have still enough points left, to accept some downvotes on my answer :-) without loosing my democratic rights to vote or to comment.
Totonga
2009-10-25 04:46:04
This answer is basic, in the sense that pretty much everything else depends on it. If you aren't using a profiler, you aren't optimizing effectively. The "low hanging fruits" are the only ones worth bothering with. After all, if you spend 20% of the time in one routine, doubling its speed will reduce runtime by about 10%. If you spend 2% in another, making it instantaneous will reduce runtime by 2%.
David Thornley
2009-10-30 15:38:58
+2
A:
Michael Abrash has written some books on optimization. His focus will be on using x86 assembly code, but the underlying concepts/reasons/techniques for optimization will apply to many programming languages, especially C++. And when not using assembly code, he will use C or C++ so it might be relevent.
For anyone trying to optimize their code, his books will be more of an inspiration than actual reference.
Xen Borderworld
2009-10-22 06:42:16
+2
A:
I really liked Bulka & Mayhew's "Efficient C++: Performance Programming Techniques".
Drew Hall
2009-10-22 06:47:09
+3
A:
This isn't exactly specific to C++ but personally I think the best optimizations are done on an algorithm/data structure level and thus I'd strongly recommend Programming Pearls: http://www.cs.bell-labs.com/cm/cs/pearls/
Christian
2009-10-22 07:19:42
@sbi - you are creating a false dichotomy between algorithmic improvements and everything else. Don't forget that algorithmic performance is typically measured in O(f(n)), ignoring constant factors. Paying attention to those constant factors is not "obscure t[weaks and tricks", it's proper engineering.
Tom
2009-10-25 15:51:36
+4
A:
My favorite low-level source is actually a website: http://www.agner.org/optimize/
Will
2009-10-22 07:36:30
+5
A:
Michael Abrash's Graphics Programming black book can be downloaded, legitimately, from here ... for free!. A brilliant in depth description of assembler optimisation even if it is pretty graphics-centric
Goz
2009-10-22 07:38:51
+2
A:
Code Optimization: Effective Memory Usage, Kris Kaspersky
Write Great Code Vol. I/II, Randall Hyde
Fabio Ceconello
2009-10-22 23:03:11
+2
A:
You can find books on algorithms and compiler (low-level) optimization. Those are fine, as far as they go, but large real software has a completely different problem.
Large real software is dominated, in my experience, by slowness due to "galloping generality", and it requires a different approach to optimization, as in this example. I have yet to see a book about this.*
*Except for my own (modest cough), which is long out of print.
Mike Dunlavey
2009-10-23 17:24:27
+1
A:
Some books that I've found very useful, and although they are not specific to the issues of optimization, they do touch on a lot of the issues, are Scott Meyers books: Effective C++, More Effective C++ and Effective STL.
Mutmansky
2009-10-28 15:30:31
+4
A:
I'm going to give you a generalized answer:
- Make sure the program is working correctly.
- Consider changing your algorithms with faster ones.
- Consider the impact of your data structures. Memory locality, CPU cache hits and the like will give you performance gains.
- If you can't find candidates for the two above, can you change the original problem? E.g., instead of solving something with an exact solution, is an approximation good enough?
- Improve your code; make it clearer, remove redundant stuff.
- Perform micro-optimizations
And remember to always time and profile your code.
Some very good books for improving your code are the Effective C++ series by Scott Meyers. Couple those with the ones other people are suggesting, and you should be well on your way.
As for micro-optimizations, some common techniques are increasing CPU cache hits, improving branch prediction, unrolling loops, consider CPU vector operations and so on.
These are general techniques, but to get the last drop of performance you will have to tie everything closely to the CPU architecture you're working on.
csl
2009-10-28 15:41:27
+1 for "Make sure the program is working correctly" - the most important optimization. Incorrect code is as unoptimized as you can get.
Michael Burr
2009-10-30 08:54:56
@Michael Burr: Excellent point. For any given problem, I can give you an incorrect solution in approximately zero time, so any program that runs for a noticeable amount of time to get the wrong answer cannot be said to be optimized.
David Thornley
2009-10-30 15:57:32
+1
A:
Ulrich Drepper's 114-page article "What Every Programmer Should Know About Memory" is essential reading, I think. It won't tell you much about how to speed up code using algorithmic optimizations or concurrency, but it will definitely help you get the most out of the memory and cache systems your code is running on.
timday
2009-10-29 22:36:27
+1
A:
Really knowing your algorithms is a good way to optimize you code. Two kinds of book help me do this. Algorithmic books like
Donald E. Knuth, The Art of Computer Programming
and then the puzzle books like
Jon Bentley, Programming Pearls
I know that they aren't specific for C++ but a lot of optimizations can probably be applied independently of language.
Niels Castle
2009-10-30 15:08:18