How to assess the improvement from a treatment? When optimizing a computer program, I need to determine how much faster the program runs with the latest optimization. To do this, I run the program N times without the optimization and N times with the optimization. After each run, I record the elapsed time. So I get two sets of N measurements each, which I would like to compare to determine the gain from the optimization.  
Suppose that A and B are the sets of measurements with and without the optimization respectively. So:
A = [Ta1, Ta2, ..., TaN] <-- without optimization
B = [Tb1, Tb2, ..., TbN] <-- with optimization

Specifically I am asking:


*

*Are the measurements consistent? I want to use the values only if they are consistent, and be sure that there was no noise that corrupted the results. Right now, I check that stddev(A)/mean(A) < 0.03, and the same for B.

*How many measurements are needed in order to have a good confidence in the comparison?

*What is the best method for comparing the two series: mean(A)/mean(B), median(A)/median(B), or (mean(B)-mean(A))/mean(A)?

 A: 1. To answer the question, you have to define what you mean - I can't tell you what 'consistency' means for your application
2. This depends on (i) what the distribution is (mostly, if N is large, on the variance), (ii) what the comparison measure is, and (iii) what you mean by 'good confidence'. If you specify enough things, specific answers can be derived. If you have some runs available already, you should be able to compute what you need. Failing that, some assumptions combined with either some algebra or some simulation may be sufficient.
3. That's a matter for you, but for this problem - if the distribution of times tends to be quite skew - I'd be inclined to look at either a ratio, of means or perhaps a difference in the mean of log-time; ultimately, you have to work out what you want to know.
A: The Python benchmarker/profiler timeit uses an interesting approach: it reports the best (i.e., minimum) running time. The timeit documentation argues that this actually presents the clearest picture of the code's performance. There are many factors that can introduce variability into your program's run-time (e.g., other programs, cache misses, garbage collection, cosmic rays), but all of these cause your program to run slower; there aren't really any factors that can make your code run unexpectedly quickly [*]. 
You could take a similar approach and stick with A as long as $\min(T_a) \le \min(T_b)$.
That is probably sufficient for practical purposes, but if you wanted to make a production out of this, there's been some work on order statistics, which was discussed a while ago in this thread. 
[*] This assumes two things, which may or may not be true:


*

*Your algorithm is deterministic and doesn't have any internal sources of variability. I would hesitate to use this approach to test how long it takes to fit a curve when the initial parameters were chosen at random for each run.

*You're avoiding (or don't care about) cacheing, pre-loading, memoizing, or other tricks that might speed up consecutive runs of the same function. A lot of this could be avoided by properly designing your benchmark. 
