1 /*
2 * Copyright (c) 2018, 2019, Red Hat, Inc. 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
27 #include "gc/shenandoah/shenandoahNumberSeq.hpp"
28 #include "runtime/atomic.hpp"
29
30 HdrSeq::HdrSeq() {
31 _hdr = NEW_C_HEAP_ARRAY(int*, MagBuckets, mtInternal);
32 for (int c = 0; c < MagBuckets; c++) {
33 _hdr[c] = nullptr;
34 }
35 }
36
37 HdrSeq::~HdrSeq() {
38 for (int c = 0; c < MagBuckets; c++) {
39 int* sub = _hdr[c];
40 if (sub != nullptr) {
41 FREE_C_HEAP_ARRAY(int, sub);
42 }
43 }
44 FREE_C_HEAP_ARRAY(int*, _hdr);
45 }
46
47 void HdrSeq::add(double val) {
48 if (val < 0) {
49 assert (false, "value (%8.2f) is not negative", val);
50 val = 0;
51 }
52
53 NumberSeq::add(val);
54
55 double v = val;
56 int mag;
57 if (v > 0) {
58 mag = 0;
59 while (v >= 1) {
60 mag++;
61 v /= 10;
62 }
63 while (v < 0.1) {
64 mag--;
65 v *= 10;
66 }
67 } else {
68 mag = MagMinimum;
69 }
70
71 int bucket = -MagMinimum + mag;
72 int sub_bucket = (int) (v * ValBuckets);
73
74 // Defensively saturate for product bits
75 if (bucket < 0) {
76 assert (false, "bucket index (%d) underflow for value (%8.2f)", bucket, val);
77 bucket = 0;
78 }
79
80 if (bucket >= MagBuckets) {
81 assert (false, "bucket index (%d) overflow for value (%8.2f)", bucket, val);
82 bucket = MagBuckets - 1;
83 }
84
85 if (sub_bucket < 0) {
86 assert (false, "sub-bucket index (%d) underflow for value (%8.2f)", sub_bucket, val);
87 sub_bucket = 0;
88 }
89
90 if (sub_bucket >= ValBuckets) {
91 assert (false, "sub-bucket index (%d) overflow for value (%8.2f)", sub_bucket, val);
92 sub_bucket = ValBuckets - 1;
93 }
94
95 int* b = _hdr[bucket];
96 if (b == nullptr) {
97 b = NEW_C_HEAP_ARRAY(int, ValBuckets, mtInternal);
98 for (int c = 0; c < ValBuckets; c++) {
99 b[c] = 0;
100 }
101 _hdr[bucket] = b;
102 }
103 b[sub_bucket]++;
104 }
105
106 double HdrSeq::percentile(double level) const {
107 // target should be non-zero to find the first sample
108 int target = MAX2(1, (int) (level * num() / 100));
109 int cnt = 0;
110 for (int mag = 0; mag < MagBuckets; mag++) {
111 if (_hdr[mag] != nullptr) {
112 for (int val = 0; val < ValBuckets; val++) {
113 cnt += _hdr[mag][val];
114 if (cnt >= target) {
115 return pow(10.0, MagMinimum + mag) * val / ValBuckets;
116 }
117 }
118 }
119 }
120 return maximum();
121 }
122
123 BinaryMagnitudeSeq::BinaryMagnitudeSeq() {
124 _mags = NEW_C_HEAP_ARRAY(size_t, BitsPerSize_t, mtInternal);
125 clear();
126 }
127
128 BinaryMagnitudeSeq::~BinaryMagnitudeSeq() {
129 FREE_C_HEAP_ARRAY(size_t, _mags);
130 }
131
132 void BinaryMagnitudeSeq::clear() {
133 for (int c = 0; c < BitsPerSize_t; c++) {
134 _mags[c] = 0;
135 }
136 _sum = 0;
137 }
138
139 void BinaryMagnitudeSeq::add(size_t val) {
140 Atomic::add(&_sum, val);
141
142 int mag = log2i_graceful(val) + 1;
143
144 // Defensively saturate for product bits:
145 if (mag < 0) {
146 assert (false, "bucket index (%d) underflow for value (" SIZE_FORMAT ")", mag, val);
147 mag = 0;
148 }
149
150 if (mag >= BitsPerSize_t) {
151 assert (false, "bucket index (%d) overflow for value (" SIZE_FORMAT ")", mag, val);
152 mag = BitsPerSize_t - 1;
153 }
154
155 Atomic::add(&_mags[mag], (size_t)1);
156 }
157
158 size_t BinaryMagnitudeSeq::level(int level) const {
159 if (0 <= level && level < BitsPerSize_t) {
160 return _mags[level];
161 } else {
162 return 0;
163 }
164 }
165
166 size_t BinaryMagnitudeSeq::num() const {
167 size_t r = 0;
168 for (int c = 0; c < BitsPerSize_t; c++) {
169 r += _mags[c];
170 }
171 return r;
172 }
173
174 size_t BinaryMagnitudeSeq::sum() const {
175 return _sum;
176 }
177
178 int BinaryMagnitudeSeq::min_level() const {
179 for (int c = 0; c < BitsPerSize_t; c++) {
180 if (_mags[c] != 0) {
181 return c;
182 }
183 }
184 return BitsPerSize_t - 1;
185 }
186
187 int BinaryMagnitudeSeq::max_level() const {
188 for (int c = BitsPerSize_t - 1; c > 0; c--) {
189 if (_mags[c] != 0) {
190 return c;
191 }
192 }
193 return 0;
194 }