be/src/util/hdr-histogram.cc

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.

#include "util/hdr-histogram.h"

#include <algorithm>
#include <cmath>
#include <limits>
#include <gutil/strings/substitute.h>
#include <gutil/atomicops.h>

#include "common/status.h"
#include "util/bit-util.h"

#include "common/names.h"

using base::subtle::Atomic64;
using base::subtle::NoBarrier_AtomicIncrement;
using base::subtle::NoBarrier_Store;
using base::subtle::NoBarrier_Load;
using base::subtle::NoBarrier_CompareAndSwap;

using namespace impala;

HdrHistogram::HdrHistogram(uint64_t highest_trackable_value, int num_significant_digits)
  : highest_trackable_value_(highest_trackable_value),
    num_significant_digits_(num_significant_digits),
    counts_array_length_(0),
    bucket_count_(0),
    sub_bucket_count_(0),
    sub_bucket_half_count_magnitude_(0),
    sub_bucket_half_count_(0),
    sub_bucket_mask_(0),
    total_count_(0),
    total_sum_(0),
    min_value_(std::numeric_limits<Atomic64>::max()),
    max_value_(0),
    counts_(0) {
  Init();
}

HdrHistogram::HdrHistogram(const HdrHistogram& other)
  : highest_trackable_value_(other.highest_trackable_value_),
    num_significant_digits_(other.num_significant_digits_),
    counts_array_length_(0),
    bucket_count_(0),
    sub_bucket_count_(0),
    sub_bucket_half_count_magnitude_(0),
    sub_bucket_half_count_(0),
    sub_bucket_mask_(0),
    total_count_(0),
    total_sum_(0),
    min_value_(std::numeric_limits<Atomic64>::max()),
    max_value_(0),
    counts_(0) {
  Init();

  // Not a consistent snapshot but we try to roughly keep it close.
  // Copy the min first.
  NoBarrier_Store(&total_sum_, NoBarrier_Load(&other.total_sum_));
  NoBarrier_Store(&min_value_, NoBarrier_Load(&other.min_value_));
  uint64_t total_copied_count = 0;
  // Copy the counts in order of ascending magnitude.
  for (int i = 0; i < counts_array_length_; i++) {
    uint64_t count = NoBarrier_Load(&other.counts_[i]);
    NoBarrier_Store(&counts_[i], count);
    total_copied_count += count;
  }
  // Copy the max observed value last.
  NoBarrier_Store(&max_value_, NoBarrier_Load(&other.max_value_));
  // We must ensure the total is consistent with the copied counts.
  NoBarrier_Store(&total_count_, total_copied_count);
}

bool HdrHistogram::IsValidHighestTrackableValue(uint64_t highest_trackable_value) {
  return highest_trackable_value >= kMinHighestTrackableValue;
}

bool HdrHistogram::IsValidNumSignificantDigits(int num_significant_digits) {
  return num_significant_digits >= kMinValidNumSignificantDigits &&
         num_significant_digits <= kMaxValidNumSignificantDigits;
}

void HdrHistogram::Init() {
  // Verify parameter validity
  CHECK(IsValidHighestTrackableValue(highest_trackable_value_)) <<
      Substitute("highest_trackable_value must be >= $0", kMinHighestTrackableValue);
  CHECK(IsValidNumSignificantDigits(num_significant_digits_)) <<
      Substitute("num_significant_digits must be between $0 and $1",
          kMinValidNumSignificantDigits, kMaxValidNumSignificantDigits);

  uint32_t largest_value_with_single_unit_resolution =
      2 * static_cast<uint32_t>(pow(10.f, num_significant_digits_));

  // We need to maintain power-of-two sub_bucket_count_ (for clean direct
  // indexing) that is large enough to provide unit resolution to at least
  // largest_value_with_single_unit_resolution. So figure out
  // largest_value_with_single_unit_resolution's nearest power-of-two
  // (rounded up), and use that:

  // The sub-buckets take care of the precision.
  // Each sub-bucket is sized to have enough bits for the requested
  // 10^precision accuracy.
  int sub_bucket_count_magnitude =
      BitUtil::Log2Ceiling(largest_value_with_single_unit_resolution);
  sub_bucket_half_count_magnitude_ =
      (sub_bucket_count_magnitude >= 1) ? sub_bucket_count_magnitude - 1 : 0;

  // sub_bucket_count_ is approx. 10^num_sig_digits (as a power of 2)
  sub_bucket_count_ = pow(2.f, sub_bucket_half_count_magnitude_ + 1);
  sub_bucket_mask_ = sub_bucket_count_ - 1;
  sub_bucket_half_count_ = sub_bucket_count_ / 2;

  // The buckets take care of the magnitude.
  // Determine exponent range needed to support the trackable value with no
  // overflow:
  uint64_t trackable_value = sub_bucket_count_ - 1;
  int buckets_needed = 1;
  while (trackable_value < highest_trackable_value_) {
    trackable_value <<= 1;
    buckets_needed++;
  }
  bucket_count_ = buckets_needed;

  counts_array_length_ = (bucket_count_ + 1) * sub_bucket_half_count_;
  counts_.reset(new Atomic64[counts_array_length_]());  // value-initialized
}

void HdrHistogram::Increment(int64_t value) {
  IncrementBy(value, 1);
}

void HdrHistogram::IncrementBy(int64_t value, int64_t count) {
  DCHECK_GE(value, 0);
  DCHECK_GE(count, 0);

  // Dissect the value into bucket and sub-bucket parts, and derive index into
  // counts array:
  int bucket_index = BucketIndex(value);
  int sub_bucket_index = SubBucketIndex(value, bucket_index);
  int counts_index = CountsArrayIndex(bucket_index, sub_bucket_index);

  // Increment bucket & total.
  NoBarrier_AtomicIncrement(&counts_[counts_index], count);
  NoBarrier_AtomicIncrement(&total_count_, count);
  NoBarrier_AtomicIncrement(&total_sum_, value * count);

  // Update min, if needed.
  {
    Atomic64 min_val;
    while (PREDICT_FALSE(value < (min_val = MinValue()))) {
      Atomic64 old_val = NoBarrier_CompareAndSwap(&min_value_, min_val, value);
      if (PREDICT_TRUE(old_val == min_val)) break; // CAS success.
    }
  }

  // Update max, if needed.
  {
    Atomic64 max_val;
    while (PREDICT_FALSE(value > (max_val = MaxValue()))) {
      Atomic64 old_val = NoBarrier_CompareAndSwap(&max_value_, max_val, value);
      if (PREDICT_TRUE(old_val == max_val)) break; // CAS success.
    }
  }
}

void HdrHistogram::IncrementWithExpectedInterval(int64_t value,
                                                 int64_t expected_interval_between_samples) {
  Increment(value);
  if (expected_interval_between_samples <= 0) {
    return;
  }
  for (int64_t missing_value = value - expected_interval_between_samples;
      missing_value >= expected_interval_between_samples;
      missing_value -= expected_interval_between_samples) {
    Increment(missing_value);
  }
}

////////////////////////////////////

int HdrHistogram::BucketIndex(uint64_t value) const {
  if (PREDICT_FALSE(value > highest_trackable_value_)) {
    value = highest_trackable_value_;
  }
  // Here we are calculating the power-of-2 magnitude of the value with a
  // correction for precision in the first bucket.
  // Smallest power of 2 containing value.
  int pow2ceiling = BitUtil::Log2Ceiling64(value | sub_bucket_mask_);
  return pow2ceiling - (sub_bucket_half_count_magnitude_ + 1);
}

int HdrHistogram::SubBucketIndex(uint64_t value, int bucket_index) const {
  if (PREDICT_FALSE(value > highest_trackable_value_)) {
    value = highest_trackable_value_;
  }
  // We hack off the magnitude and are left with only the relevant precision
  // portion, which gives us a direct index into the sub-bucket. TODO: Right??
  return static_cast<int>(value >> bucket_index);
}

int HdrHistogram::CountsArrayIndex(int bucket_index, int sub_bucket_index) const {
  DCHECK(sub_bucket_index < sub_bucket_count_);
  DCHECK(bucket_index < bucket_count_);
  DCHECK(bucket_index == 0 || (sub_bucket_index >= sub_bucket_half_count_));
  // Calculate the index for the first entry in the bucket:
  // (The following is the equivalent of ((bucket_index + 1) * sub_bucket_half_count_) ):
  int bucket_base_index = (bucket_index + 1) << sub_bucket_half_count_magnitude_;
  // Calculate the offset in the bucket:
  int offset_in_bucket = sub_bucket_index - sub_bucket_half_count_;
  return bucket_base_index + offset_in_bucket;
}

uint64_t HdrHistogram::CountAt(int bucket_index, int sub_bucket_index) const {
  return counts_[CountsArrayIndex(bucket_index, sub_bucket_index)];
}

uint64_t HdrHistogram::CountInBucketForValue(uint64_t value) const {
  int bucket_index = BucketIndex(value);
  int sub_bucket_index = SubBucketIndex(value, bucket_index);
  return CountAt(bucket_index, sub_bucket_index);
}

uint64_t HdrHistogram::ValueFromIndex(int bucket_index, int sub_bucket_index) {
  return static_cast<uint64_t>(sub_bucket_index) << bucket_index;
}

////////////////////////////////////

uint64_t HdrHistogram::SizeOfEquivalentValueRange(uint64_t value) const {
  int bucket_index = BucketIndex(value);
  int sub_bucket_index = SubBucketIndex(value, bucket_index);
  uint64_t distance_to_next_value =
    (1 << ((sub_bucket_index >= sub_bucket_count_) ? (bucket_index + 1) : bucket_index));
  return distance_to_next_value;
}

uint64_t HdrHistogram::LowestEquivalentValue(uint64_t value) const {
  int bucket_index = BucketIndex(value);
  int sub_bucket_index = SubBucketIndex(value, bucket_index);
  uint64_t this_value_base_level = ValueFromIndex(bucket_index, sub_bucket_index);
  return this_value_base_level;
}

uint64_t HdrHistogram::HighestEquivalentValue(uint64_t value) const {
  return NextNonEquivalentValue(value) - 1;
}

uint64_t HdrHistogram::MedianEquivalentValue(uint64_t value) const {
  return (LowestEquivalentValue(value) + (SizeOfEquivalentValueRange(value) >> 1));
}

uint64_t HdrHistogram::NextNonEquivalentValue(uint64_t value) const {
  return LowestEquivalentValue(value) + SizeOfEquivalentValueRange(value);
}

bool HdrHistogram::ValuesAreEquivalent(uint64_t value1, uint64_t value2) const {
  return (LowestEquivalentValue(value1) == LowestEquivalentValue(value2));
}

uint64_t HdrHistogram::MinValue() const {
  if (PREDICT_FALSE(TotalCount() == 0)) return 0;
  return NoBarrier_Load(&min_value_);
}

uint64_t HdrHistogram::MaxValue() const {
  if (PREDICT_FALSE(TotalCount() == 0)) return 0;
  return NoBarrier_Load(&max_value_);
}

double HdrHistogram::MeanValue() const {
  uint64_t count = TotalCount();
  if (PREDICT_FALSE(count == 0)) return 0.0;

  RecordedValuesIterator iter(this);
  uint64_t total_value = 0;
  HistogramIterationValue val;
  while (iter.HasNext()) {
    Status s = iter.Next(&val);
    if (!s.ok()) {
      LOG(DFATAL) << "Error while iterating over histogram: " << s.GetDetail();
      return 0.0;
    }
    total_value = val.total_value_to_this_value;
  }
  return static_cast<double>(total_value) / static_cast<double>(count);
}

uint64_t HdrHistogram::ValueAtPercentile(double percentile) const {
  uint64_t count = TotalCount();
  if (PREDICT_FALSE(count == 0)) return 0;

  double requested_percentile = std::min(percentile, 100.0); // Truncate down to 100%
  uint64_t count_at_percentile =
    static_cast<uint64_t>(((requested_percentile / 100.0) * count) + 0.5); // Round
  // Make sure we at least reach the first recorded entry
  count_at_percentile = std::max<int64_t>(count_at_percentile, 1);

  uint64_t total_to_current_iJ = 0;
  for (int i = 0; i < bucket_count_; i++) {
    int j = (i == 0) ? 0 : (sub_bucket_count_ / 2);
    for (; j < sub_bucket_count_; j++) {
      total_to_current_iJ += CountAt(i, j);
      if (total_to_current_iJ >= count_at_percentile) {
        uint64_t valueAtIndex = ValueFromIndex(i, j);
        return valueAtIndex;
      }
    }
  }

  LOG(DFATAL) << "Fell through while iterating, likely concurrent modification of histogram";
  return 0;
}

///////////////////////////////////////////////////////////////////////
// AbstractHistogramIterator
///////////////////////////////////////////////////////////////////////

AbstractHistogramIterator::AbstractHistogramIterator(const HdrHistogram* histogram)
  : histogram_(CHECK_NOTNULL(histogram)),
    cur_iter_val_(),
    histogram_total_count_(histogram_->TotalCount()),
    current_bucket_index_(0),
    current_sub_bucket_index_(0),
    current_value_at_index_(0),
    next_bucket_index_(0),
    next_sub_bucket_index_(1),
    next_value_at_index_(1),
    prev_value_iterated_to_(0),
    total_count_to_prev_index_(0),
    total_count_to_current_index_(0),
    total_value_to_current_index_(0),
    count_at_this_value_(0),
    fresh_sub_bucket_(true) {
}

bool AbstractHistogramIterator::HasNext() const {
  return total_count_to_current_index_ < histogram_total_count_;
}

Status AbstractHistogramIterator::Next(HistogramIterationValue* value) {
  if (histogram_->TotalCount() != histogram_total_count_) {
    return Status("Concurrently modified histogram while traversing it");
  }

  // Move through the sub buckets and buckets until we hit the next reporting level:
  while (!ExhaustedSubBuckets()) {
    count_at_this_value_ =
        histogram_->CountAt(current_bucket_index_, current_sub_bucket_index_);
    if (fresh_sub_bucket_) { // Don't add unless we've incremented since last bucket...
      total_count_to_current_index_ += count_at_this_value_;
      total_value_to_current_index_ +=
        count_at_this_value_ * histogram_->MedianEquivalentValue(current_value_at_index_);
      fresh_sub_bucket_ = false;
    }
    if (ReachedIterationLevel()) {
      uint64_t value_iterated_to = ValueIteratedTo();

      // Update iterator value.
      cur_iter_val_.value_iterated_to = value_iterated_to;
      cur_iter_val_.value_iterated_from = prev_value_iterated_to_;
      cur_iter_val_.count_at_value_iterated_to = count_at_this_value_;
      cur_iter_val_.count_added_in_this_iteration_step =
          (total_count_to_current_index_ - total_count_to_prev_index_);
      cur_iter_val_.total_count_to_this_value = total_count_to_current_index_;
      cur_iter_val_.total_value_to_this_value = total_value_to_current_index_;
      cur_iter_val_.percentile =
          ((100.0 * total_count_to_current_index_) / histogram_total_count_);
      cur_iter_val_.percentile_level_iterated_to = PercentileIteratedTo();

      prev_value_iterated_to_ = value_iterated_to;
      total_count_to_prev_index_ = total_count_to_current_index_;
      // Move the next percentile reporting level forward.
      IncrementIterationLevel();

      *value = cur_iter_val_;
      return Status::OK();
    }
    IncrementSubBucket();
  }
  return Status("Histogram array index out of bounds while traversing");
}

double AbstractHistogramIterator::PercentileIteratedTo() const {
  return (100.0 * static_cast<double>(total_count_to_current_index_)) / histogram_total_count_;
}

double AbstractHistogramIterator::PercentileIteratedFrom() const {
  return (100.0 * static_cast<double>(total_count_to_prev_index_)) / histogram_total_count_;
}

uint64_t AbstractHistogramIterator::ValueIteratedTo() const {
  return histogram_->HighestEquivalentValue(current_value_at_index_);
}

bool AbstractHistogramIterator::ExhaustedSubBuckets() const {
  return (current_bucket_index_ >= histogram_->bucket_count_);
}

void AbstractHistogramIterator::IncrementSubBucket() {
  fresh_sub_bucket_ = true;
  // Take on the next index:
  current_bucket_index_ = next_bucket_index_;
  current_sub_bucket_index_ = next_sub_bucket_index_;
  current_value_at_index_ = next_value_at_index_;
  // Figure out the next next index:
  next_sub_bucket_index_++;
  if (next_sub_bucket_index_ >= histogram_->sub_bucket_count_) {
    next_sub_bucket_index_ = histogram_->sub_bucket_half_count_;
    next_bucket_index_++;
  }
  next_value_at_index_ = HdrHistogram::ValueFromIndex(next_bucket_index_, next_sub_bucket_index_);
}

///////////////////////////////////////////////////////////////////////
// RecordedValuesIterator
///////////////////////////////////////////////////////////////////////

RecordedValuesIterator::RecordedValuesIterator(const HdrHistogram* histogram)
  : AbstractHistogramIterator(histogram),
    visited_sub_bucket_index_(-1),
    visited_bucket_index_(-1) {
}

void RecordedValuesIterator::IncrementIterationLevel() {
  visited_sub_bucket_index_ = current_sub_bucket_index_;
  visited_bucket_index_ = current_bucket_index_;
}

bool RecordedValuesIterator::ReachedIterationLevel() const {
  uint64_t current_ij_count =
      histogram_->CountAt(current_bucket_index_, current_sub_bucket_index_);
  return current_ij_count != 0 &&
      ((visited_sub_bucket_index_ != current_sub_bucket_index_) ||
       (visited_bucket_index_ != current_bucket_index_));
}

///////////////////////////////////////////////////////////////////////
// PercentileIterator
///////////////////////////////////////////////////////////////////////

PercentileIterator::PercentileIterator(const HdrHistogram* histogram,
                                       int percentile_ticks_per_half_distance)
  : AbstractHistogramIterator(histogram),
    percentile_ticks_per_half_distance_(percentile_ticks_per_half_distance),
    percentile_level_to_iterate_to_(0.0),
    percentile_level_to_iterate_from_(0.0),
    reached_last_recorded_value_(false) {
}

bool PercentileIterator::HasNext() const {
  if (AbstractHistogramIterator::HasNext()) {
    return true;
  }
  // We want one additional last step to 100%
  if (!reached_last_recorded_value_ && (histogram_total_count_ > 0)) {
    const_cast<PercentileIterator*>(this)->percentile_level_to_iterate_to_ = 100.0;
    const_cast<PercentileIterator*>(this)->reached_last_recorded_value_ = true;
    return true;
  }
  return false;
}

double PercentileIterator::PercentileIteratedTo() const {
  return percentile_level_to_iterate_to_;
}


double PercentileIterator::PercentileIteratedFrom() const {
  return percentile_level_to_iterate_from_;
}

void PercentileIterator::IncrementIterationLevel() {
  percentile_level_to_iterate_from_ = percentile_level_to_iterate_to_;
  // TODO: Can this expression be simplified?
  uint64_t percentile_reporting_ticks = percentile_ticks_per_half_distance_ *
    static_cast<uint64_t>(pow(2.0,
            (log(100.0 / (100.0 - (percentile_level_to_iterate_to_))) / log(2)) + 1));
  percentile_level_to_iterate_to_ += 100.0 / percentile_reporting_ticks;
}

bool PercentileIterator::ReachedIterationLevel() const {
  if (count_at_this_value_ == 0) return false;
  double current_percentile =
      (100.0 * static_cast<double>(total_count_to_current_index_)) / histogram_total_count_;
  return (current_percentile >= percentile_level_to_iterate_to_);
}