Consider adding high-precision microbenchmarks for small sequences

[ldionne]

Forking #124 to discuss high precision microbenchmarks for small inputs more precisely. The idea is that we'd like to have a precise view of the behavior of algorithms on small sequences, because this is how they are mostly (but not only) used in the wild. I see two different approaches:

1. For each sequence length N, generate K different sequences of length N and call the algorithm once on each sequence. By having a sufficiently large K, the total compilation time is increased and the relative error is reduced.
2. Same as (1), but then divide the result by K to find an approximation of the absolute time taken for a single algorithm. I have reservations with this approach, because the compilation time as we increase K (the number of small sequences) is not necessarily linear.

[brunocodutra]

Would K be constant for all N for a given algorithm? If so, I'd be ok with the first option. If not I think we would have to stick with the second one, because otherwise charts would be non-intuitive to the viewer.

Edit: Just to clarify, since the overhead already decreases for larger N so that a smaller K would be enough, having K decrease with the increase of N would have the benefit of keeping build times reasonably short. This is quite obvious when you look at benchmarks that take over a second for N > 100, where the noise basically disappears even on travis.

[ldionne]

Would K be constant for all N for a given algorithm?

We can choose to go either way. I agree that decreasing K as N increases would help keep the build times short and having a large K for large Ns would not be useful. However, I'm unclear on how we would specify which K to associate to which N.

[brunocodutra]

I'm unclear on how we would specify which K to associate to which N

I believe choosing K so that K*N = <some constant> should be good enough.

We can choose to go either way.

So let us take a step at a time. Since the first option is basically a special case of the second one, why don't we implement 1. and then, if necessary, refine it into 2.?

[ldionne]

So let us take a step at a time. Since the first option is basically a special case of the second one, why don't we implement 1. and then, if necessary, refine it into 2.?

Sounds good. That raises (at least) one question: do we want to tweak the existing benchmarks so that they have higher precision for smaller sequences, or do we want to create a new set of benchmarks for "small sequences"? The first option would obviously be better if that can be done, but that might end up taking too much Travis time, depending on how smart we can be.

[brunocodutra]

do we want to tweak the existing benchmarks so that they have higher precision for smaller sequences, or do we want to create a new set of benchmarks for "small sequences"?

I'd say a bit of both, reduce the maximum size of sequences, so that we don't abuse travis too much, and make sure all measurements are precise enough, so that results don't vary that much across runs. As for a number, @ericniebler suggested we focused on < 100 elements. I have no strong opinion about this, but I think it's a reasonable suggestion.

I'm just not very comfortable with the idea of fine tuning K for each algorithm heuristically until results "look good", but I'm afraid we have no better way?

[ldionne]

I don't see a better way either.

[ldionne]

This has been resolved by #150.