LCOV - code coverage report
Current view: top level - core/support - histogram.c (source / functions) Hit Total Coverage
Test: tmp.CaZ6RjdVn2 Lines: 98 99 99.0 %
Date: 2015-12-10 22:15:08 Functions: 19 19 100.0 %

          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             : }

Generated by: LCOV version 1.11