CernVM-FS  2.9.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
algorithm.cc
Go to the documentation of this file.
1 
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 
29 
30 
31 double DiffTimeSeconds(struct timeval start, struct timeval end) {
32  // Time substraction, from GCC documentation
33  if (end.tv_usec < start.tv_usec) {
34  int64_t nsec = (end.tv_usec - start.tv_usec) / 1000000 + 1;
35  start.tv_usec -= 1000000 * nsec;
36  start.tv_sec += nsec;
37  }
38  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  uint64_t elapsed_usec = ((end.tv_sec - start.tv_sec)*1000000) +
47  (end.tv_usec - start.tv_usec);
48  return static_cast<double>(elapsed_usec)/1000000.0;
49 }
50 
51 
52 
54  assert(!running_);
55 
56  gettimeofday(&start_, NULL);
57  running_ = true;
58 }
59 
60 
62  assert(running_);
63 
64  gettimeofday(&end_, NULL);
65  running_ = false;
66 }
67 
68 
70  start_ = timeval();
71  end_ = timeval();
72  running_ = false;
73 }
74 
75 
76 double StopWatch::GetTime() const {
77  assert(!running_);
78 
79  return DiffTimeSeconds(start_, end_);
80 }
81 
82 namespace {
83 
84 static unsigned int CountDigits(uint64_t n) {
85  return static_cast<unsigned int>(floor(log10(static_cast<double>(n)))) + 1;
86 }
87 
88 static std::string GenerateStars(unsigned int n) {
89  return std::string(n, '*');
90 }
91 
92 } // anonymous namespace
93 
94 Log2Histogram::Log2Histogram(unsigned int nbins) {
95  assert(nbins != 0);
96  this->bins_.assign(nbins + 1, 0); // +1 for overflow bin.
97  this->boundary_values_.assign(nbins + 1, 0); // +1 to avoid big if statement
98 
99  unsigned int i;
100  for (i = 1; i <= nbins; i++) {
101  this->boundary_values_[i] = (1 << ((i - 1) + 1));
102  }
103 }
104 
105 std::vector<atomic_int32> UTLog2Histogram::GetBins(const Log2Histogram &h) {
106  return h.bins_;
107 }
108 
109 unsigned int Log2Histogram::GetQuantile(float n) {
110  uint64_t total = this->N();
111  // pivot is the index of the element corresponding to the requested quantile
112  uint64_t pivot = static_cast<uint64_t>(static_cast<float>(total) * n);
113  float normalized_pivot = 0.0;
114  // now we iterate through all the bins
115  // note that we _exclude_ the overflow bin
116  unsigned int i = 0;
117  for (i = 1; 1 <= this->bins_.size() - 1; i++) {
118  unsigned int bin_value =
119  static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
120  if (pivot <= bin_value) {
121  normalized_pivot =
122  static_cast<float>(pivot) / static_cast<float>(bin_value);
123  break;
124  }
125  pivot -= bin_value;
126  }
127  // now i stores the index of the bin corresponding to the requested quantile
128  // and normalized_pivot is the element we want inside the bin
129  unsigned int min_value = this->boundary_values_[i - 1];
130  unsigned int max_value = this->boundary_values_[i];
131  // and we return the linear interpolation
132  return min_value + static_cast<unsigned int>(
133  static_cast<float>(max_value - min_value) * normalized_pivot);
134 }
135 
136 std::string Log2Histogram::ToString() {
137  unsigned int i = 0;
138 
139  unsigned int max_left_boundary_count = 1;
140  unsigned int max_right_boundary_count = 1;
141  unsigned int max_value_count = 1;
142  unsigned int max_stars = 0;
143  unsigned int max_bins = 0;
144  unsigned int total_stars = 38;
145  uint64_t total_sum_of_bins = 0;
146 
147  for (i = 1; i <= this->bins_.size() - 1; i++) {
148  max_left_boundary_count = std::max(max_left_boundary_count,
149  CountDigits(boundary_values_[i] / 2));
150  max_right_boundary_count = std::max(max_right_boundary_count,
151  CountDigits(boundary_values_[i] - 1));
152  max_value_count = std::max(max_value_count, CountDigits(this->bins_[i]));
153  max_bins = std::max(max_bins, static_cast<unsigned int>(
154  atomic_read32(&(this->bins_[i]))));
155  total_sum_of_bins +=
156  static_cast<unsigned int>(atomic_read32(&(this->bins_[i])));
157  }
158 
159  max_bins = std::max(max_bins, static_cast<unsigned int>(
160  atomic_read32(&(this->bins_[0]))));
161  total_sum_of_bins +=
162  static_cast<unsigned int>(atomic_read32(&(this->bins_[0])));
163 
164  if (total_sum_of_bins != 0) {
165  max_stars = max_bins * total_stars / total_sum_of_bins;
166  }
167 
168  std::string format = " %" + StringifyUint(max_left_boundary_count < 2 ?
169  2 : max_left_boundary_count) +
170  "d -> %" + StringifyUint(max_right_boundary_count) +
171  "d : %" + StringifyUint(max_value_count) + "d | %" +
172  StringifyUint(max_stars < 12 ? 12 : max_stars) + "s |\n";
173 
174  std::string title_format = " %" +
175  StringifyUint((max_left_boundary_count < 2 ?
176  2 : max_left_boundary_count) +
177  max_right_boundary_count +
178  4) +
179  "s | %" + StringifyUint(max_value_count + 4) +
180  "s | %" + StringifyUint(max_stars < 12 ? 12 : max_stars) +
181  "s |\n";
182 
183  std::string overflow_format = "%" +
184  StringifyUint(max_left_boundary_count +
185  max_right_boundary_count +
186  5) +
187  "s : %" + StringifyUint(max_value_count + 4) +
188  "d | %" + StringifyUint(max_stars < 12 ? 12 : max_stars) +
189  "s |\n";
190 
191  std::string total_format = "%" +
192  StringifyUint(max_left_boundary_count +
193  max_right_boundary_count +
194  5 < 8 ? 8 : max_left_boundary_count +
195  max_right_boundary_count + 5) +
196  "s : %" + StringifyUint(max_value_count + 4) + "lld\n";
197 
198  std::string result_string = "";
199 
200  const unsigned int kBufSize = 300;
201  char buffer[kBufSize];
202  memset(buffer, 0, sizeof(buffer));
203 
204  snprintf(buffer,
205  kBufSize,
206  title_format.c_str(),
207  "nsec",
208  "count",
209  "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,
247  kBufSize,
248  total_format.c_str(),
249  "total",
250  total_sum_of_bins);
251  result_string += buffer;
252  memset(buffer, 0, sizeof(buffer));
253 
254  float qs[15] = {.1, .2, .25, .3, .4, .5, .6, .7,
255  .75, .8, .9, .95, .99, .995, .999};
256  snprintf(buffer, kBufSize,
257  "\n\nQuantiles\n"
258  "%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,%0.4f,"
259  "%0.4f,%0.4f,%0.4f,%0.4f\n"
260  "%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n"
261  "End Quantiles"
262  "\n-----------------------\n",
263  qs[0], qs[1], qs[2], qs[3], qs[4], qs[5], qs[6], qs[7], qs[8], qs[9],
264  qs[10], qs[11], qs[12], qs[13], qs[14], GetQuantile(qs[0]),
265  GetQuantile(qs[1]), GetQuantile(qs[2]), GetQuantile(qs[3]),
266  GetQuantile(qs[4]), GetQuantile(qs[5]), GetQuantile(qs[6]),
267  GetQuantile(qs[7]), GetQuantile(qs[8]), GetQuantile(qs[9]),
268  GetQuantile(qs[10]), GetQuantile(qs[11]), GetQuantile(qs[12]),
269  GetQuantile(qs[13]), GetQuantile(qs[14]));
270 
271  result_string += buffer;
272  memset(buffer, 0, sizeof(buffer));
273 
274  return result_string;
275 }
276 
278  printf("%s", this->ToString().c_str());
279 }
280 
281 #ifdef CVMFS_NAMESPACE_GUARD
282 } // namespace CVMFS_NAMESPACE_GUARD
283 #endif
std::vector< atomic_int32 > bins_
Definition: algorithm.h:166
double DiffTimeSeconds(struct timeval start, struct timeval end)
Definition: algorithm.cc:31
double GetTime() const
Definition: algorithm.cc:76
void Reset()
Definition: algorithm.cc:69
static std::string GenerateStars(unsigned int n)
Definition: algorithm.cc:88
assert((mem||(size==0))&&"Out Of Memory")
Log2Histogram(unsigned int nbins)
Definition: algorithm.cc:94
std::string StringifyUint(const uint64_t value)
Definition: string.cc:84
unsigned int GetQuantile(float n)
Definition: algorithm.cc:109
std::string ToString()
Definition: algorithm.cc:136
static unsigned int CountDigits(uint64_t n)
Definition: algorithm.cc:84
void PrintLog2Histogram()
Definition: algorithm.cc:277
void Stop()
Definition: algorithm.cc:61
static bool g_is_enabled
Definition: algorithm.h:184
void Start()
Definition: algorithm.cc:53
std::vector< atomic_int32 > GetBins(const Log2Histogram &h)
Definition: algorithm.cc:105