StatHist.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 #include "squid.h"
10 #include "StatHist.h"
11 
12 #include <cmath>
13 
14 /* Local functions */
16 
17 namespace Math
18 {
22 };
23 
24 /* low level init, higher level functions has less params */
25 void
26 StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax)
27 {
28  /* check before we divide to get scale_ */
29  assert(val_in_(newMax - newMin) > 0);
30  min_ = newMin;
31  max_ = newMax;
32  capacity_ = newCapacity;
33  val_in = val_in_;
34  val_out = val_out_;
35  bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type)));
37 }
38 
40  bins(NULL),
41  capacity_(src.capacity_),
42  min_(src.min_),
43  max_(src.max_),
44  scale_(src.scale_),
45  val_in(src.val_in),
46  val_out(src.val_out)
47 {
48  if (src.bins!=NULL) {
49  bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type)));
50  memcpy(bins,src.bins,capacity_*sizeof(*bins));
51  }
52 }
53 
54 void
55 StatHist::count(double v)
56 {
57  if (bins==NULL) //do not count before initialization or after destruction
58  return;
59  const unsigned int bin = findBin(v);
60  ++bins[bin];
61 }
62 
63 unsigned int
65 {
66  v -= min_; /* offset */
67 
68  if (v <= 0.0) /* too small */
69  return 0;
70 
71  unsigned int bin;
72  double tmp_bin=floor(scale_ * val_in(v) + 0.5);
73 
74  if (tmp_bin < 0.0) // should not happen
75  return 0;
76  bin = static_cast <unsigned int>(tmp_bin);
77 
78  if (bin >= capacity_) /* too big */
79  bin = capacity_ - 1;
80 
81  return bin;
82 }
83 
84 double
85 StatHist::val(unsigned int bin) const
86 {
87  return val_out((double) bin / scale_) + min_;
88 }
89 
90 double
92 {
93  return statHistDeltaPctile(A, B, 0.5);
94 }
95 
96 double
97 statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile)
98 {
99  return A.deltaPctile(B, pctile);
100 }
101 
102 double
103 StatHist::deltaPctile(const StatHist & B, double pctile) const
104 {
105  unsigned int i;
106  bins_type s1 = 0;
107  bins_type h = 0;
108  bins_type a = 0;
109  bins_type b = 0;
110  unsigned int I = 0;
111  unsigned int J = capacity_;
112  unsigned int K;
113  double f;
114 
115  assert(capacity_ == B.capacity_);
116 
117  int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int)));
118 
119  for (i = 0; i < capacity_; ++i) {
120  D[i] = B.bins[i] - bins[i];
121  assert(D[i] >= 0);
122  }
123 
124  for (i = 0; i < capacity_; ++i)
125  s1 += D[i];
126 
127  h = int(s1 * pctile);
128 
129  for (i = 0; i < capacity_; ++i) {
130  J = i;
131  b += D[J];
132 
133  if (a <= h && h <= b)
134  break;
135 
136  I = i;
137 
138  a += D[I];
139  }
140 
141  xfree(D);
142 
143  if (s1 == 0)
144  return 0.0;
145 
146  if (a > h)
147  return 0.0;
148 
149  if (a >= b)
150  return 0.0;
151 
152  if (I >= J)
153  return 0.0;
154 
155  f = (h - a) / (b - a);
156 
157  K = (unsigned int) floor(f * (double) (J - I) + I);
158 
159  return val(K);
160 }
161 
162 static void
163 statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
164 {
165  if (count)
166  storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
167  idx, val, count, count / size);
168 }
169 
170 void
172 {
173  double left_border = min_;
174 
175  if (!bd)
176  bd = statHistBinDumper;
177 
178  for (unsigned int i = 0; i < capacity_; ++i) {
179  const double right_border = val(i + 1);
180  assert(right_border - left_border > 0.0);
181  bd(sentry, i, left_border, right_border - left_border, bins[i]);
182  left_border = right_border;
183  }
184 }
185 
186 StatHist &
188 {
189  Must(capacity_ == B.capacity_);
190  Must(min_ == B.min_);
191  Must(max_ == B.max_);
192 
193  if (B.bins == NULL) { // B was not yet initializted
194  return *this;
195  }
196  if (bins == NULL) { // this histogram was not yet initialized
197  *this = B;
198  return *this;
199  }
200  for (unsigned int i = 0; i < capacity_; ++i) {
201  bins[i] += B.bins[i];
202  }
203  return *this;
204 }
205 
206 /* log based histogram */
207 double
208 Math::Log(double x)
209 {
210  assert((x + 1.0) >= 0.0);
211  return log(x + 1.0);
212 }
213 
214 double
215 Math::Exp(double x)
216 {
217  return exp(x) - 1.0;
218 }
219 
220 void
221 StatHist::logInit(unsigned int capacity, double min, double max)
222 {
223  init(capacity, Math::Log, Math::Exp, min, max);
224 }
225 
226 /* linear histogram for enums */
227 /* we want to be have [-1,last_enum+1] range to track out of range enums */
228 double
229 Math::Null(double x)
230 {
231  return x;
232 }
233 
234 void
235 StatHist::enumInit(unsigned int last_enum)
236 {
237  init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum));
238 }
239 
240 void
241 statHistEnumDumper(StoreEntry * sentry, int idx, double val, double, int count)
242 {
243  if (count)
244  storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
245  idx, (int) val, count);
246 }
247 
248 void
249 statHistIntDumper(StoreEntry * sentry, int, double val, double, int count)
250 {
251  if (count)
252  storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
253 }
254 
void * xcalloc(size_t n, size_t sz)
Definition: xalloc.cc:71
void StatHistBinDumper(StoreEntry *, int idx, double val, double size, int count)
function signature for StatHist dumping functions
Definition: StatHist.h:19
double scale_
scaling factor when looking for a bin
Definition: StatHist.h:111
hbase_f Exp
Definition: StatHist.cc:20
@ s1
Definition: cf_gen.cc:55
void log(char *format,...)
double max_
value of the maximum counter in the histogram
Definition: StatHist.h:108
hbase_f Null
Definition: StatHist.cc:21
void storeAppendPrintf(StoreEntry *e, const char *fmt,...)
Definition: store.cc:830
hbase_f * val_out
Definition: StatHist.h:113
Definition: SquidMath.h:22
double val(unsigned int bin) const
Definition: StatHist.cc:85
void statHistEnumDumper(StoreEntry *sentry, int idx, double val, double, int count)
Definition: StatHist.cc:241
static StatHistBinDumper statHistBinDumper
Definition: StatHist.cc:15
double statHistDeltaMedian(const StatHist &A, const StatHist &B)
Definition: StatHist.cc:91
A const & max(A const &lhs, A const &rhs)
unsigned int findBin(double v)
Definition: StatHist.cc:64
StatHist & operator+=(const StatHist &B)
Definition: StatHist.cc:187
double min_
minimum value to be stored, corresponding to the first bin
Definition: StatHist.h:105
int size
Definition: ModDevPoll.cc:75
#define NULL
Definition: types.h:166
double deltaPctile(const StatHist &B, double pctile) const
Definition: StatHist.cc:103
void dump(StoreEntry *sentry, StatHistBinDumper *bd) const
Definition: StatHist.cc:171
static uint32 A
Definition: md4.c:43
void enumInit(unsigned int last_enum)
Definition: StatHist.cc:235
hbase_f Log
Definition: StatHist.cc:19
void statHistIntDumper(StoreEntry *sentry, int, double val, double, int count)
Definition: StatHist.cc:249
double statHistDeltaPctile(const StatHist &A, const StatHist &B, double pctile)
Definition: StatHist.cc:97
void count(double val)
Definition: StatHist.cc:55
#define assert(EX)
Definition: assert.h:19
#define xfree
void init(unsigned int capacity, hbase_f *val_in, hbase_f *val_out, double min, double max)
Definition: StatHist.cc:26
unsigned int capacity_
Definition: StatHist.h:102
double hbase_f(double)
function signature for in/out StatHist adaptation
Definition: StatHist.h:16
#define Must(condition)
Definition: TextException.h:71
void logInit(unsigned int capacity, double min, double max)
Definition: StatHist.cc:221
hbase_f * val_in
Definition: StatHist.h:112
bins_type * bins
the histogram counters
Definition: StatHist.h:101
static uint32 B
Definition: md4.c:43
StatHist()=default
A const & min(A const &lhs, A const &rhs)
static uint32 D
Definition: md4.c:43
uint64_t bins_type
Definition: StatHist.h:44
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors