← Back to branch summary

~ubuntu-branches/ubuntu/raring/ceph/raring

« back to all changes in this revision

Viewing changes to src/leveldb/util/histogram.cc

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-06-08 15:54:37 UTC
  • mfrom: (1.1.8) (0.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120608155437-gy3j9k6wzv7w4gn9
Tags: 0.44.1-1ubuntu1
* Merge from Debian unstable.  Remaining changes:
  - d/control: Switch from libcryptopp to libnss as libcryptopp
    is not seeded.
  - d/control,d/rules: Move from python-support to dh_python2.
  - d/patches/manpage_updates*.patch: cherry picked upstream manpage
    updates warning about lack of encryption, per MIR review.
  - d/rules,d/control: Drop radosgw since libfcgi is not in main and
    the code may not be suitable for LTS.
  - d/rules,d/control: Drop tcmalloc since google perftools is not
    in main yet.
  - d/rules,d/control: Drop ceph-fuse entirely per MIR review
    recommendation.
* d/patches/fix-radosgw-tests.patch: Cherry picked patch from upstream
  VCS to fixup tests to conditionally use radosgw if enabled.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/leveldb/util/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 <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