GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/util/algorithm.cc
Date: 2024-04-21 02:33:16
Exec Total Coverage
Lines: 54 154 35.1%
Branches: 17 158 10.8%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 *
4 * Some common functions.
5 */
6
7 #ifndef __STDC_FORMAT_MACROS
8 // NOLINTNEXTLINE
9 #define __STDC_FORMAT_MACROS
10 #endif
11
12 #include <algorithm>
13 #include <cassert>
14 #include <cmath>
15 #include <cstdio>
16 #include <cstdlib>
17 #include <cstring>
18
19 #include "cvmfs_config.h"
20 #include "util/algorithm.h"
21 #include "util/string.h"
22
23
24 #ifdef CVMFS_NAMESPACE_GUARD
25 namespace CVMFS_NAMESPACE_GUARD {
26 #endif
27
28 bool HighPrecisionTimer::g_is_enabled = false;
29
30
31 7 double DiffTimeSeconds(struct timeval start, struct timeval end) {
32 // Time subtraction, from GCC documentation
33
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5 times.
 7 if (end.tv_usec < start.tv_usec) {
34 2 int64_t nsec = (end.tv_usec - start.tv_usec) / 1000000 + 1;
35 2 start.tv_usec -= 1000000 * nsec;
36 2 start.tv_sec += nsec;
37 }
38
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7 times.
 7 if (end.tv_usec - start.tv_usec > 1000000) {
39 ✗ int64_t nsec = (end.tv_usec - start.tv_usec) / 1000000;
40 ✗ start.tv_usec += 1000000 * nsec;
41 ✗ start.tv_sec -= nsec;
42 }
43
44 // Compute the time remaining to wait in microseconds.
45 // tv_usec is certainly positive.
46 7 uint64_t elapsed_usec = ((end.tv_sec - start.tv_sec)*1000000) +
47 7 (end.tv_usec - start.tv_usec);
48 7 return static_cast<double>(elapsed_usec)/1000000.0;
49 }
50
51
52
53 2 void StopWatch::Start() {
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 assert(!running_);
55
56 2 gettimeofday(&start_, NULL);
57 2 running_ = true;
58 2 }
59
60
61 2 void StopWatch::Stop() {
62
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 assert(running_);
63
64 2 gettimeofday(&end_, NULL);
65 2 running_ = false;
66 2 }
67
68
69 1 void StopWatch::Reset() {
70 1 start_ = timeval();
71 1 end_ = timeval();
72 1 running_ = false;
73 1 }
74
75
76 4 double StopWatch::GetTime() const {
77
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 assert(!running_);
78
79 4 return DiffTimeSeconds(start_, end_);
80 }
81
82 namespace {
83
84 ✗ static unsigned int CountDigits(uint64_t n) {
85 ✗ if (n == 0) {
86 ✗ return 1;
87 }
88 ✗ return static_cast<unsigned int>(floor(log10(static_cast<double>(n)))) + 1;
89 }
90
91 ✗ static std::string GenerateStars(unsigned int n) {
92 ✗ return std::string(n, '*');
93 }
94
95 } // anonymous namespace
96
97 851 Log2Histogram::Log2Histogram(unsigned int nbins) {
98
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 851 times.
 851 assert(nbins != 0);
99
1/2
✓ Branch 1 taken 851 times.
✗ Branch 2 not taken.
 851 this->bins_.assign(nbins + 1, 0); // +1 for overflow bin.
100
1/2
✓ Branch 1 taken 851 times.
✗ Branch 2 not taken.
 851 this->boundary_values_.assign(nbins + 1, 0); // +1 to avoid big if statement
101
102 unsigned int i;
103
2/2
✓ Branch 0 taken 25434 times.
✓ Branch 1 taken 851 times.
 26285 for (i = 1; i <= nbins; i++) {
104 25434 this->boundary_values_[i] = (1 << ((i - 1) + 1));
105 }
106 851 }
107
108 3 std::vector<atomic_int32> UTLog2Histogram::GetBins(const Log2Histogram &h) {
109 3 return h.bins_;
110 }
111
112 13 unsigned int Log2Histogram::GetQuantile(float n) {
113 13 uint64_t total = this->N();
114 // pivot is the index of the element corresponding to the requested quantile
115 13 uint64_t pivot = static_cast<uint64_t>(static_cast<float>(total) * n);
116 13 float normalized_pivot = 0.0;
117 // now we iterate through all the bins
118 // note that we _exclude_ the overflow bin
119 13 unsigned int i = 0;
120
2/2
✓ Branch 1 taken 188 times.
✓ Branch 2 taken 1 times.
 189 for (i = 1; i <= this->bins_.size() - 1; i++) {
121 unsigned int bin_value =
122 188 static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
123
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 176 times.
 188 if (pivot <= bin_value) {
124 12 normalized_pivot =
125 12 static_cast<float>(pivot) / static_cast<float>(bin_value);
126 12 break;
127 }
128 176 pivot -= bin_value;
129 }
130
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 12 times.
 13 if (i >= this->bins_.size()) {
131 1 return this->boundary_values_[this->bins_.size() - 1];
132 }
133 // now i stores the index of the bin corresponding to the requested quantile
134 // and normalized_pivot is the element we want inside the bin
135 12 unsigned int min_value = this->boundary_values_[i - 1];
136 12 unsigned int max_value = this->boundary_values_[i];
137 // and we return the linear interpolation
138 12 return min_value + static_cast<unsigned int>(
139 12 static_cast<float>(max_value - min_value) * normalized_pivot);
140 }
141
142 ✗ std::string Log2Histogram::ToString() {
143 ✗ unsigned int i = 0;
144
145 ✗ unsigned int max_left_boundary_count = 1;
146 ✗ unsigned int max_right_boundary_count = 1;
147 ✗ unsigned int max_value_count = 1;
148 ✗ unsigned int max_stars = 0;
149 ✗ unsigned int max_bins = 0;
150 ✗ unsigned int total_stars = 38;
151 ✗ uint64_t total_sum_of_bins = 0;
152
153 ✗ for (i = 1; i <= this->bins_.size() - 1; i++) {
154 ✗ max_left_boundary_count = std::max(max_left_boundary_count,
155 ✗ CountDigits(boundary_values_[i] / 2));
156 ✗ max_right_boundary_count = std::max(max_right_boundary_count,
157 ✗ CountDigits(boundary_values_[i] - 1));
158 ✗ max_value_count = std::max(max_value_count,
159 ✗ CountDigits(atomic_read32(&(this->bins_[i]))));
160 ✗ max_bins = std::max(max_bins, static_cast<unsigned int>(
161 ✗ atomic_read32(&(this->bins_[i]))));
162 ✗ total_sum_of_bins +=
163 ✗ static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
164 }
165
166 ✗ max_bins = std::max(max_bins, static_cast<unsigned int>(
167 ✗ atomic_read32(&(this->bins_[0]))));
168 ✗ total_sum_of_bins +=
169 ✗ static_cast<unsigned int>(atomic_read32(&(this->bins_[0])));
170
171 ✗ if (total_sum_of_bins != 0) {
172 ✗ max_stars = max_bins * total_stars / total_sum_of_bins;
173 }
174
175 ✗ std::string format = " %" + StringifyUint(max_left_boundary_count < 2 ?
176 ✗ 2 : max_left_boundary_count) +
177 ✗ "d -> %" + StringifyUint(max_right_boundary_count) +
178 ✗ "d : %" + StringifyUint(max_value_count) + "d | %" +
179 ✗ StringifyUint(max_stars < 12 ? 12 : max_stars) + "s |\n";
180
181 ✗ std::string title_format = " %" +
182 ✗ StringifyUint((max_left_boundary_count < 2 ?
183 ✗ 2 : max_left_boundary_count) +
184 ✗ max_right_boundary_count +
185 ✗ 4) +
186 ✗ "s | %" + StringifyUint(max_value_count + 4) +
187 ✗ "s | %" + StringifyUint(max_stars < 12 ? 12 : max_stars) +
188 ✗ "s |\n";
189
190 ✗ std::string overflow_format = "%" +
191 ✗ StringifyUint(max_left_boundary_count +
192 ✗ max_right_boundary_count +
193 ✗ 5) +
194 ✗ "s : %" + StringifyUint(max_value_count + 4) +
195 ✗ "d | %" + StringifyUint(max_stars < 12 ? 12 : max_stars) +
196 ✗ "s |\n";
197
198 ✗ std::string total_format = "%" +
199 ✗ StringifyUint(max_left_boundary_count +
200 ✗ max_right_boundary_count +
201 ✗ 5 < 8 ? 8 : max_left_boundary_count +
202 ✗ max_right_boundary_count + 5) +
203 ✗ "s : %" + StringifyUint(max_value_count + 4) + "lld\n";
204
205 ✗ std::string result_string = "";
206
207 ✗ const unsigned int kBufSize = 300;
208 char buffer[kBufSize];
209 ✗ memset(buffer, 0, sizeof(buffer));
210
211 ✗ snprintf(buffer,
212 kBufSize,
213 title_format.c_str(),
214 "nsec",
215 "count",
216 "distribution");
217 ✗ result_string += buffer;
218 ✗ memset(buffer, 0, sizeof(buffer));
219
220 ✗ for (i = 1; i <= this->bins_.size() - 1; i++) {
221 ✗ unsigned int n_of_stars = 0;
222 ✗ if (total_sum_of_bins != 0) {
223 ✗ n_of_stars = static_cast<unsigned int>(atomic_read32(&(this->bins_[i]))) *
224 ✗ total_stars / total_sum_of_bins;
225 }
226
227 ✗ snprintf(buffer,
228 kBufSize,
229 format.c_str(),
230 ✗ boundary_values_[i - 1],
231 ✗ boundary_values_[i] - 1,
232 ✗ static_cast<unsigned int>(atomic_read32(&this->bins_[i])),
233 ✗ GenerateStars(n_of_stars).c_str());
234 ✗ result_string += buffer;
235 ✗ memset(buffer, 0, sizeof(buffer));
236 }
237
238 ✗ unsigned int n_of_stars = 0;
239 ✗ if (total_sum_of_bins != 0) {
240 ✗ n_of_stars = static_cast<unsigned int>(atomic_read32(&(this->bins_[0])))
241 ✗ * total_stars / total_sum_of_bins;
242 }
243
244 ✗ snprintf(buffer,
245 kBufSize,
246 overflow_format.c_str(),
247 "overflow",
248 ✗ static_cast<unsigned int>(atomic_read32(&(this->bins_[0]))),
249 ✗ GenerateStars(n_of_stars).c_str());
250 ✗ result_string += buffer;
251 ✗ memset(buffer, 0, sizeof(buffer));
252
253 ✗ snprintf(buffer,
254 kBufSize,
255 total_format.c_str(),
256 "total",
257 total_sum_of_bins);
258 ✗ result_string += buffer;
259 ✗ memset(buffer, 0, sizeof(buffer));
260
261 ✗ float qs[15] = {.1, .2, .25, .3, .4, .5, .6, .7,
262 .75, .8, .9, .95, .99, .995, .999};
263 ✗ snprintf(buffer, kBufSize,
264 "\n\nQuantiles\n"
265 "%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,"
266 "%0.4f,%0.4f,%0.4f,%0.4f\n"
267 "%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n"
268 "End Quantiles"
269 "\n-----------------------\n",
270 ✗ qs[0], qs[1], qs[2], qs[3], qs[4], qs[5], qs[6], qs[7], qs[8], qs[9],
271 ✗ qs[10], qs[11], qs[12], qs[13], qs[14], GetQuantile(qs[0]),
272 GetQuantile(qs[1]), GetQuantile(qs[2]), GetQuantile(qs[3]),
273 GetQuantile(qs[4]), GetQuantile(qs[5]), GetQuantile(qs[6]),
274 GetQuantile(qs[7]), GetQuantile(qs[8]), GetQuantile(qs[9]),
275 GetQuantile(qs[10]), GetQuantile(qs[11]), GetQuantile(qs[12]),
276 GetQuantile(qs[13]), GetQuantile(qs[14]));
277
278 ✗ result_string += buffer;
279 ✗ memset(buffer, 0, sizeof(buffer));
280
281 ✗ return result_string;
282 }
283
284 ✗ void Log2Histogram::PrintLog2Histogram() {
285 ✗ printf("%s", this->ToString().c_str());
286 }
287
288 #ifdef CVMFS_NAMESPACE_GUARD
289 } // namespace CVMFS_NAMESPACE_GUARD
290 #endif
291