1 | /** |
2 | * hdr_histogram.c |
3 | * Written by Michael Barker and released to the public domain, |
4 | * as explained at http://creativecommons.org/publicdomain/zero/1.0/ |
5 | */ |
6 | |
7 | #include <stdlib.h> |
8 | #include <stdbool.h> |
9 | #include <math.h> |
10 | #include <stdio.h> |
11 | #include <string.h> |
12 | #include <stdint.h> |
13 | #include <errno.h> |
14 | #include <inttypes.h> |
15 | |
16 | #include "hdr_histogram.h" |
17 | #include "hdr_tests.h" |
18 | #include "hdr_atomic.h" |
19 | |
20 | #ifndef HDR_MALLOC_INCLUDE |
21 | #define HDR_MALLOC_INCLUDE "hdr_malloc.h" |
22 | #endif |
23 | |
24 | #include HDR_MALLOC_INCLUDE |
25 | |
26 | /* ###### ####### ## ## ## ## ######## ###### */ |
27 | /* ## ## ## ## ## ## ### ## ## ## ## */ |
28 | /* ## ## ## ## ## #### ## ## ## */ |
29 | /* ## ## ## ## ## ## ## ## ## ###### */ |
30 | /* ## ## ## ## ## ## #### ## ## */ |
31 | /* ## ## ## ## ## ## ## ### ## ## ## */ |
32 | /* ###### ####### ####### ## ## ## ###### */ |
33 | |
34 | static int32_t normalize_index(const struct hdr_histogram* h, int32_t index) |
35 | { |
36 | int32_t normalized_index; |
37 | int32_t adjustment = 0; |
38 | if (h->normalizing_index_offset == 0) |
39 | { |
40 | return index; |
41 | } |
42 | |
43 | normalized_index = index - h->normalizing_index_offset; |
44 | |
45 | if (normalized_index < 0) |
46 | { |
47 | adjustment = h->counts_len; |
48 | } |
49 | else if (normalized_index >= h->counts_len) |
50 | { |
51 | adjustment = -h->counts_len; |
52 | } |
53 | |
54 | return normalized_index + adjustment; |
55 | } |
56 | |
57 | static int64_t counts_get_direct(const struct hdr_histogram* h, int32_t index) |
58 | { |
59 | return h->counts[index]; |
60 | } |
61 | |
62 | static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t index) |
63 | { |
64 | return counts_get_direct(h, normalize_index(h, index)); |
65 | } |
66 | |
67 | static void counts_inc_normalised( |
68 | struct hdr_histogram* h, int32_t index, int64_t value) |
69 | { |
70 | int32_t normalised_index = normalize_index(h, index); |
71 | h->counts[normalised_index] += value; |
72 | h->total_count += value; |
73 | } |
74 | |
75 | static void counts_inc_normalised_atomic( |
76 | struct hdr_histogram* h, int32_t index, int64_t value) |
77 | { |
78 | int32_t normalised_index = normalize_index(h, index); |
79 | |
80 | hdr_atomic_add_fetch_64(&h->counts[normalised_index], value); |
81 | hdr_atomic_add_fetch_64(&h->total_count, value); |
82 | } |
83 | |
84 | static void update_min_max(struct hdr_histogram* h, int64_t value) |
85 | { |
86 | h->min_value = (value < h->min_value && value != 0) ? value : h->min_value; |
87 | h->max_value = (value > h->max_value) ? value : h->max_value; |
88 | } |
89 | |
90 | static void update_min_max_atomic(struct hdr_histogram* h, int64_t value) |
91 | { |
92 | int64_t current_min_value; |
93 | int64_t current_max_value; |
94 | do |
95 | { |
96 | current_min_value = hdr_atomic_load_64(&h->min_value); |
97 | |
98 | if (0 == value || current_min_value <= value) |
99 | { |
100 | break; |
101 | } |
102 | } |
103 | while (!hdr_atomic_compare_exchange_64(&h->min_value, ¤t_min_value, value)); |
104 | |
105 | do |
106 | { |
107 | current_max_value = hdr_atomic_load_64(&h->max_value); |
108 | |
109 | if (value <= current_max_value) |
110 | { |
111 | break; |
112 | } |
113 | } |
114 | while (!hdr_atomic_compare_exchange_64(&h->max_value, ¤t_max_value, value)); |
115 | } |
116 | |
117 | |
118 | /* ## ## ######## #### ## #### ######## ## ## */ |
119 | /* ## ## ## ## ## ## ## ## ## */ |
120 | /* ## ## ## ## ## ## ## #### */ |
121 | /* ## ## ## ## ## ## ## ## */ |
122 | /* ## ## ## ## ## ## ## ## */ |
123 | /* ## ## ## ## ## ## ## ## */ |
124 | /* ####### ## #### ######## #### ## ## */ |
125 | |
126 | static int64_t power(int64_t base, int64_t exp) |
127 | { |
128 | int64_t result = 1; |
129 | while(exp) |
130 | { |
131 | result *= base; exp--; |
132 | } |
133 | return result; |
134 | } |
135 | |
136 | #if defined(_MSC_VER) |
137 | # if defined(_WIN64) |
138 | # pragma intrinsic(_BitScanReverse64) |
139 | # else |
140 | # pragma intrinsic(_BitScanReverse) |
141 | # endif |
142 | #endif |
143 | |
144 | static int32_t count_leading_zeros_64(int64_t value) |
145 | { |
146 | #if defined(_MSC_VER) |
147 | uint32_t leading_zero = 0; |
148 | #if defined(_WIN64) |
149 | _BitScanReverse64(&leading_zero, value); |
150 | #else |
151 | uint32_t high = value >> 32; |
152 | if (_BitScanReverse(&leading_zero, high)) |
153 | { |
154 | leading_zero += 32; |
155 | } |
156 | else |
157 | { |
158 | uint32_t low = value & 0x00000000FFFFFFFF; |
159 | _BitScanReverse(&leading_zero, low); |
160 | } |
161 | #endif |
162 | return 63 - leading_zero; /* smallest power of 2 containing value */ |
163 | #else |
164 | return __builtin_clzll(value); /* smallest power of 2 containing value */ |
165 | #endif |
166 | } |
167 | |
168 | static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value) |
169 | { |
170 | int32_t pow2ceiling = 64 - count_leading_zeros_64(value | h->sub_bucket_mask); /* smallest power of 2 containing value */ |
171 | return pow2ceiling - h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1); |
172 | } |
173 | |
174 | static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude) |
175 | { |
176 | return (int32_t)(value >> (bucket_index + unit_magnitude)); |
177 | } |
178 | |
179 | static int32_t counts_index(const struct hdr_histogram* h, int32_t bucket_index, int32_t sub_bucket_index) |
180 | { |
181 | /* Calculate the index for the first entry in the bucket: */ |
182 | /* (The following is the equivalent of ((bucket_index + 1) * subBucketHalfCount) ): */ |
183 | int32_t bucket_base_index = (bucket_index + 1) << h->sub_bucket_half_count_magnitude; |
184 | /* Calculate the offset in the bucket: */ |
185 | int32_t offset_in_bucket = sub_bucket_index - h->sub_bucket_half_count; |
186 | /* The following is the equivalent of ((sub_bucket_index - subBucketHalfCount) + bucketBaseIndex; */ |
187 | return bucket_base_index + offset_in_bucket; |
188 | } |
189 | |
190 | static int64_t value_from_index(int32_t bucket_index, int32_t sub_bucket_index, int32_t unit_magnitude) |
191 | { |
192 | return ((int64_t) sub_bucket_index) << (bucket_index + unit_magnitude); |
193 | } |
194 | |
195 | int32_t counts_index_for(const struct hdr_histogram* h, int64_t value) |
196 | { |
197 | int32_t bucket_index = get_bucket_index(h, value); |
198 | int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); |
199 | |
200 | return counts_index(h, bucket_index, sub_bucket_index); |
201 | } |
202 | |
203 | int64_t hdr_value_at_index(const struct hdr_histogram *h, int32_t index) |
204 | { |
205 | int32_t bucket_index = (index >> h->sub_bucket_half_count_magnitude) - 1; |
206 | int32_t sub_bucket_index = (index & (h->sub_bucket_half_count - 1)) + h->sub_bucket_half_count; |
207 | |
208 | if (bucket_index < 0) |
209 | { |
210 | sub_bucket_index -= h->sub_bucket_half_count; |
211 | bucket_index = 0; |
212 | } |
213 | |
214 | return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); |
215 | } |
216 | |
217 | int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_t value) |
218 | { |
219 | int32_t bucket_index = get_bucket_index(h, value); |
220 | int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); |
221 | int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index; |
222 | return INT64_C(1) << (h->unit_magnitude + adjusted_bucket); |
223 | } |
224 | |
225 | static int64_t size_of_equivalent_value_range_given_bucket_indices( |
226 | const struct hdr_histogram *h, |
227 | int32_t bucket_index, |
228 | int32_t sub_bucket_index) |
229 | { |
230 | const int32_t adjusted_bucket = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index; |
231 | return INT64_C(1) << (h->unit_magnitude + adjusted_bucket); |
232 | } |
233 | |
234 | static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value) |
235 | { |
236 | int32_t bucket_index = get_bucket_index(h, value); |
237 | int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, h->unit_magnitude); |
238 | return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); |
239 | } |
240 | |
241 | static int64_t lowest_equivalent_value_given_bucket_indices( |
242 | const struct hdr_histogram *h, |
243 | int32_t bucket_index, |
244 | int32_t sub_bucket_index) |
245 | { |
246 | return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude); |
247 | } |
248 | |
249 | int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value) |
250 | { |
251 | return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value); |
252 | } |
253 | |
254 | static int64_t highest_equivalent_value(const struct hdr_histogram* h, int64_t value) |
255 | { |
256 | return hdr_next_non_equivalent_value(h, value) - 1; |
257 | } |
258 | |
259 | int64_t hdr_median_equivalent_value(const struct hdr_histogram *h, int64_t value) |
260 | { |
261 | return lowest_equivalent_value(h, value) + (hdr_size_of_equivalent_value_range(h, value) >> 1); |
262 | } |
263 | |
264 | static int64_t non_zero_min(const struct hdr_histogram* h) |
265 | { |
266 | if (INT64_MAX == h->min_value) |
267 | { |
268 | return INT64_MAX; |
269 | } |
270 | |
271 | return lowest_equivalent_value(h, h->min_value); |
272 | } |
273 | |
274 | void hdr_reset_internal_counters(struct hdr_histogram* h) |
275 | { |
276 | int min_non_zero_index = -1; |
277 | int max_index = -1; |
278 | int64_t observed_total_count = 0; |
279 | int i; |
280 | |
281 | for (i = 0; i < h->counts_len; i++) |
282 | { |
283 | int64_t count_at_index; |
284 | |
285 | if ((count_at_index = counts_get_direct(h, i)) > 0) |
286 | { |
287 | observed_total_count += count_at_index; |
288 | max_index = i; |
289 | if (min_non_zero_index == -1 && i != 0) |
290 | { |
291 | min_non_zero_index = i; |
292 | } |
293 | } |
294 | } |
295 | |
296 | if (max_index == -1) |
297 | { |
298 | h->max_value = 0; |
299 | } |
300 | else |
301 | { |
302 | int64_t max_value = hdr_value_at_index(h, max_index); |
303 | h->max_value = highest_equivalent_value(h, max_value); |
304 | } |
305 | |
306 | if (min_non_zero_index == -1) |
307 | { |
308 | h->min_value = INT64_MAX; |
309 | } |
310 | else |
311 | { |
312 | h->min_value = hdr_value_at_index(h, min_non_zero_index); |
313 | } |
314 | |
315 | h->total_count = observed_total_count; |
316 | } |
317 | |
318 | static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_count, int32_t unit_magnitude) |
319 | { |
320 | int64_t smallest_untrackable_value = ((int64_t) sub_bucket_count) << unit_magnitude; |
321 | int32_t buckets_needed = 1; |
322 | while (smallest_untrackable_value <= value) |
323 | { |
324 | if (smallest_untrackable_value > INT64_MAX / 2) |
325 | { |
326 | return buckets_needed + 1; |
327 | } |
328 | smallest_untrackable_value <<= 1; |
329 | buckets_needed++; |
330 | } |
331 | |
332 | return buckets_needed; |
333 | } |
334 | |
335 | /* ## ## ######## ## ## ####### ######## ## ## */ |
336 | /* ### ### ## ### ### ## ## ## ## ## ## */ |
337 | /* #### #### ## #### #### ## ## ## ## #### */ |
338 | /* ## ### ## ###### ## ### ## ## ## ######## ## */ |
339 | /* ## ## ## ## ## ## ## ## ## ## */ |
340 | /* ## ## ## ## ## ## ## ## ## ## */ |
341 | /* ## ## ######## ## ## ####### ## ## ## */ |
342 | |
343 | int hdr_calculate_bucket_config( |
344 | int64_t lowest_discernible_value, |
345 | int64_t highest_trackable_value, |
346 | int significant_figures, |
347 | struct hdr_histogram_bucket_config* cfg) |
348 | { |
349 | int32_t sub_bucket_count_magnitude; |
350 | int64_t largest_value_with_single_unit_resolution; |
351 | |
352 | if (lowest_discernible_value < 1 || |
353 | significant_figures < 1 || 5 < significant_figures || |
354 | lowest_discernible_value * 2 > highest_trackable_value) |
355 | { |
356 | return EINVAL; |
357 | } |
358 | |
359 | cfg->lowest_discernible_value = lowest_discernible_value; |
360 | cfg->significant_figures = significant_figures; |
361 | cfg->highest_trackable_value = highest_trackable_value; |
362 | |
363 | largest_value_with_single_unit_resolution = 2 * power(10, significant_figures); |
364 | sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2)); |
365 | cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1; |
366 | |
367 | double unit_magnitude = log((double)lowest_discernible_value) / log(2); |
368 | if (INT32_MAX < unit_magnitude) |
369 | { |
370 | return EINVAL; |
371 | } |
372 | |
373 | cfg->unit_magnitude = (int32_t) unit_magnitude; |
374 | cfg->sub_bucket_count = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1)); |
375 | cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2; |
376 | cfg->sub_bucket_mask = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude; |
377 | |
378 | if (cfg->unit_magnitude + cfg->sub_bucket_half_count_magnitude > 61) |
379 | { |
380 | return EINVAL; |
381 | } |
382 | |
383 | cfg->bucket_count = buckets_needed_to_cover_value(highest_trackable_value, cfg->sub_bucket_count, (int32_t)cfg->unit_magnitude); |
384 | cfg->counts_len = (cfg->bucket_count + 1) * (cfg->sub_bucket_count / 2); |
385 | |
386 | return 0; |
387 | } |
388 | |
389 | void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg) |
390 | { |
391 | h->lowest_discernible_value = cfg->lowest_discernible_value; |
392 | h->highest_trackable_value = cfg->highest_trackable_value; |
393 | h->unit_magnitude = (int32_t)cfg->unit_magnitude; |
394 | h->significant_figures = (int32_t)cfg->significant_figures; |
395 | h->sub_bucket_half_count_magnitude = cfg->sub_bucket_half_count_magnitude; |
396 | h->sub_bucket_half_count = cfg->sub_bucket_half_count; |
397 | h->sub_bucket_mask = cfg->sub_bucket_mask; |
398 | h->sub_bucket_count = cfg->sub_bucket_count; |
399 | h->min_value = INT64_MAX; |
400 | h->max_value = 0; |
401 | h->normalizing_index_offset = 0; |
402 | h->conversion_ratio = 1.0; |
403 | h->bucket_count = cfg->bucket_count; |
404 | h->counts_len = cfg->counts_len; |
405 | h->total_count = 0; |
406 | } |
407 | |
408 | int hdr_init( |
409 | int64_t lowest_discernible_value, |
410 | int64_t highest_trackable_value, |
411 | int significant_figures, |
412 | struct hdr_histogram** result) |
413 | { |
414 | int64_t* counts; |
415 | struct hdr_histogram_bucket_config cfg; |
416 | struct hdr_histogram* histogram; |
417 | |
418 | int r = hdr_calculate_bucket_config(lowest_discernible_value, highest_trackable_value, significant_figures, &cfg); |
419 | if (r) |
420 | { |
421 | return r; |
422 | } |
423 | |
424 | counts = (int64_t*) hdr_calloc((size_t) cfg.counts_len, sizeof(int64_t)); |
425 | if (!counts) |
426 | { |
427 | return ENOMEM; |
428 | } |
429 | |
430 | histogram = (struct hdr_histogram*) hdr_calloc(1, sizeof(struct hdr_histogram)); |
431 | if (!histogram) |
432 | { |
433 | hdr_free(counts); |
434 | return ENOMEM; |
435 | } |
436 | |
437 | histogram->counts = counts; |
438 | |
439 | hdr_init_preallocated(histogram, &cfg); |
440 | *result = histogram; |
441 | |
442 | return 0; |
443 | } |
444 | |
445 | void hdr_close(struct hdr_histogram* h) |
446 | { |
447 | if (h) { |
448 | hdr_free(h->counts); |
449 | hdr_free(h); |
450 | } |
451 | } |
452 | |
453 | int hdr_alloc(int64_t highest_trackable_value, int significant_figures, struct hdr_histogram** result) |
454 | { |
455 | return hdr_init(1, highest_trackable_value, significant_figures, result); |
456 | } |
457 | |
458 | /* reset a histogram to zero. */ |
459 | void hdr_reset(struct hdr_histogram *h) |
460 | { |
461 | h->total_count=0; |
462 | h->min_value = INT64_MAX; |
463 | h->max_value = 0; |
464 | memset(h->counts, 0, (sizeof(int64_t) * h->counts_len)); |
465 | } |
466 | |
467 | size_t hdr_get_memory_size(struct hdr_histogram *h) |
468 | { |
469 | return sizeof(struct hdr_histogram) + h->counts_len * sizeof(int64_t); |
470 | } |
471 | |
472 | /* ## ## ######## ######## ### ######## ######## ###### */ |
473 | /* ## ## ## ## ## ## ## ## ## ## ## ## */ |
474 | /* ## ## ## ## ## ## ## ## ## ## ## */ |
475 | /* ## ## ######## ## ## ## ## ## ###### ###### */ |
476 | /* ## ## ## ## ## ######### ## ## ## */ |
477 | /* ## ## ## ## ## ## ## ## ## ## ## */ |
478 | /* ####### ## ######## ## ## ## ######## ###### */ |
479 | |
480 | |
481 | bool hdr_record_value(struct hdr_histogram* h, int64_t value) |
482 | { |
483 | return hdr_record_values(h, value, 1); |
484 | } |
485 | |
486 | bool hdr_record_value_atomic(struct hdr_histogram* h, int64_t value) |
487 | { |
488 | return hdr_record_values_atomic(h, value, 1); |
489 | } |
490 | |
491 | bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count) |
492 | { |
493 | int32_t counts_index; |
494 | |
495 | if (value < 0) |
496 | { |
497 | return false; |
498 | } |
499 | |
500 | counts_index = counts_index_for(h, value); |
501 | |
502 | if (counts_index < 0 || h->counts_len <= counts_index) |
503 | { |
504 | return false; |
505 | } |
506 | |
507 | counts_inc_normalised(h, counts_index, count); |
508 | update_min_max(h, value); |
509 | |
510 | return true; |
511 | } |
512 | |
513 | bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count) |
514 | { |
515 | int32_t counts_index; |
516 | |
517 | if (value < 0) |
518 | { |
519 | return false; |
520 | } |
521 | |
522 | counts_index = counts_index_for(h, value); |
523 | |
524 | if (counts_index < 0 || h->counts_len <= counts_index) |
525 | { |
526 | return false; |
527 | } |
528 | |
529 | counts_inc_normalised_atomic(h, counts_index, count); |
530 | update_min_max_atomic(h, value); |
531 | |
532 | return true; |
533 | } |
534 | |
535 | bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval) |
536 | { |
537 | return hdr_record_corrected_values(h, value, 1, expected_interval); |
538 | } |
539 | |
540 | bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval) |
541 | { |
542 | return hdr_record_corrected_values_atomic(h, value, 1, expected_interval); |
543 | } |
544 | |
545 | bool hdr_record_corrected_values(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) |
546 | { |
547 | int64_t missing_value; |
548 | |
549 | if (!hdr_record_values(h, value, count)) |
550 | { |
551 | return false; |
552 | } |
553 | |
554 | if (expected_interval <= 0 || value <= expected_interval) |
555 | { |
556 | return true; |
557 | } |
558 | |
559 | missing_value = value - expected_interval; |
560 | for (; missing_value >= expected_interval; missing_value -= expected_interval) |
561 | { |
562 | if (!hdr_record_values(h, missing_value, count)) |
563 | { |
564 | return false; |
565 | } |
566 | } |
567 | |
568 | return true; |
569 | } |
570 | |
571 | bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value, int64_t count, int64_t expected_interval) |
572 | { |
573 | int64_t missing_value; |
574 | |
575 | if (!hdr_record_values_atomic(h, value, count)) |
576 | { |
577 | return false; |
578 | } |
579 | |
580 | if (expected_interval <= 0 || value <= expected_interval) |
581 | { |
582 | return true; |
583 | } |
584 | |
585 | missing_value = value - expected_interval; |
586 | for (; missing_value >= expected_interval; missing_value -= expected_interval) |
587 | { |
588 | if (!hdr_record_values_atomic(h, missing_value, count)) |
589 | { |
590 | return false; |
591 | } |
592 | } |
593 | |
594 | return true; |
595 | } |
596 | |
597 | int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from) |
598 | { |
599 | struct hdr_iter iter; |
600 | int64_t dropped = 0; |
601 | hdr_iter_recorded_init(&iter, from); |
602 | |
603 | while (hdr_iter_next(&iter)) |
604 | { |
605 | int64_t value = iter.value; |
606 | int64_t count = iter.count; |
607 | |
608 | if (!hdr_record_values(h, value, count)) |
609 | { |
610 | dropped += count; |
611 | } |
612 | } |
613 | |
614 | return dropped; |
615 | } |
616 | |
617 | int64_t hdr_add_while_correcting_for_coordinated_omission( |
618 | struct hdr_histogram* h, struct hdr_histogram* from, int64_t expected_interval) |
619 | { |
620 | struct hdr_iter iter; |
621 | int64_t dropped = 0; |
622 | hdr_iter_recorded_init(&iter, from); |
623 | |
624 | while (hdr_iter_next(&iter)) |
625 | { |
626 | int64_t value = iter.value; |
627 | int64_t count = iter.count; |
628 | |
629 | if (!hdr_record_corrected_values(h, value, count, expected_interval)) |
630 | { |
631 | dropped += count; |
632 | } |
633 | } |
634 | |
635 | return dropped; |
636 | } |
637 | |
638 | |
639 | |
640 | /* ## ## ### ## ## ## ######## ###### */ |
641 | /* ## ## ## ## ## ## ## ## ## ## */ |
642 | /* ## ## ## ## ## ## ## ## ## */ |
643 | /* ## ## ## ## ## ## ## ###### ###### */ |
644 | /* ## ## ######### ## ## ## ## ## */ |
645 | /* ## ## ## ## ## ## ## ## ## ## */ |
646 | /* ### ## ## ######## ####### ######## ###### */ |
647 | |
648 | |
649 | int64_t hdr_max(const struct hdr_histogram* h) |
650 | { |
651 | if (0 == h->max_value) |
652 | { |
653 | return 0; |
654 | } |
655 | |
656 | return highest_equivalent_value(h, h->max_value); |
657 | } |
658 | |
659 | int64_t hdr_min(const struct hdr_histogram* h) |
660 | { |
661 | if (0 < hdr_count_at_index(h, 0)) |
662 | { |
663 | return 0; |
664 | } |
665 | |
666 | return non_zero_min(h); |
667 | } |
668 | |
669 | static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile) |
670 | { |
671 | int64_t count_to_idx = 0; |
672 | |
673 | count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1; |
674 | for (int32_t idx = 0; idx < h->counts_len; idx++) |
675 | { |
676 | count_to_idx += h->counts[idx]; |
677 | if (count_to_idx >= count_at_percentile) |
678 | { |
679 | return hdr_value_at_index(h, idx); |
680 | } |
681 | } |
682 | |
683 | return 0; |
684 | } |
685 | |
686 | |
687 | int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) |
688 | { |
689 | double requested_percentile = percentile < 100.0 ? percentile : 100.0; |
690 | int64_t count_at_percentile = |
691 | (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5); |
692 | int64_t value_from_idx = get_value_from_idx_up_to_count(h, count_at_percentile); |
693 | if (percentile == 0.0) |
694 | { |
695 | return lowest_equivalent_value(h, value_from_idx); |
696 | } |
697 | return highest_equivalent_value(h, value_from_idx); |
698 | } |
699 | |
700 | int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length) |
701 | { |
702 | if (NULL == percentiles || NULL == values) |
703 | { |
704 | return EINVAL; |
705 | } |
706 | |
707 | struct hdr_iter iter; |
708 | const int64_t total_count = h->total_count; |
709 | // to avoid allocations we use the values array for intermediate computation |
710 | // i.e. to store the expected cumulative count at each percentile |
711 | for (size_t i = 0; i < length; i++) |
712 | { |
713 | const double requested_percentile = percentiles[i] < 100.0 ? percentiles[i] : 100.0; |
714 | const int64_t count_at_percentile = |
715 | (int64_t) (((requested_percentile / 100) * total_count) + 0.5); |
716 | values[i] = count_at_percentile > 1 ? count_at_percentile : 1; |
717 | } |
718 | |
719 | hdr_iter_init(&iter, h); |
720 | int64_t total = 0; |
721 | size_t at_pos = 0; |
722 | while (hdr_iter_next(&iter) && at_pos < length) |
723 | { |
724 | total += iter.count; |
725 | while (at_pos < length && total >= values[at_pos]) |
726 | { |
727 | values[at_pos] = highest_equivalent_value(h, iter.value); |
728 | at_pos++; |
729 | } |
730 | } |
731 | return 0; |
732 | } |
733 | |
734 | double hdr_mean(const struct hdr_histogram* h) |
735 | { |
736 | struct hdr_iter iter; |
737 | int64_t total = 0; |
738 | |
739 | hdr_iter_init(&iter, h); |
740 | |
741 | while (hdr_iter_next(&iter)) |
742 | { |
743 | if (0 != iter.count) |
744 | { |
745 | total += iter.count * hdr_median_equivalent_value(h, iter.value); |
746 | } |
747 | } |
748 | |
749 | return (total * 1.0) / h->total_count; |
750 | } |
751 | |
752 | double hdr_stddev(const struct hdr_histogram* h) |
753 | { |
754 | double mean = hdr_mean(h); |
755 | double geometric_dev_total = 0.0; |
756 | |
757 | struct hdr_iter iter; |
758 | hdr_iter_init(&iter, h); |
759 | |
760 | while (hdr_iter_next(&iter)) |
761 | { |
762 | if (0 != iter.count) |
763 | { |
764 | double dev = (hdr_median_equivalent_value(h, iter.value) * 1.0) - mean; |
765 | geometric_dev_total += (dev * dev) * iter.count; |
766 | } |
767 | } |
768 | |
769 | return sqrt(geometric_dev_total / h->total_count); |
770 | } |
771 | |
772 | bool hdr_values_are_equivalent(const struct hdr_histogram* h, int64_t a, int64_t b) |
773 | { |
774 | return lowest_equivalent_value(h, a) == lowest_equivalent_value(h, b); |
775 | } |
776 | |
777 | int64_t hdr_lowest_equivalent_value(const struct hdr_histogram* h, int64_t value) |
778 | { |
779 | return lowest_equivalent_value(h, value); |
780 | } |
781 | |
782 | int64_t hdr_count_at_value(const struct hdr_histogram* h, int64_t value) |
783 | { |
784 | return counts_get_normalised(h, counts_index_for(h, value)); |
785 | } |
786 | |
787 | int64_t hdr_count_at_index(const struct hdr_histogram* h, int32_t index) |
788 | { |
789 | return counts_get_normalised(h, index); |
790 | } |
791 | |
792 | |
793 | /* #### ######## ######## ######## ### ######## ####### ######## ###### */ |
794 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
795 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
796 | /* ## ## ###### ######## ## ## ## ## ## ######## ###### */ |
797 | /* ## ## ## ## ## ######### ## ## ## ## ## ## */ |
798 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
799 | /* #### ## ######## ## ## ## ## ## ####### ## ## ###### */ |
800 | |
801 | |
802 | static bool has_buckets(struct hdr_iter* iter) |
803 | { |
804 | return iter->counts_index < iter->h->counts_len; |
805 | } |
806 | |
807 | static bool has_next(struct hdr_iter* iter) |
808 | { |
809 | return iter->cumulative_count < iter->total_count; |
810 | } |
811 | |
812 | static bool move_next(struct hdr_iter* iter) |
813 | { |
814 | iter->counts_index++; |
815 | |
816 | if (!has_buckets(iter)) |
817 | { |
818 | return false; |
819 | } |
820 | |
821 | iter->count = counts_get_normalised(iter->h, iter->counts_index); |
822 | iter->cumulative_count += iter->count; |
823 | const int64_t value = hdr_value_at_index(iter->h, iter->counts_index); |
824 | const int32_t bucket_index = get_bucket_index(iter->h, value); |
825 | const int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, iter->h->unit_magnitude); |
826 | const int64_t leq = lowest_equivalent_value_given_bucket_indices(iter->h, bucket_index, sub_bucket_index); |
827 | const int64_t size_of_equivalent_value_range = size_of_equivalent_value_range_given_bucket_indices( |
828 | iter->h, bucket_index, sub_bucket_index); |
829 | iter->lowest_equivalent_value = leq; |
830 | iter->value = value; |
831 | iter->highest_equivalent_value = leq + size_of_equivalent_value_range - 1; |
832 | iter->median_equivalent_value = leq + (size_of_equivalent_value_range >> 1); |
833 | |
834 | return true; |
835 | } |
836 | |
837 | static int64_t peek_next_value_from_index(struct hdr_iter* iter) |
838 | { |
839 | return hdr_value_at_index(iter->h, iter->counts_index + 1); |
840 | } |
841 | |
842 | static bool next_value_greater_than_reporting_level_upper_bound( |
843 | struct hdr_iter *iter, int64_t reporting_level_upper_bound) |
844 | { |
845 | if (iter->counts_index >= iter->h->counts_len) |
846 | { |
847 | return false; |
848 | } |
849 | |
850 | return peek_next_value_from_index(iter) > reporting_level_upper_bound; |
851 | } |
852 | |
853 | static bool basic_iter_next(struct hdr_iter *iter) |
854 | { |
855 | if (!has_next(iter) || iter->counts_index >= iter->h->counts_len) |
856 | { |
857 | return false; |
858 | } |
859 | |
860 | move_next(iter); |
861 | |
862 | return true; |
863 | } |
864 | |
865 | static void update_iterated_values(struct hdr_iter* iter, int64_t new_value_iterated_to) |
866 | { |
867 | iter->value_iterated_from = iter->value_iterated_to; |
868 | iter->value_iterated_to = new_value_iterated_to; |
869 | } |
870 | |
871 | static bool all_values_iter_next(struct hdr_iter* iter) |
872 | { |
873 | bool result = move_next(iter); |
874 | |
875 | if (result) |
876 | { |
877 | update_iterated_values(iter, iter->value); |
878 | } |
879 | |
880 | return result; |
881 | } |
882 | |
883 | void hdr_iter_init(struct hdr_iter* iter, const struct hdr_histogram* h) |
884 | { |
885 | iter->h = h; |
886 | |
887 | iter->counts_index = -1; |
888 | iter->total_count = h->total_count; |
889 | iter->count = 0; |
890 | iter->cumulative_count = 0; |
891 | iter->value = 0; |
892 | iter->highest_equivalent_value = 0; |
893 | iter->value_iterated_from = 0; |
894 | iter->value_iterated_to = 0; |
895 | |
896 | iter->_next_fp = all_values_iter_next; |
897 | } |
898 | |
899 | bool hdr_iter_next(struct hdr_iter* iter) |
900 | { |
901 | return iter->_next_fp(iter); |
902 | } |
903 | |
904 | /* ######## ######## ######## ###### ######## ## ## ######## #### ## ######## ###### */ |
905 | /* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## ## */ |
906 | /* ## ## ## ## ## ## ## #### ## ## ## ## ## ## */ |
907 | /* ######## ###### ######## ## ###### ## ## ## ## ## ## ###### ###### */ |
908 | /* ## ## ## ## ## ## ## #### ## ## ## ## ## */ |
909 | /* ## ## ## ## ## ## ## ## ### ## ## ## ## ## ## */ |
910 | /* ## ######## ## ## ###### ######## ## ## ## #### ######## ######## ###### */ |
911 | |
912 | static bool percentile_iter_next(struct hdr_iter* iter) |
913 | { |
914 | int64_t temp, half_distance, percentile_reporting_ticks; |
915 | |
916 | struct hdr_iter_percentiles* percentiles = &iter->specifics.percentiles; |
917 | |
918 | if (!has_next(iter)) |
919 | { |
920 | if (percentiles->seen_last_value) |
921 | { |
922 | return false; |
923 | } |
924 | |
925 | percentiles->seen_last_value = true; |
926 | percentiles->percentile = 100.0; |
927 | |
928 | return true; |
929 | } |
930 | |
931 | if (iter->counts_index == -1 && !basic_iter_next(iter)) |
932 | { |
933 | return false; |
934 | } |
935 | |
936 | do |
937 | { |
938 | double current_percentile = (100.0 * (double) iter->cumulative_count) / iter->h->total_count; |
939 | if (iter->count != 0 && |
940 | percentiles->percentile_to_iterate_to <= current_percentile) |
941 | { |
942 | update_iterated_values(iter, highest_equivalent_value(iter->h, iter->value)); |
943 | |
944 | percentiles->percentile = percentiles->percentile_to_iterate_to; |
945 | temp = (int64_t)(log(100 / (100.0 - (percentiles->percentile_to_iterate_to))) / log(2)) + 1; |
946 | half_distance = (int64_t) pow(2, (double) temp); |
947 | percentile_reporting_ticks = percentiles->ticks_per_half_distance * half_distance; |
948 | percentiles->percentile_to_iterate_to += 100.0 / percentile_reporting_ticks; |
949 | |
950 | return true; |
951 | } |
952 | } |
953 | while (basic_iter_next(iter)); |
954 | |
955 | return true; |
956 | } |
957 | |
958 | void hdr_iter_percentile_init(struct hdr_iter* iter, const struct hdr_histogram* h, int32_t ticks_per_half_distance) |
959 | { |
960 | iter->h = h; |
961 | |
962 | hdr_iter_init(iter, h); |
963 | |
964 | iter->specifics.percentiles.seen_last_value = false; |
965 | iter->specifics.percentiles.ticks_per_half_distance = ticks_per_half_distance; |
966 | iter->specifics.percentiles.percentile_to_iterate_to = 0.0; |
967 | iter->specifics.percentiles.percentile = 0.0; |
968 | |
969 | iter->_next_fp = percentile_iter_next; |
970 | } |
971 | |
972 | static void format_line_string(char* str, size_t len, int significant_figures, format_type format) |
973 | { |
974 | #if defined(_MSC_VER) |
975 | #define snprintf _snprintf |
976 | #pragma warning(push) |
977 | #pragma warning(disable: 4996) |
978 | #endif |
979 | const char* format_str = "%s%d%s" ; |
980 | |
981 | switch (format) |
982 | { |
983 | case CSV: |
984 | snprintf(str, len, format_str, "%." , significant_figures, "f,%f,%d,%.2f\n" ); |
985 | break; |
986 | case CLASSIC: |
987 | snprintf(str, len, format_str, "%12." , significant_figures, "f %12f %12d %12.2f\n" ); |
988 | break; |
989 | default: |
990 | snprintf(str, len, format_str, "%12." , significant_figures, "f %12f %12d %12.2f\n" ); |
991 | } |
992 | #if defined(_MSC_VER) |
993 | #undef snprintf |
994 | #pragma warning(pop) |
995 | #endif |
996 | } |
997 | |
998 | |
999 | /* ######## ######## ###### ####### ######## ######## ######## ######## */ |
1000 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
1001 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
1002 | /* ######## ###### ## ## ## ######## ## ## ###### ## ## */ |
1003 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
1004 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
1005 | /* ## ## ######## ###### ####### ## ## ######## ######## ######## */ |
1006 | |
1007 | |
1008 | static bool recorded_iter_next(struct hdr_iter* iter) |
1009 | { |
1010 | while (basic_iter_next(iter)) |
1011 | { |
1012 | if (iter->count != 0) |
1013 | { |
1014 | update_iterated_values(iter, iter->value); |
1015 | |
1016 | iter->specifics.recorded.count_added_in_this_iteration_step = iter->count; |
1017 | return true; |
1018 | } |
1019 | } |
1020 | |
1021 | return false; |
1022 | } |
1023 | |
1024 | void hdr_iter_recorded_init(struct hdr_iter* iter, const struct hdr_histogram* h) |
1025 | { |
1026 | hdr_iter_init(iter, h); |
1027 | |
1028 | iter->specifics.recorded.count_added_in_this_iteration_step = 0; |
1029 | |
1030 | iter->_next_fp = recorded_iter_next; |
1031 | } |
1032 | |
1033 | /* ## #### ## ## ######## ### ######## */ |
1034 | /* ## ## ### ## ## ## ## ## ## */ |
1035 | /* ## ## #### ## ## ## ## ## ## */ |
1036 | /* ## ## ## ## ## ###### ## ## ######## */ |
1037 | /* ## ## ## #### ## ######### ## ## */ |
1038 | /* ## ## ## ### ## ## ## ## ## */ |
1039 | /* ######## #### ## ## ######## ## ## ## ## */ |
1040 | |
1041 | |
1042 | static bool iter_linear_next(struct hdr_iter* iter) |
1043 | { |
1044 | struct hdr_iter_linear* linear = &iter->specifics.linear; |
1045 | |
1046 | linear->count_added_in_this_iteration_step = 0; |
1047 | |
1048 | if (has_next(iter) || |
1049 | next_value_greater_than_reporting_level_upper_bound( |
1050 | iter, linear->next_value_reporting_level_lowest_equivalent)) |
1051 | { |
1052 | do |
1053 | { |
1054 | if (iter->value >= linear->next_value_reporting_level_lowest_equivalent) |
1055 | { |
1056 | update_iterated_values(iter, linear->next_value_reporting_level); |
1057 | |
1058 | linear->next_value_reporting_level += linear->value_units_per_bucket; |
1059 | linear->next_value_reporting_level_lowest_equivalent = |
1060 | lowest_equivalent_value(iter->h, linear->next_value_reporting_level); |
1061 | |
1062 | return true; |
1063 | } |
1064 | |
1065 | if (!move_next(iter)) |
1066 | { |
1067 | return true; |
1068 | } |
1069 | |
1070 | linear->count_added_in_this_iteration_step += iter->count; |
1071 | } |
1072 | while (true); |
1073 | } |
1074 | |
1075 | return false; |
1076 | } |
1077 | |
1078 | |
1079 | void hdr_iter_linear_init(struct hdr_iter* iter, const struct hdr_histogram* h, int64_t value_units_per_bucket) |
1080 | { |
1081 | hdr_iter_init(iter, h); |
1082 | |
1083 | iter->specifics.linear.count_added_in_this_iteration_step = 0; |
1084 | iter->specifics.linear.value_units_per_bucket = value_units_per_bucket; |
1085 | iter->specifics.linear.next_value_reporting_level = value_units_per_bucket; |
1086 | iter->specifics.linear.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_per_bucket); |
1087 | |
1088 | iter->_next_fp = iter_linear_next; |
1089 | } |
1090 | |
1091 | void hdr_iter_linear_set_value_units_per_bucket(struct hdr_iter* iter, int64_t value_units_per_bucket) |
1092 | { |
1093 | iter->specifics.linear.value_units_per_bucket = value_units_per_bucket; |
1094 | } |
1095 | |
1096 | /* ## ####### ###### ### ######## #### ######## ## ## ## ## #### ###### */ |
1097 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ### ### ## ## ## */ |
1098 | /* ## ## ## ## ## ## ## ## ## ## ## ## #### #### ## ## */ |
1099 | /* ## ## ## ## #### ## ## ######## ## ## ######### ## ### ## ## ## */ |
1100 | /* ## ## ## ## ## ######### ## ## ## ## ## ## ## ## ## ## */ |
1101 | /* ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## */ |
1102 | /* ######## ####### ###### ## ## ## ## #### ## ## ## ## ## #### ###### */ |
1103 | |
1104 | static bool log_iter_next(struct hdr_iter *iter) |
1105 | { |
1106 | struct hdr_iter_log* logarithmic = &iter->specifics.log; |
1107 | |
1108 | logarithmic->count_added_in_this_iteration_step = 0; |
1109 | |
1110 | if (has_next(iter) || |
1111 | next_value_greater_than_reporting_level_upper_bound( |
1112 | iter, logarithmic->next_value_reporting_level_lowest_equivalent)) |
1113 | { |
1114 | do |
1115 | { |
1116 | if (iter->value >= logarithmic->next_value_reporting_level_lowest_equivalent) |
1117 | { |
1118 | update_iterated_values(iter, logarithmic->next_value_reporting_level); |
1119 | |
1120 | logarithmic->next_value_reporting_level *= (int64_t)logarithmic->log_base; |
1121 | logarithmic->next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(iter->h, logarithmic->next_value_reporting_level); |
1122 | |
1123 | return true; |
1124 | } |
1125 | |
1126 | if (!move_next(iter)) |
1127 | { |
1128 | return true; |
1129 | } |
1130 | |
1131 | logarithmic->count_added_in_this_iteration_step += iter->count; |
1132 | } |
1133 | while (true); |
1134 | } |
1135 | |
1136 | return false; |
1137 | } |
1138 | |
1139 | void hdr_iter_log_init( |
1140 | struct hdr_iter* iter, |
1141 | const struct hdr_histogram* h, |
1142 | int64_t value_units_first_bucket, |
1143 | double log_base) |
1144 | { |
1145 | hdr_iter_init(iter, h); |
1146 | iter->specifics.log.count_added_in_this_iteration_step = 0; |
1147 | iter->specifics.log.log_base = log_base; |
1148 | iter->specifics.log.next_value_reporting_level = value_units_first_bucket; |
1149 | iter->specifics.log.next_value_reporting_level_lowest_equivalent = lowest_equivalent_value(h, value_units_first_bucket); |
1150 | |
1151 | iter->_next_fp = log_iter_next; |
1152 | } |
1153 | |
1154 | /* Printing. */ |
1155 | |
1156 | static const char* format_head_string(format_type format) |
1157 | { |
1158 | switch (format) |
1159 | { |
1160 | case CSV: |
1161 | return "%s,%s,%s,%s\n" ; |
1162 | case CLASSIC: |
1163 | default: |
1164 | return "%12s %12s %12s %12s\n\n" ; |
1165 | } |
1166 | } |
1167 | |
1168 | static const char [] = |
1169 | "#[Mean = %12.3f, StdDeviation = %12.3f]\n" |
1170 | "#[Max = %12.3f, Total count = %12" PRIu64 "]\n" |
1171 | "#[Buckets = %12d, SubBuckets = %12d]\n" ; |
1172 | |
1173 | int hdr_percentiles_print( |
1174 | struct hdr_histogram* h, FILE* stream, int32_t ticks_per_half_distance, |
1175 | double value_scale, format_type format) |
1176 | { |
1177 | char line_format[25]; |
1178 | const char* head_format; |
1179 | int rc = 0; |
1180 | struct hdr_iter iter; |
1181 | struct hdr_iter_percentiles * percentiles; |
1182 | |
1183 | format_line_string(line_format, 25, h->significant_figures, format); |
1184 | head_format = format_head_string(format); |
1185 | |
1186 | hdr_iter_percentile_init(&iter, h, ticks_per_half_distance); |
1187 | |
1188 | if (fprintf( |
1189 | stream, head_format, |
1190 | "Value" , "Percentile" , "TotalCount" , "1/(1-Percentile)" ) < 0) |
1191 | { |
1192 | rc = EIO; |
1193 | goto cleanup; |
1194 | } |
1195 | |
1196 | percentiles = &iter.specifics.percentiles; |
1197 | while (hdr_iter_next(&iter)) |
1198 | { |
1199 | double value = iter.highest_equivalent_value / value_scale; |
1200 | double percentile = percentiles->percentile / 100.0; |
1201 | int64_t total_count = iter.cumulative_count; |
1202 | double inverted_percentile = (1.0 / (1.0 - percentile)); |
1203 | |
1204 | if (fprintf( |
1205 | stream, line_format, value, percentile, total_count, inverted_percentile) < 0) |
1206 | { |
1207 | rc = EIO; |
1208 | goto cleanup; |
1209 | } |
1210 | } |
1211 | |
1212 | if (CLASSIC == format) |
1213 | { |
1214 | double mean = hdr_mean(h) / value_scale; |
1215 | double stddev = hdr_stddev(h) / value_scale; |
1216 | double max = hdr_max(h) / value_scale; |
1217 | |
1218 | if (fprintf( |
1219 | stream, CLASSIC_FOOTER, mean, stddev, max, |
1220 | h->total_count, h->bucket_count, h->sub_bucket_count) < 0) |
1221 | { |
1222 | rc = EIO; |
1223 | goto cleanup; |
1224 | } |
1225 | } |
1226 | |
1227 | cleanup: |
1228 | return rc; |
1229 | } |
1230 | |