1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #ifndef ART_RUNTIME_BASE_HISTOGRAM_H_ 17 #define ART_RUNTIME_BASE_HISTOGRAM_H_ 18 19 #include <vector> 20 #include <string> 21 22 #include "base/logging.h" 23 #include "utils.h" 24 25 namespace art { 26 27 // Creates a data histogram for a better understanding of statistical data. 28 // Histogram analysis goes beyond simple mean and standard deviation to provide 29 // percentiles values, describing where the $% of the input data lies. 30 // Designed to be simple and used with timing logger in art. 31 32 template <class Value> class Histogram { 33 const double kAdjust; 34 const size_t kInitialBucketCount; 35 36 public: 37 class CumulativeData { 38 friend class Histogram<Value>; 39 std::vector<uint64_t> freq_; 40 std::vector<double> perc_; 41 }; 42 43 Histogram(const char* name, Value initial_bucket_width, size_t max_buckets = 100); 44 void AddValue(Value); 45 // Builds the cumulative distribution function from the frequency data. 46 // Accumulative summation of frequencies. 47 // cumulative_freq[i] = sum(frequency[j] : 0 < j < i ) 48 // Accumulative summation of percentiles; which is the frequency / SampleSize 49 // cumulative_perc[i] = sum(frequency[j] / SampleSize : 0 < j < i ) 50 void CreateHistogram(CumulativeData& data); 51 // Reset the cumulative values, next time CreateHistogram is called it will recreate the cache. 52 void Reset(); 53 double Mean() const; 54 double Variance() const; 55 double Percentile(double per, const CumulativeData& data) const; 56 void PrintConfidenceIntervals(std::ostream& os, double interval, 57 const CumulativeData& data) const; 58 void PrintBins(std::ostream& os, const CumulativeData& data) const; 59 Value GetRange(size_t bucket_idx) const; 60 size_t GetBucketCount() const; 61 SampleSize()62 uint64_t SampleSize() const { 63 return sample_size_; 64 } 65 Sum()66 Value Sum() const { 67 return sum_; 68 } 69 Min()70 Value Min() const { 71 return min_value_added_; 72 } 73 Max()74 Value Max() const { 75 return max_value_added_; 76 } 77 Name()78 const std::string& Name() const { 79 return name_; 80 } 81 82 private: 83 void Initialize(); 84 size_t FindBucket(Value val) const; 85 void BucketiseValue(Value val); 86 // Add more buckets to the histogram to fill in a new value that exceeded 87 // the max_read_value_. 88 void GrowBuckets(Value val); 89 std::string name_; 90 // Maximum number of buckets. 91 const size_t max_buckets_; 92 // Number of samples placed in histogram. 93 size_t sample_size_; 94 // Width of the bucket range. The lower the value is the more accurate 95 // histogram percentiles are. Grows adaptively when we hit max buckets. 96 Value bucket_width_; 97 // How many occurrences of values fall within a bucket at index i where i covers the range 98 // starting at min_ + i * bucket_width_ with size bucket_size_. 99 std::vector<uint32_t> frequency_; 100 // Summation of all the elements inputed by the user. 101 Value sum_; 102 // Minimum value that can fit in the histogram. Fixed to zero for now. 103 Value min_; 104 // Maximum value that can fit in the histogram, grows adaptively. 105 Value max_; 106 // Summation of the values entered. Used to calculate variance. 107 Value sum_of_squares_; 108 // Maximum value entered in the histogram. 109 Value min_value_added_; 110 // Minimum value entered in the histogram. 111 Value max_value_added_; 112 113 DISALLOW_COPY_AND_ASSIGN(Histogram); 114 }; 115 } // namespace art 116 117 #endif // ART_RUNTIME_BASE_HISTOGRAM_H_ 118