Quantile: significant performance improvements

[cespare]

I started by adding more benchmarks to hit a variety of scenarios:

• Both targeted and biased streams
• Smaller epsilon (for a larger internal sample list -- important because one of the improvements was to remove container/list)
• Querying

Then I made three different changes. Each of those commits includes intermediate benchmark output.

Here's the final result:

benchmark                               old ns/op     new ns/op     delta
BenchmarkQuery                          691           97.5          -85.89%
BenchmarkQuerySmallEpsilon              44491         6500          -85.39%
BenchmarkInsertBiasedSmallEpsilon       2641          914           -65.39%
BenchmarkInsertTargetedSmallEpsilon     1016          442           -56.50%
BenchmarkInsertBiased                   324           172           -46.91%
BenchmarkInsertTargeted                 294           171           -41.84%

[bmizerany]

Whoa. How did I miss this for so long? I'm sorry. Merging.

[cespare]

Thanks :) Nice meeting you yesterday btw

[bmizerany]

Hrm. I'm getting test failures:

$ go test ./...
ok      github.com/bmizerany/perks/histogram    0.221s
--- FAIL: Example_simple (21.423106ms)
got:
perc50: 5
perc90: 17
perc99: 221
count: 2388
want:
perc50: 5
perc90: 14
perc99: 40
count: 2388
FAIL
FAIL    github.com/bmizerany/perks/quantile 1.422s
ok      github.com/bmizerany/perks/topk 1.732s

[bmizerany]

@cespare any development on the above?

[cespare]

Sorry for the test failure; I must've gotten too caught up in the benchmarks and forgotten to run the tests.

I dug into this for a few hours yesterday. The problem is in the list -> slice conversion, but it proved surprisingly hard to figure out where the logic in my version differs. I had to give up on it last night but I'll get back to it tonight or tomorrow and come back with a fixed version.

[bmizerany]

Np. Let me know if you find anything.

[cespare]

Fixed. It was an off-by-one error on my end. I rebased the fixed commits and re-ran the benchmarks.

PTAL

[bmizerany]

LGTM. Great work!!!!

[ryandotsmith]

:thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: :thumbsup: