1 /* 2 * Copyright (c) 2001, 2010, 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 #include "precompiled.hpp" 26 #include "memory/allocation.inline.hpp" 27 #include "utilities/debug.hpp" 28 #include "utilities/globalDefinitions.hpp" 29 #include "utilities/numberSeq.hpp" 30 31 AbsSeq::AbsSeq(double alpha) : 32 _num(0), _sum(0.0), _sum_of_squares(0.0), 33 _davg(0.0), _dvariance(0.0), _alpha(alpha) { 34 } 35 36 void AbsSeq::add(double val) { 37 if (_num == 0) { 38 // if the sequence is empty, the davg is the same as the value 39 _davg = val; 40 // and the variance is 0 41 _dvariance = 0.0; 42 } else { 43 // otherwise, calculate both 44 _davg = (1.0 - _alpha) * val + _alpha * _davg; 45 double diff = val - _davg; 46 _dvariance = (1.0 - _alpha) * diff * diff + _alpha * _dvariance; 47 } 48 } 49 50 double AbsSeq::avg() const { 51 if (_num == 0) 52 return 0.0; 53 else 54 return _sum / total(); 55 } 56 57 double AbsSeq::variance() const { 58 if (_num <= 1) 59 return 0.0; 60 61 double x_bar = avg(); 62 double result = _sum_of_squares / total() - x_bar * x_bar; 63 if (result < 0.0) { 64 // due to loss-of-precision errors, the variance might be negative 65 // by a small bit 66 67 // guarantee(-0.1 < result && result < 0.0, 68 // "if variance is negative, it should be very small"); 69 result = 0.0; 70 } 71 return result; 72 } 73 74 double AbsSeq::sd() const { 75 double var = variance(); 76 guarantee( var >= 0.0, "variance should not be negative" ); 77 return sqrt(var); 78 } 79 80 double AbsSeq::davg() const { 81 return _davg; 82 } 83 84 double AbsSeq::dvariance() const { 85 if (_num <= 1) 86 return 0.0; 87 88 double result = _dvariance; 89 if (result < 0.0) { 90 // due to loss-of-precision errors, the variance might be negative 91 // by a small bit 92 93 guarantee(-0.1 < result && result < 0.0, 94 "if variance is negative, it should be very small"); 95 result = 0.0; 96 } 97 return result; 98 } 99 100 double AbsSeq::dsd() const { 101 double var = dvariance(); 102 guarantee( var >= 0.0, "variance should not be negative" ); 103 return sqrt(var); 104 } 105 106 NumberSeq::NumberSeq(double alpha) : 107 AbsSeq(alpha), _maximum(0.0), _last(0.0) { 108 } 109 110 bool NumberSeq::check_nums(NumberSeq *total, int n, NumberSeq **parts) { 111 for (int i = 0; i < n; ++i) { 112 if (parts[i] != NULL && total->num() != parts[i]->num()) 113 return false; 114 } 115 return true; 116 } 117 118 NumberSeq::NumberSeq(NumberSeq *total, int n, NumberSeq **parts) { 119 guarantee(check_nums(total, n, parts), "all seq lengths should match"); 120 double sum = total->sum(); 121 for (int i = 0; i < n; ++i) { 122 if (parts[i] != NULL) 123 sum -= parts[i]->sum(); 124 } 125 126 _num = total->num(); 127 _sum = sum; 128 129 // we do not calculate these... 130 _sum_of_squares = -1.0; 131 _maximum = -1.0; 132 _davg = -1.0; 133 _dvariance = -1.0; 134 } 135 136 void NumberSeq::add(double val) { 137 AbsSeq::add(val); 138 139 _last = val; 140 if (_num == 0) { 141 _maximum = val; 142 } else { 143 if (val > _maximum) 144 _maximum = val; 145 } 146 _sum += val; 147 _sum_of_squares += val * val; 148 ++_num; 149 } 150 151 152 TruncatedSeq::TruncatedSeq(int length, double alpha): 153 AbsSeq(alpha), _length(length), _next(0) { 154 _sequence = NEW_C_HEAP_ARRAY(double, _length); 155 for (int i = 0; i < _length; ++i) 156 _sequence[i] = 0.0; 157 } 158 159 void TruncatedSeq::add(double val) { 160 AbsSeq::add(val); 161 162 // get the oldest value in the sequence... 163 double old_val = _sequence[_next]; 164 // ...remove it from the sum and sum of squares 165 _sum -= old_val; 166 _sum_of_squares -= old_val * old_val; 167 168 // ...and update them with the new value 169 _sum += val; 170 _sum_of_squares += val * val; 171 172 // now replace the old value with the new one 173 _sequence[_next] = val; 174 _next = (_next + 1) % _length; 175 176 // only increase it if the buffer is not full 177 if (_num < _length) 178 ++_num; 179 180 guarantee( variance() > -1.0, "variance should be >= 0" ); 181 } 182 183 // can't easily keep track of this incrementally... 184 double TruncatedSeq::maximum() const { 185 if (_num == 0) 186 return 0.0; 187 double ret = _sequence[0]; 188 for (int i = 1; i < _num; ++i) { 189 double val = _sequence[i]; 190 if (val > ret) 191 ret = val; 192 } 193 return ret; 194 } 195 196 double TruncatedSeq::last() const { 197 if (_num == 0) 198 return 0.0; 199 unsigned last_index = (_next + _length - 1) % _length; 200 return _sequence[last_index]; 201 } 202 203 double TruncatedSeq::oldest() const { 204 if (_num == 0) 205 return 0.0; 206 else if (_num < _length) 207 // index 0 always oldest value until the array is full 208 return _sequence[0]; 209 else { 210 // since the array is full, _next is over the oldest value 211 return _sequence[_next]; 212 } 213 } 214 215 double TruncatedSeq::predict_next() const { 216 if (_num == 0) 217 return 0.0; 218 219 double num = (double) _num; 220 double x_squared_sum = 0.0; 221 double x_sum = 0.0; 222 double y_sum = 0.0; 223 double xy_sum = 0.0; 224 double x_avg = 0.0; 225 double y_avg = 0.0; 226 227 int first = (_next + _length - _num) % _length; 228 for (int i = 0; i < _num; ++i) { 229 double x = (double) i; 230 double y = _sequence[(first + i) % _length]; 231 232 x_squared_sum += x * x; 233 x_sum += x; 234 y_sum += y; 235 xy_sum += x * y; 236 } 237 x_avg = x_sum / num; 238 y_avg = y_sum / num; 239 240 double Sxx = x_squared_sum - x_sum * x_sum / num; 241 double Sxy = xy_sum - x_sum * y_sum / num; 242 double b1 = Sxy / Sxx; 243 double b0 = y_avg - b1 * x_avg; 244 245 return b0 + b1 * num; 246 } 247 248 249 // Printing/Debugging Support 250 251 void AbsSeq::dump() { dump_on(gclog_or_tty); } 252 253 void AbsSeq::dump_on(outputStream* s) { 254 s->print_cr("\t _num = %d, _sum = %7.3f, _sum_of_squares = %7.3f", 255 _num, _sum, _sum_of_squares); 256 s->print_cr("\t _davg = %7.3f, _dvariance = %7.3f, _alpha = %7.3f", 257 _davg, _dvariance, _alpha); 258 } 259 260 void NumberSeq::dump_on(outputStream* s) { 261 AbsSeq::dump_on(s); 262 s->print_cr("\t\t _last = %7.3f, _maximum = %7.3f"); 263 } 264 265 void TruncatedSeq::dump_on(outputStream* s) { 266 AbsSeq::dump_on(s); 267 s->print_cr("\t\t _length = %d, _next = %d", _length, _next); 268 for (int i = 0; i < _length; i++) { 269 if (i%5 == 0) { 270 s->cr(); 271 s->print("\t"); 272 } 273 s->print("\t[%d]=%7.3f", i, _sequence[i]); 274 } 275 s->print_cr(""); 276 }