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