GCC Code Coverage Report

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