Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include <grpc/support/histogram.h>
35 :
36 : #include <math.h>
37 : #include <stddef.h>
38 : #include <string.h>
39 :
40 : #include <grpc/support/alloc.h>
41 : #include <grpc/support/port_platform.h>
42 : #include <grpc/support/log.h>
43 : #include <grpc/support/useful.h>
44 :
45 : /* Histograms are stored with exponentially increasing bucket sizes.
46 : The first bucket is [0, m) where m = 1 + resolution
47 : Bucket n (n>=1) contains [m**n, m**(n+1))
48 : There are sufficient buckets to reach max_bucket_start */
49 :
50 : struct gpr_histogram {
51 : /* Sum of all values seen so far */
52 : double sum;
53 : /* Sum of squares of all values seen so far */
54 : double sum_of_squares;
55 : /* number of values seen so far */
56 : double count;
57 : /* m in the description */
58 : double multiplier;
59 : double one_on_log_multiplier;
60 : /* minimum value seen */
61 : double min_seen;
62 : /* maximum value seen */
63 : double max_seen;
64 : /* maximum representable value */
65 : double max_possible;
66 : /* number of buckets */
67 : size_t num_buckets;
68 : /* the buckets themselves */
69 : gpr_uint32 *buckets;
70 : };
71 :
72 : /* determine a bucket index given a value - does no bounds checking */
73 1950822 : static size_t bucket_for_unchecked(gpr_histogram *h, double x) {
74 1950822 : return (size_t)(log(x) * h->one_on_log_multiplier);
75 : }
76 :
77 : /* bounds checked version of the above */
78 1951008 : static size_t bucket_for(gpr_histogram *h, double x) {
79 1951008 : size_t bucket = bucket_for_unchecked(h, GPR_CLAMP(x, 1.0, h->max_possible));
80 1950825 : GPR_ASSERT(bucket < h->num_buckets);
81 1950825 : return bucket;
82 : }
83 :
84 : /* at what value does a bucket start? */
85 40086 : static double bucket_start(gpr_histogram *h, double x) {
86 40086 : return pow(h->multiplier, x);
87 : }
88 :
89 67 : gpr_histogram *gpr_histogram_create(double resolution,
90 : double max_bucket_start) {
91 67 : gpr_histogram *h = gpr_malloc(sizeof(gpr_histogram));
92 67 : GPR_ASSERT(resolution > 0.0);
93 67 : GPR_ASSERT(max_bucket_start > resolution);
94 67 : h->sum = 0.0;
95 67 : h->sum_of_squares = 0.0;
96 67 : h->multiplier = 1.0 + resolution;
97 67 : h->one_on_log_multiplier = 1.0 / log(1.0 + resolution);
98 67 : h->max_possible = max_bucket_start;
99 67 : h->count = 0.0;
100 67 : h->min_seen = max_bucket_start;
101 67 : h->max_seen = 0.0;
102 67 : h->num_buckets = bucket_for_unchecked(h, max_bucket_start) + 1;
103 67 : GPR_ASSERT(h->num_buckets > 1);
104 67 : GPR_ASSERT(h->num_buckets < 100000000);
105 67 : h->buckets = gpr_malloc(sizeof(gpr_uint32) * h->num_buckets);
106 67 : memset(h->buckets, 0, sizeof(gpr_uint32) * h->num_buckets);
107 67 : return h;
108 : }
109 :
110 67 : void gpr_histogram_destroy(gpr_histogram *h) {
111 67 : gpr_free(h->buckets);
112 67 : gpr_free(h);
113 67 : }
114 :
115 1950704 : void gpr_histogram_add(gpr_histogram *h, double x) {
116 1950704 : h->sum += x;
117 1950704 : h->sum_of_squares += x * x;
118 1950704 : h->count++;
119 1950704 : if (x < h->min_seen) {
120 3996 : h->min_seen = x;
121 : }
122 1950704 : if (x > h->max_seen) {
123 4975 : h->max_seen = x;
124 : }
125 1950704 : h->buckets[bucket_for(h, x)]++;
126 1950823 : }
127 :
128 30 : int gpr_histogram_merge(gpr_histogram *dst, const gpr_histogram *src) {
129 58 : if ((dst->num_buckets != src->num_buckets) ||
130 28 : (dst->multiplier != src->multiplier)) {
131 : /* Fail because these histograms don't match */
132 2 : return 0;
133 : }
134 28 : gpr_histogram_merge_contents(dst, src->buckets, src->num_buckets,
135 : src->min_seen, src->max_seen, src->sum,
136 : src->sum_of_squares, src->count);
137 28 : return 1;
138 : }
139 :
140 34 : void gpr_histogram_merge_contents(gpr_histogram *dst, const gpr_uint32 *data,
141 : size_t data_count, double min_seen,
142 : double max_seen, double sum,
143 : double sum_of_squares, double count) {
144 : size_t i;
145 34 : GPR_ASSERT(dst->num_buckets == data_count);
146 34 : dst->sum += sum;
147 34 : dst->sum_of_squares += sum_of_squares;
148 34 : dst->count += count;
149 34 : if (min_seen < dst->min_seen) {
150 22 : dst->min_seen = min_seen;
151 : }
152 34 : if (max_seen > dst->max_seen) {
153 23 : dst->max_seen = max_seen;
154 : }
155 80724 : for (i = 0; i < dst->num_buckets; i++) {
156 80690 : dst->buckets[i] += data[i];
157 : }
158 34 : }
159 :
160 20049 : static double threshold_for_count_below(gpr_histogram *h, double count_below) {
161 : double count_so_far;
162 : double lower_bound;
163 : double upper_bound;
164 : size_t lower_idx;
165 : size_t upper_idx;
166 :
167 20049 : if (h->count == 0) {
168 0 : return 0.0;
169 : }
170 :
171 20049 : if (count_below <= 0) {
172 4 : return h->min_seen;
173 : }
174 20045 : if (count_below >= h->count) {
175 2 : return h->max_seen;
176 : }
177 :
178 : /* find the lowest bucket that gets us above count_below */
179 20043 : count_so_far = 0.0;
180 629735 : for (lower_idx = 0; lower_idx < h->num_buckets; lower_idx++) {
181 629735 : count_so_far += h->buckets[lower_idx];
182 629735 : if (count_so_far >= count_below) {
183 20043 : break;
184 : }
185 : }
186 20043 : if (count_so_far == count_below) {
187 : /* this bucket hits the threshold exactly... we should be midway through
188 : any run of zero values following the bucket */
189 34 : for (upper_idx = lower_idx + 1; upper_idx < h->num_buckets; upper_idx++) {
190 34 : if (h->buckets[upper_idx]) {
191 3 : break;
192 : }
193 : }
194 6 : return (bucket_start(h, (double)lower_idx) +
195 3 : bucket_start(h, (double)upper_idx)) /
196 : 2.0;
197 : } else {
198 : /* treat values as uniform throughout the bucket, and find where this value
199 : should lie */
200 20040 : lower_bound = bucket_start(h, (double)lower_idx);
201 20040 : upper_bound = bucket_start(h, (double)(lower_idx + 1));
202 20040 : return GPR_CLAMP(upper_bound -
203 : (upper_bound - lower_bound) *
204 : (count_so_far - count_below) /
205 : h->buckets[lower_idx],
206 : h->min_seen, h->max_seen);
207 : }
208 : }
209 :
210 20049 : double gpr_histogram_percentile(gpr_histogram *h, double percentile) {
211 20049 : return threshold_for_count_below(h, h->count * percentile / 100.0);
212 : }
213 :
214 4 : double gpr_histogram_mean(gpr_histogram *h) {
215 4 : GPR_ASSERT(h->count != 0);
216 4 : return h->sum / h->count;
217 : }
218 :
219 2 : double gpr_histogram_stddev(gpr_histogram *h) {
220 2 : return sqrt(gpr_histogram_variance(h));
221 : }
222 :
223 4 : double gpr_histogram_variance(gpr_histogram *h) {
224 4 : if (h->count == 0) return 0.0;
225 8 : return (h->sum_of_squares * h->count - h->sum * h->sum) /
226 4 : (h->count * h->count);
227 : }
228 :
229 15 : double gpr_histogram_maximum(gpr_histogram *h) { return h->max_seen; }
230 :
231 15 : double gpr_histogram_minimum(gpr_histogram *h) { return h->min_seen; }
232 :
233 21 : double gpr_histogram_count(gpr_histogram *h) { return h->count; }
234 :
235 15 : double gpr_histogram_sum(gpr_histogram *h) { return h->sum; }
236 :
237 15 : double gpr_histogram_sum_of_squares(gpr_histogram *h) {
238 15 : return h->sum_of_squares;
239 : }
240 :
241 12 : const gpr_uint32 *gpr_histogram_get_contents(gpr_histogram *h, size_t *size) {
242 12 : *size = h->num_buckets;
243 12 : return h->buckets;
244 : }
|
