folly/test/HistogramTest.cpp

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