1 // Copyright 2017 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 } 80