Histogram.cc revision 9773 
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
29#include <cmath>
30#include <iomanip>
31
32#include "base/intmath.hh"
33#include "mem/ruby/common/Histogram.hh"
34
35using namespace std;
36
37Histogram::Histogram(int binsize, uint32_t bins)
38{
39    m_binsize = binsize;
40    clear(bins);
41}
42
43Histogram::~Histogram()
44{
45}
46
47void
48Histogram::clear(int binsize, uint32_t bins)
49{
50    m_binsize = binsize;
51    clear(bins);
52}
53
54void
55Histogram::clear(uint32_t bins)
56{
57    m_largest_bin = 0;
58    m_max = 0;
59    m_data.resize(bins);
60    for (uint32_t i = 0; i < bins; i++) {
61        m_data[i] = 0;
62    }
63
64    m_count = 0;
65    m_max = 0;
66    m_sumSamples = 0;
67    m_sumSquaredSamples = 0;
68}
69
70void
71Histogram::doubleBinSize()
72{
73    assert(m_binsize != -1);
74    uint32_t t_bins = m_data.size();
75
76    for (uint32_t i = 0; i < t_bins/2; i++) {
77        m_data[i] = m_data[i*2] + m_data[i*2 + 1];
78    }
79    for (uint32_t i = t_bins/2; i < t_bins; i++) {
80        m_data[i] = 0;
81    }
82
83    m_binsize *= 2;
84}
85
86void
87Histogram::add(int64 value)
88{
89    assert(value >= 0);
90    m_max = max(m_max, value);
91    m_count++;
92
93    m_sumSamples += value;
94    m_sumSquaredSamples += (value*value);
95
96    uint32_t index;
97
98    if (m_binsize == -1) {
99        // This is a log base 2 histogram
100        if (value == 0) {
101            index = 0;
102        } else {
103            index = floorLog2(value) + 1;
104            if (index >= m_data.size()) {
105                index = m_data.size() - 1;
106            }
107        }
108    } else {
109        // This is a linear histogram
110        uint32_t t_bins = m_data.size();
111
112        while (m_max >= (t_bins * m_binsize)) doubleBinSize();
113        index = value/m_binsize;
114    }
115
116    assert(index < m_data.size());
117    m_data[index]++;
118    m_largest_bin = max(m_largest_bin, index);
119}
120
121void
122Histogram::add(Histogram& hist)
123{
124    uint32_t t_bins = m_data.size();
125
126    if (hist.getBins() != t_bins) {
127        if (m_count == 0) {
128            m_data.resize(hist.getBins());
129        } else {
130            fatal("Histograms with different number of bins "
131                  "cannot be combined!");
132        }
133    }
134
135    m_max = max(m_max, hist.getMax());
136    m_count += hist.size();
137    m_sumSamples += hist.getTotal();
138    m_sumSquaredSamples += hist.getSquaredTotal();
139
140    // Both histograms are log base 2.
141    if (hist.getBinSize() == -1 && m_binsize == -1) {
142        for (int j = 0; j < hist.getData(0); j++) {
143            add(0);
144        }
145
146        for (uint32_t i = 1; i < t_bins; i++) {
147            for (int j = 0; j < hist.getData(i); j++) {
148                add(1<<(i-1));  // account for the + 1 index
149            }
150        }
151    } else if (hist.getBinSize() >= 1 && m_binsize >= 1) {
152        // Both the histogram are linear.
153        // We are assuming that the two histograms have the same
154        // minimum value that they can store.
155
156        while (m_binsize > hist.getBinSize()) hist.doubleBinSize();
157        while (hist.getBinSize() > m_binsize) doubleBinSize();
158
159        assert(m_binsize == hist.getBinSize());
160
161        for (uint32_t i = 0; i < t_bins; i++) {
162            m_data[i] += hist.getData(i);
163
164            if (m_data[i] > 0) m_largest_bin = i;
165        }
166    } else {
167        fatal("Don't know how to combine log and linear histograms!");
168    }
169}
170
171// Computation of standard deviation of samples a1, a2, ... aN
172// variance = [SUM {ai^2} - (SUM {ai})^2/N]/(N-1)
173// std deviation equals square root of variance
174double
175Histogram::getStandardDeviation() const
176{
177    if (m_count <= 1)
178        return 0.0;
179
180    double variance =
181        (double)(m_sumSquaredSamples - m_sumSamples * m_sumSamples / m_count)
182        / (m_count - 1);
183    return sqrt(variance);
184}
185
186void
187Histogram::print(ostream& out) const
188{
189    printWithMultiplier(out, 1.0);
190}
191
192void
193Histogram::printPercent(ostream& out) const
194{
195    if (m_count == 0) {
196        printWithMultiplier(out, 0.0);
197    } else {
198        printWithMultiplier(out, 100.0 / double(m_count));
199    }
200}
201
202void
203Histogram::printWithMultiplier(ostream& out, double multiplier) const
204{
205    if (m_binsize == -1) {
206        out << "[binsize: log2 ";
207    } else {
208        out << "[binsize: " << m_binsize << " ";
209    }
210    out << "max: " << m_max << " ";
211    out << "count: " << m_count << " ";
212    //  out << "total: " <<  m_sumSamples << " ";
213    if (m_count == 0) {
214        out << "average: NaN |";
215        out << "standard deviation: NaN |";
216    } else {
217        out << "average: " << setw(5) << ((double) m_sumSamples)/m_count
218            << " | ";
219        out << "standard deviation: " << getStandardDeviation() << " |";
220    }
221
222    for (uint32_t i = 0; i <= m_largest_bin; i++) {
223        if (multiplier == 1.0) {
224            out << " " << m_data[i];
225        } else {
226            out << " " << double(m_data[i]) * multiplier;
227        }
228    }
229    out << " ]";
230}
231
232bool
233node_less_then_eq(const Histogram* n1, const Histogram* n2)
234{
235    return (n1->size() > n2->size());
236}
237