Why optimization is usually a waste of time

There is also the payback issue. Let’s say it takes 4 hours for a given program to run and based on your experience you could probably get the program to run in 5 minutes or less. Sounds like a no-brainer, right? What if that program will only ever be run once and it will take you 6-8 hours to make the modifications and test them? Net result: a waste of 2-4 hours, a very poor choice for optimization. On the other hand, it may be valuable to work on a process that is taking 1 second when it is practical to get it to run in 0.01 second if it is running over and over again and the change takes little time to code and test (in one situation there was an insert trigger in a database that was doing a scan on a table with millions of rows and was taking 3 seconds to execute; simply adding a new index to the base table resulted in a 67 fold improvement in performance resulting in a cumulative time savings of hours in just a week).

Another critical issue to keep in mind when deciding whether to invest time in optimization: modern processors are so bloody fast that they are actually in a wait state 70% or more of the time even when they are marked as at 100% utilization. This unfortunate reality is due to the massive discrepancy between CPU register bandwidth and RAM IO bandwidth. (Which is why all these caches are spread all over.) If, by some miracle, you are able to utilize these wasted cycles (keep in mind that 30% utilization is often the highly tuned optimum, in reality it may be much closer to 5% or less) you can see awesome performance boots. If you do manage that, call me and tell me how you did it, then call Intel, AMD, IBM, etc. and get a job earning huge dollars, as they have brilliant people there that are hard pressed to reach that 30% utilization level.

Understanding IO and OS data/instruction caching are critical to reproducing and interpreting experimental results. If the machine has been freshly rebooted then there is essentially nothing (related to your program and/or data) in the various caches. Therefore, on program startup the OS has to first read in your program from the disk (it typically does so by memory mapping the file, so the file may not actually ever entirely make it into RAM), then your program has to do its startup, likely reading from a file somewhere (or possibly even a database on another machine). Up to this point there is nothing you can do to your program to have the slightest impact on its performance. If your program quits at this point and then you rerun it, you are likely to find that it’s ‘performance’ is much better. That is because the instructions and data have already been read into memory and it is working from a cached version. Let’s say your program processes a large (multi-megabyte) file. The very first time it processes the file it is slow, thereafter it runs 10-100 times faster. Why? Because the first time the file was on disk and had to be read in (disk IO is often 1,000 times slower than RAM IO), the second time it was already cached in RAM. How do you measure that sort of thing during optimization trials? It ain’t easy! Rebooting your machine after each recompilation would be very tedious and time consuming. But look, if your process is IO bound, there is nothing you can do to make it complete sooner anyway, why are you bothering with optimization? The best you can do is free up CPU cycles for other processes! If you find that your program is IO bound, then you are done ‘optimizing’ unless you can figure some way to reduce the disk access time (via compression, use of binary files, perhaps indexs if you don’t need the entire dataset, etc.).

Lets say you are running a program communicating over a socket (to a database, for file sharing, web, mail, etc.). While excellent networks today are often faster than pedestrian disk IO (gigabit Ethernet vs IDE drives), they are still in the realm of 1,000 times slower than RAM. To add insult to injury, there is no caching with network communication, so every single request will have to be repeated at its same slow rate. Therefore (as in disk IO), if your program is network bound, you are done; there is nothing to optimize.

It is the algorithm

Sometimes it is the hardware

Occasionally it is the program logic

The 10/90 rule

Nitty gritty low-level things to think about

Some C and C++ performance tips

Thanks for some suggestions from Scorpions4ever and infamous41md!

• Never copy a complex function variable onto the stack, use pointers (and references in C++) instead (use const pointers/references if you know the object won’t change). If you plan on changing the object you are passing as a variable and do not want those changes to be reflected in the callee’s instance, you may want to rethink your logic. If you may want to change a small part of a large object, consider passing the large object by const pointer/reference and the small bit that may need to change as a separate, by value, variable. Having said that, if the variable is a simple data type (int, float, etc.), copying onto the stack can result in better performance as you can reduce potential lag in accessing the variable (better locality of data).
  For example:
  int slowfunc(string s);
  int fastfunc2(const string &s);
  The performance improvement of fastfunc2 will be considerable for large string objects, since a copy will not be made on the stack.
• Inline functions/methods where ever possible (some compilers will do it for you automagically, some need the ‘inline’ hint (and then may ignore you)).
• In most modern compilers using the ‘register’ keyword is probably a waste of key strokes, but go ahead and use it if you think the compiler needs the hint.
• Unless there are side effects, use the pre-increment rather than post-increment instruction on counters. For example, “for (i=0; i<VAR; i++)” is slower than “for (i=0; i<VAR; ++i)”. That is because (unless the compiler is clever), it has to make a copy of i before it increments it in case there happens to be a side effect. In this particular case the compiler is probably smart enough to know it can take that optimization, but if you have an object or you have some dense code, the compiler may not be able to know if there is a side effect and will be conservative.
• When creating objects, it is best to disable copy constructors (make it private with no body). It is better to see compiler errors when there is a default copy so you can judge if the code can be modified to side step the need for the copy. Without a little thought your code can easily spend most of its time doing copy construction instead of real work. In addition, if you dynamically allocate memory inside your object, the default copy constructor will FAIL as it makes a ‘shallow’ copy and does NOT make copies of the allocated memory (creating all sorts of nasty bugs).
• Don’t use exceptions for routine or expected errors, most exceptions are very expensive. Return an error code instead.
• Sometimes it pays to manually unroll loops (as opposed to relying on the compiler to do so); you can occasionally get better pipelining that way.
• Move loop-invariant assignment outside the loop. Often the compiler will do so for you, but it is best not to rely on it AND it makes it easier for a maintainer to realize what is important. In for/while/do loops where you are testing against a value not expected to change during the processing, make a temporary local variable and assign it to the value. This is particularly important when processing through objects (such as vectors, maps, etc.) as it is extremely unlikely that the compiler will do this for you as the potential for side effects is huge.
  For instance, if you are looping while processing a C string (character array) like this:

  
  for (i=0; i<strlen(myString); i++)
      ....
  
  

  Do this instead (move the strlen test out of the loop):

  
  int size = strlen(myString);
  for (i=0; i<size; i++)
      ....
  
  

• C string functions are actually quite inefficient if used improperly. For instance: using strncat() or even strcat() in a loop is a bad idea once the string starts to get large. This is because strncat() needs to recompute the length of the string each time before appending to the end of it. It is better to keep a pointer to the end of the string buffer after each append operation and then strncpy() or strcpy() from this pointer.
  Also, strncpy() copies the full length provided as the 3rd parameter. For example: strncpy(buf, "hi", 1000); will copy "hi", followed by 998 NULL bytes into buf, so be smart about what you are copying.
• Many C++ containers (like strings, vectors, etc.) can have their size 'pre-allocated' which can result in quite noticable performance enhancements. I built a million character string via concatenation in no measurable time by 'reserve'ing the space ahead of time. I didn't measure the difference, but doing it without the reserve took a noticable amount of time (perhaps a second or so).
• Use local const references wherever possible, it allows the compiler to make all sorts of optimizations because it knows the variable will not change.
• As mentioned above, know your patterns of memory access so you can ensure that you are not thrashing the various caches. Occasionally this may require gross reorganization of the code, be sure that the payoff is worth the increased maintenance cost.
• If your problem lends itself to this, break it up into bits and run the bits in parallel (keep in mind you get little benefit unless you have parallel processors!). If you can minimize the need for the various parts to access memory in common (or can live with copies of that memory and are not going to write changes there), you can reduce or eliminate contention and can see nearly a 1:1 performance increase benefit (meaning if you have 10 processors you can get your program to run in 1/10th the time). If your problem lends itself to it, you can even utilize distributed processing (like the SETI@home project).

Inlined assembler

Check the assembler output

Performance and executable size

Unless you are writing to run on embedded systems, where bytes often count (but continue to count less and less as memory gets cheaper by the day), worrying about exe size is very seldom a valuable use of your time. In the unlikely event that your exe, when zipped up, fails to fit on a floppy (does anyone still use floppies? (note that speed optimized binaries tend to compress very well)), then you may want to investigate some alternatives like dynamic linking (only useful if your customers have already received the libs, else you have to distribute them anyway). Of course, you could always pony up the few cents it takes (often as little or even less than floppies) to get a CD and burn it, giving you at least 650 MB (uncompressed) of space; heck you can even fit a few MS programs on single a CD! If you are distributing your program via the web, certainly having a huge file is problematic for those unfortunates still stuck with dialup (or worse), but you need to first be sure that your efforts are going to be worth while. How much can you expect to shrink your program? If you are using a lot of third-party libraries (like most anyone doing MFC/.Net is going to do), you may have very little control over your exe size except for making the choice of static vs. dynamic linking. Static linking is great because you never have to worry about the libraries your program needs changing unexpectedly helping to protect you from DLL hell.

With respect to minimizing code to try to fit the program in the instruction cache, the entire program need not fit in the instruction cache to see an increase in performance! Only the bits that are actually executing in a repetitive manner need to be in the cache (recall the 10/90 rule), the rest could even be on disk for all the impact on performance it will have. Because the instruction cache will be empty on initial load of the program (instruction caches are not, to my knowledge, shared amongst processes, only betwixt threads), if your program is only using a given cache line’s worth of instructions once, you won’t get any significant performance gain unless you have a huge number of instructions that are executed only once (thus, reducing the number of instructions will reduce the number of cache misses, potentially (though very unlikely, due to other IO dependencies) reducing the execution time).

You can reduce the size of your exe with compiler switches, which will strip out some unneeded symbol information and will bias the instruction selection to minimize them, eliminate loop unrolling, in-lining, (you will notice, I hope, that minimizing exe size almost always means eliminating run-time optimizations, resulting in slower execution), dynamic linking etc. Alternatively, going with the 10/90 rule, you can find the portions of your code that are compute bound, pull them into a separate file, optimize the compilation of that file and use these other tricks to reduce the size of the rest of the executable. It can be a lot of extra work and is seldom going to result in any measurable change in performance. However, if your distribution channel requires minimal executable sizes, this is a way to keep most of your cake and eat it also.

There are some “old wife’s tails” about how to reduce the size of your binaries. While older compilers did lack a lot of sophistication, unless you are stuck with some out-of-date compiler (and why, when excellent free compilers are available for download?), dead code (code that can never be executed) is eliminated, thus including a bunch of unused #include files will have no significant impact on the size of your program. Smart linkers (same caveat as above) will also eliminate chunks of program if they can detect that the code is not going to be used. The use of statically allocated memory vs. dynamic memory will also show no significant change in exe size or in performance. Indeed, if you are not careful with the use of statically allocated memory you can even increase the size of your binary (if you initiate your static memory at compile time, the compiler must make room for it in the binary). It is true that typical compilers put a whole lot of code in the program start up that can be eliminated with careful use of declarations (if you don’t use environment variables or command-line arguments, your program doesn’t need the code for that); the reduction in code is often not meaningful for performance. Keep in mind that modern OSs read disks in pages (generally at least 2K, sometimes 4K or more), so if you’re binary is less than a page you get absolutely no benefit in attempting to shrink it further.