GCC Code Coverage Report

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