histogram.cc
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 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 snprintf(buf, sizeof(buf), "Count: %.0f Average: %.4f StdDev: %.2f\n", num_, 245 Average(), StandardDeviation()); 246 r.append(buf); 247 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 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