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
12namespace leveldb {
13
14const 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
171void 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
182void 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
196void 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
207double Histogram::Median() const { return Percentile(50.0); }
208
209double 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
230double Histogram::Average() const {
231 if (num_ == 0.0) return 0;
232 return sum_ / num_;
233}
234
235double 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
241std::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