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 void Histogram::Clear() { 34 min_ = kBucketLimit[kNumBuckets-1]; 35 max_ = 0; 36 num_ = 0; 37 sum_ = 0; 38 sum_squares_ = 0; 39 for (int i = 0; i < kNumBuckets; i++) { 40 buckets_[i] = 0; 41 } 42 } 43 44 void Histogram::Add(double value) { 45 // Linear search is fast enough for our usage in db_bench 46 int b = 0; 47 while (b < kNumBuckets - 1 && kBucketLimit[b] <= value) { 48 b++; 49 } 50 buckets_[b] += 1.0; 51 if (min_ > value) min_ = value; 52 if (max_ < value) max_ = value; 53 num_++; 54 sum_ += value; 55 sum_squares_ += (value * value); 56 } 57 58 void Histogram::Merge(const Histogram& other) { 59 if (other.min_ < min_) min_ = other.min_; 60 if (other.max_ > max_) max_ = other.max_; 61 num_ += other.num_; 62 sum_ += other.sum_; 63 sum_squares_ += other.sum_squares_; 64 for (int b = 0; b < kNumBuckets; b++) { 65 buckets_[b] += other.buckets_[b]; 66 } 67 } 68 69 double Histogram::Median() const { 70 return Percentile(50.0); 71 } 72 73 double Histogram::Percentile(double p) const { 74 double threshold = num_ * (p / 100.0); 75 double sum = 0; 76 for (int b = 0; b < kNumBuckets; b++) { 77 sum += buckets_[b]; 78 if (sum >= threshold) { 79 // Scale linearly within this bucket 80 double left_point = (b == 0) ? 0 : kBucketLimit[b-1]; 81 double right_point = kBucketLimit[b]; 82 double left_sum = sum - buckets_[b]; 83 double right_sum = sum; 84 double pos = (threshold - left_sum) / (right_sum - left_sum); 85 double r = left_point + (right_point - left_point) * pos; 86 if (r < min_) r = min_; 87 if (r > max_) r = max_; 88 return r; 89 } 90 } 91 return max_; 92 } 93 94 double Histogram::Average() const { 95 if (num_ == 0.0) return 0; 96 return sum_ / num_; 97 } 98 99 double Histogram::StandardDeviation() const { 100 if (num_ == 0.0) return 0; 101 double variance = (sum_squares_ * num_ - sum_ * sum_) / (num_ * num_); 102 return sqrt(variance); 103 } 104 105 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 num_, Average(), StandardDeviation()); 111 r.append(buf); 112 snprintf(buf, sizeof(buf), 113 "Min: %.4f Median: %.4f Max: %.4f\n", 114 (num_ == 0.0 ? 0.0 : min_), Median(), max_); 115 r.append(buf); 116 r.append("------------------------------------------------------\n"); 117 const double mult = 100.0 / num_; 118 double sum = 0; 119 for (int b = 0; b < kNumBuckets; b++) { 120 if (buckets_[b] <= 0.0) continue; 121 sum += buckets_[b]; 122 snprintf(buf, sizeof(buf), 123 "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ", 124 ((b == 0) ? 0.0 : kBucketLimit[b-1]), // left 125 kBucketLimit[b], // right 126 buckets_[b], // count 127 mult * buckets_[b], // percentage 128 mult * sum); // cumulative percentage 129 r.append(buf); 130 131 // Add hash marks based on percentage; 20 marks for 100%. 132 int marks = static_cast<int>(20*(buckets_[b] / num_) + 0.5); 133 r.append(marks, '#'); 134 r.push_back('\n'); 135 } 136 return r; 137 } 138 139 } // namespace leveldb 140
