pMax value is "quantized" and can be the same between similar sets of data, which looks suspicious

[RaduBerinde]

See 95df80c for a reproduction.

var pmaxSampleParams = Params{Lo: 1_000, Hi: 10e9, ErrorBound: 0.10}

=== RUN   TestPMaxQuantization
    pmax_test.go:137: set A (n=38357)
    pmax_test.go:138:                exact   estimated     error
    pmax_test.go:144:   p50        0.072ms     0.072ms     +0.3%
    pmax_test.go:144:   p90        0.485ms     0.481ms     -0.9%
    pmax_test.go:144:   p99        8.843ms     9.080ms     +2.7%
    pmax_test.go:144:   p99.9     16.059ms    16.558ms     +3.1%
    pmax_test.go:144:   pMax      33.956ms    39.903ms    +17.5%
    pmax_test.go:137: set B (n=13355)
    pmax_test.go:138:                exact   estimated     error
    pmax_test.go:144:   p50        0.064ms     0.064ms     +0.7%
    pmax_test.go:144:   p90        0.128ms     0.128ms     +0.5%
    pmax_test.go:144:   p99       16.740ms    16.701ms     -0.2%
    pmax_test.go:144:   p99.9     20.462ms    21.313ms     +4.2%
    pmax_test.go:144:   pMax      34.440ms    39.903ms    +15.9%
    pmax_test.go:167: true maxima differ by 0.484ms but both report pMax=39.903ms

[angles-n-daemons]

Couple of notes on this:

• The error delta seems to violate the error bound.
• Reporting the midpoint of the bucket would respect the error bound, but could theoretically underestimate max values (do we care?)
• If we store the absolute max, we'd also probably need capture the absolute min, and check / update them in the hotpath. Might need careful weighing there.

[RaduBerinde]

If we store the absolute max, we'd also probably need capture the absolute min, and check / update them in the hotpath. Might need careful weighing there.

Not sure the min is that useful in practice. Note that the hot path could look something like:

if idx == h.cfg.numBuckets-1 && x > maxVal.Load() {
   // .. compare and swap loop
}

The inner path will be very rare; the hot path will be just an extra load only when we end up in the last bucket.