From cb6933e3463ff23c33129722d30e8d5062397be3 Mon Sep 17 00:00:00 2001 From: yoav-steinberg Date: Sun, 22 May 2022 13:44:29 +0300 Subject: Updated HDR histogram from upsteam after they merged our fix in #10606. (#10755) The code is based on upstream https://github.com/HdrHistogram/HdrHistogram_c master branch latest commit (e4448cf6d1cd08fff519812d3b1e58bd5a94ac42). The reason to pull this in now is that their final version of our optimization is even faster. See: https://github.com/HdrHistogram/HdrHistogram_c/pull/107. --- deps/README.md | 4 +- deps/hdr_histogram/README.md | 78 +++++++++++++++++++++++++++++++++++--- deps/hdr_histogram/hdr_histogram.c | 38 ++++--------------- 3 files changed, 83 insertions(+), 37 deletions(-) (limited to 'deps') diff --git a/deps/README.md b/deps/README.md index f37922f19..bd1280e5e 100644 --- a/deps/README.md +++ b/deps/README.md @@ -100,8 +100,8 @@ Hdr_Histogram --- Updated source can be found here: https://github.com/HdrHistogram/HdrHistogram_c -We use a customized version 0.11.5 -1. Compare all changes under /hdr_histogram directory to version 0.11.5 +We use a customized version based on master branch commit e4448cf6d1cd08fff519812d3b1e58bd5a94ac42. +1. Compare all changes under /hdr_histogram directory to upstream master commit e4448cf6d1cd08fff519812d3b1e58bd5a94ac42 2. Copy updated files from newer version onto files in /hdr_histogram. 3. Apply the changes from 1 above to the updated files. diff --git a/deps/hdr_histogram/README.md b/deps/hdr_histogram/README.md index a951520db..93a156e79 100644 --- a/deps/hdr_histogram/README.md +++ b/deps/hdr_histogram/README.md @@ -1,10 +1,78 @@ -HdrHistogram_c v0.11.5 +HdrHistogram_c: 'C' port of High Dynamic Range (HDR) Histogram +HdrHistogram ---------------------------------------------- -This port contains a subset of the 'C' version of High Dynamic Range (HDR) Histogram available at [github.com/HdrHistogram/HdrHistogram_c](https://github.com/HdrHistogram/HdrHistogram_c). +[![Gitter chat](https://badges.gitter.im/HdrHistogram/HdrHistogram.png)](https://gitter.im/HdrHistogram/HdrHistogram) +This port contains a subset of the functionality supported by the Java +implementation. The current supported features are: -The code present on `hdr_histogram.c`, `hdr_histogram.h`, and `hdr_atomic.c` was Written by Gil Tene, Michael Barker, -and Matt Warren, and released to the public domain, as explained at -http://creativecommons.org/publicdomain/zero/1.0/. +* Standard histogram with 64 bit counts (32/16 bit counts not supported) +* All iterator types (all values, recorded, percentiles, linear, logarithmic) +* Histogram serialisation (encoding version 1.2, decoding 1.0-1.2) +* Reader/writer phaser and interval recorder + +Features not supported, but planned + +* Auto-resizing of histograms + +Features unlikely to be implemented + +* Double histograms +* Atomic/Concurrent histograms +* 16/32 bit histograms + +# Simple Tutorial + +## Recording values + +```C +#include + +struct hdr_histogram* histogram; + +// Initialise the histogram +hdr_init( + 1, // Minimum value + INT64_C(3600000000), // Maximum value + 3, // Number of significant figures + &histogram) // Pointer to initialise + +// Record value +hdr_record_value( + histogram, // Histogram to record to + value) // Value to record + +// Record value n times +hdr_record_values( + histogram, // Histogram to record to + value, // Value to record + 10) // Record value 10 times + +// Record value with correction for co-ordinated omission. +hdr_record_corrected_value( + histogram, // Histogram to record to + value, // Value to record + 1000) // Record with expected interval of 1000. + +// Print out the values of the histogram +hdr_percentiles_print( + histogram, + stdout, // File to write to + 5, // Granularity of printed values + 1.0, // Multiplier for results + CLASSIC); // Format CLASSIC/CSV supported. +``` + +## More examples + +For more detailed examples of recording and logging results look at the +[hdr_decoder](examples/hdr_decoder.c) +and [hiccup](examples/hiccup.c) +examples. You can run hiccup and decoder +and pipe the results of one into the other. + +``` +$ ./examples/hiccup | ./examples/hdr_decoder +``` diff --git a/deps/hdr_histogram/hdr_histogram.c b/deps/hdr_histogram/hdr_histogram.c index d227f1a45..f469347b7 100644 --- a/deps/hdr_histogram/hdr_histogram.c +++ b/deps/hdr_histogram/hdr_histogram.c @@ -165,16 +165,6 @@ static int32_t count_leading_zeros_64(int64_t value) #endif } -static int64_t get_count_at_index_given_bucket_base_idx(const struct hdr_histogram* h, int32_t bucket_base_idx, int32_t sub_bucket_idx) -{ - return h->counts[(bucket_base_idx + sub_bucket_idx) - h->sub_bucket_half_count]; -} - -static int32_t get_bucket_base_index(const struct hdr_histogram* h, int32_t bucket_index) -{ - return (bucket_index + 1) << h->sub_bucket_half_count_magnitude; -} - static int32_t get_bucket_index(const struct hdr_histogram* h, int64_t value) { int32_t pow2ceiling = 64 - count_leading_zeros_64(value | h->sub_bucket_mask); /* smallest power of 2 containing value */ @@ -679,33 +669,21 @@ int64_t hdr_min(const struct hdr_histogram* h) static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile) { int64_t count_to_idx = 0; - int64_t value_from_idx = 0; - int32_t sub_bucket_idx = -1; - int32_t bucket_idx = 0; - int32_t bucket_base_idx = get_bucket_base_index(h, bucket_idx); - // Overflow check - if (count_at_percentile > h->total_count) + count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1; + for (int32_t idx = 0; idx < h->counts_len; idx++) { - count_at_percentile = h->total_count; - } - - while (count_to_idx < count_at_percentile) - { - // increment bucket - sub_bucket_idx++; - if (sub_bucket_idx >= h->sub_bucket_count) + count_to_idx += h->counts[idx]; + if (count_to_idx >= count_at_percentile) { - sub_bucket_idx = h->sub_bucket_half_count; - bucket_idx++; - bucket_base_idx = get_bucket_base_index(h, bucket_idx); + return hdr_value_at_index(h, idx); } - count_to_idx += get_count_at_index_given_bucket_base_idx(h, bucket_base_idx, sub_bucket_idx); - value_from_idx = ((int64_t)(sub_bucket_idx)) << (((int64_t)(bucket_idx)) + h->unit_magnitude); } - return value_from_idx; + + return 0; } + int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) { double requested_percentile = percentile < 100.0 ? percentile : 100.0; -- cgit v1.2.1