Overhead redux (questioning #178)

[patrickdoc]

While the change made by #178 did fix the problems of #160, #161, and #162, the overhead code was not necessarily incorrect.

For reference, here is the central sampling loop:
https://github.com/bos/criterion/blob/52ef4a7699237a8952475146c51fc5d8ebff5876/Criterion/Measurement.hs#L270-L293

This code is going to come up a few times, so here are the highlights of what the loop does,

• For each Int i in the list of iters, run the function to be benchmarked i times
• measure returns a pair (Measured, Double) of data and the time at the end of the benchmark
• There are then three conditions that are checked
  1. Have we used up our suggested time? (endTime - start >= timeLimit, default is 5 seconds)
  2. Do we have at least 10 * threshold seconds of quality data? (tracked by overThresh and prev, default is 300 ms)
  3. Do we have at least 4 Measured values with runtime greater than the threshold? (tracked by count, a subset of acc, default 30 ms)
• Loop until all conditions are true

The list of iterations passed to the loop is effectively iterate (*1.05) 1, where elements are truncated to be Ints. (This eventually come up in another issue :P)

---

Using this, there is a simple explanation of the three issues listed above. The third condition above is counting samples that can be passed to the bootstrap in Criterion.Analysis.analyseSample. There, samples with runtime greater than 30 ms are passed in stime to the bootstrap analysis. By the condition, we should have at least 4. However, before being filtered, they are adjusted for overhead.

The loop guarantees 4 good bootstrap samples, but after adjusting for overhead, they could be below the threshold. That's how the check is circumvented.

---

Regarding the correctness of overhead, it's hard to say. Some quick runs on my computer reported an overhead of 150-200ms. This value is clearly wrong as ~90% of the measurements take less time than that. On the other hand this program

main = do
    start <- getTime
    end <- getTime
    print $ end - start

reports at least 20 ns.

I think my conclusion is that removing the overhead code was the right choice. But it should be eventually reintroduced. I think the overhead is actually closer to about 2 microseconds, but measure is returning some inconsistent values in the getOverhead code. And at that small a value, statistics should smooth out the final report.

---

This issue hopefully will be a useful reference for how the loop function works because I have some more I want to say about it (sorry :/ there is a real tangle of minor weirdnesses happening).

To actually make a point though, getOverhead was broken, we were probably right to remove it, it should be reintroduced when we can get a consistent and accurate reading. To that end, a "ground truth" timing would be really nice. Although that might require some GHC or assembly hacking :P

[RyanGlScott]

What is the current status of this, @patrickdoc?

[patrickdoc]

I think we can close this. As with #179, this is covered by the GC changes. I opened this because the Sample is empty issue persisted after removing overhead. But that was only because we were generating so few samples. Now that things are running smoothly, the small loop issues don't apply.

Additionally, linear regression naturally accounts for overhead. The stats are only returning the slope of the line. You can see the overhead (the y-intercept) if you pass --regress time:iters or any other pair on the command line.

[RyanGlScott]

Great! Do you think there are any others issues that would be blocking a new release?

[patrickdoc]

I've been reviewing tickets today, and I don't think so. All the other ideas I had are pretty much worthless after the GC change, so I think I am basically done.

I would be willing to help with some of the documentation tickets, but there isn't really a clear place to contribute to. If you point me, I can at least cover some of the implementation details.

[RyanGlScott]

I'm not sure which tickets you had in mind, but an issue like #69 would be quite doable, for instance—it simply requests some additional info be inserted into the HTML tutorial, the source for which is located here.

[patrickdoc]

I was thinking more like #95, but I can do that too.

[RyanGlScott]

As far as where to put documentation, I would generally lean towards finding the most relevant function's Haddocks and putting it there (#69 being an exception, of course, since someone specifically requested that the tutorial be amended). At least that way we have an easily linkable location in case we need to refer to it in other places.

[patrickdoc]

Sounds good