1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
/*
* Copyright (C) 2013 The Android Open Source Project
*
* Licensed 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.
*/
#ifndef ART_RUNTIME_BASE_HISTOGRAM_H_
#define ART_RUNTIME_BASE_HISTOGRAM_H_
#include <vector>
#include <string>
#include "base/logging.h"
#include "utils.h"
namespace art {
// Creates a data histogram for a better understanding of statistical data.
// Histogram analysis goes beyond simple mean and standard deviation to provide
// percentiles values, describing where the $% of the input data lies.
// Designed to be simple and used with timing logger in art.
template <class Value> class Histogram {
const double kAdjust;
const Value kBucketWidth;
const size_t kInitialBucketCount;
public:
Histogram(std::string);
void AddValue(Value);
void CreateHistogram();
void Reset();
double Mean() const;
double Variance() const;
double Percentile(double) const;
void PrintConfidenceIntervals(std::ostream &, double) const;
void PrintBins(std::ostream &);
uint64_t SampleSize() const {
return sample_size_;
}
Value Sum() const {
return sum_;
}
Value Min() const {
return min_value_added_;
}
Value Max() const {
return max_value_added_;
}
const std::string &Name() const {
return name_;
}
private:
void BuildRanges();
void Initialize();
size_t FindBucket(Value);
void BucketiseValue(Value);
// Builds the cumulative distribution function from the frequency data.
// Must be called before using the percentile function.
void BuildCDF();
// Add more buckets to the histogram to fill in a new value that exceeded
// the max_read_value_.
void GrowBuckets(Value);
bool new_values_added_;
std::string name_;
// Number of samples placed in histogram.
uint64_t sample_size_;
// Width of the bucket range. The lower the value is the more accurate
// histogram percentiles are.
Value bucket_width_;
// Number of bucket to have in the histogram. this value will increase
// to accommodate for big values that don't fit in initial bucket ranges.
size_t bucket_count_;
// Represents the ranges of the histograms. Has SampleSize() + 1 elements
// e.g. 0,5,10,15 represents ranges 0-5, 5-10, 10-15
std::vector<Value> ranges_;
// How many occurrences of values fall within a corresponding range that is
// saved in the ranges_ vector.
std::vector<uint64_t> frequency_;
// Accumulative summation of frequencies.
// cumulative_freq_[i] = sum(cumulative_freq_[j] : 0 < j < i )
std::vector<uint64_t> cumulative_freq_;
// Accumulative summation of percentiles; which is the frequency / SampleSize
// cumulative_freq_[i] = sum(cumulative_freq_[j] : 0 < j < i )
std::vector<double> cumulative_perc_;
// Summation of all the elements inputed by the user.
Value sum_;
// Maximum value that can fit in the histogram, grows adaptively.
Value min_;
// Minimum value that can fit in the histogram. Fixed to zero for now.
Value max_;
// Summation of the values entered. Used to calculate variance.
Value sum_of_squares_;
// Maximum value entered in the histogram.
Value min_value_added_;
// Minimum value entered in the histogram.
Value max_value_added_;
DISALLOW_COPY_AND_ASSIGN(Histogram);
};
}
#endif // ART_RUNTIME_BASE_HISTOGRAM_H_
|
