]>
Commit | Line | Data |
---|---|---|
5625c032 | 1 | /* |
bde978a6 | 2 | * Copyright (C) 1996-2015 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) : |
f53969cc SM |
42 | capacity_(src.capacity_), min_(src.min_), max_(src.max_), |
43 | scale_(src.scale_), val_in(src.val_in), val_out(src.val_out) | |
978901be | 44 | { |
bcc16048 | 45 | if (src.bins!=NULL) { |
b1bcd7da | 46 | bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type))); |
978901be FC |
47 | memcpy(bins,src.bins,capacity_*sizeof(*bins)); |
48 | } | |
49 | } | |
50 | ||
5625c032 | 51 | void |
9dca980d | 52 | StatHist::count(double v) |
5625c032 | 53 | { |
4541d989 FC |
54 | if (bins==NULL) //do not count before initialization or after destruction |
55 | return; | |
9dca980d | 56 | const unsigned int bin = findBin(v); |
f30f7998 | 57 | ++bins[bin]; |
5625c032 | 58 | } |
59 | ||
4541d989 | 60 | unsigned int |
3da5974d | 61 | StatHist::findBin(double v) |
5625c032 | 62 | { |
62e76326 | 63 | |
f53969cc | 64 | v -= min_; /* offset */ |
62e76326 | 65 | |
f53969cc | 66 | if (v <= 0.0) /* too small */ |
62e76326 | 67 | return 0; |
68 | ||
4541d989 FC |
69 | unsigned int bin; |
70 | double tmp_bin=floor(scale_ * val_in(v) + 0.5); | |
62e76326 | 71 | |
4541d989 | 72 | if (tmp_bin < 0.0) // should not happen |
a343943f | 73 | return 0; |
4541d989 | 74 | bin = static_cast <unsigned int>(tmp_bin); |
62e76326 | 75 | |
f53969cc | 76 | if (bin >= capacity_) /* too big */ |
532efbb9 | 77 | bin = capacity_ - 1; |
62e76326 | 78 | |
5625c032 | 79 | return bin; |
80 | } | |
81 | ||
5eeda86d | 82 | double |
4541d989 | 83 | StatHist::val(unsigned int bin) const |
5625c032 | 84 | { |
532efbb9 | 85 | return val_out((double) bin / scale_) + min_; |
5625c032 | 86 | } |
87 | ||
88 | double | |
3888201e | 89 | statHistDeltaMedian(const StatHist & A, const StatHist & B) |
04a28d46 | 90 | { |
a343943f | 91 | return statHistDeltaPctile(A, B, 0.5); |
04a28d46 | 92 | } |
93 | ||
94 | double | |
3888201e | 95 | statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile) |
4fa5ccf4 | 96 | { |
a343943f | 97 | return A.deltaPctile(B, pctile); |
4fa5ccf4 FC |
98 | } |
99 | ||
100 | double | |
101 | StatHist::deltaPctile(const StatHist & B, double pctile) const | |
5625c032 | 102 | { |
4541d989 FC |
103 | unsigned int i; |
104 | bins_type s1 = 0; | |
105 | bins_type h = 0; | |
106 | bins_type a = 0; | |
107 | bins_type b = 0; | |
108 | unsigned int I = 0; | |
109 | unsigned int J = capacity_; | |
110 | unsigned int K; | |
5625c032 | 111 | double f; |
62e76326 | 112 | |
532efbb9 | 113 | assert(capacity_ == B.capacity_); |
5eeda86d | 114 | |
532efbb9 | 115 | int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int))); |
5eeda86d | 116 | |
532efbb9 | 117 | for (i = 0; i < capacity_; ++i) { |
4fa5ccf4 | 118 | D[i] = B.bins[i] - bins[i]; |
62e76326 | 119 | assert(D[i] >= 0); |
5625c032 | 120 | } |
62e76326 | 121 | |
532efbb9 | 122 | for (i = 0; i < capacity_; ++i) |
62e76326 | 123 | s1 += D[i]; |
124 | ||
04a28d46 | 125 | h = int(s1 * pctile); |
62e76326 | 126 | |
532efbb9 | 127 | for (i = 0; i < capacity_; ++i) { |
62e76326 | 128 | J = i; |
129 | b += D[J]; | |
130 | ||
131 | if (a <= h && h <= b) | |
132 | break; | |
133 | ||
134 | I = i; | |
135 | ||
136 | a += D[I]; | |
5625c032 | 137 | } |
62e76326 | 138 | |
5625c032 | 139 | xfree(D); |
62e76326 | 140 | |
5625c032 | 141 | if (s1 == 0) |
62e76326 | 142 | return 0.0; |
143 | ||
6a6c3b50 | 144 | if (a > h) |
62e76326 | 145 | return 0.0; |
146 | ||
6a6c3b50 | 147 | if (a >= b) |
62e76326 | 148 | return 0.0; |
149 | ||
6a6c3b50 | 150 | if (I >= J) |
62e76326 | 151 | return 0.0; |
152 | ||
5625c032 | 153 | f = (h - a) / (b - a); |
62e76326 | 154 | |
4541d989 | 155 | K = (unsigned int) floor(f * (double) (J - I) + I); |
62e76326 | 156 | |
4fa5ccf4 | 157 | return val(K); |
5625c032 | 158 | } |
159 | ||
160 | static void | |
161 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
162 | { | |
163 | if (count) | |
62e76326 | 164 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
165 | idx, val, count, count / size); | |
5625c032 | 166 | } |
167 | ||
168 | void | |
96886986 | 169 | StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const |
5625c032 | 170 | { |
532efbb9 | 171 | double left_border = min_; |
62e76326 | 172 | |
5625c032 | 173 | if (!bd) |
62e76326 | 174 | bd = statHistBinDumper; |
175 | ||
4541d989 | 176 | for (unsigned int i = 0; i < capacity_; ++i) { |
96886986 | 177 | const double right_border = val(i + 1); |
62e76326 | 178 | assert(right_border - left_border > 0.0); |
96886986 | 179 | bd(sentry, i, left_border, right_border - left_border, bins[i]); |
62e76326 | 180 | left_border = right_border; |
5625c032 | 181 | } |
182 | } | |
183 | ||
ff1eb053 FC |
184 | StatHist & |
185 | StatHist::operator += (const StatHist &B) | |
186 | { | |
187 | Must(capacity_ == B.capacity_); | |
188 | Must(min_ == B.min_); | |
189 | Must(max_ == B.max_); | |
190 | ||
191 | if (B.bins == NULL) { // B was not yet initializted | |
192 | return *this; | |
193 | } | |
194 | if (bins == NULL) { // this histogram was not yet initialized | |
195 | *this = B; | |
196 | return *this; | |
197 | } | |
198 | for (unsigned int i = 0; i < capacity_; ++i) { | |
199 | bins[i] += B.bins[i]; | |
200 | } | |
201 | return *this; | |
202 | } | |
203 | ||
5625c032 | 204 | /* log based histogram */ |
853310e4 | 205 | double |
20efa1c2 | 206 | Math::Log(double x) |
2ac76861 | 207 | { |
9689d97c | 208 | assert((x + 1.0) >= 0.0); |
209 | return log(x + 1.0); | |
2ac76861 | 210 | } |
853310e4 | 211 | |
853310e4 | 212 | double |
20efa1c2 | 213 | Math::Exp(double x) |
2ac76861 | 214 | { |
9689d97c | 215 | return exp(x) - 1.0; |
2ac76861 | 216 | } |
853310e4 | 217 | |
97d30a2e | 218 | void |
4541d989 | 219 | StatHist::logInit(unsigned int capacity, double min, double max) |
97d30a2e FC |
220 | { |
221 | init(capacity, Math::Log, Math::Exp, min, max); | |
222 | } | |
223 | ||
5625c032 | 224 | /* linear histogram for enums */ |
225 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
853310e4 | 226 | double |
20efa1c2 | 227 | Math::Null(double x) |
2ac76861 | 228 | { |
229 | return x; | |
230 | } | |
ba4f8e5a | 231 | |
d982012a | 232 | void |
4541d989 | 233 | StatHist::enumInit(unsigned int last_enum) |
d982012a | 234 | { |
a343943f | 235 | init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum)); |
d982012a FC |
236 | } |
237 | ||
173d54ab | 238 | void |
ced8def3 | 239 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double, int count) |
173d54ab | 240 | { |
241 | if (count) | |
62e76326 | 242 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
243 | idx, (int) val, count); | |
173d54ab | 244 | } |
ba4f8e5a | 245 | |
ba4f8e5a | 246 | void |
ced8def3 | 247 | statHistIntDumper(StoreEntry * sentry, int, double val, double, int count) |
ba4f8e5a | 248 | { |
249 | if (count) | |
62e76326 | 250 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 251 | } |
f53969cc | 252 |