Debian Codegraph @

pubsub/v2/internal/distribution/distribution.go

raw
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 }