1 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #include "util/histogram.h" |
6 | |
7 | #include <cmath> |
8 | #include <cstdio> |
9 | |
10 | #include "port/port.h" |
11 | |
12 | namespace leveldb { |
13 | |
14 | const double Histogram::kBucketLimit[kNumBuckets] = { |
15 | 1, |
16 | 2, |
17 | 3, |
18 | 4, |
19 | 5, |
20 | 6, |
21 | 7, |
22 | 8, |
23 | 9, |
24 | 10, |
25 | 12, |
26 | 14, |
27 | 16, |
28 | 18, |
29 | 20, |
30 | 25, |
31 | 30, |
32 | 35, |
33 | 40, |
34 | 45, |
35 | 50, |
36 | 60, |
37 | 70, |
38 | 80, |
39 | 90, |
40 | 100, |
41 | 120, |
42 | 140, |
43 | 160, |
44 | 180, |
45 | 200, |
46 | 250, |
47 | 300, |
48 | 350, |
49 | 400, |
50 | 450, |
51 | 500, |
52 | 600, |
53 | 700, |
54 | 800, |
55 | 900, |
56 | 1000, |
57 | 1200, |
58 | 1400, |
59 | 1600, |
60 | 1800, |
61 | 2000, |
62 | 2500, |
63 | 3000, |
64 | 3500, |
65 | 4000, |
66 | 4500, |
67 | 5000, |
68 | 6000, |
69 | 7000, |
70 | 8000, |
71 | 9000, |
72 | 10000, |
73 | 12000, |
74 | 14000, |
75 | 16000, |
76 | 18000, |
77 | 20000, |
78 | 25000, |
79 | 30000, |
80 | 35000, |
81 | 40000, |
82 | 45000, |
83 | 50000, |
84 | 60000, |
85 | 70000, |
86 | 80000, |
87 | 90000, |
88 | 100000, |
89 | 120000, |
90 | 140000, |
91 | 160000, |
92 | 180000, |
93 | 200000, |
94 | 250000, |
95 | 300000, |
96 | 350000, |
97 | 400000, |
98 | 450000, |
99 | 500000, |
100 | 600000, |
101 | 700000, |
102 | 800000, |
103 | 900000, |
104 | 1000000, |
105 | 1200000, |
106 | 1400000, |
107 | 1600000, |
108 | 1800000, |
109 | 2000000, |
110 | 2500000, |
111 | 3000000, |
112 | 3500000, |
113 | 4000000, |
114 | 4500000, |
115 | 5000000, |
116 | 6000000, |
117 | 7000000, |
118 | 8000000, |
119 | 9000000, |
120 | 10000000, |
121 | 12000000, |
122 | 14000000, |
123 | 16000000, |
124 | 18000000, |
125 | 20000000, |
126 | 25000000, |
127 | 30000000, |
128 | 35000000, |
129 | 40000000, |
130 | 45000000, |
131 | 50000000, |
132 | 60000000, |
133 | 70000000, |
134 | 80000000, |
135 | 90000000, |
136 | 100000000, |
137 | 120000000, |
138 | 140000000, |
139 | 160000000, |
140 | 180000000, |
141 | 200000000, |
142 | 250000000, |
143 | 300000000, |
144 | 350000000, |
145 | 400000000, |
146 | 450000000, |
147 | 500000000, |
148 | 600000000, |
149 | 700000000, |
150 | 800000000, |
151 | 900000000, |
152 | 1000000000, |
153 | 1200000000, |
154 | 1400000000, |
155 | 1600000000, |
156 | 1800000000, |
157 | 2000000000, |
158 | 2500000000.0, |
159 | 3000000000.0, |
160 | 3500000000.0, |
161 | 4000000000.0, |
162 | 4500000000.0, |
163 | 5000000000.0, |
164 | 6000000000.0, |
165 | 7000000000.0, |
166 | 8000000000.0, |
167 | 9000000000.0, |
168 | 1e200, |
169 | }; |
170 | |
171 | void Histogram::Clear() { |
172 | min_ = kBucketLimit[kNumBuckets - 1]; |
173 | max_ = 0; |
174 | num_ = 0; |
175 | sum_ = 0; |
176 | sum_squares_ = 0; |
177 | for (int i = 0; i < kNumBuckets; i++) { |
178 | buckets_[i] = 0; |
179 | } |
180 | } |
181 | |
182 | void Histogram::Add(double value) { |
183 | // Linear search is fast enough for our usage in db_bench |
184 | int b = 0; |
185 | while (b < kNumBuckets - 1 && kBucketLimit[b] <= value) { |
186 | b++; |
187 | } |
188 | buckets_[b] += 1.0; |
189 | if (min_ > value) min_ = value; |
190 | if (max_ < value) max_ = value; |
191 | num_++; |
192 | sum_ += value; |
193 | sum_squares_ += (value * value); |
194 | } |
195 | |
196 | void Histogram::Merge(const Histogram& other) { |
197 | if (other.min_ < min_) min_ = other.min_; |
198 | if (other.max_ > max_) max_ = other.max_; |
199 | num_ += other.num_; |
200 | sum_ += other.sum_; |
201 | sum_squares_ += other.sum_squares_; |
202 | for (int b = 0; b < kNumBuckets; b++) { |
203 | buckets_[b] += other.buckets_[b]; |
204 | } |
205 | } |
206 | |
207 | double Histogram::Median() const { return Percentile(50.0); } |
208 | |
209 | double Histogram::Percentile(double p) const { |
210 | double threshold = num_ * (p / 100.0); |
211 | double sum = 0; |
212 | for (int b = 0; b < kNumBuckets; b++) { |
213 | sum += buckets_[b]; |
214 | if (sum >= threshold) { |
215 | // Scale linearly within this bucket |
216 | double left_point = (b == 0) ? 0 : kBucketLimit[b - 1]; |
217 | double right_point = kBucketLimit[b]; |
218 | double left_sum = sum - buckets_[b]; |
219 | double right_sum = sum; |
220 | double pos = (threshold - left_sum) / (right_sum - left_sum); |
221 | double r = left_point + (right_point - left_point) * pos; |
222 | if (r < min_) r = min_; |
223 | if (r > max_) r = max_; |
224 | return r; |
225 | } |
226 | } |
227 | return max_; |
228 | } |
229 | |
230 | double Histogram::Average() const { |
231 | if (num_ == 0.0) return 0; |
232 | return sum_ / num_; |
233 | } |
234 | |
235 | double Histogram::StandardDeviation() const { |
236 | if (num_ == 0.0) return 0; |
237 | double variance = (sum_squares_ * num_ - sum_ * sum_) / (num_ * num_); |
238 | return sqrt(variance); |
239 | } |
240 | |
241 | std::string Histogram::ToString() const { |
242 | std::string r; |
243 | char buf[200]; |
244 | std::snprintf(buf, sizeof(buf), "Count: %.0f Average: %.4f StdDev: %.2f\n" , |
245 | num_, Average(), StandardDeviation()); |
246 | r.append(buf); |
247 | std::snprintf(buf, sizeof(buf), "Min: %.4f Median: %.4f Max: %.4f\n" , |
248 | (num_ == 0.0 ? 0.0 : min_), Median(), max_); |
249 | r.append(buf); |
250 | r.append("------------------------------------------------------\n" ); |
251 | const double mult = 100.0 / num_; |
252 | double sum = 0; |
253 | for (int b = 0; b < kNumBuckets; b++) { |
254 | if (buckets_[b] <= 0.0) continue; |
255 | sum += buckets_[b]; |
256 | std::snprintf(buf, sizeof(buf), "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% " , |
257 | ((b == 0) ? 0.0 : kBucketLimit[b - 1]), // left |
258 | kBucketLimit[b], // right |
259 | buckets_[b], // count |
260 | mult * buckets_[b], // percentage |
261 | mult * sum); // cumulative percentage |
262 | r.append(buf); |
263 | |
264 | // Add hash marks based on percentage; 20 marks for 100%. |
265 | int marks = static_cast<int>(20 * (buckets_[b] / num_) + 0.5); |
266 | r.append(marks, '#'); |
267 | r.push_back('\n'); |
268 | } |
269 | return r; |
270 | } |
271 | |
272 | } // namespace leveldb |
273 | |