Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When coding performance-critical portions of code (not necessarily large, but code that gets executed a lot), what topics should I be aware of/take into account.

I'm already fairly familiar with caching, aliasing, branching, cost of arithmetic operations, loop unrolling (and I guess some others that don't come to mind).

What else should I know? (not necessarily looking for details, just concepts I can look up on my own)

share|improve this question

closed as not a real question by gnat, Caleb, Martijn Pieters, Walter, Glenn Nelson Jan 22 '13 at 12:50

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

see Performance optimization strategies of last resort at Stack Overflow – gnat Jan 22 '13 at 9:24
@gnat thanks, helpful – Luchian Grigore Jan 22 '13 at 9:26
closed as not a real question This IS a real question... and one worth knowing. – Thomas Eding Jan 22 '13 at 19:16
There's what you do before you write it, and what you do after. What you do before is KEEP IT SIMPLE, especially in the class and data structure, so you avoid putting in performance problems. What you do after is TAKE OUT THE PROBLEMS YOU DID PUT IN, and be willing to do large re-writes. It's possible to reduce time by a factor of 10-100. gnat's link gives an example. – Mike Dunlavey Jan 23 '13 at 19:09
@MikeDunlavey yes, but that's beside the point of the question. I already know that. – Luchian Grigore Jan 23 '13 at 19:24

My 2 cents:

It's about how effectively you manage your resources and utilize the available hardware.

Generally, you will be limited in the amount of memory you have(RAM), but there's aplenty of processing speed available than we utilize.

While effective utilization of memory is largely dependent upon the techniques and algorithms(caching, aliasing, branching, cost of arithmetic operations, loop unrolling (and I guess some others that don't come to mind)). In platforms where memory is managed(Java, .NET), having GC run frequently takes a toll on performance. If there is less free memory, GC keeps running frequently trying to free memory. So, keep a tab on how your objects are created and destroyed. In languages where memory is explicitly managed(C,C++), by rule of thumb, you always keep a check(you free the memory as soon as you finish the task). So, in both cases, having enough free memory will ensure having little/less toll on performance.

Concurrency is the way to utilize CPU effectively. Instead of blocking and keeping CPU idle, concurrency allows you to utilize CPU effectively on tasks that could be run in parallel. While concurrency is one step above single threaded programs, the advent of multi-core machines and its ubiquity needs us to take one more step(see here) to effectively utilize all the cores. Utilizing CPU effectively improves the performance.

share|improve this answer
Keeping memory usage low tends to improve cache utilization and therefore performance. That makes tuning managed runtimes especially tricky, because more frequent collection will take more time, but less frequent collection will make caches inefficient, eventually negating the savings on collection. – Jan Hudec Jan 22 '13 at 13:28
Good point on the frequency of collection. Collection shouldn't be overdone so it negatively effects performance, which is the cause. So, it has to be balanced. However, I didn't understand how less frequent collection makes the caches inefficient. I believe otherwise. – Sundeep Jan 23 '13 at 13:42
The memory cache is rather strange piece of hardware. It does not cache individual memory cells, but cache-lines (usually 32 or 64 bytes) and it can only cache 2 locations with addresses congruent some number (half the cache size). If you have lot of garbage between the objects, you increase the amount of it that gets pulled in the cache lines uselessly and you increase the risk it will be multiple of cache half-size apart and fighting over a cache line. – Jan Hudec Jan 23 '13 at 14:06

I think when it comes to performance, being familiar with the compiler optimization strategies and methods is essential. What this helps you with is that when you understand what kind of optimizations the compiler is capable of doing and under which circumstances, you actually can offload the performance tuning to the compiler(as you should anyway, if possible) by making sure that you give it the maximum possible opportunity to optimize the code.

Of course being familiar with tools which assist you with profiling and benchmarking your code/implementations is an essential. Infact, there's no point in optimizing unless you can measure the benefit. In the end this boils down to being able to reason between multiple implementations and what and why the performance differs at the lowest level possible - without this understanding it is very hard to come up with valid optimizing opportunities which you can reason about.

As the bottom line I would argue that being familiar with the compiler and it's optimizing capabilities and opportunities as well as being familiar with tools to measure benefits and spot bottlenecks as well as understanding the CPU's capabilities and instruction set are the three most important things for any programmer when it comes to writing performant native code. Yes, this is very general but as such it's also very applicable. Everything boils down to this in the end.

share|improve this answer

First of all, most performance problems end up being caused either by using, possibly by mistake, algorithm with unfavourable complexity. So first and foremost, keep on lookout for anything that is done more times than expected.

When you've flushed those out and are really down to micro-optimizations as your last chance, tuning for memory cache utilization can make some difference. It can be profiled using valgrind cachegrind skin. General suggestions are to keep the working set (frequently accessed memory) small, related objects together and possibly employ allocator that can do cache coloring.

Also despite the research that went into allocators, standard libraries still often provide rather poor memory allocators, so consider using a custom one (umem, tcmalloc, ...) and/or employ memory pools for common data structures (improvements to allocator specification in C++11 make that much easier and more usable).

share|improve this answer
You can assume I "have a working version and it is not fast enough and you've profiled it and found where the hot-spots are." I'm aware of "premature optimization is the root of all evil". – Luchian Grigore Jan 22 '13 at 9:41
@LuchianGrigore: In my experience most bottlenecks boil down to either wrong algorithm or bug that increases complexity. – Jan Hudec Jan 22 '13 at 9:44
I know, in my experience as well. – Luchian Grigore Jan 22 '13 at 9:59
JanHudec, I can vouche for @LuchianGrigore. He's no neophyte when it comes to these things. – Neil Jan 22 '13 at 10:51
@LuchianGrigore: Ok, I pruned most of the text about complexity and mentioned two optimizations that I think were not mentioned yet in other answers. – Jan Hudec Jan 22 '13 at 13:47

if you need to work with numbers and 100% accurate results are not needed then don't be shy to try out faster less accurate algorithms

this is heavily apparent in game development where the results on screen don't need to be exact they just need to be close enough too look right, it's more important the calculations happen fast; see the fast inverse square root for a classic example

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.