Q1: What tools are you using for code profiling (profiling, not
Q2: How long do you let the code run (statistics: how many time
Q3: How large are the cases (if the case fits in the cache, the solver
is orders of magnitude faster, but then I'll miss the memory related
Here's an example of how I do it.
I separate the benchmarking (seeing how long it takes) from the profiling (identifying how to make it faster). It is not important that the profiler be fast. It is important that it tell you what to fix.
I don't even like the word "profiling" because it conjures an image something like a histogram, where there's a cost-bar for each routine, or "bottleneck" because it implies there's just a little place in the code that needs to be fixed. Both of these things imply some sort of timing and statistics, for which you assume accuracy is important. It is not worth giving up insight for accuracy of timing.
The method I use is random pausing, and there's a full case study and slide show here.
Part of the profiler-bottleneck world view is that if you don't find anything, there's nothing to be found, and if you do find something and get a certain percent speedup, you declare victory and quit. Profiler fans almost never say how much speedup they get,
and the ads only show artificially contrived problems designed to be easy to find.
Random pausing finds the problems whether they are easy or hard.
Then fixing one problem exposes others, so the process can be repeated, to get compounded speedup.
In my experience from numerous examples, here's how it goes:
I can find one problem (by random pausing) and fix it, getting a speedup of some percent, say 30% or 1.3x.
Then I can do it again, find another problem and fix it, getting another speedup, maybe less than 30%, maybe more.
Then I can do it again, multiple times until I truly can't find anything else to fix.
The ultimate speedup factor is the running product of the individual factors, and it can be amazingly large - orders of magnitude in some cases.
INSERTED: Just to illustrate this last point. There's a detailed example here, with slide show and all files, showing how a speedup of 730x was achieved in a series of problem removals. The first version took 2700 microseconds per unit of work. Problem A was removed, bringing the time down to 1800, and magnifying the percentages of remaining problems by 1.5x (2700/1800). Then B was removed. This process continued through six iterations, resulting in almost 3 orders of magnitude speedup. But the profiling technique has to be really efficacious, because if any of those problems are not found, i.e. if you reach a point where you incorrectly think nothing more can be done, the process stalls.
INSERTED: To put it another way, here's a graph of the total speedup factor as successive problems are removed:
So for Q1, for benchmarking a simple timer suffices. For "profiling" I use random pausing.
Q2: I give it enough workload (or just put a loop around it) so it runs long enough to pause.
Q3: By all means, give it realistically large workload so you don't miss cache problems. Those will show up as samples in the code doing the memory fetches.