folly/stats/test/HistogramTest.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <folly/stats/Histogram.h>
  18
  19 #include <folly/portability/GTest.h>
  20 #include <folly/stats/Histogram-defs.h>
  21
  22 using folly::Histogram;
  23
  24 // Insert 100 evenly distributed values into a histogram with 100 buckets
  25 TEST(Histogram, Test100) {
  26   Histogram<int64_t> h(1, 0, 100);
  27
  28   for (unsigned int n = 0; n < 100; ++n) {
  29     h.addValue(n);
  30   }
  31
  32   // 100 buckets, plus 1 for below min, and 1 for above max
  33   EXPECT_EQ(h.getNumBuckets(), 102);
  34
  35   double epsilon = 1e-6;
  36   for (unsigned int n = 0; n <= 100; ++n) {
  37     double pct = n / 100.0;
  38
  39     // Floating point arithmetic isn't 100% accurate, and if we just divide
  40     // (n / 100) the value should be exactly on a bucket boundary.  Add espilon
  41     // to ensure we fall in the upper bucket.
  42     if (n < 100) {
  43       double lowPct = -1.0;
  44       double highPct = -1.0;
  45       unsigned int bucketIdx =
  46           h.getPercentileBucketIdx(pct + epsilon, &lowPct, &highPct);
  47       EXPECT_EQ(n + 1, bucketIdx);
  48       EXPECT_FLOAT_EQ(n / 100.0, lowPct);
  49       EXPECT_FLOAT_EQ((n + 1) / 100.0, highPct);
  50     }
  51
  52     // Also test n - epsilon, to test falling in the lower bucket.
  53     if (n > 0) {
  54       double lowPct = -1.0;
  55       double highPct = -1.0;
  56       unsigned int bucketIdx =
  57           h.getPercentileBucketIdx(pct - epsilon, &lowPct, &highPct);
  58       EXPECT_EQ(n, bucketIdx);
  59       EXPECT_FLOAT_EQ((n - 1) / 100.0, lowPct);
  60       EXPECT_FLOAT_EQ(n / 100.0, highPct);
  61     }
  62
  63     // Check getPercentileEstimate()
  64     EXPECT_EQ(n, h.getPercentileEstimate(pct));
  65   }
  66 }
  67
  68 // Test calling getPercentileBucketIdx() and getPercentileEstimate() on an
  69 // empty histogram
  70 TEST(Histogram, TestEmpty) {
  71   Histogram<int64_t> h(1, 0, 100);
  72
  73   for (unsigned int n = 0; n <= 100; ++n) {
  74     double pct = n / 100.0;
  75
  76     double lowPct = -1.0;
  77     double highPct = -1.0;
  78     unsigned int bucketIdx = h.getPercentileBucketIdx(pct, &lowPct, &highPct);
  79     EXPECT_EQ(1, bucketIdx);
  80     EXPECT_FLOAT_EQ(0.0, lowPct);
  81     EXPECT_FLOAT_EQ(0.0, highPct);
  82
  83     EXPECT_EQ(0, h.getPercentileEstimate(pct));
  84   }
  85 }
  86
  87 // Test calling getPercentileBucketIdx() and getPercentileEstimate() on a
  88 // histogram with just a single value.
  89 TEST(Histogram, Test1) {
  90   Histogram<int64_t> h(1, 0, 100);
  91   h.addValue(42);
  92
  93   for (unsigned int n = 0; n < 100; ++n) {
  94     double pct = n / 100.0;
  95
  96     double lowPct = -1.0;
  97     double highPct = -1.0;
  98     unsigned int bucketIdx = h.getPercentileBucketIdx(pct, &lowPct, &highPct);
  99     EXPECT_EQ(43, bucketIdx);
 100     EXPECT_FLOAT_EQ(0.0, lowPct);
 101     EXPECT_FLOAT_EQ(1.0, highPct);
 102
 103     EXPECT_EQ(42, h.getPercentileEstimate(pct));
 104   }
 105 }
 106
 107 // Test adding enough numbers to make the sum value overflow in the
 108 // "below min" bucket
 109 TEST(Histogram, TestOverflowMin) {
 110   Histogram<int64_t> h(1, 0, 100);
 111
 112   for (unsigned int n = 0; n < 9; ++n) {
 113     h.addValue(-0x0fffffffffffffff);
 114   }
 115
 116   // Compute a percentile estimate.  We only added values to the "below min"
 117   // bucket, so this should check that bucket.  We're mainly verifying that the
 118   // code doesn't crash here when the bucket average is larger than the max
 119   // value that is supposed to be in the bucket.
 120   int64_t estimate = h.getPercentileEstimate(0.05);
 121   // The code will return the smallest possible value when it detects an
 122   // overflow beyond the minimum value.
 123   EXPECT_EQ(std::numeric_limits<int64_t>::min(), estimate);
 124 }
 125
 126 // Test adding enough numbers to make the sum value overflow in the
 127 // "above max" bucket
 128 TEST(Histogram, TestOverflowMax) {
 129   Histogram<int64_t> h(1, 0, 100);
 130
 131   for (unsigned int n = 0; n < 9; ++n) {
 132     h.addValue(0x0fffffffffffffff);
 133   }
 134
 135   // The code will return the maximum possible value when it detects an
 136   // overflow beyond the max value.
 137   int64_t estimate = h.getPercentileEstimate(0.95);
 138   EXPECT_EQ(std::numeric_limits<int64_t>::max(), estimate);
 139 }
 140
 141 // Test adding enough numbers to make the sum value overflow in one of the
 142 // normal buckets
 143 TEST(Histogram, TestOverflowBucket) {
 144   Histogram<int64_t> h(0x0100000000000000, 0, 0x1000000000000000);
 145
 146   for (unsigned int n = 0; n < 9; ++n) {
 147     h.addValue(0x0fffffffffffffff);
 148   }
 149
 150   // The histogram code should return the bucket midpoint
 151   // when it detects overflow.
 152   int64_t estimate = h.getPercentileEstimate(0.95);
 153   EXPECT_EQ(0x0f80000000000000, estimate);
 154 }
 155
 156 TEST(Histogram, TestDouble) {
 157   // Insert 100 evenly spaced values into a histogram
 158   Histogram<double> h(100.0, 0.0, 5000.0);
 159   for (double n = 50; n < 5000; n += 100) {
 160     h.addValue(n);
 161   }
 162   EXPECT_EQ(52, h.getNumBuckets());
 163   EXPECT_EQ(2500.0, h.getPercentileEstimate(0.5));
 164   EXPECT_EQ(4500.0, h.getPercentileEstimate(0.9));
 165 }
 166
 167 // Test where the bucket width is not an even multiple of the histogram range
 168 TEST(Histogram, TestDoubleInexactWidth) {
 169   Histogram<double> h(100.0, 0.0, 4970.0);
 170   for (double n = 50; n < 5000; n += 100) {
 171     h.addValue(n);
 172   }
 173   EXPECT_EQ(52, h.getNumBuckets());
 174   EXPECT_EQ(2500.0, h.getPercentileEstimate(0.5));
 175   EXPECT_EQ(4500.0, h.getPercentileEstimate(0.9));
 176
 177   EXPECT_EQ(0, h.getBucketByIndex(51).count);
 178   h.addValue(4990);
 179   h.addValue(5100);
 180   EXPECT_EQ(2, h.getBucketByIndex(51).count);
 181   EXPECT_EQ(2600.0, h.getPercentileEstimate(0.5));
 182 }
 183
 184 // Test where the bucket width is larger than the histogram range
 185 // (There isn't really much point to defining a histogram this way,
 186 // but we want to ensure that it still works just in case.)
 187 TEST(Histogram, TestDoubleWidthTooBig) {
 188   Histogram<double> h(100.0, 0.0, 7.0);
 189   EXPECT_EQ(3, h.getNumBuckets());
 190
 191   for (double n = 0; n < 7; n += 1) {
 192     h.addValue(n);
 193   }
 194   EXPECT_EQ(0, h.getBucketByIndex(0).count);
 195   EXPECT_EQ(7, h.getBucketByIndex(1).count);
 196   EXPECT_EQ(0, h.getBucketByIndex(2).count);
 197   EXPECT_EQ(3.0, h.getPercentileEstimate(0.5));
 198
 199   h.addValue(-1.0);
 200   EXPECT_EQ(1, h.getBucketByIndex(0).count);
 201   h.addValue(7.5);
 202   EXPECT_EQ(1, h.getBucketByIndex(2).count);
 203   EXPECT_NEAR(3.0, h.getPercentileEstimate(0.5), 1e-14);
 204 }
 205
 206 // Test that we get counts right
 207 TEST(Histogram, Counts) {
 208   Histogram<int32_t> h(1, 0, 10);
 209   EXPECT_EQ(12, h.getNumBuckets());
 210   EXPECT_EQ(0, h.computeTotalCount());
 211
 212   // Add one to each bucket, make sure the counts match
 213   for (int32_t i = 0; i < 10; i++) {
 214     h.addValue(i);
 215     EXPECT_EQ(i + 1, h.computeTotalCount());
 216   }
 217
 218   // Add a lot to one bucket, make sure the counts still make sense
 219   for (int32_t i = 0; i < 100; i++) {
 220     h.addValue(0);
 221   }
 222   EXPECT_EQ(110, h.computeTotalCount());
 223 }