| 1 |
// Copyright 2025 Google LLC |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
package distribution |
| 16 |
|
| 17 |
import ( |
| 18 |
"log" |
| 19 |
"math" |
| 20 |
"sort" |
| 21 |
"sync" |
| 22 |
"sync/atomic" |
| 23 |
) |
| 24 |
|
| 25 |
// D is a distribution. Methods of D can be called concurrently by multiple |
| 26 |
// goroutines. |
| 27 |
type D struct { |
| 28 |
buckets []uint64 |
| 29 |
// sumsReuse is the scratch space that is reused |
| 30 |
// to store sums during invocations of Percentile. |
| 31 |
// After an invocation of New(n): |
| 32 |
// len(buckets) == len(sumsReuse) == n |
| 33 |
sumsReuse []uint64 |
| 34 |
mu sync.Mutex |
| 35 |
} |
| 36 |
|
| 37 |
// New creates a new distribution capable of holding values from 0 to n-1. |
| 38 |
func New(n int) *D { |
| 39 |
return &D{ |
| 40 |
buckets: make([]uint64, n), |
| 41 |
sumsReuse: make([]uint64, n), |
| 42 |
} |
| 43 |
} |
| 44 |
|
| 45 |
// Record records value v to the distribution. |
| 46 |
// To help with distributions with long tails, if v is larger than the maximum value, |
| 47 |
// Record records the maximum value instead. |
| 48 |
// If v is negative, Record panics. |
| 49 |
func (d *D) Record(v int) { |
| 50 |
if v < 0 { |
| 51 |
log.Panicf("Record: value out of range: %d", v) |
| 52 |
} else if v >= len(d.buckets) { |
| 53 |
v = len(d.buckets) - 1 |
| 54 |
} |
| 55 |
atomic.AddUint64(&d.buckets[v], 1) |
| 56 |
} |
| 57 |
|
| 58 |
// Percentile computes the p-th percentile of the distribution where |
| 59 |
// p is between 0 and 1. This method may be called by multiple goroutines. |
| 60 |
func (d *D) Percentile(p float64) int { |
| 61 |
// NOTE: This implementation uses the nearest-rank method. |
| 62 |
// https://en.wikipedia.org/wiki/Percentile#The_nearest-rank_method |
| 63 |
|
| 64 |
if p < 0 || p > 1 { |
| 65 |
log.Panicf("Percentile: percentile out of range: %f", p) |
| 66 |
} |
| 67 |
|
| 68 |
d.mu.Lock() |
| 69 |
defer d.mu.Unlock() |
| 70 |
|
| 71 |
var sum uint64 |
| 72 |
for i := range d.sumsReuse { |
| 73 |
sum += atomic.LoadUint64(&d.buckets[i]) |
| 74 |
d.sumsReuse[i] = sum |
| 75 |
} |
| 76 |
|
| 77 |
target := uint64(math.Ceil(float64(sum) * p)) |
| 78 |
return sort.Search(len(d.sumsReuse), func(i int) bool { return d.sumsReuse[i] >= target }) |
| 79 |
} |