1/*
2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
|
35
36using namespace std;
37
38Histogram::Histogram(int binsize, uint32_t bins)
39{
40 m_binsize = binsize;
41 clear(bins);
42}
43
44Histogram::~Histogram()
45{
46}
47
48void
49Histogram::clear(int binsize, uint32_t bins)
50{
51 m_binsize = binsize;
52 clear(bins);
53}
54
55void
56Histogram::clear(uint32_t bins)
57{
58 m_largest_bin = 0;
59 m_max = 0;
60 m_data.resize(bins);
61 for (uint32_t i = 0; i < bins; i++) {
62 m_data[i] = 0;
63 }
64
65 m_count = 0;
66 m_max = 0;
67 m_sumSamples = 0;
68 m_sumSquaredSamples = 0;
69}
70
71void
72Histogram::doubleBinSize()
73{
74 assert(m_binsize != -1);
75 uint32_t t_bins = m_data.size();
76
77 for (uint32_t i = 0; i < t_bins/2; i++) {
78 m_data[i] = m_data[i*2] + m_data[i*2 + 1];
79 }
80 for (uint32_t i = t_bins/2; i < t_bins; i++) {
81 m_data[i] = 0;
82 }
83
84 m_binsize *= 2;
85}
86
87void
88Histogram::add(int64_t value)
89{
90 assert(value >= 0);
91 m_max = max(m_max, value);
92 m_count++;
93
94 m_sumSamples += value;
95 m_sumSquaredSamples += (value*value);
96
97 uint32_t index;
98
99 if (m_binsize == -1) {
100 // This is a log base 2 histogram
101 if (value == 0) {
102 index = 0;
103 } else {
104 index = floorLog2(value) + 1;
105 if (index >= m_data.size()) {
106 index = m_data.size() - 1;
107 }
108 }
109 } else {
110 // This is a linear histogram
111 uint32_t t_bins = m_data.size();
112
113 while (m_max >= (t_bins * m_binsize)) doubleBinSize();
114 index = value/m_binsize;
115 }
116
117 assert(index < m_data.size());
118 m_data[index]++;
119 m_largest_bin = max(m_largest_bin, index);
120}
121
122void
123Histogram::add(Histogram& hist)
124{
125 uint32_t t_bins = m_data.size();
126
127 if (hist.getBins() != t_bins) {
128 if (m_count == 0) {
129 m_data.resize(hist.getBins());
130 } else {
131 fatal("Histograms with different number of bins "
132 "cannot be combined!");
133 }
134 }
135
136 m_max = max(m_max, hist.getMax());
137 m_count += hist.size();
138 m_sumSamples += hist.getTotal();
139 m_sumSquaredSamples += hist.getSquaredTotal();
140
141 // Both histograms are log base 2.
142 if (hist.getBinSize() == -1 && m_binsize == -1) {
143 for (int j = 0; j < hist.getData(0); j++) {
144 add(0);
145 }
146
147 for (uint32_t i = 1; i < t_bins; i++) {
148 for (int j = 0; j < hist.getData(i); j++) {
149 add(1<<(i-1)); // account for the + 1 index
150 }
151 }
152 } else if (hist.getBinSize() >= 1 && m_binsize >= 1) {
153 // Both the histogram are linear.
154 // We are assuming that the two histograms have the same
155 // minimum value that they can store.
156
157 while (m_binsize > hist.getBinSize()) hist.doubleBinSize();
158 while (hist.getBinSize() > m_binsize) doubleBinSize();
159
160 assert(m_binsize == hist.getBinSize());
161
162 for (uint32_t i = 0; i < t_bins; i++) {
163 m_data[i] += hist.getData(i);
164
165 if (m_data[i] > 0) m_largest_bin = i;
166 }
167 } else {
168 fatal("Don't know how to combine log and linear histograms!");
169 }
170}
171
172// Computation of standard deviation of samples a1, a2, ... aN
173// variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
174// std deviation equals square root of variance
175double
176Histogram::getStandardDeviation() const
177{
178 if (m_count <= 1)
179 return 0.0;
180
181 double variance =
182 (double)(m_sumSquaredSamples - m_sumSamples * m_sumSamples / m_count)
183 / (m_count - 1);
184 return sqrt(variance);
185}
186
187void
188Histogram::print(ostream& out) const
189{
190 printWithMultiplier(out, 1.0);
191}
192
193void
194Histogram::printPercent(ostream& out) const
195{
196 if (m_count == 0) {
197 printWithMultiplier(out, 0.0);
198 } else {
199 printWithMultiplier(out, 100.0 / double(m_count));
200 }
201}
202
203void
204Histogram::printWithMultiplier(ostream& out, double multiplier) const
205{
206 if (m_binsize == -1) {
207 out << "[binsize: log2 ";
208 } else {
209 out << "[binsize: " << m_binsize << " ";
210 }
211 out << "max: " << m_max << " ";
212 out << "count: " << m_count << " ";
213 // out << "total: " << m_sumSamples << " ";
214 if (m_count == 0) {
215 out << "average: NaN |";
216 out << "standard deviation: NaN |";
217 } else {
218 out << "average: " << setw(5) << ((double) m_sumSamples)/m_count
219 << " | ";
220 out << "standard deviation: " << getStandardDeviation() << " |";
221 }
222
223 for (uint32_t i = 0; i <= m_largest_bin; i++) {
224 if (multiplier == 1.0) {
225 out << " " << m_data[i];
226 } else {
227 out << " " << double(m_data[i]) * multiplier;
228 }
229 }
230 out << " ]";
231}
232
233bool
234node_less_then_eq(const Histogram* n1, const Histogram* n2)
235{
236 return (n1->size() > n2->size());
237}
|