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 <math.h>
6 : #include <stdio.h>
7 : #include "port/port.h"
8 : #include "util/histogram.h"
9 :
10 : namespace leveldb {
11 :
12 : const double Histogram::kBucketLimit[kNumBuckets] = {
13 : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 25, 30, 35, 40, 45,
14 : 50, 60, 70, 80, 90, 100, 120, 140, 160, 180, 200, 250, 300, 350, 400, 450,
15 : 500, 600, 700, 800, 900, 1000, 1200, 1400, 1600, 1800, 2000, 2500, 3000,
16 : 3500, 4000, 4500, 5000, 6000, 7000, 8000, 9000, 10000, 12000, 14000,
17 : 16000, 18000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 60000,
18 : 70000, 80000, 90000, 100000, 120000, 140000, 160000, 180000, 200000,
19 : 250000, 300000, 350000, 400000, 450000, 500000, 600000, 700000, 800000,
20 : 900000, 1000000, 1200000, 1400000, 1600000, 1800000, 2000000, 2500000,
21 : 3000000, 3500000, 4000000, 4500000, 5000000, 6000000, 7000000, 8000000,
22 : 9000000, 10000000, 12000000, 14000000, 16000000, 18000000, 20000000,
23 : 25000000, 30000000, 35000000, 40000000, 45000000, 50000000, 60000000,
24 : 70000000, 80000000, 90000000, 100000000, 120000000, 140000000, 160000000,
25 : 180000000, 200000000, 250000000, 300000000, 350000000, 400000000,
26 : 450000000, 500000000, 600000000, 700000000, 800000000, 900000000,
27 : 1000000000, 1200000000, 1400000000, 1600000000, 1800000000, 2000000000,
28 : 2500000000.0, 3000000000.0, 3500000000.0, 4000000000.0, 4500000000.0,
29 : 5000000000.0, 6000000000.0, 7000000000.0, 8000000000.0, 9000000000.0,
30 : 1e200,
31 : };
32 :
33 0 : void Histogram::Clear() {
34 0 : min_ = kBucketLimit[kNumBuckets-1];
35 0 : max_ = 0;
36 0 : num_ = 0;
37 0 : sum_ = 0;
38 0 : sum_squares_ = 0;
39 0 : for (int i = 0; i < kNumBuckets; i++) {
40 0 : buckets_[i] = 0;
41 : }
42 0 : }
43 :
44 0 : void Histogram::Add(double value) {
45 : // Linear search is fast enough for our usage in db_bench
46 0 : int b = 0;
47 0 : while (b < kNumBuckets - 1 && kBucketLimit[b] <= value) {
48 0 : b++;
49 : }
50 0 : buckets_[b] += 1.0;
51 0 : if (min_ > value) min_ = value;
52 0 : if (max_ < value) max_ = value;
53 0 : num_++;
54 0 : sum_ += value;
55 0 : sum_squares_ += (value * value);
56 0 : }
57 :
58 0 : void Histogram::Merge(const Histogram& other) {
59 0 : if (other.min_ < min_) min_ = other.min_;
60 0 : if (other.max_ > max_) max_ = other.max_;
61 0 : num_ += other.num_;
62 0 : sum_ += other.sum_;
63 0 : sum_squares_ += other.sum_squares_;
64 0 : for (int b = 0; b < kNumBuckets; b++) {
65 0 : buckets_[b] += other.buckets_[b];
66 : }
67 0 : }
68 :
69 0 : double Histogram::Median() const {
70 0 : return Percentile(50.0);
71 : }
72 :
73 0 : double Histogram::Percentile(double p) const {
74 0 : double threshold = num_ * (p / 100.0);
75 0 : double sum = 0;
76 0 : for (int b = 0; b < kNumBuckets; b++) {
77 0 : sum += buckets_[b];
78 0 : if (sum >= threshold) {
79 : // Scale linearly within this bucket
80 0 : double left_point = (b == 0) ? 0 : kBucketLimit[b-1];
81 0 : double right_point = kBucketLimit[b];
82 0 : double left_sum = sum - buckets_[b];
83 0 : double right_sum = sum;
84 0 : double pos = (threshold - left_sum) / (right_sum - left_sum);
85 0 : double r = left_point + (right_point - left_point) * pos;
86 0 : if (r < min_) r = min_;
87 0 : if (r > max_) r = max_;
88 0 : return r;
89 : }
90 : }
91 0 : return max_;
92 : }
93 :
94 0 : double Histogram::Average() const {
95 0 : if (num_ == 0.0) return 0;
96 0 : return sum_ / num_;
97 : }
98 :
99 0 : double Histogram::StandardDeviation() const {
100 0 : if (num_ == 0.0) return 0;
101 0 : double variance = (sum_squares_ * num_ - sum_ * sum_) / (num_ * num_);
102 0 : return sqrt(variance);
103 : }
104 :
105 0 : std::string Histogram::ToString() const {
106 : std::string r;
107 : char buf[200];
108 : snprintf(buf, sizeof(buf),
109 : "Count: %.0f Average: %.4f StdDev: %.2f\n",
110 0 : num_, Average(), StandardDeviation());
111 0 : r.append(buf);
112 : snprintf(buf, sizeof(buf),
113 : "Min: %.4f Median: %.4f Max: %.4f\n",
114 0 : (num_ == 0.0 ? 0.0 : min_), Median(), max_);
115 0 : r.append(buf);
116 0 : r.append("------------------------------------------------------\n");
117 0 : const double mult = 100.0 / num_;
118 0 : double sum = 0;
119 0 : for (int b = 0; b < kNumBuckets; b++) {
120 0 : if (buckets_[b] <= 0.0) continue;
121 0 : sum += buckets_[b];
122 : snprintf(buf, sizeof(buf),
123 : "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ",
124 0 : ((b == 0) ? 0.0 : kBucketLimit[b-1]), // left
125 0 : kBucketLimit[b], // right
126 : buckets_[b], // count
127 : mult * buckets_[b], // percentage
128 0 : mult * sum); // cumulative percentage
129 0 : r.append(buf);
130 :
131 : // Add hash marks based on percentage; 20 marks for 100%.
132 0 : int marks = static_cast<int>(20*(buckets_[b] / num_) + 0.5);
133 0 : r.append(marks, '#');
134 0 : r.push_back('\n');
135 : }
136 0 : return r;
137 : }
138 :
139 : } // namespace leveldb
|
