List of common C++ Optimization Techniques [closed]

by

I will echo what others have said: a better algorithm is going to win in terms of performance gains.

That said, I work in image processing, which as a problem domain can be stickier. For example, many years ago I had a chunk of code that looked like this:

void FlipBuffer(unsigned char *start, unsigned char *end)
{
    unsigned char temp;

    while (start <= end) {
        temp = _bitRev[*start];
        *start++ = _bitRev[*end];
        *end-- = temp;
    }
 }

which rotates a 1-bit frame buffer 180 degrees. _bitRev is a 256 byte table of reversed bits. This code is about as tight as you can get it. It ran on an 8MHz 68K laser printer controller and took roughly 2.5 seconds for a legal sized piece of paper. To spare you the details, the customer couldn’t bear 2.5 seconds. The solution was an identical algorithm to this. The difference was that

  1. I used a 128K table and operated on words instead of bytes (the 68K is much happier on words)
  2. I used Duff’s device to unroll the loop as much as would fit within a short branch
  3. I put in an optimization to skip blank words
  4. I finally rewrote it in assembly to take advantage of the sobgtr instruction (subtract one and branch on greater) and have “free” post increment and pre-decrements in the right places.

So 5x: no algorithm change.

The point is that you also need to understand your problem domain and what bottlenecks means. In image processing, algorithm is still king, but if your loops are doing extra work, multiply that work by several million and that’s the price you pay.

More Related Contents:

  1. Why does flowing off the end of a non-void function without returning a value not produce a compiler error?
  2. Undefined reference to vtable
  3. What is the difference between g++ and gcc?
  4. How does #include work in C++? [duplicate]
  5. gcc optimization flag -O3 makes code slower than -O2
  6. Compiling a C++ program with GCC
  7. Why does typeid.name() return weird characters using GCC and how to make it print unmangled names?
  8. Different floating point result with optimization enabled – compiler bug?
  9. __builtin_prefetch, How much does it read?
  10. How to create a static library with g++?
  11. What is the purpose of using -pedantic in the GCC/G++ compiler?
  12. GCC C++ “Hello World” program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?
  13. gcc/g++: “No such file or directory”
  14. 😃 (and other Unicode characters) in identifiers not allowed by g++
  15. constexpr initializing static member using static function
  16. How to tell where a header file is included from?
  17. How to include omp.h in OS X?
  18. Linking g++ 4.8 to libstdc++
  19. Linking to MSVC DLL from MinGW
  20. GNU C++ how to check when -std=c++0x is in effect?
  21. Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts?
  22. request for member `…’ is ambiguous in g++
  23. How to use profile guided optimizations in g++?
  24. GCC: Difference between -O3 and -Os
  25. Why “initializer-string for array of chars is too long” compiles fine in C & not in C++?
  26. Does the restrict keyword provide significant benefits in gcc/g++?
  27. Install gcc on linux with no root privilege
  28. How should I use g++’s -finput-charset compiler option correctly in order to compile a non-UTF-8 source file?
  29. Can I make GCC warn on passing too-wide types to functions?
  30. std::array with aggregate initialization on g++ generates huge code

Leave a Comment