]>
Commit | Line | Data |
---|---|---|
5625c032 | 1 | /* |
ef57eb7b | 2 | * Copyright (C) 1996-2016 The Squid Software Foundation and contributors |
e25c139f | 3 | * |
bbc27441 AJ |
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. | |
5625c032 | 7 | */ |
8 | ||
bbc27441 AJ |
9 | /* DEBUG: section 62 Generic Histogram */ |
10 | ||
f7f3304a | 11 | #include "squid.h" |
00a7574e | 12 | #include "StatHist.h" |
5625c032 | 13 | |
074d6a40 AJ |
14 | #include <cmath> |
15 | ||
5625c032 | 16 | /* Local functions */ |
ba4f8e5a | 17 | static StatHistBinDumper statHistBinDumper; |
6617702a | 18 | |
20efa1c2 AJ |
19 | namespace Math |
20 | { | |
6617702a AJ |
21 | hbase_f Log; |
22 | hbase_f Exp; | |
23 | hbase_f Null; | |
20efa1c2 | 24 | }; |
5625c032 | 25 | |
26 | /* low level init, higher level functions has less params */ | |
406c0a08 | 27 | void |
4541d989 | 28 | StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax) |
5625c032 | 29 | { |
532efbb9 FC |
30 | /* check before we divide to get scale_ */ |
31 | assert(val_in_(newMax - newMin) > 0); | |
32 | min_ = newMin; | |
33 | max_ = newMax; | |
34 | capacity_ = newCapacity; | |
406c0a08 FC |
35 | val_in = val_in_; |
36 | val_out = val_out_; | |
4541d989 | 37 | bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type))); |
532efbb9 | 38 | scale_ = capacity_ / val_in(max_ - min_); |
5625c032 | 39 | } |
40 | ||
978901be | 41 | StatHist::StatHist(const StatHist &src) : |
cc8c4af2 AJ |
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) | |
978901be | 49 | { |
bcc16048 | 50 | if (src.bins!=NULL) { |
b1bcd7da | 51 | bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type))); |
978901be FC |
52 | memcpy(bins,src.bins,capacity_*sizeof(*bins)); |
53 | } | |
54 | } | |
55 | ||
5625c032 | 56 | void |
9dca980d | 57 | StatHist::count(double v) |
5625c032 | 58 | { |
4541d989 FC |
59 | if (bins==NULL) //do not count before initialization or after destruction |
60 | return; | |
9dca980d | 61 | const unsigned int bin = findBin(v); |
f30f7998 | 62 | ++bins[bin]; |
5625c032 | 63 | } |
64 | ||
4541d989 | 65 | unsigned int |
3da5974d | 66 | StatHist::findBin(double v) |
5625c032 | 67 | { |
f53969cc | 68 | v -= min_; /* offset */ |
62e76326 | 69 | |
f53969cc | 70 | if (v <= 0.0) /* too small */ |
62e76326 | 71 | return 0; |
72 | ||
4541d989 FC |
73 | unsigned int bin; |
74 | double tmp_bin=floor(scale_ * val_in(v) + 0.5); | |
62e76326 | 75 | |
4541d989 | 76 | if (tmp_bin < 0.0) // should not happen |
a343943f | 77 | return 0; |
4541d989 | 78 | bin = static_cast <unsigned int>(tmp_bin); |
62e76326 | 79 | |
f53969cc | 80 | if (bin >= capacity_) /* too big */ |
532efbb9 | 81 | bin = capacity_ - 1; |
62e76326 | 82 | |
5625c032 | 83 | return bin; |
84 | } | |
85 | ||
5eeda86d | 86 | double |
4541d989 | 87 | StatHist::val(unsigned int bin) const |
5625c032 | 88 | { |
532efbb9 | 89 | return val_out((double) bin / scale_) + min_; |
5625c032 | 90 | } |
91 | ||
92 | double | |
3888201e | 93 | statHistDeltaMedian(const StatHist & A, const StatHist & B) |
04a28d46 | 94 | { |
a343943f | 95 | return statHistDeltaPctile(A, B, 0.5); |
04a28d46 | 96 | } |
97 | ||
98 | double | |
3888201e | 99 | statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile) |
4fa5ccf4 | 100 | { |
a343943f | 101 | return A.deltaPctile(B, pctile); |
4fa5ccf4 FC |
102 | } |
103 | ||
104 | double | |
105 | StatHist::deltaPctile(const StatHist & B, double pctile) const | |
5625c032 | 106 | { |
4541d989 FC |
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; | |
5625c032 | 115 | double f; |
62e76326 | 116 | |
532efbb9 | 117 | assert(capacity_ == B.capacity_); |
5eeda86d | 118 | |
532efbb9 | 119 | int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int))); |
5eeda86d | 120 | |
532efbb9 | 121 | for (i = 0; i < capacity_; ++i) { |
4fa5ccf4 | 122 | D[i] = B.bins[i] - bins[i]; |
62e76326 | 123 | assert(D[i] >= 0); |
5625c032 | 124 | } |
62e76326 | 125 | |
532efbb9 | 126 | for (i = 0; i < capacity_; ++i) |
62e76326 | 127 | s1 += D[i]; |
128 | ||
04a28d46 | 129 | h = int(s1 * pctile); |
62e76326 | 130 | |
532efbb9 | 131 | for (i = 0; i < capacity_; ++i) { |
62e76326 | 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]; | |
5625c032 | 141 | } |
62e76326 | 142 | |
5625c032 | 143 | xfree(D); |
62e76326 | 144 | |
5625c032 | 145 | if (s1 == 0) |
62e76326 | 146 | return 0.0; |
147 | ||
6a6c3b50 | 148 | if (a > h) |
62e76326 | 149 | return 0.0; |
150 | ||
6a6c3b50 | 151 | if (a >= b) |
62e76326 | 152 | return 0.0; |
153 | ||
6a6c3b50 | 154 | if (I >= J) |
62e76326 | 155 | return 0.0; |
156 | ||
5625c032 | 157 | f = (h - a) / (b - a); |
62e76326 | 158 | |
4541d989 | 159 | K = (unsigned int) floor(f * (double) (J - I) + I); |
62e76326 | 160 | |
4fa5ccf4 | 161 | return val(K); |
5625c032 | 162 | } |
163 | ||
164 | static void | |
165 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
166 | { | |
167 | if (count) | |
62e76326 | 168 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
169 | idx, val, count, count / size); | |
5625c032 | 170 | } |
171 | ||
172 | void | |
96886986 | 173 | StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const |
5625c032 | 174 | { |
532efbb9 | 175 | double left_border = min_; |
62e76326 | 176 | |
5625c032 | 177 | if (!bd) |
62e76326 | 178 | bd = statHistBinDumper; |
179 | ||
4541d989 | 180 | for (unsigned int i = 0; i < capacity_; ++i) { |
96886986 | 181 | const double right_border = val(i + 1); |
62e76326 | 182 | assert(right_border - left_border > 0.0); |
96886986 | 183 | bd(sentry, i, left_border, right_border - left_border, bins[i]); |
62e76326 | 184 | left_border = right_border; |
5625c032 | 185 | } |
186 | } | |
187 | ||
ff1eb053 FC |
188 | StatHist & |
189 | StatHist::operator += (const StatHist &B) | |
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 | ||
5625c032 | 208 | /* log based histogram */ |
853310e4 | 209 | double |
20efa1c2 | 210 | Math::Log(double x) |
2ac76861 | 211 | { |
9689d97c | 212 | assert((x + 1.0) >= 0.0); |
213 | return log(x + 1.0); | |
2ac76861 | 214 | } |
853310e4 | 215 | |
853310e4 | 216 | double |
20efa1c2 | 217 | Math::Exp(double x) |
2ac76861 | 218 | { |
9689d97c | 219 | return exp(x) - 1.0; |
2ac76861 | 220 | } |
853310e4 | 221 | |
97d30a2e | 222 | void |
4541d989 | 223 | StatHist::logInit(unsigned int capacity, double min, double max) |
97d30a2e FC |
224 | { |
225 | init(capacity, Math::Log, Math::Exp, min, max); | |
226 | } | |
227 | ||
5625c032 | 228 | /* linear histogram for enums */ |
229 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
853310e4 | 230 | double |
20efa1c2 | 231 | Math::Null(double x) |
2ac76861 | 232 | { |
233 | return x; | |
234 | } | |
ba4f8e5a | 235 | |
d982012a | 236 | void |
4541d989 | 237 | StatHist::enumInit(unsigned int last_enum) |
d982012a | 238 | { |
a343943f | 239 | init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum)); |
d982012a FC |
240 | } |
241 | ||
173d54ab | 242 | void |
ced8def3 | 243 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double, int count) |
173d54ab | 244 | { |
245 | if (count) | |
62e76326 | 246 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
247 | idx, (int) val, count); | |
173d54ab | 248 | } |
ba4f8e5a | 249 | |
ba4f8e5a | 250 | void |
ced8def3 | 251 | statHistIntDumper(StoreEntry * sentry, int, double val, double, int count) |
ba4f8e5a | 252 | { |
253 | if (count) | |
62e76326 | 254 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 255 | } |
f53969cc | 256 |