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 "mem/ruby/common/Histogram.hh"
30
31#include <cmath>
32#include <iomanip>
33
34#include "base/intmath.hh"
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}
238