2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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.
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.
32 #include "base/intmath.hh"
33 #include "mem/ruby/common/Histogram.hh"
37 Histogram::Histogram(int binsize
, int bins
)
44 Histogram::~Histogram()
49 Histogram::clear(int binsize
, int bins
)
56 Histogram::clear(int bins
)
61 m_data
.resize(m_bins
);
62 for (int i
= 0; i
< m_bins
; i
++) {
69 m_sumSquaredSamples
= 0;
74 Histogram::add(int64 value
)
77 m_max
= max(m_max
, value
);
80 m_sumSamples
+= value
;
81 m_sumSquaredSamples
+= (value
*value
);
84 if (m_binsize
== -1) {
85 // This is a log base 2 histogram
89 index
= floorLog2(value
) + 1;
90 if (index
>= m_data
.size()) {
91 index
= m_data
.size() - 1;
95 // This is a linear histogram
96 while (m_max
>= (m_bins
* m_binsize
)) {
97 for (int i
= 0; i
< m_bins
/2; i
++) {
98 m_data
[i
] = m_data
[i
*2] + m_data
[i
*2 + 1];
100 for (int i
= m_bins
/2; i
< m_bins
; i
++) {
105 index
= value
/m_binsize
;
109 m_largest_bin
= max(m_largest_bin
, index
);
113 Histogram::add(const Histogram
& hist
)
115 assert(hist
.getBins() == m_bins
);
116 assert(hist
.getBinSize() == -1); // assume log histogram
117 assert(m_binsize
== -1);
119 for (int j
= 0; j
< hist
.getData(0); j
++) {
123 for (int i
= 1; i
< m_bins
; i
++) {
124 for (int j
= 0; j
< hist
.getData(i
); j
++) {
125 add(1<<(i
-1)); // account for the + 1 index
130 // Computation of standard deviation of samples a1, a2, ... aN
131 // variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
132 // std deviation equals square root of variance
134 Histogram::getStandardDeviation() const
140 (double)(m_sumSquaredSamples
- m_sumSamples
* m_sumSamples
/ m_count
)
142 return sqrt(variance
);
146 Histogram::print(ostream
& out
) const
148 printWithMultiplier(out
, 1.0);
152 Histogram::printPercent(ostream
& out
) const
155 printWithMultiplier(out
, 0.0);
157 printWithMultiplier(out
, 100.0 / double(m_count
));
162 Histogram::printWithMultiplier(ostream
& out
, double multiplier
) const
164 if (m_binsize
== -1) {
165 out
<< "[binsize: log2 ";
167 out
<< "[binsize: " << m_binsize
<< " ";
169 out
<< "max: " << m_max
<< " ";
170 out
<< "count: " << m_count
<< " ";
171 // out << "total: " << m_sumSamples << " ";
173 out
<< "average: NaN |";
174 out
<< "standard deviation: NaN |";
176 out
<< "average: " << setw(5) << ((double) m_sumSamples
)/m_count
178 out
<< "standard deviation: " << getStandardDeviation() << " |";
180 for (int i
= 0; i
< m_bins
&& i
<= m_largest_bin
; i
++) {
181 if (multiplier
== 1.0) {
182 out
<< " " << m_data
[i
];
184 out
<< " " << double(m_data
[i
]) * multiplier
;
191 node_less_then_eq(const Histogram
* n1
, const Histogram
* n2
)
193 return (n1
->size() > n2
->size());