GCC Code Coverage Report

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