Take the 2-minute tour ×

How would you mathematically model the distribution of repeated real life performance measurements - "Real life" meaning you are not just looping over the code in question, but it is just a short snippet within a large application running in a typical user scenario?

My experience shows that you usually have a peak around the average execution time that can be modeled adequately with a Gaussian distribution. In addition, there's a "long tail" containing outliers - often with a multiple of the average time. (The behavior is understandable considering the factors contributing to first execution penalty).

My goal is to model aggregate values that reasonably reflect this, and can be calculated from aggregate values (like for the Gaussian, calculate mu and sigma from N, sum of values and sum of squares). In other terms, number of repetitions is unlimited, but memory and calculation requirements should be minimized.

A normal Gaussian distribution can't model the long tail appropriately and will have the average biased strongly even by a very small percentage of outliers.

I am looking for ideas, especially if this has been attempted/analysed before. I've checked various distributions models, and I think I could work out something, but my statistics is rusty and I might end up with an overblown solution. Oh, a complete shrink-wrapped solution would be fine, too ;)

Other aspects / ideas: Sometimes you get "two humps" distributions, which would be acceptable in my scenario with a single mu/sigma covering both, but ideally would be identified separately.

Extrapolating this, another approach would be a "floating probability density calculation" that uses only a limited buffer and adjusts automatically to the range (due to the long tail, bins may not be spaced evenly) - haven't found anything, but with some assumptions about the distribution it should be possible in principle.

Why (since it was asked) -

For a complex process we need to make guarantees such as "only 0.1% of runs exceed a limit of 3 seconds, and the average processing time is 2.8 seconds". The performance of an isolated piece of code can be very different from a normal run-time environment involving varying levels of disk and network access, background services, scheduled events that occur within a day, etc.

This can be solved trivially by accumulating all data. However, to accumulate this data in production, the data produced needs to be limited. For analysis of isolated pieces of code, a gaussian deviation plus first run penalty is ok. That doesn't work anymore for the distributions found above.

[edit] I've already got very good answers (and finally - maybe - some time to work on this). I'm starting a bounty to look for more input / ideas.

share|improve this question
This begs the question "Why?" –  Lazarus Dec 8 '09 at 14:51
@Scottie T: Happy flying in that 172! –  Mike Dunlavey Dec 8 '09 at 15:26
@peterchen: for skewed distributions, people sometimes say what the average is, but they really shouldn't. The median is more meaningful. The average is skewed to the right because of the long tails that you mentioned. –  Mike Dunlavey Dec 8 '09 at 21:08
@Mike: I'd love to use the median - but it needs all samples. –  peterchen Dec 9 '09 at 10:23
While Medians can be an appropriate "average" as an input to statistical population models, it is not appropriate as an input parameter for mathematical modelling because it is inherently non-arithmetic. Arithmetic Means, however, can be valid "average" as they are inherently arithmetic (assuming that they are otherwise valid for the type of model). For instance, MVA models (a type of QNA Analytical Performance model) are based entirely on arithmetic means. –  RBarryYoung Dec 9 '09 at 16:40
show 1 more comment

6 Answers

Often when you have a random value that can only be positive, a log-normal distribution is a good way to model it. That is, you take the log of each measurement, and assume that is normally distributed.

If you want, you can consider that to have multiple humps, i.e. to be the sum of two normals having different mean. Those are a bit tricky to estimate the parameters of, because you may have to estimate, for each measurement, its probability of belonging to each hump. That may be more than you want to bother with.

Log-normal distributions are very convenient and well-behaved. For example, you don't deal with its average, you deal with it's geometric mean, which is the same as its median.

BTW, in pharmacometric modeling, log-normal distributions are ubiquitous, modeling such things as blood volume, absorption and elimination rates, body mass, etc.

ADDED: If you want what you call a floating distribution, that's called an empirical or non-parametric distribution. To model that, typically you save the measurements in a sorted array. Then it's easy to pick off the percentiles. For example the median is the "middle number". If you have too many measurements to save, you can go to some kind of binning after you have enough measurements to get the general shape.

ADDED: There's an easy way to tell if a distribution is normal (or log-normal). Take the logs of the measurements and put them in a sorted array. Then generate a QQ plot (quantile-quantile). To do that, generate as many normal random numbers as you have samples, and sort them. Then just plot the points, where X is the normal distribution point, and Y is the log-sample point. The results should be a straight line. (A really simple way to generate a normal random number is to just add together 12 uniform random numbers in the range +/- 0.5.)

share|improve this answer
log-normal looks like a good idea - I'll check how well it fits the actual data we have acquired. –  peterchen Dec 8 '09 at 15:53
@peterchen: let me know how it works. –  Mike Dunlavey Dec 8 '09 at 16:38
@peterchen: I would get a good run of lots of empirical data, and then get QQ plots against all possible distributions: normal, log-normal, gamma, and poisson. The one that has the straightest line is the best distribution to use. (R or S or SPlus can make short work of this.) –  Mike Dunlavey Mar 29 '10 at 22:51
add comment

The problem you describe is called "Distribution Fitting" and has nothing to do with performance measurements, i.e. this is generic problem of fitting suitable distribution to any gathered/measured data sample.

The standard process is something like that:

  1. Guess the best distribution.
  2. Run hypothesis tests to check how well it describes gathered data.
  3. Repeat 1-3 if not well enough.

You can find interesting article describing how this can be done with open-source R software system here. I think especially useful to you may be function fitdistr.

share|improve this answer
add comment

In addition to already given answers consider Empirical Distributions. I have successful experience in using empirical distributions for performance analysis of several distributed systems. The idea is very straightforward. You need to build histogram of performance measurements. Measurements should be discretized with given accuracy. When you have histogram you could do several useful things:

  • calculate the probability of any given value (you are bound by accuracy only);
  • build PDF and CDF functions for the performance measurements;
  • generate sequence of response times according to a distribution. This one is very useful for performance modeling.
share|improve this answer
+1 for suggesting a non-parametric method. You might also consider a kernel-smoothing density estimator. –  Chris Taylor Jul 13 '12 at 12:15
add comment

Try whit gamma distribution http://en.wikipedia.org/wiki/Gamma%5Fdistribution

From wikipedia

The gamma distribution is frequently a probability model for waiting times; for instance, in life testing, the waiting time until death is a random variable that is frequently modeled with a gamma distribution.

share|improve this answer
add comment

The standard for randomized Arrival times for performance modelling is either Exponential distribution or Poisson distribution (which is just the distribution of multiple Exponential distributions added together).

share|improve this answer
Yeah, that makes sense for processes governed by hazard (inverse mean time between arrivals). For something like a computation which has, roughly, a particular amount of time it should take (as a function of input), I'm not sure how you should model the variations. –  Mike Dunlavey Mar 29 '10 at 21:27
add comment

Not exactly answering your question, but relevant still: Mor Harchol-Balter did a very nice analysis of the size of jobs submitted to a scheduler, The effect of heavy-tailed job size distributions on computer systems design (1999). She found that the size of jobs submitted to her distributed task assignment system took a power-law distribution, which meant that certain pieces of conventional wisdom she had assumed in the construction of her task assignment system, most importantly that the jobs should be well load balanced, had awful consequences for submitters of jobs. She's done good follor-up work on this issue.

The broader point is, you need to ask such questions as:

  1. What happens if reasonable-seeming assumptions about the distribution of performance, such as that they take a normal distribution, break down?
  2. Are the data sets I'm looking at really representative of the problem I'm trying to solve?
share|improve this answer
add comment

Your Answer


