Add histogram and kde measurements and js displays

lyrm commented 3 years ago

What it is about

This PR adds probability density functions for measurements to bechamel. Displaying such functions enables to visualize modes i.e. the different values around which measurements are centered. Two different ways to display such function are proposed here:

a histogram
kernel density estimation (KDE).

One major difficulty with these charts is to determine their "granularity" i.e. the barwidth or the bandwidth. Several methods can be used to compute the optimal values of these parameters but the related hypotheses are often very restrictive. As an alternative, I chose here to let the user control these parameters. This way, it enables them to see the raw distribution of the measurements and also to search manually for an optimal value and get close to the estimate distribution.

Why not use oLS/ransac measurements

To display such charts, it is necessary to collected more data. We want to display a probability density function so we need these data to have the right statistic properties meaning we can't use the measurement collected for oLS/ransac analysis: indeed, each of these samples is taken for a different number of runs. If we use these measurements weighted by this number, we get variables with the right averaged value but a different standard deviation.

What we need are measurements taken for a single run. This can be an issue if these measurements are very small (compared to what it takes to acquire the measurement itself). In other words, the additions proposed in this PR aren't good for "true" micro-benchmarking. It is still quite useful for larger functions, like hash functions.

What I actually added

Additional measurements

`Benchmarks` module

First main change, the outputs of Benchmark.run and Benchmark.all need now to include optional measurements for kde. It is now defined by a type:

type t = {
   stats : stats;
   lr : Measurement_raw.t array;
   kde : Measurement_raw.t array option; 
}

Then , to choose to acquired such data, the cfg has a new optional parameter kde: int option (default None): if it is Some n, n measurements are acquired (each for a single function execution).

`Analyze` module

The changes in this module simply takes into account the output type change of the Benchmark functions.

`Bechamel_js` module

Here, I simply added one additional and optional field kde to the json output depending on the value of the Benchmark.kde field in the benchmarks results.

Histogram/KDE displays

Most of the changes are actually here, in the js file.

File structure et script

To be able to maintain it properly, I chose to separate the css and js for the initial html file. Right now, the index.html file used a with_data.js file, that the user need to be built using Benchamel-html. So basically, the script is something like that:

 dune exec src/main.exe > html/output.json
 dune exec bin/bechamel-html/bechamel_html.exe < html/output.json > html/with_data.js

It is obviously something that could be improved.

Various info and features

the kernel function used to compute KDE is a gaussian function
if there is no kde data, the display uses a one column layout, and a two columns layout otherwise
value of an histogram bar is written when the mouse passes over.

Summarize bargraph

I also added a summarize bargraph at the top of the page. It seemed useful to collect all the estimated value of each benchmarks in a single chart. Like for the other histograms, it is possible to see the value of each bar by passing the mouse over it.

Some words about `criterion`

The inspiration for KDE charts originally came for the haskell benchmarking library [criterion](https://github.com/bos/criterion). However, they use the same data for both charts and the bandwidth is computed using the rule of thumb approximation which is wrong for multi-modal densities.

TODO list

`Notty` module

I did not look at the notty part of bechamel, that most probably requires some changes to take into account the change in the type of the Benchmark.all and Benchmark.run function.

`Bechamel-html` (DONE)

~~Make it produce a single html file that combines the index.html, output.json, style.css and without_data.js files.~~

Future improvements

~~axis titles for hist/kde charts~~
add some zoom features (be able to change axis ranges)
add information table below histogram/kde charts with standard deviation
add standard deviation display in summarize graph (if it is possible to compute the standard deviation value)

dinosaure commented 3 years ago

I look quickly the code and it seems good :+1:.

Make it produce a single html file that combines the index.html, output.json, style.css and without_data.js files.

This is my strongest requirement before merging. notty is not a big deal but I really would like to a single standalone generated HTML file :+1:.

dinosaure commented 3 years ago

Ready to merge, I will fix on my side the test suite.

mirage / bechamel