Optimising your code has to be done carefully. Let's also assume you have already debugged the code already. You can save a lot of time if you follow certain priorities, namely:
1. Use highly optimised (or professionally optimised) libraries where possible. Some examples might include FFTW, OpenBlas, Intel MKL, NAG libraries, etc. Unless you are highly talented (like the developer of GotoBLAS), you probably can't beat the professionals.
2. Use a profiler (quite a few in the following list have already been named in this thread--Intel Tune, valgrind, gprof, gcov, etc.) to find out what portions of your code take the most time. No point wasting time optimising portions of code that are rarely called.
3. From the profiler results, look at the portion of your code that took the most time. Determine what the nature of your algorithm is--is it CPU bound or memory bound? Each requires a different set of optimisation techniques. 242
If you are getting a lot of cache misses, memory might be the bottleneck--the CPU is wasting clock cycles waiting for memory to become available. Think about whether the loop fits into the L1/L2/L3 cache of your system. If you have "if" statements in your loop, check if the profiler says anything about branch misprediction? What is the branch misprediction penalty of your system? By the way, you can get branch misprediction data from the Intel Optimisation Reference Manuals [1]. Note that the branch misprediction penalty is processor-specific, as you'll see in the Intel manual. The manual will also tell you things like how many clock cycles various instructions take (again, this is processor-specific).
4. Lastly, address the problems identified by the profiler. A number of techniques have already been discussed here. A number of good, reliable, comprehensive resources on optimization are also available. To name just two, there is the Intel Optimization Reference Manual [1], and the five optimization manuals by <PERSON> [2]. Note that there are some things that you may not need to do, if the compiler does it already--for example, loop unrolling, aligning memory, etc. Read your compiler documentation carefully.
References:
[1] Intel 64 and IA-32 Architectures Optimization Reference Manual: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf
[2] <PERSON>, "Software Optimisation Resources": http://www.agner.org/optimize/
* "Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms"
* "Optimizing subroutines in assembly language: An optimization guide for x86 platforms"
* "The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers"
* "Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs"
* "Calling conventions for different C++ compilers and operating systems" 242