1 /*
2 * Copyright (c) 2018, Red Hat, Inc. All rights reserved.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 *
22 */
23
24 #include "precompiled.hpp"
25
26 #include "gc/shenandoah/shenandoahNumberSeq.hpp"
27 #include "runtime/atomic.hpp"
28
HdrSeq()29 HdrSeq::HdrSeq() {
30 _hdr = NEW_C_HEAP_ARRAY(int*, MagBuckets, mtInternal);
31 for (int c = 0; c < MagBuckets; c++) {
32 _hdr[c] = NULL;
33 }
34 }
35
~HdrSeq()36 HdrSeq::~HdrSeq() {
37 for (int c = 0; c < MagBuckets; c++) {
38 int* sub = _hdr[c];
39 if (sub != NULL) {
40 FREE_C_HEAP_ARRAY(int, sub);
41 }
42 }
43 FREE_C_HEAP_ARRAY(int*, _hdr);
44 }
45
add(double val)46 void HdrSeq::add(double val) {
47 if (val < 0) {
48 assert (false, "value (%8.2f) is not negative", val);
49 val = 0;
50 }
51
52 NumberSeq::add(val);
53
54 double v = val;
55 int mag;
56 if (v > 0) {
57 mag = 0;
58 while (v > 1) {
59 mag++;
60 v /= 10;
61 }
62 while (v < 0.1) {
63 mag--;
64 v *= 10;
65 }
66 } else {
67 mag = MagMinimum;
68 }
69
70 int bucket = -MagMinimum + mag;
71 int sub_bucket = (int) (v * ValBuckets);
72
73 // Defensively saturate for product bits:
74 if (bucket < 0) {
75 assert (false, "bucket index (%d) underflow for value (%8.2f)", bucket, val);
76 bucket = 0;
77 }
78
79 if (bucket >= MagBuckets) {
80 assert (false, "bucket index (%d) overflow for value (%8.2f)", bucket, val);
81 bucket = MagBuckets - 1;
82 }
83
84 if (sub_bucket < 0) {
85 assert (false, "sub-bucket index (%d) underflow for value (%8.2f)", sub_bucket, val);
86 sub_bucket = 0;
87 }
88
89 if (sub_bucket >= ValBuckets) {
90 assert (false, "sub-bucket index (%d) overflow for value (%8.2f)", sub_bucket, val);
91 sub_bucket = ValBuckets - 1;
92 }
93
94 int* b = _hdr[bucket];
95 if (b == NULL) {
96 b = NEW_C_HEAP_ARRAY(int, ValBuckets, mtInternal);
97 for (int c = 0; c < ValBuckets; c++) {
98 b[c] = 0;
99 }
100 _hdr[bucket] = b;
101 }
102 b[sub_bucket]++;
103 }
104
percentile(double level) const105 double HdrSeq::percentile(double level) const {
106 // target should be non-zero to find the first sample
107 int target = MAX2(1, (int) (level * num() / 100));
108 int cnt = 0;
109 for (int mag = 0; mag < MagBuckets; mag++) {
110 if (_hdr[mag] != NULL) {
111 for (int val = 0; val < ValBuckets; val++) {
112 cnt += _hdr[mag][val];
113 if (cnt >= target) {
114 return pow(10.0, MagMinimum + mag) * val / ValBuckets;
115 }
116 }
117 }
118 }
119 return maximum();
120 }
121
BinaryMagnitudeSeq()122 BinaryMagnitudeSeq::BinaryMagnitudeSeq() {
123 _mags = NEW_C_HEAP_ARRAY(size_t, BitsPerSize_t, mtInternal);
124 clear();
125 }
126
~BinaryMagnitudeSeq()127 BinaryMagnitudeSeq::~BinaryMagnitudeSeq() {
128 FREE_C_HEAP_ARRAY(size_t, _mags);
129 }
130
clear()131 void BinaryMagnitudeSeq::clear() {
132 for (int c = 0; c < BitsPerSize_t; c++) {
133 _mags[c] = 0;
134 }
135 _sum = 0;
136 }
137
add(size_t val)138 void BinaryMagnitudeSeq::add(size_t val) {
139 Atomic::add(val, &_sum);
140
141 int mag = log2_intptr(val) + 1;
142
143 // Defensively saturate for product bits:
144 if (mag < 0) {
145 assert (false, "bucket index (%d) underflow for value (" SIZE_FORMAT ")", mag, val);
146 mag = 0;
147 }
148
149 if (mag >= BitsPerSize_t) {
150 assert (false, "bucket index (%d) overflow for value (" SIZE_FORMAT ")", mag, val);
151 mag = BitsPerSize_t - 1;
152 }
153
154 Atomic::add((size_t)1, &_mags[mag]);
155 }
156
level(int level) const157 size_t BinaryMagnitudeSeq::level(int level) const {
158 if (0 <= level && level < BitsPerSize_t) {
159 return _mags[level];
160 } else {
161 return 0;
162 }
163 }
164
num() const165 size_t BinaryMagnitudeSeq::num() const {
166 size_t r = 0;
167 for (int c = 0; c < BitsPerSize_t; c++) {
168 r += _mags[c];
169 }
170 return r;
171 }
172
sum() const173 size_t BinaryMagnitudeSeq::sum() const {
174 return _sum;
175 }
176
min_level() const177 int BinaryMagnitudeSeq::min_level() const {
178 for (int c = 0; c < BitsPerSize_t; c++) {
179 if (_mags[c] != 0) {
180 return c;
181 }
182 }
183 return BitsPerSize_t - 1;
184 }
185
max_level() const186 int BinaryMagnitudeSeq::max_level() const {
187 for (int c = BitsPerSize_t - 1; c > 0; c--) {
188 if (_mags[c] != 0) {
189 return c;
190 }
191 }
192 return 0;
193 }
194