Branch data Line data Source code
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 <math.h>
8 : : #include <stdio.h>
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 : 0 : void Histogram::Clear() {
172 : 0 : min_ = kBucketLimit[kNumBuckets - 1];
173 : 0 : max_ = 0;
174 : 0 : num_ = 0;
175 : 0 : sum_ = 0;
176 : 0 : sum_squares_ = 0;
177 [ # # ]: 0 : for (int i = 0; i < kNumBuckets; i++) {
178 : 0 : buckets_[i] = 0;
179 : : }
180 : 0 : }
181 : :
182 : 0 : void Histogram::Add(double value) {
183 : : // Linear search is fast enough for our usage in db_bench
184 : 0 : int b = 0;
185 [ # # # # ]: 0 : while (b < kNumBuckets - 1 && kBucketLimit[b] <= value) {
186 : 0 : b++;
187 : : }
188 : 0 : buckets_[b] += 1.0;
189 [ # # ]: 0 : if (min_ > value) min_ = value;
190 [ # # ]: 0 : if (max_ < value) max_ = value;
191 : 0 : num_++;
192 : 0 : sum_ += value;
193 : 0 : sum_squares_ += (value * value);
194 : 0 : }
195 : :
196 : 0 : void Histogram::Merge(const Histogram& other) {
197 [ # # ]: 0 : if (other.min_ < min_) min_ = other.min_;
198 [ # # ]: 0 : if (other.max_ > max_) max_ = other.max_;
199 : 0 : num_ += other.num_;
200 : 0 : sum_ += other.sum_;
201 : 0 : sum_squares_ += other.sum_squares_;
202 [ # # ]: 0 : for (int b = 0; b < kNumBuckets; b++) {
203 : 0 : buckets_[b] += other.buckets_[b];
204 : : }
205 : 0 : }
206 : :
207 : 0 : double Histogram::Median() const { return Percentile(50.0); }
208 : :
209 : 0 : double Histogram::Percentile(double p) const {
210 : 0 : double threshold = num_ * (p / 100.0);
211 : 0 : double sum = 0;
212 [ # # ]: 0 : for (int b = 0; b < kNumBuckets; b++) {
213 : 0 : sum += buckets_[b];
214 [ # # ]: 0 : if (sum >= threshold) {
215 : : // Scale linearly within this bucket
216 [ # # ]: 0 : double left_point = (b == 0) ? 0 : kBucketLimit[b - 1];
217 : 0 : double right_point = kBucketLimit[b];
218 : 0 : double left_sum = sum - buckets_[b];
219 : 0 : double right_sum = sum;
220 : 0 : double pos = (threshold - left_sum) / (right_sum - left_sum);
221 : 0 : double r = left_point + (right_point - left_point) * pos;
222 [ # # ]: 0 : if (r < min_) r = min_;
223 [ # # ]: 0 : if (r > max_) r = max_;
224 : 0 : return r;
225 : : }
226 : : }
227 : 0 : return max_;
228 : : }
229 : :
230 : 0 : double Histogram::Average() const {
231 [ # # ]: 0 : if (num_ == 0.0) return 0;
232 : 0 : return sum_ / num_;
233 : : }
234 : :
235 : 0 : double Histogram::StandardDeviation() const {
236 [ # # ]: 0 : if (num_ == 0.0) return 0;
237 : 0 : double variance = (sum_squares_ * num_ - sum_ * sum_) / (num_ * num_);
238 : 0 : return sqrt(variance);
239 : : }
240 : :
241 : 0 : std::string Histogram::ToString() const {
242 [ # # ]: 0 : std::string r;
243 : 0 : char buf[200];
244 [ # # # # : 0 : snprintf(buf, sizeof(buf), "Count: %.0f Average: %.4f StdDev: %.2f\n", num_,
# # ]
245 : : Average(), StandardDeviation());
246 [ # # ]: 0 : r.append(buf);
247 : 0 : snprintf(buf, sizeof(buf), "Min: %.4f Median: %.4f Max: %.4f\n",
248 [ # # # # ]: 0 : (num_ == 0.0 ? 0.0 : min_), Median(), max_);
249 [ # # ]: 0 : r.append(buf);
250 [ # # ]: 0 : r.append("------------------------------------------------------\n");
251 : 0 : const double mult = 100.0 / num_;
252 : 0 : double sum = 0;
253 [ # # ]: 0 : for (int b = 0; b < kNumBuckets; b++) {
254 [ # # ]: 0 : if (buckets_[b] <= 0.0) continue;
255 : 0 : sum += buckets_[b];
256 : 0 : snprintf(buf, sizeof(buf), "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ",
257 : 0 : ((b == 0) ? 0.0 : kBucketLimit[b - 1]), // left
258 [ # # ]: 0 : kBucketLimit[b], // right
259 : : buckets_[b], // count
260 : : mult * buckets_[b], // percentage
261 : : mult * sum); // cumulative percentage
262 [ # # ]: 0 : r.append(buf);
263 : :
264 : : // Add hash marks based on percentage; 20 marks for 100%.
265 : 0 : int marks = static_cast<int>(20 * (buckets_[b] / num_) + 0.5);
266 [ # # ]: 0 : r.append(marks, '#');
267 [ # # ]: 0 : r.push_back('\n');
268 : : }
269 : 0 : return r;
270 : 0 : }
271 : :
272 : : } // namespace leveldb
|
