leveldb::Histogram Class Reference

#include <histogram.h>

Public Member Functions
	Histogram ()
	~Histogram ()
void	Clear ()
void	Add (double value)
void	Merge (const Histogram &other)
std::string	ToString () const

Private Types
enum	{ kNumBuckets = 154 }

Private Member Functions
double	Median () const
double	Percentile (double p) const
double	Average () const
double	StandardDeviation () const

Private Attributes
double	min_
double	max_
double	num_
double	sum_
double	sum_squares_
double	buckets_ [kNumBuckets]

Static Private Attributes
static const double	kBucketLimit [kNumBuckets]

Detailed Description

Definition at line 12 of file histogram.h.

Member Enumeration Documentation

anonymous enum

anonymous enum

private

Enumerator
kNumBuckets

Definition at line 30 of file histogram.h.

{ kNumBuckets = 154 };

Constructor & Destructor Documentation

Histogram()

leveldb::Histogram::Histogram ( )

inline

Definition at line 14 of file histogram.h.

{ }

~Histogram()

leveldb::Histogram::~Histogram ( )

inline

Definition at line 15 of file histogram.h.

{ }

Here is the call graph for this function:

Member Function Documentation

Add()

void leveldb::Histogram::Add

(

double

value

)

Definition at line 44 of file histogram.cc.

                                {
  // Linear search is fast enough for our usage in db_bench
  int b = 0;
  while (b < kNumBuckets - 1 && kBucketLimit[b] <= value) {
    b++;
  }
  buckets_[b] += 1.0;
  if (min_ > value) min_ = value;
  if (max_ < value) max_ = value;
  num_++;
  sum_ += value;
  sum_squares_ += (value * value);
}

Here is the caller graph for this function:

Average()

double leveldb::Histogram::Average ( ) const

private

Definition at line 94 of file histogram.cc.

                                {
  if (num_ == 0.0) return 0;
  return sum_ / num_;
}

Here is the caller graph for this function:

Clear()

void leveldb::Histogram::Clear

(

)

Definition at line 33 of file histogram.cc.

                      {
  min_ = kBucketLimit[kNumBuckets-1];
  max_ = 0;
  num_ = 0;
  sum_ = 0;
  sum_squares_ = 0;
  for (int i = 0; i < kNumBuckets; i++) {
    buckets_[i] = 0;
  }
}

Here is the caller graph for this function:

Median()

double leveldb::Histogram::Median ( ) const

private

Definition at line 69 of file histogram.cc.

                               {
  return Percentile(50.0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Merge()

void leveldb::Histogram::Merge

(

const Histogram &

other

)

Definition at line 58 of file histogram.cc.

                                            {
  if (other.min_ < min_) min_ = other.min_;
  if (other.max_ > max_) max_ = other.max_;
  num_ += other.num_;
  sum_ += other.sum_;
  sum_squares_ += other.sum_squares_;
  for (int b = 0; b < kNumBuckets; b++) {
    buckets_[b] += other.buckets_[b];
  }
}

Here is the caller graph for this function:

Percentile()

double leveldb::Histogram::Percentile ( double  p ) const

private

Definition at line 73 of file histogram.cc.

                                           {
  double threshold = num_ * (p / 100.0);
  double sum = 0;
  for (int b = 0; b < kNumBuckets; b++) {
    sum += buckets_[b];
    if (sum >= threshold) {
      // Scale linearly within this bucket
      double left_point = (b == 0) ? 0 : kBucketLimit[b-1];
      double right_point = kBucketLimit[b];
      double left_sum = sum - buckets_[b];
      double right_sum = sum;
      double pos = (threshold - left_sum) / (right_sum - left_sum);
      double r = left_point + (right_point - left_point) * pos;
      if (r < min_) r = min_;
      if (r > max_) r = max_;
      return r;
    }
  }
  return max_;
}

Here is the caller graph for this function:

StandardDeviation()

double leveldb::Histogram::StandardDeviation ( ) const

private

Definition at line 99 of file histogram.cc.

                                          {
  if (num_ == 0.0) return 0;
  double variance = (sum_squares_ * num_ - sum_ * sum_) / (num_ * num_);
  return sqrt(variance);
}

Here is the caller graph for this function:

ToString()

std::string leveldb::Histogram::ToString

(

)

const

Definition at line 105 of file histogram.cc.

                                    {
  std::string r;
  char buf[200];
  snprintf(buf, sizeof(buf),
           "Count: %.0f  Average: %.4f  StdDev: %.2f\n",
           num_, Average(), StandardDeviation());
  r.append(buf);
  snprintf(buf, sizeof(buf),
           "Min: %.4f  Median: %.4f  Max: %.4f\n",
           (num_ == 0.0 ? 0.0 : min_), Median(), max_);
  r.append(buf);
  r.append("------------------------------------------------------\n");
  const double mult = 100.0 / num_;
  double sum = 0;
  for (int b = 0; b < kNumBuckets; b++) {
    if (buckets_[b] <= 0.0) continue;
    sum += buckets_[b];
    snprintf(buf, sizeof(buf),
             "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ",
             ((b == 0) ? 0.0 : kBucketLimit[b-1]),      // left
             kBucketLimit[b],                           // right
             buckets_[b],                               // count
             mult * buckets_[b],                        // percentage
             mult * sum);                               // cumulative percentage
    r.append(buf);

    // Add hash marks based on percentage; 20 marks for 100%.
    int marks = static_cast<int>(20*(buckets_[b] / num_) + 0.5);
    r.append(marks, '#');
    r.push_back('\n');
  }
  return r;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

buckets_

double leveldb::Histogram::buckets_[kNumBuckets]

private

Definition at line 32 of file histogram.h.

kBucketLimit

const double leveldb::Histogram::kBucketLimit

staticprivate

Initial value:

= {
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 25, 30, 35, 40, 45,
  50, 60, 70, 80, 90, 100, 120, 140, 160, 180, 200, 250, 300, 350, 400, 450,
  500, 600, 700, 800, 900, 1000, 1200, 1400, 1600, 1800, 2000, 2500, 3000,
  3500, 4000, 4500, 5000, 6000, 7000, 8000, 9000, 10000, 12000, 14000,
  16000, 18000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 60000,
  70000, 80000, 90000, 100000, 120000, 140000, 160000, 180000, 200000,
  250000, 300000, 350000, 400000, 450000, 500000, 600000, 700000, 800000,
  900000, 1000000, 1200000, 1400000, 1600000, 1800000, 2000000, 2500000,
  3000000, 3500000, 4000000, 4500000, 5000000, 6000000, 7000000, 8000000,
  9000000, 10000000, 12000000, 14000000, 16000000, 18000000, 20000000,
  25000000, 30000000, 35000000, 40000000, 45000000, 50000000, 60000000,
  70000000, 80000000, 90000000, 100000000, 120000000, 140000000, 160000000,
  180000000, 200000000, 250000000, 300000000, 350000000, 400000000,
  450000000, 500000000, 600000000, 700000000, 800000000, 900000000,
  1000000000, 1200000000, 1400000000, 1600000000, 1800000000, 2000000000,
  2500000000.0, 3000000000.0, 3500000000.0, 4000000000.0, 4500000000.0,
  5000000000.0, 6000000000.0, 7000000000.0, 8000000000.0, 9000000000.0,
  1e200,
}

Definition at line 31 of file histogram.h.

max_

double leveldb::Histogram::max_

private

Definition at line 25 of file histogram.h.

min_

double leveldb::Histogram::min_

private

Definition at line 24 of file histogram.h.

num_

double leveldb::Histogram::num_

private

Definition at line 26 of file histogram.h.

sum_

double leveldb::Histogram::sum_

private

Definition at line 27 of file histogram.h.

sum_squares_

double leveldb::Histogram::sum_squares_

private

Definition at line 28 of file histogram.h.

---

The documentation for this class was generated from the following files:

• util/histogram.h
• util/histogram.cc