2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/stats/Histogram.h>
18 #include <folly/stats/Histogram-defs.h>
20 #include <gflags/gflags.h>
21 #include <gtest/gtest.h>
23 using folly::Histogram;
25 // Insert 100 evenly distributed values into a histogram with 100 buckets
26 TEST(Histogram, Test100) {
27 Histogram<int64_t> h(1, 0, 100);
29 for (unsigned int n = 0; n < 100; ++n) {
33 // 100 buckets, plus 1 for below min, and 1 for above max
34 EXPECT_EQ(h.getNumBuckets(), 102);
36 double epsilon = 1e-6;
37 for (unsigned int n = 0; n <= 100; ++n) {
38 double pct = n / 100.0;
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.
45 double highPct = -1.0;
46 unsigned int bucketIdx = h.getPercentileBucketIdx(pct + epsilon,
48 EXPECT_EQ(n + 1, bucketIdx);
49 EXPECT_FLOAT_EQ(n / 100.0, lowPct);
50 EXPECT_FLOAT_EQ((n + 1) / 100.0, highPct);
53 // Also test n - epsilon, to test falling in the lower bucket.
56 double highPct = -1.0;
57 unsigned int bucketIdx = h.getPercentileBucketIdx(pct - epsilon,
59 EXPECT_EQ(n, bucketIdx);
60 EXPECT_FLOAT_EQ((n - 1) / 100.0, lowPct);
61 EXPECT_FLOAT_EQ(n / 100.0, highPct);
64 // Check getPercentileEstimate()
65 EXPECT_EQ(n, h.getPercentileEstimate(pct));
69 // Test calling getPercentileBucketIdx() and getPercentileEstimate() on an
71 TEST(Histogram, TestEmpty) {
72 Histogram<int64_t> h(1, 0, 100);
74 for (unsigned int n = 0; n <= 100; ++n) {
75 double pct = n / 100.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);
84 EXPECT_EQ(0, h.getPercentileEstimate(pct));
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);
94 for (unsigned int n = 0; n < 100; ++n) {
95 double pct = n / 100.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);
104 EXPECT_EQ(42, h.getPercentileEstimate(pct));
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);
113 for (unsigned int n = 0; n < 9; ++n) {
114 h.addValue(-0x0fffffffffffffff);
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);
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);
132 for (unsigned int n = 0; n < 9; ++n) {
133 h.addValue(0x0fffffffffffffff);
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);
142 // Test adding enough numbers to make the sum value overflow in one of the
144 TEST(Histogram, TestOverflowBucket) {
145 Histogram<int64_t> h(0x0100000000000000, 0, 0x1000000000000000);
147 for (unsigned int n = 0; n < 9; ++n) {
148 h.addValue(0x0fffffffffffffff);
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);
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) {
163 EXPECT_EQ(52, h.getNumBuckets());
164 EXPECT_EQ(2500.0, h.getPercentileEstimate(0.5));
165 EXPECT_EQ(4500.0, h.getPercentileEstimate(0.9));
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) {
174 EXPECT_EQ(52, h.getNumBuckets());
175 EXPECT_EQ(2500.0, h.getPercentileEstimate(0.5));
176 EXPECT_EQ(4500.0, h.getPercentileEstimate(0.9));
178 EXPECT_EQ(0, h.getBucketByIndex(51).count);
181 EXPECT_EQ(2, h.getBucketByIndex(51).count);
182 EXPECT_EQ(2600.0, h.getPercentileEstimate(0.5));
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());
192 for (double n = 0; n < 7; n += 1) {
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));
201 EXPECT_EQ(1, h.getBucketByIndex(0).count);
203 EXPECT_EQ(1, h.getBucketByIndex(2).count);
204 EXPECT_EQ(3.0, h.getPercentileEstimate(0.5));
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());
213 // Add one to each bucket, make sure the counts match
214 for (int32_t i = 0; i < 10; i++) {
216 EXPECT_EQ(i+1, h.computeTotalCount());
219 // Add a lot to one bucket, make sure the counts still make sense
220 for (int32_t i = 0; i < 100; i++) {
223 EXPECT_EQ(110, h.computeTotalCount());