GCC Code Coverage Report

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