1 /*
2  * Copyright (C) 2013 The Android Open Source Project
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 <memory>
18 #include <sstream>
19 
20 #include "gtest/gtest.h"
21 #include "histogram-inl.h"
22 
23 namespace art {
24 
25 // Simple usage:
26 //   Histogram *hist(new Histogram("SimplePercentiles"));
27 //   Percentile PerValue
28 //   hist->AddValue(121);
29 //   hist->AddValue(132);
30 //   hist->AddValue(140);
31 //   hist->AddValue(145);
32 //   hist->AddValue(155);
33 //   hist->CreateHistogram();
34 //   PerValue = hist->PercentileVal(0.50); finds the 50th percentile(median).
35 
TEST(Histtest,MeanTest)36 TEST(Histtest, MeanTest) {
37   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("MeanTest", 5));
38 
39   double mean;
40   for (size_t Idx = 0; Idx < 90; Idx++) {
41     hist->AddValue(static_cast<uint64_t>(50));
42   }
43   mean = hist->Mean();
44   EXPECT_DOUBLE_EQ(mean, 50.0);
45   hist->Reset();
46   hist->AddValue(9);
47   hist->AddValue(17);
48   hist->AddValue(28);
49   hist->AddValue(28);
50   mean = hist->Mean();
51   EXPECT_DOUBLE_EQ(20.5, mean);
52 }
53 
TEST(Histtest,VarianceTest)54 TEST(Histtest, VarianceTest) {
55   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("VarianceTest", 5));
56 
57   double variance;
58   hist->AddValue(9);
59   hist->AddValue(17);
60   hist->AddValue(28);
61   hist->AddValue(28);
62   variance = hist->Variance();
63   EXPECT_DOUBLE_EQ(64.25, variance);
64 }
65 
TEST(Histtest,Percentile)66 TEST(Histtest, Percentile) {
67   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("Percentile", 5));
68   Histogram<uint64_t>::CumulativeData data;
69 
70   double PerValue;
71 
72   hist->AddValue(20);
73   hist->AddValue(31);
74   hist->AddValue(42);
75   hist->AddValue(50);
76   hist->AddValue(60);
77   hist->AddValue(70);
78 
79   hist->AddValue(98);
80 
81   hist->AddValue(110);
82   hist->AddValue(121);
83   hist->AddValue(132);
84   hist->AddValue(140);
85   hist->AddValue(145);
86   hist->AddValue(155);
87 
88   hist->CreateHistogram(&data);
89   PerValue = hist->Percentile(0.50, data);
90   EXPECT_EQ(875, static_cast<int>(PerValue * 10));
91 }
92 
TEST(Histtest,UpdateRange)93 TEST(Histtest, UpdateRange) {
94   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("UpdateRange", 5));
95   Histogram<uint64_t>::CumulativeData data;
96 
97   double PerValue;
98 
99   hist->AddValue(15);
100   hist->AddValue(17);
101   hist->AddValue(35);
102   hist->AddValue(50);
103   hist->AddValue(68);
104   hist->AddValue(75);
105   hist->AddValue(93);
106   hist->AddValue(110);
107   hist->AddValue(121);
108   hist->AddValue(132);
109   hist->AddValue(140);  // Median  value
110   hist->AddValue(145);
111   hist->AddValue(155);
112   hist->AddValue(163);
113   hist->AddValue(168);
114   hist->AddValue(175);
115   hist->AddValue(182);
116   hist->AddValue(193);
117   hist->AddValue(200);
118   hist->AddValue(205);
119   hist->AddValue(212);
120   hist->CreateHistogram(&data);
121   PerValue = hist->Percentile(0.50, data);
122 
123   std::string text;
124   std::stringstream stream;
125   std::string expected("UpdateRange:\tSum: 2.654ms 99% C.I. 15us-212us Avg: 126.380us Max: 212us\n");
126   hist->PrintConfidenceIntervals(stream, 0.99, data);
127 
128   EXPECT_EQ(expected, stream.str());
129   EXPECT_GE(PerValue, 132);
130   EXPECT_LE(PerValue, 145);
131 }
132 
TEST(Histtest,Reset)133 TEST(Histtest, Reset) {
134   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("Reset", 5));
135 
136   double PerValue;
137   hist->AddValue(0);
138   hist->AddValue(189);
139   hist->AddValue(389);
140   hist->Reset();
141   hist->AddValue(15);
142   hist->AddValue(17);
143   hist->AddValue(35);
144   hist->AddValue(50);
145   hist->AddValue(68);
146   hist->AddValue(75);
147   hist->AddValue(93);
148   hist->AddValue(110);
149   hist->AddValue(121);
150   hist->AddValue(132);
151   hist->AddValue(140);  // Median  value
152   hist->AddValue(145);
153   hist->AddValue(155);
154   hist->AddValue(163);
155   hist->AddValue(168);
156   hist->AddValue(175);
157   hist->AddValue(182);
158   hist->AddValue(193);
159   hist->AddValue(200);
160   hist->AddValue(205);
161   hist->AddValue(212);
162   Histogram<uint64_t>::CumulativeData data;
163   hist->CreateHistogram(&data);
164   PerValue = hist->Percentile(0.50, data);
165 
166   std::string text;
167   std::stringstream stream;
168   std::string expected("Reset:\tSum: 2.654ms 99% C.I. 15us-212us Avg: 126.380us Max: 212us\n");
169   hist->PrintConfidenceIntervals(stream, 0.99, data);
170 
171   EXPECT_EQ(expected, stream.str());
172   EXPECT_GE(PerValue, 132);
173   EXPECT_LE(PerValue, 145);
174 }
175 
TEST(Histtest,MultipleCreateHist)176 TEST(Histtest, MultipleCreateHist) {
177   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("MultipleCreateHist", 5));
178   Histogram<uint64_t>::CumulativeData data;
179 
180   double PerValue;
181   hist->AddValue(15);
182   hist->AddValue(17);
183   hist->AddValue(35);
184   hist->AddValue(50);
185   hist->AddValue(68);
186   hist->AddValue(75);
187   hist->AddValue(93);
188   hist->CreateHistogram(&data);
189   hist->AddValue(110);
190   hist->AddValue(121);
191   hist->AddValue(132);
192   hist->AddValue(140);  // Median  value
193   hist->AddValue(145);
194   hist->AddValue(155);
195   hist->AddValue(163);
196   hist->AddValue(168);
197   hist->CreateHistogram(&data);
198   hist->AddValue(175);
199   hist->AddValue(182);
200   hist->AddValue(193);
201   hist->AddValue(200);
202   hist->AddValue(205);
203   hist->AddValue(212);
204   hist->CreateHistogram(&data);
205   PerValue = hist->Percentile(0.50, data);
206   std::stringstream stream;
207   std::string expected("MultipleCreateHist:\tSum: 2.654ms 99% C.I. 15us-212us Avg: 126.380us Max: 212us\n");
208   hist->PrintConfidenceIntervals(stream, 0.99, data);
209 
210   EXPECT_EQ(expected, stream.str());
211   EXPECT_GE(PerValue, 132);
212   EXPECT_LE(PerValue, 145);
213 }
214 
TEST(Histtest,SingleValue)215 TEST(Histtest, SingleValue) {
216   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("SingleValue", 5));
217   Histogram<uint64_t>::CumulativeData data;
218 
219   hist->AddValue(1);
220   hist->CreateHistogram(&data);
221   std::stringstream stream;
222   std::string expected = "SingleValue:\tSum: 1us 99% C.I. 1us-1us Avg: 1us Max: 1us\n";
223   hist->PrintConfidenceIntervals(stream, 0.99, data);
224   EXPECT_EQ(expected, stream.str());
225 }
226 
TEST(Histtest,CappingPercentiles)227 TEST(Histtest, CappingPercentiles) {
228   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("CappingPercentiles", 5));
229   Histogram<uint64_t>::CumulativeData data;
230 
231   double per_995;
232   double per_005;
233   // All values are similar.
234   for (uint64_t idx = 0ull; idx < 150ull; idx++) {
235     hist->AddValue(0);
236   }
237   hist->CreateHistogram(&data);
238   per_995 = hist->Percentile(0.995, data);
239   EXPECT_DOUBLE_EQ(per_995, 0.0);
240   hist->Reset();
241   for (size_t idx = 0; idx < 200; idx++) {
242     for (uint64_t val = 1ull; val <= 4ull; val++) {
243       hist->AddValue(val);
244     }
245   }
246   hist->CreateHistogram(&data);
247   per_005 = hist->Percentile(0.005, data);
248   per_995 = hist->Percentile(0.995, data);
249   EXPECT_DOUBLE_EQ(1.0, per_005);
250   EXPECT_DOUBLE_EQ(4.0, per_995);
251 }
252 
TEST(Histtest,SpikyValues)253 TEST(Histtest, SpikyValues) {
254   std::unique_ptr<Histogram<uint64_t>> hist(new Histogram<uint64_t>("SpikyValues", 5, 4096));
255   Histogram<uint64_t>::CumulativeData data;
256 
257   for (uint64_t idx = 0ull; idx < 30ull; idx++) {
258     for (uint64_t idx_inner = 0ull; idx_inner < 5ull; idx_inner++) {
259       hist->AddValue(idx * idx_inner);
260     }
261   }
262   hist->AddValue(10000);
263   hist->CreateHistogram(&data);
264   std::stringstream stream;
265   std::string expected = "SpikyValues:\tSum: 14.350ms 99% C.I. 0.089us-2541.825us Avg: 95.033us Max: 10000us\n";
266   hist->PrintConfidenceIntervals(stream, 0.99, data);
267   EXPECT_EQ(expected, stream.str());
268 }
269 
270 }  // namespace art
271