What are the statistical drawbacks of my naive and simple approach to discarding outliers?

Question

I'm trying to measure and compare the performance of some computer programs. The simplest idea that comes to mind is to time, say, 10 runs in a row and present the arithmetic mean of the 10 timings as the final result. This however is quite inadequate and will produce an inflated result because individual timings will very often be significantly inflated, what I consider to be a measurement error (modern computer architectures cause highly nondeterministic performance for programs, except some embedded ones).

Example: there are three timings of the same program with the same input and output: 16.6483 seconds, 16.6626 seconds and 17.4575 seconds. The third value is obviously the result of an irreproducible and highly nondeterministic event, perhaps related to, e.g., CPU frequency scaling, CPU cache, ASLR, process scheduling, some kernel mischief, etc; and making it contribute to the mean calculation would make the result meaningless, at least with the small sample sizes that are relevant here.

I should note that some relatively big names actually advocate always taking only the minimum as the final measurement result, but I suspect that this is a quite bad choice because the minimum may represent some quite improbable alignment of events that may not be significant (if it is unlikely enough) to real program performance.

If it isn't clear by now, my goal was get a final result that would be robust to those kinds of measurement "errors", and I assume that high-valued outliers repeat fairly often.

A quick web search and skimming some Wikipedia pages indicates that this is a quite common problem and well-studied in statistics. However I'm wondering about the quality of this very simple method that should get rid of the measurement errors: for each program, take 12 measurements, sort them, delete the top 4 timings, return the mean of the 8 remaining timings

Answer 1

You are right that using the mean is better than using the minimum. Indeed, what you want is to estimate the mean time which is representative of the typical time your CPU will take. On the other hand, the minimum is very biased for this problem and you will not obtain good results.

One possible solution to your problem is to use the median which is also a good representative of the time your CPU take. Indeed, the median is in fact a typical time your CPU will take if the median is 15s then it means that if you took 100 measurements then approximately half of them would be below 15s.

Your approach to "remove outliers" by considering only the 8 smallest time is rather sound, this is called "trimmed mean" and is use extensively in a lot of field like econometrics, statistical biology... It is also mathematically more efficient than the median. Now, you have two parameters you want to tune:

• The proportion of point you consider outlier: why delete the top 4 timings ? Why not the top 5 ?
• The number of observation: here you said you take 12 measurements. Why ?

Typically, the proportion of points considered outliers is around 10%, with a smaller proportion is the data are rather clean and higher proportion for data with a lot of outliers. You can also rely on your expertise to know what is the proportion of outlier.

To choose the number of observations, you have to get an idea of what is the spread of your data. Is your data very variable ? If it is very variable, you should use more observation (the theoretical tool here is the central limit theorem). You can check this by repeating the same experiment. Try to compute the mean as you said "take 12 measurements, sort them, delete the top 4 timings, return the mean of the 8 remaining timings", do this several time for the same program and if the result vary a lot then increase the "12" here to obtain a less variable result.