1/*
2 * Copyright (c) 2002, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25#ifndef SHARE_VM_GC_SHARED_GCUTIL_HPP
26#define SHARE_VM_GC_SHARED_GCUTIL_HPP
27
28#include "memory/allocation.hpp"
29#include "runtime/timer.hpp"
30#include "utilities/debug.hpp"
31#include "utilities/globalDefinitions.hpp"
32#include "utilities/ostream.hpp"
33
34// Catch-all file for utility classes
35
36// A weighted average maintains a running, weighted average
37// of some float value (templates would be handy here if we
38// need different types).
39//
40// The average is adaptive in that we smooth it for the
41// initial samples; we don't use the weight until we have
42// enough samples for it to be meaningful.
43//
44// This serves as our best estimate of a future unknown.
45//
46class AdaptiveWeightedAverage : public CHeapObj<mtGC> {
47 private:
48  float            _average;        // The last computed average
49  unsigned         _sample_count;   // How often we've sampled this average
50  unsigned         _weight;         // The weight used to smooth the averages
51                                    //   A higher weight favors the most
52                                    //   recent data.
53  bool             _is_old;         // Has enough historical data
54
55  const static unsigned OLD_THRESHOLD = 100;
56
57 protected:
58  float            _last_sample;    // The last value sampled.
59
60  void  increment_count() {
61    _sample_count++;
62    if (!_is_old && _sample_count > OLD_THRESHOLD) {
63      _is_old = true;
64    }
65  }
66
67  void  set_average(float avg)  { _average = avg;        }
68
69  // Helper function, computes an adaptive weighted average
70  // given a sample and the last average
71  float compute_adaptive_average(float new_sample, float average);
72
73 public:
74  // Input weight must be between 0 and 100
75  AdaptiveWeightedAverage(unsigned weight, float avg = 0.0) :
76    _average(avg), _sample_count(0), _weight(weight), _last_sample(0.0),
77    _is_old(false) {
78  }
79
80  void clear() {
81    _average = 0;
82    _sample_count = 0;
83    _last_sample = 0;
84    _is_old = false;
85  }
86
87  // Useful for modifying static structures after startup.
88  void  modify(size_t avg, unsigned wt, bool force = false)  {
89    assert(force, "Are you sure you want to call this?");
90    _average = (float)avg;
91    _weight  = wt;
92  }
93
94  // Accessors
95  float    average() const       { return _average;       }
96  unsigned weight()  const       { return _weight;        }
97  unsigned count()   const       { return _sample_count;  }
98  float    last_sample() const   { return _last_sample;   }
99  bool     is_old()  const       { return _is_old;        }
100
101  // Update data with a new sample.
102  void sample(float new_sample);
103
104  static inline float exp_avg(float avg, float sample,
105                               unsigned int weight) {
106    assert(weight <= 100, "weight must be a percent");
107    return (100.0F - weight) * avg / 100.0F + weight * sample / 100.0F;
108  }
109  static inline size_t exp_avg(size_t avg, size_t sample,
110                               unsigned int weight) {
111    // Convert to float and back to avoid integer overflow.
112    return (size_t)exp_avg((float)avg, (float)sample, weight);
113  }
114
115  // Printing
116  void print_on(outputStream* st) const;
117  void print() const;
118};
119
120
121// A weighted average that includes a deviation from the average,
122// some multiple of which is added to the average.
123//
124// This serves as our best estimate of an upper bound on a future
125// unknown.
126class AdaptivePaddedAverage : public AdaptiveWeightedAverage {
127 private:
128  float          _padded_avg;     // The last computed padded average
129  float          _deviation;      // Running deviation from the average
130  unsigned       _padding;        // A multiple which, added to the average,
131                                  // gives us an upper bound guess.
132
133 protected:
134  void set_padded_average(float avg)  { _padded_avg = avg;  }
135  void set_deviation(float dev)       { _deviation  = dev;  }
136
137 public:
138  AdaptivePaddedAverage() :
139    AdaptiveWeightedAverage(0),
140    _padded_avg(0.0), _deviation(0.0), _padding(0) {}
141
142  AdaptivePaddedAverage(unsigned weight, unsigned padding) :
143    AdaptiveWeightedAverage(weight),
144    _padded_avg(0.0), _deviation(0.0), _padding(padding) {}
145
146  // Placement support
147  void* operator new(size_t ignored, void* p) throw() { return p; }
148  // Allocator
149  void* operator new(size_t size) throw() { return CHeapObj<mtGC>::operator new(size); }
150
151  // Accessor
152  float padded_average() const         { return _padded_avg; }
153  float deviation()      const         { return _deviation;  }
154  unsigned padding()     const         { return _padding;    }
155
156  void clear() {
157    AdaptiveWeightedAverage::clear();
158    _padded_avg = 0;
159    _deviation = 0;
160  }
161
162  // Override
163  void  sample(float new_sample);
164
165  // Printing
166  void print_on(outputStream* st) const;
167  void print() const;
168};
169
170// A weighted average that includes a deviation from the average,
171// some multiple of which is added to the average.
172//
173// This serves as our best estimate of an upper bound on a future
174// unknown.
175// A special sort of padded average:  it doesn't update deviations
176// if the sample is zero. The average is allowed to change. We're
177// preventing the zero samples from drastically changing our padded
178// average.
179class AdaptivePaddedNoZeroDevAverage : public AdaptivePaddedAverage {
180public:
181  AdaptivePaddedNoZeroDevAverage(unsigned weight, unsigned padding) :
182    AdaptivePaddedAverage(weight, padding)  {}
183  // Override
184  void  sample(float new_sample);
185
186  // Printing
187  void print_on(outputStream* st) const;
188  void print() const;
189};
190
191// Use a least squares fit to a set of data to generate a linear
192// equation.
193//              y = intercept + slope * x
194
195class LinearLeastSquareFit : public CHeapObj<mtGC> {
196  double _sum_x;        // sum of all independent data points x
197  double _sum_x_squared; // sum of all independent data points x**2
198  double _sum_y;        // sum of all dependent data points y
199  double _sum_xy;       // sum of all x * y.
200  double _intercept;     // constant term
201  double _slope;        // slope
202  // The weighted averages are not currently used but perhaps should
203  // be used to get decaying averages.
204  AdaptiveWeightedAverage _mean_x; // weighted mean of independent variable
205  AdaptiveWeightedAverage _mean_y; // weighted mean of dependent variable
206
207 public:
208  LinearLeastSquareFit(unsigned weight);
209  void update(double x, double y);
210  double y(double x);
211  double slope() { return _slope; }
212  // Methods to decide if a change in the dependent variable will
213  // achieve a desired goal.  Note that these methods are not
214  // complementary and both are needed.
215  bool decrement_will_decrease();
216  bool increment_will_decrease();
217};
218
219#endif // SHARE_VM_GC_SHARED_GCUTIL_HPP
220