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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors