google / google/caliper

Add useful summary statistics to the webapp

Open
#200 0 comments 0 reactions 0 assignees View on GitHub
component: web ui P4 type=enhancement
Dominant language
Java
Stars
818
Forks
112
Avg merge
12m
Merged PRs (30d)
5

Description

```
There are two issues with variance computation in Caliper.

1. Incorrect normalization. This is sample variance, so it should be divided by
(n-1) instead of (n). When n is small, such as 3, this makes a huge difference!
This may in turn lead to incorrect short circuits!

2. It suffers from catastrophic cancellation in the computation. The formula

(sumOfSquaresOfLastN / size()) - squared(mean())

will return incorrect results when the mean is signficantly different from 0,
and the standard deviation is significantly smaller than the mean (which should
be the case for reasonable benchmarks!).

In the worst case, you may even see a negative variance.

See this page for details, or Knuth if you prefer:

https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance

Since "n" is small (say, less than 1000, fits in memory easily), I actually
recommend just doing the two-pass approach!

Here's a modified code:

---
public double mean() {
double sum = 0;
for (int i = size() - 1; i >= 0; i--) {
sum += lastN[i];
}
return sum / size();
}

public double variance() {
final double m = mean();
double sum = 0;
// Note: this is numerically more stable than E(X*X)-E(X)*E(X)!
for (int i = size() - 1; i >= 0; i--) {
sum += squared(lastN[i] - m);
}
return sum / (size() - 1);
}

---

Maybe also consider using the median instead of the mean.

Here is an example run before:

0% Scenario{vm=java, trial=0, ...} 97520,99 ns; σ=2484,44 ns @ 10 trials
20% Scenario{vm=java, trial=1, ...} 93689,45 ns; σ=775,55 ns @ 3 trials
40% Scenario{vm=java, trial=2, ...} 91320,40 ns; σ=1171,48 ns @ 10 trials
60% Scenario{vm=java, trial=3, ...} 90497,03 ns; σ=507,98 ns @ 3 trials
80% Scenario{vm=java, trial=4, ...} 91625,80 ns; σ=2577,81 ns @ 10 trials

Note A) the large differences in standard deviation, and B) it's either 3 or 10
trials.

Afterwards:

0% Scenario{vm=java, trial=0, ...} 91669,36 ns; σ=502,03 ns @ 3 trials
20% Scenario{vm=java, trial=1, ...} 95936,66 ns; σ=398,25 ns @ 3 trials
40% Scenario{vm=java, trial=2, ...} 90981,60 ns; σ=834,11 ns @ 4 trials
60% Scenario{vm=java, trial=3, ...} 91487,95 ns; σ=362,09 ns @ 3 trials
80% Scenario{vm=java, trial=4, ...} 94000,82 ns; σ=920,91 ns @ 6 trials

Note how now the standard deviations are much more stable, and the
short-circuit rule also was able to kick in at other situations than 3 and 10?
```

Original issue reported on code.google.com by `erich.sc...@gmail.com` on 16 Jan 2013 at 3:27

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.