Optimized `hdr_value_at_percentile` (#10606)

`hdr_value_at_percentile()` is part of the Hdr_Histogram library
used when generating `latencystats` report. 

There's a pending optimization for this function which greatly
affects the performance of `info latencystats`.
https://github.com/HdrHistogram/HdrHistogram_c/pull/107

This PR:
1. Upgrades the sources in _deps/hdr_histogram_ to the latest Hdr_Histogram
  version 0.11.5
2. Applies the referenced optimization.
3. Adds minor documentation about the hdr_histogram dependency which was
  missing under _deps/README.md_.

benchmark on my machine:
running: `redis-benchmark -n 100000 info latencystats` on a clean build with no data.

| benchmark | RPS |
| ---- | ---- |
| before upgrade to v0.11.05  | 7,681 |
| before optimization | 12,474 |
| after optimization | 52,606 |

Co-authored-by: filipe oliveira <filipecosta.90@gmail.com>

9 files changed, 204 insertions, 138 deletions

diff --git a/deps/README.md b/deps/README.md
index 591bb2cd5..f37922f19 100644
--- a/deps/README.md
+++ b/deps/README.md
@@ -5,6 +5,7 @@ should be provided by the operating system.
 * **hiredis** is the official C client library for Redis. It is used by redis-cli, redis-benchmark and Redis Sentinel. It is part of the Redis official ecosystem but is developed externally from the Redis repository, so we just upgrade it as needed.
 * **linenoise** is a readline replacement. It is developed by the same authors of Redis but is managed as a separated project and updated as needed.
 * **lua** is Lua 5.1 with minor changes for security and additional libraries.
+* **hdr_histogram** Used for per-command latency tracking histograms.
 
 How to upgrade the above dependencies
 ===
@@ -94,3 +95,13 @@ and our version:
 1. Makefile is modified to allow a different compiler than GCC.
 2. We have the implementation source code, and directly link to the following external libraries: `lua_cjson.o`, `lua_struct.o`, `lua_cmsgpack.o` and `lua_bit.o`.
 3. There is a security fix in `ldo.c`, line 498: The check for `LUA_SIGNATURE[0]` is removed in order to avoid direct bytecode execution.
+
+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
+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/Makefile b/deps/hdr_histogram/Makefile
index 64f2e547a..28dd93ea1 100644
--- a/deps/hdr_histogram/Makefile
+++ b/deps/hdr_histogram/Makefile
@@ -1,8 +1,8 @@
-STD=
+STD= -std=c99
 WARN= -Wall
 OPT= -Os
 
-R_CFLAGS= $(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS)
+R_CFLAGS= $(STD) $(WARN) $(OPT) $(DEBUG) $(CFLAGS) -DHDR_MALLOC_INCLUDE=\"hdr_redis_malloc.h\"
 R_LDFLAGS= $(LDFLAGS)
 DEBUG= -g
 
@@ -12,12 +12,10 @@ R_LD=$(CC) $(R_LDFLAGS)
 AR= ar
 ARFLAGS= rcs
 
-libhdrhistogram.a: hdr_histogram.o hdr_alloc.o
+libhdrhistogram.a: hdr_histogram.o
 	$(AR) $(ARFLAGS) $@ $+
 
-hdr_alloc.o: hdr_alloc.h hdr_alloc.c
-
-hdr_histogram.o: hdr_alloc.o hdr_histogram.h hdr_histogram.c
+hdr_histogram.o: hdr_histogram.h hdr_histogram.c
 
 .c.o:
 	$(R_CC) -c  $< 
diff --git a/deps/hdr_histogram/README.md b/deps/hdr_histogram/README.md
index 5f62c234c..a951520db 100644
--- a/deps/hdr_histogram/README.md
+++ b/deps/hdr_histogram/README.md
@@ -1,4 +1,4 @@
-HdrHistogram_c v0.11.0
+HdrHistogram_c v0.11.5
 
 ----------------------------------------------
 
@@ -7,4 +7,4 @@ This port contains a subset of the 'C' version of High Dynamic Range (HDR) Histo
 
 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/.
\ No newline at end of file
+http://creativecommons.org/publicdomain/zero/1.0/.
diff --git a/deps/hdr_histogram/hdr_alloc.c b/deps/hdr_histogram/hdr_alloc.c
deleted file mode 100644
index d2bc611d9..000000000
--- a/deps/hdr_histogram/hdr_alloc.c
+++ /dev/null
@@ -1,34 +0,0 @@
-/**
- * hdr_alloc.c
- * Written by Filipe Oliveira and released to the public domain,
- * as explained at http://creativecommons.org/publicdomain/zero/1.0/
- */
-
-#include "hdr_alloc.h"
-#include <stdlib.h>
-
-hdrAllocFuncs hdrAllocFns = {
-    .mallocFn = malloc,
-    .callocFn = calloc,
-    .reallocFn = realloc,
-    .freeFn = free,
-};
-
-/* Override hdr' allocators with ones supplied by the user */
-hdrAllocFuncs hdrSetAllocators(hdrAllocFuncs *override) {
-    hdrAllocFuncs orig = hdrAllocFns;
-
-    hdrAllocFns = *override;
-
-    return orig;
-}
-
-/* Reset allocators to use build time defaults */
-void hdrResetAllocators(void) {
-    hdrAllocFns = (hdrAllocFuncs){
-        .mallocFn = malloc,
-        .callocFn = calloc,
-        .reallocFn = realloc,
-        .freeFn = free,
-    };
-}
diff --git a/deps/hdr_histogram/hdr_alloc.h b/deps/hdr_histogram/hdr_alloc.h
deleted file mode 100644
index 410f640af..000000000
--- a/deps/hdr_histogram/hdr_alloc.h
+++ /dev/null
@@ -1,47 +0,0 @@
-/**
- * hdr_alloc.h
- * Written by Filipe Oliveira and released to the public domain,
- * as explained at http://creativecommons.org/publicdomain/zero/1.0/
- *
- * Allocator selection.
- *
- * This file is used in order to change the HdrHistogram allocator at run
- * time. */
-
-#ifndef HDR_ALLOC_H
-#define HDR_ALLOC_H
-
-#include <stddef.h> /* for size_t */
-#include <stdint.h>
-
-/* Structure pointing to our actually configured allocators */
-typedef struct hdrAllocFuncs {
-    void *(*mallocFn)(size_t);
-    void *(*callocFn)(size_t, size_t);
-    void *(*reallocFn)(void *, size_t);
-    void (*freeFn)(void *);
-} hdrAllocFuncs;
-
-/* hdr' configured allocator function pointer struct */
-extern hdrAllocFuncs hdrAllocFns;
-
-hdrAllocFuncs hdrSetAllocators(hdrAllocFuncs *ha);
-void hdrResetAllocators(void);
-
-static inline void *hdr_malloc(size_t size) {
-    return hdrAllocFns.mallocFn(size);
-}
-
-static inline void *hdr_calloc(size_t nmemb, size_t size) {
-    return hdrAllocFns.callocFn(nmemb, size);
-}
-
-static inline void *hdr_realloc(void *ptr, size_t size) {
-    return hdrAllocFns.reallocFn(ptr, size);
-}
-
-static inline void hdr_free(void *ptr) {
-    hdrAllocFns.freeFn(ptr);
-}
-
-#endif /* HDR_ALLOC_H */
diff --git a/deps/hdr_histogram/hdr_histogram.c b/deps/hdr_histogram/hdr_histogram.c
index 42fdcb687..d227f1a45 100644
--- a/deps/hdr_histogram/hdr_histogram.c
+++ b/deps/hdr_histogram/hdr_histogram.c
@@ -14,13 +14,14 @@
 #include <inttypes.h>
 
 #include "hdr_histogram.h"
+#include "hdr_tests.h"
 #include "hdr_atomic.h"
-#include "hdr_alloc.h"
 
-#define malloc hdr_malloc
-#define calloc hdr_calloc
-#define free hdr_free
-#define realloc hdr_realloc
+#ifndef HDR_MALLOC_INCLUDE
+#define HDR_MALLOC_INCLUDE "hdr_malloc.h"
+#endif
+
+#include HDR_MALLOC_INCLUDE
 
 /*  ######   #######  ##     ## ##    ## ########  ######  */
 /* ##    ## ##     ## ##     ## ###   ##    ##    ##    ## */
@@ -164,6 +165,16 @@ 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 */
@@ -221,6 +232,15 @@ int64_t hdr_size_of_equivalent_value_range(const struct hdr_histogram* h, int64_
     return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
 }
 
+static int64_t size_of_equivalent_value_range_given_bucket_indices(
+    const struct hdr_histogram *h,
+    int32_t bucket_index,
+    int32_t sub_bucket_index)
+{
+    const int32_t adjusted_bucket  = (sub_bucket_index >= h->sub_bucket_count) ? (bucket_index + 1) : bucket_index;
+    return INT64_C(1) << (h->unit_magnitude + adjusted_bucket);
+}
+
 static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t value)
 {
     int32_t bucket_index     = get_bucket_index(h, value);
@@ -228,6 +248,14 @@ static int64_t lowest_equivalent_value(const struct hdr_histogram* h, int64_t va
     return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
 }
 
+static int64_t lowest_equivalent_value_given_bucket_indices(
+    const struct hdr_histogram *h,
+    int32_t bucket_index,
+    int32_t sub_bucket_index)
+{
+    return value_from_index(bucket_index, sub_bucket_index, h->unit_magnitude);
+}
+
 int64_t hdr_next_non_equivalent_value(const struct hdr_histogram *h, int64_t value)
 {
     return lowest_equivalent_value(h, value) + hdr_size_of_equivalent_value_range(h, value);
@@ -323,7 +351,7 @@ static int32_t buckets_needed_to_cover_value(int64_t value, int32_t sub_bucket_c
 /* ##     ## ######## ##     ##  #######  ##     ##    ##    */
 
 int hdr_calculate_bucket_config(
-        int64_t lowest_trackable_value,
+        int64_t lowest_discernible_value,
         int64_t highest_trackable_value,
         int significant_figures,
         struct hdr_histogram_bucket_config* cfg)
@@ -331,14 +359,14 @@ int hdr_calculate_bucket_config(
     int32_t sub_bucket_count_magnitude;
     int64_t largest_value_with_single_unit_resolution;
 
-    if (lowest_trackable_value < 1 ||
+    if (lowest_discernible_value < 1 ||
             significant_figures < 1 || 5 < significant_figures ||
-            lowest_trackable_value * 2 > highest_trackable_value)
+            lowest_discernible_value * 2 > highest_trackable_value)
     {
         return EINVAL;
     }
 
-    cfg->lowest_trackable_value = lowest_trackable_value;
+    cfg->lowest_discernible_value = lowest_discernible_value;
     cfg->significant_figures = significant_figures;
     cfg->highest_trackable_value = highest_trackable_value;
 
@@ -346,8 +374,13 @@ int hdr_calculate_bucket_config(
     sub_bucket_count_magnitude = (int32_t) ceil(log((double)largest_value_with_single_unit_resolution) / log(2));
     cfg->sub_bucket_half_count_magnitude = ((sub_bucket_count_magnitude > 1) ? sub_bucket_count_magnitude : 1) - 1;
 
-    cfg->unit_magnitude = (int32_t) floor(log((double)lowest_trackable_value) / log(2));
+    double unit_magnitude = log((double)lowest_discernible_value) / log(2);
+    if (INT32_MAX < unit_magnitude)
+    {
+        return EINVAL;
+    }
 
+    cfg->unit_magnitude = (int32_t) unit_magnitude;
     cfg->sub_bucket_count      = (int32_t) pow(2, (cfg->sub_bucket_half_count_magnitude + 1));
     cfg->sub_bucket_half_count = cfg->sub_bucket_count / 2;
     cfg->sub_bucket_mask       = ((int64_t) cfg->sub_bucket_count - 1) << cfg->unit_magnitude;
@@ -365,7 +398,7 @@ int hdr_calculate_bucket_config(
 
 void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_config* cfg)
 {
-    h->lowest_trackable_value          = cfg->lowest_trackable_value;
+    h->lowest_discernible_value        = cfg->lowest_discernible_value;
     h->highest_trackable_value         = cfg->highest_trackable_value;
     h->unit_magnitude                  = (int32_t)cfg->unit_magnitude;
     h->significant_figures             = (int32_t)cfg->significant_figures;
@@ -383,7 +416,7 @@ void hdr_init_preallocated(struct hdr_histogram* h, struct hdr_histogram_bucket_
 }
 
 int hdr_init(
-        int64_t lowest_trackable_value,
+        int64_t lowest_discernible_value,
         int64_t highest_trackable_value,
         int significant_figures,
         struct hdr_histogram** result)
@@ -392,22 +425,22 @@ int hdr_init(
     struct hdr_histogram_bucket_config cfg;
     struct hdr_histogram* histogram;
 
-    int r = hdr_calculate_bucket_config(lowest_trackable_value, highest_trackable_value, significant_figures, &cfg);
+    int r = hdr_calculate_bucket_config(lowest_discernible_value, highest_trackable_value, significant_figures, &cfg);
     if (r)
     {
         return r;
     }
 
-    counts = (int64_t*) calloc((size_t) cfg.counts_len, sizeof(int64_t));
+    counts = (int64_t*) hdr_calloc((size_t) cfg.counts_len, sizeof(int64_t));
     if (!counts)
     {
         return ENOMEM;
     }
 
-    histogram = (struct hdr_histogram*) calloc(1, sizeof(struct hdr_histogram));
+    histogram = (struct hdr_histogram*) hdr_calloc(1, sizeof(struct hdr_histogram));
     if (!histogram)
     {
-        free(counts);
+        hdr_free(counts);
         return ENOMEM;
     }
 
@@ -422,8 +455,8 @@ int hdr_init(
 void hdr_close(struct hdr_histogram* h)
 {
     if (h) {
-	free(h->counts);
-	free(h);
+	hdr_free(h->counts);
+	hdr_free(h);
     }
 }
 
@@ -643,28 +676,80 @@ int64_t hdr_min(const struct hdr_histogram* h)
     return non_zero_min(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 = h->total_count;
+    }
+
+    while (count_to_idx < count_at_percentile)
+    {
+        // increment bucket
+        sub_bucket_idx++;
+        if (sub_bucket_idx >= h->sub_bucket_count)
+        {
+            sub_bucket_idx = h->sub_bucket_half_count;
+            bucket_idx++;
+            bucket_base_idx = get_bucket_base_index(h, bucket_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;
+}
+
 int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile)
 {
-    struct hdr_iter iter;
-    int64_t total = 0;
     double requested_percentile = percentile < 100.0 ? percentile : 100.0;
     int64_t count_at_percentile =
         (int64_t) (((requested_percentile / 100) * h->total_count) + 0.5);
-    count_at_percentile = count_at_percentile > 1 ? count_at_percentile : 1;
+    int64_t value_from_idx = get_value_from_idx_up_to_count(h, count_at_percentile);
+    if (percentile == 0.0)
+    {
+        return lowest_equivalent_value(h, value_from_idx);
+    }
+    return highest_equivalent_value(h, value_from_idx);
+}
 
-    hdr_iter_init(&iter, h);
+int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length)
+{
+    if (NULL == percentiles || NULL == values)
+    {
+        return EINVAL;
+    }
 
-    while (hdr_iter_next(&iter))
+    struct hdr_iter iter;
+    const int64_t total_count = h->total_count;
+    // to avoid allocations we use the values array for intermediate computation
+    // i.e. to store the expected cumulative count at each percentile
+    for (size_t i = 0; i < length; i++)
     {
-        total += iter.count;
+        const double requested_percentile = percentiles[i] < 100.0 ? percentiles[i] : 100.0;
+        const int64_t count_at_percentile =
+        (int64_t) (((requested_percentile / 100) * total_count) + 0.5);
+        values[i] = count_at_percentile > 1 ? count_at_percentile : 1;
+    }
 
-        if (total >= count_at_percentile)
+    hdr_iter_init(&iter, h);
+    int64_t total = 0;
+    size_t at_pos = 0;
+    while (hdr_iter_next(&iter) && at_pos < length)
+    {
+        total += iter.count;
+        while (at_pos < length && total >= values[at_pos])
         {
-            int64_t value_from_index = iter.value;
-            return highest_equivalent_value(h, value_from_index);
+            values[at_pos] = highest_equivalent_value(h, iter.value);
+            at_pos++;
         }
     }
-
     return 0;
 }
 
@@ -757,11 +842,16 @@ static bool move_next(struct hdr_iter* iter)
 
     iter->count = counts_get_normalised(iter->h, iter->counts_index);
     iter->cumulative_count += iter->count;
-
-    iter->value = hdr_value_at_index(iter->h, iter->counts_index);
-    iter->highest_equivalent_value = highest_equivalent_value(iter->h, iter->value);
-    iter->lowest_equivalent_value = lowest_equivalent_value(iter->h, iter->value);
-    iter->median_equivalent_value = hdr_median_equivalent_value(iter->h, iter->value);
+    const int64_t value = hdr_value_at_index(iter->h, iter->counts_index);
+    const int32_t bucket_index = get_bucket_index(iter->h, value);
+    const int32_t sub_bucket_index = get_sub_bucket_index(value, bucket_index, iter->h->unit_magnitude);
+    const int64_t leq = lowest_equivalent_value_given_bucket_indices(iter->h, bucket_index, sub_bucket_index);
+    const int64_t size_of_equivalent_value_range = size_of_equivalent_value_range_given_bucket_indices(
+        iter->h, bucket_index, sub_bucket_index);
+    iter->lowest_equivalent_value = leq;
+    iter->value = value;
+    iter->highest_equivalent_value = leq + size_of_equivalent_value_range - 1;
+    iter->median_equivalent_value = leq + (size_of_equivalent_value_range >> 1);
 
     return true;
 }
diff --git a/deps/hdr_histogram/hdr_histogram.h b/deps/hdr_histogram/hdr_histogram.h
index 11ece2442..01b1e086c 100644
--- a/deps/hdr_histogram/hdr_histogram.h
+++ b/deps/hdr_histogram/hdr_histogram.h
@@ -13,9 +13,10 @@
 #include <stdint.h>
 #include <stdbool.h>
 #include <stdio.h>
+
 struct hdr_histogram
 {
-    int64_t lowest_trackable_value;
+    int64_t lowest_discernible_value;
     int64_t highest_trackable_value;
     int32_t unit_magnitude;
     int32_t significant_figures;
@@ -44,8 +45,8 @@ extern "C" {
  * involved math on the input parameters this function it is tricky to stack allocate.
  * The histogram should be released with hdr_close
  *
- * @param lowest_trackable_value The smallest possible value to be put into the
- * histogram.
+ * @param lowest_discernible_value The smallest possible value that is distinguishable from 0.
+ * Must be a positive integer that is >= 1. May be internally rounded down to nearest power of 2.
  * @param highest_trackable_value The largest possible value to be put into the
  * histogram.
  * @param significant_figures The level of precision for this histogram, i.e. the number
@@ -53,12 +54,12 @@ extern "C" {
  * the results from the histogram will be accurate up to the first three digits.  Must
  * be a value between 1 and 5 (inclusive).
  * @param result Output parameter to capture allocated histogram.
- * @return 0 on success, EINVAL if lowest_trackable_value is < 1 or the
+ * @return 0 on success, EINVAL if lowest_discernible_value is < 1 or the
  * significant_figure value is outside of the allowed range, ENOMEM if malloc
  * failed.
  */
 int hdr_init(
-    int64_t lowest_trackable_value,
+    int64_t lowest_discernible_value,
     int64_t highest_trackable_value,
     int significant_figures,
     struct hdr_histogram** result);
@@ -158,10 +159,10 @@ bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t co
  * Record a value in the histogram and backfill based on an expected interval.
  *
  * Records a value in the histogram, will round this value of to a precision at or better
- * than the significant_figure specified at contruction time.  This is specifically used
+ * than the significant_figure specified at construction time.  This is specifically used
  * for recording latency.  If the value is larger than the expected_interval then the
  * latency recording system has experienced co-ordinated omission.  This method fills in the
- * values that would have occured had the client providing the load not been blocked.
+ * values that would have occurred had the client providing the load not been blocked.
 
  * @param h "This" pointer
  * @param value Value to add to the histogram
@@ -169,16 +170,16 @@ bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t co
  * @return false if the value is larger than the highest_trackable_value and can't be recorded,
  * true otherwise.
  */
-bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expexcted_interval);
+bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t expected_interval);
 
 /**
  * Record a value in the histogram and backfill based on an expected interval.
  *
  * Records a value in the histogram, will round this value of to a precision at or better
- * than the significant_figure specified at contruction time.  This is specifically used
+ * than the significant_figure specified at construction time.  This is specifically used
  * for recording latency.  If the value is larger than the expected_interval then the
  * latency recording system has experienced co-ordinated omission.  This method fills in the
- * values that would have occured had the client providing the load not been blocked.
+ * values that would have occurred had the client providing the load not been blocked.
  *
  * Will record this value atomically, however the whole structure may appear inconsistent
  * when read concurrently with this update.  Do NOT mix calls to this method with calls
@@ -190,7 +191,7 @@ bool hdr_record_corrected_value(struct hdr_histogram* h, int64_t value, int64_t
  * @return false if the value is larger than the highest_trackable_value and can't be recorded,
  * true otherwise.
  */
-bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expexcted_interval);
+bool hdr_record_corrected_value_atomic(struct hdr_histogram* h, int64_t value, int64_t expected_interval);
 
 /**
  * Record a value in the histogram 'count' times.  Applies the same correcting logic
@@ -225,7 +226,7 @@ bool hdr_record_corrected_values_atomic(struct hdr_histogram* h, int64_t value,
 /**
  * Adds all of the values from 'from' to 'this' histogram.  Will return the
  * number of values that are dropped when copying.  Values will be dropped
- * if they around outside of h.lowest_trackable_value and
+ * if they around outside of h.lowest_discernible_value and
  * h.highest_trackable_value.
  *
  * @param h "This" pointer
@@ -237,7 +238,7 @@ int64_t hdr_add(struct hdr_histogram* h, const struct hdr_histogram* from);
 /**
  * Adds all of the values from 'from' to 'this' histogram.  Will return the
  * number of values that are dropped when copying.  Values will be dropped
- * if they around outside of h.lowest_trackable_value and
+ * if they around outside of h.lowest_discernible_value and
  * h.highest_trackable_value.
  *
  * @param h "This" pointer
@@ -272,6 +273,18 @@ int64_t hdr_max(const struct hdr_histogram* h);
 int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile);
 
 /**
+ * Get the values at the given percentiles.
+ *
+ * @param h "This" pointer.
+ * @param percentiles The ordered percentiles array to get the values for.
+ * @param length Number of elements in the arrays.
+ * @param values Destination array containing the values at the given percentiles.
+ * The values array should be allocated by the caller.
+ * @return 0 on success, ENOMEM if the provided destination array is null.
+ */
+int hdr_value_at_percentiles(const struct hdr_histogram *h, const double *percentiles, int64_t *values, size_t length);
+
+/**
  * Gets the standard deviation for the values in the histogram.
  *
  * @param h "This" pointer
@@ -469,7 +482,7 @@ int hdr_percentiles_print(
 */
 struct hdr_histogram_bucket_config
 {
-    int64_t lowest_trackable_value;
+    int64_t lowest_discernible_value;
     int64_t highest_trackable_value;
     int64_t unit_magnitude;
     int64_t significant_figures;
@@ -482,7 +495,7 @@ struct hdr_histogram_bucket_config
 };
 
 int hdr_calculate_bucket_config(
-    int64_t lowest_trackable_value,
+    int64_t lowest_discernible_value,
     int64_t highest_trackable_value,
     int significant_figures,
     struct hdr_histogram_bucket_config* cfg);
@@ -496,7 +509,7 @@ int64_t hdr_next_non_equivalent_value(const struct hdr_histogram* h, int64_t val
 int64_t hdr_median_equivalent_value(const struct hdr_histogram* h, int64_t value);
 
 /**
- * Used to reset counters after importing data manuallying into the histogram, used by the logging code
+ * Used to reset counters after importing data manually into the histogram, used by the logging code
  * and other custom serialisation tools.
  */
 void hdr_reset_internal_counters(struct hdr_histogram* h);
diff --git a/deps/hdr_histogram/hdr_redis_malloc.h b/deps/hdr_histogram/hdr_redis_malloc.h
new file mode 100644
index 000000000..d9401ca70
--- /dev/null
+++ b/deps/hdr_histogram/hdr_redis_malloc.h
@@ -0,0 +1,13 @@
+#ifndef HDR_MALLOC_H__
+#define HDR_MALLOC_H__
+
+void *zmalloc(size_t size);
+void *zcalloc_num(size_t num, size_t size);
+void *zrealloc(void *ptr, size_t size);
+void zfree(void *ptr);
+
+#define hdr_malloc zmalloc
+#define hdr_calloc zcalloc_num
+#define hdr_realloc zrealloc
+#define hdr_free zfree
+#endif
diff --git a/deps/hdr_histogram/hdr_tests.h b/deps/hdr_histogram/hdr_tests.h
new file mode 100644
index 000000000..c016d3a6d
--- /dev/null
+++ b/deps/hdr_histogram/hdr_tests.h
@@ -0,0 +1,22 @@
+#ifndef HDR_TESTS_H
+#define HDR_TESTS_H
+
+/* These are functions used in tests and are not intended for normal usage. */
+
+#include "hdr_histogram.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+int32_t counts_index_for(const struct hdr_histogram* h, int64_t value);
+int hdr_encode_compressed(struct hdr_histogram* h, uint8_t** compressed_histogram, size_t* compressed_len);
+int hdr_decode_compressed(uint8_t* buffer, size_t length, struct hdr_histogram** histogram);
+void hdr_base64_decode_block(const char* input, uint8_t* output);
+void hdr_base64_encode_block(const uint8_t* input, char* output);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif