# The Eministat library
Suppose you have two data sets, obtained from benchmarks of programs. The `eministat` library then computes basic statistical properties of the data sets and reports these on stdout. It can be used from the Erlang shell to verify that two samples are different according the the student's t-test.
## Acknowledgements
This program owes everything to Poul-Henning Kamp and his `ministat` application for FreeBSD, which was the first inspiration. It also draw a lot on Bryan O'Sullivan's Criterion benchmark suite of Haskell fame. Finally, it uses some ideas by Brent Boyer for computing outlier variance.
# Examples
Suppose you have measured the leaf thickness in (μs) of a Ligustrum, one in the sun and one in the shade. You wonder if there is any measurable difference between these two data sets. This is the question `eministat` can answer:
7> eministat:x(95.0, Sun, Shade).
x sun
+ shade
+--------------------------------------------------------------------------+
|x + + + x + + * x x|
| + x x|
| |__________________________A__________________________| |
| |___________AM___________| |
+--------------------------------------------------------------------------+
Dataset: x N=7 CI=95.0000
Statistic Value [ Bias] (Bootstrapped LB‥UB)
Min: 100.000
1st Qu. 150.000
Median: 210.000
3rd Qu. 210.000
Max: 300.000
Average: 210.000 [ 0.144571] ( 158.571 ‥ 258.571)
Std. Dev: 73.0297 [ -6.93032] ( 46.0848 ‥ 101.770)
Outliers: 0/0 = 0 (μ=210.145, σ=66.0994)
Outlier variance: 0.843583 (severe, the data set is probably unusable)
------
Dataset: + N=7 CI=95.0000
Statistic Value [ Bias] (Bootstrapped LB‥UB)
Min: 120.000
1st Qu. 125.000
Median: 160.000
3rd Qu. 170.000
Max: 200.000
Average: 157.857 [ -0.137286] ( 135.714 ‥ 182.857)
Std. Dev: 34.1391 [ -3.10808] ( 23.4267 ‥ 41.9041)
Outliers: 0/0 = 0 (μ=157.720, σ=31.0310)
Outlier variance: 0.555845 (severe, the data set is probably unusable)
No difference proven at 95.0% confidence
------
ok
This means for the 7 samples of each Ligustrum, the null hypothesis failed to be rejected, so for this data set, there is no significant difference. Either collect more samples, or be satisfied with the result.
In programming, we typically measure the performance of different algorithms and pick "the best". But looks can be deceiving. We could wonder if `lists:reverse/1` is faster than tail-recursive reverse variant
tail_reverse(L) -> tail_reverse(L, []).
tail_reverse([], Acc) -> Acc;
tail_reverse([X | Xs], Acc) -> tail_reverse(Xs, [X | Acc]).
which may or may not be true. We can use the `eministat:s/3` function to sample The above:
L = lists:seq(1, 100000),
Rev2 = eministat:s("tail_reverse/1", fun() -> tail_reverse(L) end, 50).
This will sample 50 runs of our `tail_reverse/1` function. Likewise, we can grab the output of `lists:reverse/1`:
Rev1 = eministat:s("lists:reverse/1", fun() -> lists:reverse(L) end, 50).
And finally, we can ask `eministat` if there is any difference between the data sets:
8> Rev1 = eministat_ts:reverse_1().
{dataset,"lists:reverse/1",
[3078,3085,3095,3096,3110,3126,3142,3239,3272,3513],
31756.0,101009964.0,10}
9> Rev2 = eministat_ts:reverse_2().
{dataset,"tail_reverse/1",
[4104,4140,4155,4157,4161,4173,4185,4189,4191,4192,4197,
4203,4213,4225,4461],
62946.0,264234764.0,15}
10> eministat:x(95.0, Rev1, Rev2).
x lists:reverse/1
+ tail_reverse/1
+--------------------------------------------------------------------------+
| xxxx x x x + +++++ +|
| xxx ++++ |
| + + |
| + |
| + |
||___M__A______| |
| |___A___| |
+--------------------------------------------------------------------------+
Dataset: x N=10 CI=95.0000
Statistic Value [ Bias] (Bootstrapped LB‥UB)
Min: 3078.00
1st Qu. 3095.00
Median: 3110.00
3rd Qu. 3239.00
Max: 3513.00
Average: 3175.60 [ 0.593130] ( 3118.60 ‥ 3297.30)
Std. Dev: 135.651 [ -14.7128] ( 61.9459 ‥ 216.422)
Outliers: 0/1 = 1 (μ=3176.19, σ=120.938)
Outlier variance: 9.14370e-2 (slight)
------
Dataset: + N=15 CI=95.0000
Statistic Value [ Bias] (Bootstrapped LB‥UB)
Min: 4104.00
1st Qu. 4157.00
Median: 4189.00
3rd Qu. 4197.00
Max: 4461.00
Average: 4196.40 [ 7.09000e-2] ( 4170.67 ‥ 4260.60)
Std. Dev: 79.3589 [ -9.85382] ( 26.3869 ‥ 143.088)
Outliers: 0/1 = 1 (μ=4196.47, σ=69.5050)
Outlier variance: 6.22222e-2 (slight)
Difference at 95.0% confidence
1020.80 ± 88.7257
32.1451% ± 2.79398%
(Student's t, pooled s = 105.042)
------
ok
In this case, we are told there is a significant difference between the two runs of about 1020.80μs, with an uncertainty of about 89μs. Hence we can rely on the call to `lists:reverse/1` being faster than a tail recursive variant for lists of size `100000`.
Both datasets have 1 outlier, which are values far from the mean. An analysis also shows the analysis unlikely to be affected by outliers, as the variance is only slight.
# Usage
To use `eministat`, your data must be normally distributed, and both
datasets must have the same variance. If they are not, then the
student's t method doesn't really work as expected, and one must use
more powerful tools, such as R, to analyze the data set. You will have
to make a reasonable guess that they are, before you can use the
mathematics. Once you know that to be the case, you can use
`eministat` to analyze your data sets.
The `eministat` application supports 3 major functions:
DataSet = eministat_ds:from_list(Name, DataPoints),
will construct a new data set from a list of already measured data points.
The function `s/3` can be used to sample
DataSet = eministat:s(Name, Function, N)
will run `Function` `N` times and collect the run-time in microseconds for each sample. It will then stuff the resulting data points into a dataset with `Name`. The s/3 function will first warm up by running the test for 3 seconds before actually starting to measure. This avoids numerous problems with CPU frequency scaling. It also garbage collects before each measurement.
Finally, to analyze two data sets or more, use the `x/3` function
eministat:x(ConfidenceLevel, DataSet1, DataSet2), %% or
eministat:x(ConfidenceLevel, BaseSet, [DataSet, …]),
where the `ConfidenceLevel` is one of `[80.0, 90.0, 95.0, 98.0, 99.0, or 99.5]`. The output is as above on stdout.
# Description of the output
The `eministat` output contains 4 sections:
HISTOGRAM
For each dataset:
VITALS
OUTLIER ANALYSIS
STUDENT'S T
## HISTOGRAM
x lists:reverse/1
+ tail_reverse/1
+--------------------------------------------------------------------------+
| xxxx x x x + +++++ +|
| xxx ++++ |
| + + |
| + |
| + |
||___M__A______| |
| |___A___| |
+--------------------------------------------------------------------------+
The histogram part shows you an overview of the data distribution in ASCII art. In this case, there are two data sets, `+` and `x` and for each value in the data set, they are plotted in ASCII ,so you can see the distribution. If points are overlapping, a `*` would be printed in the diagram. Below the distribution plot, you have two bars, one for each dataset. The `M` and `A` are the median and average/mean respectively. In the case of the 2nd dataset, the median and average are at the same point, so only the `A` is plotted. The part with `|____…____|` signifies 1 standard deviation assuming a normally distributed data set.
## VITALS
Dataset: x N=10 CI=95.0000
Statistic Value [ Bias] (Bootstrapped LB‥UB)
Min: 3078.00
1st Qu. 3095.00
Median: 3110.00
3rd Qu. 3239.00
Max: 3513.00
Average: 3175.60 [ 0.593130] ( 3118.60 ‥ 3297.30)
Std. Dev: 135.651 [ -14.7128] ( 61.9459 ‥ 216.422)
This part notes the vitals of the dataset in question. `N` is the number of observations, `CI` is the set confidence interval. Then follows a standard statistical summary of the data set: Min, Max, Median, Quartiles. The average (mean) of the data set is computed as well as the standard deviation.
In order to be more precise than a single point estimate, we also provide *intervals* for the average and standard deviation with a lower bound and an upper bound. That is, rather than telling you the mean is 3175 as a point, `eministat` tells you that the mean obtained from this particular sample is the interval 3118‥3297.
It is important to stress that the procedure for computing the interval uses a 95% confidence (it is configurable). This does *not* mean that there is a 95% chance the interval contains the true population mean. The true mean is an unknown and no procedure can divine what it is. Rather the 95% refers to the *configuration* of the interval estimation procedure: if you were to repeat this experiment thousands of times, and you would compute a (different) confidence interval for each of those thouand samples, then it would tend to be the case that 95% of those intervals would contain the true population mean.
The system uses a bias-corrected accelerated bootstrap method to compute the bounds on the interval. It also computes the bias from the bootstrap to the sample parameter. In the above example, you see the bias of -14 in the std. deviation which means that the bootstrap procedure usually obtains a smaller standard deviation than the sample's estimate.
## OUTLIERS
Outliers: 0/1 = 1 (μ=3176.19, σ=120.938)
Outlier variance: 9.14370e-2 (slight)
We use a simple criterion for outliers. Define `IQR = Q3 - Q1` to be the interquartile range. Then any point which is further away from the mean than 1.5IQR is deemed an outlier. We report those as `Lower/Upper` where lower outliers are below the mean and upper outliers are above the mean.
We also compute outlier variance, which is a measurement of how likely it is the case the outliers are affecting the result of the computation. The range is `unaffected‥slight‥moderate‥severe`. In the case of severe variance, it is worth looking at if you can improve the sampling to avoid it.
Common problems are garbage collection, CPU frequency scaling, other work being done on the benchmarking machine as a background task, or other kinds of interference.
## STUDENT's T
Difference at 95.0% confidence
1020.80 ± 88.7257
32.1451% ± 2.79398%
(Student's t, pooled s = 105.042)
This section only makes sense given the following rules:
* The datasets are normally distributed, or tend to be
* The datasets have equal variance
Assuming we have 2 or more datasets, we are running a 2-sample Student's T-test pairing the first set against each of the other sets. If the two datasets are far apart, then we have significance that the two data sets are really different. But in the case where the two data sets overlap a lot, then it is not a priori given the two datasets differ, as we saw in the example of the ligustrum experiment above.
We report a series of numbers: the difference in the means ± the interval for the Student's T-test.
In general, you have to pass this test for your measurements to have any meaning when comparing two benchmarks. Otherwise, the overlap in runtime is such that there is little reason to believe one way of solving the problem is faster than the other.
