]>
Commit | Line | Data |
---|---|---|
2ac76861 | 1 | |
5625c032 | 2 | /* |
5625c032 | 3 | * DEBUG: section 62 Generic Histogram |
4 | * AUTHOR: Duane Wessels | |
5 | * | |
2b6662ba | 6 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 7 | * ---------------------------------------------------------- |
5625c032 | 8 | * |
2b6662ba | 9 | * Squid is the result of efforts by numerous individuals from |
10 | * the Internet community; see the CONTRIBUTORS file for full | |
11 | * details. Many organizations have provided support for Squid's | |
12 | * development; see the SPONSORS file for full details. Squid is | |
13 | * Copyrighted (C) 2001 by the Regents of the University of | |
14 | * California; see the COPYRIGHT file for full details. Squid | |
15 | * incorporates software developed and/or copyrighted by other | |
16 | * sources; see the CREDITS file for full details. | |
5625c032 | 17 | * |
18 | * This program is free software; you can redistribute it and/or modify | |
19 | * it under the terms of the GNU General Public License as published by | |
20 | * the Free Software Foundation; either version 2 of the License, or | |
21 | * (at your option) any later version. | |
26ac0430 | 22 | * |
5625c032 | 23 | * This program is distributed in the hope that it will be useful, |
24 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
25 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
26 | * GNU General Public License for more details. | |
26ac0430 | 27 | * |
5625c032 | 28 | * You should have received a copy of the GNU General Public License |
29 | * along with this program; if not, write to the Free Software | |
cbdec147 | 30 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 31 | * |
5625c032 | 32 | */ |
33 | ||
f7f3304a | 34 | #include "squid.h" |
00a7574e | 35 | #include "StatHist.h" |
5625c032 | 36 | |
37 | /* Local functions */ | |
ba4f8e5a | 38 | static StatHistBinDumper statHistBinDumper; |
6617702a | 39 | |
20efa1c2 AJ |
40 | namespace Math |
41 | { | |
6617702a AJ |
42 | hbase_f Log; |
43 | hbase_f Exp; | |
44 | hbase_f Null; | |
20efa1c2 | 45 | }; |
5625c032 | 46 | |
47 | /* low level init, higher level functions has less params */ | |
406c0a08 | 48 | void |
4541d989 | 49 | StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax) |
5625c032 | 50 | { |
532efbb9 FC |
51 | /* check before we divide to get scale_ */ |
52 | assert(val_in_(newMax - newMin) > 0); | |
53 | min_ = newMin; | |
54 | max_ = newMax; | |
55 | capacity_ = newCapacity; | |
406c0a08 FC |
56 | val_in = val_in_; |
57 | val_out = val_out_; | |
4541d989 | 58 | bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type))); |
532efbb9 | 59 | scale_ = capacity_ / val_in(max_ - min_); |
5625c032 | 60 | } |
61 | ||
62 | void | |
2ebbe7a4 | 63 | StatHist::clear() |
5625c032 | 64 | { |
4541d989 | 65 | for (unsigned int i=0; i<capacity_; ++i) |
2a38d231 FC |
66 | bins[i]=0; |
67 | } | |
68 | ||
978901be FC |
69 | StatHist::StatHist(const StatHist &src) : |
70 | capacity_(src.capacity_), min_(src.min_), max_(src.max_), | |
71 | scale_(src.scale_), val_in(src.val_in), val_out(src.val_out) | |
72 | { | |
bcc16048 | 73 | if (src.bins!=NULL) { |
4541d989 | 74 | bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(int))); |
978901be FC |
75 | memcpy(bins,src.bins,capacity_*sizeof(*bins)); |
76 | } | |
77 | } | |
78 | ||
5625c032 | 79 | void |
f30f7998 | 80 | StatHist::count(double val) |
5625c032 | 81 | { |
4541d989 FC |
82 | if (bins==NULL) //do not count before initialization or after destruction |
83 | return; | |
84 | const unsigned int bin = findBin(val); | |
f30f7998 | 85 | ++bins[bin]; |
5625c032 | 86 | } |
87 | ||
4541d989 | 88 | unsigned int |
3da5974d | 89 | StatHist::findBin(double v) |
5625c032 | 90 | { |
62e76326 | 91 | |
532efbb9 | 92 | v -= min_; /* offset */ |
62e76326 | 93 | |
41587298 | 94 | if (v <= 0.0) /* too small */ |
62e76326 | 95 | return 0; |
96 | ||
4541d989 FC |
97 | unsigned int bin; |
98 | double tmp_bin=floor(scale_ * val_in(v) + 0.5); | |
62e76326 | 99 | |
4541d989 | 100 | if (tmp_bin < 0.0) // should not happen |
a343943f | 101 | return 0; |
4541d989 | 102 | bin = static_cast <unsigned int>(tmp_bin); |
62e76326 | 103 | |
532efbb9 FC |
104 | if (bin >= capacity_) /* too big */ |
105 | bin = capacity_ - 1; | |
62e76326 | 106 | |
5625c032 | 107 | return bin; |
108 | } | |
109 | ||
5eeda86d | 110 | double |
4541d989 | 111 | StatHist::val(unsigned int bin) const |
5625c032 | 112 | { |
532efbb9 | 113 | return val_out((double) bin / scale_) + min_; |
5625c032 | 114 | } |
115 | ||
116 | double | |
3888201e | 117 | statHistDeltaMedian(const StatHist & A, const StatHist & B) |
04a28d46 | 118 | { |
a343943f | 119 | return statHistDeltaPctile(A, B, 0.5); |
04a28d46 | 120 | } |
121 | ||
122 | double | |
3888201e | 123 | statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile) |
4fa5ccf4 | 124 | { |
a343943f | 125 | return A.deltaPctile(B, pctile); |
4fa5ccf4 FC |
126 | } |
127 | ||
128 | double | |
129 | StatHist::deltaPctile(const StatHist & B, double pctile) const | |
5625c032 | 130 | { |
4541d989 FC |
131 | unsigned int i; |
132 | bins_type s1 = 0; | |
133 | bins_type h = 0; | |
134 | bins_type a = 0; | |
135 | bins_type b = 0; | |
136 | unsigned int I = 0; | |
137 | unsigned int J = capacity_; | |
138 | unsigned int K; | |
5625c032 | 139 | double f; |
62e76326 | 140 | |
532efbb9 | 141 | assert(capacity_ == B.capacity_); |
5eeda86d | 142 | |
532efbb9 | 143 | int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int))); |
5eeda86d | 144 | |
532efbb9 | 145 | for (i = 0; i < capacity_; ++i) { |
4fa5ccf4 | 146 | D[i] = B.bins[i] - bins[i]; |
62e76326 | 147 | assert(D[i] >= 0); |
5625c032 | 148 | } |
62e76326 | 149 | |
532efbb9 | 150 | for (i = 0; i < capacity_; ++i) |
62e76326 | 151 | s1 += D[i]; |
152 | ||
04a28d46 | 153 | h = int(s1 * pctile); |
62e76326 | 154 | |
532efbb9 | 155 | for (i = 0; i < capacity_; ++i) { |
62e76326 | 156 | J = i; |
157 | b += D[J]; | |
158 | ||
159 | if (a <= h && h <= b) | |
160 | break; | |
161 | ||
162 | I = i; | |
163 | ||
164 | a += D[I]; | |
5625c032 | 165 | } |
62e76326 | 166 | |
5625c032 | 167 | xfree(D); |
62e76326 | 168 | |
5625c032 | 169 | if (s1 == 0) |
62e76326 | 170 | return 0.0; |
171 | ||
6a6c3b50 | 172 | if (a > h) |
62e76326 | 173 | return 0.0; |
174 | ||
6a6c3b50 | 175 | if (a >= b) |
62e76326 | 176 | return 0.0; |
177 | ||
6a6c3b50 | 178 | if (I >= J) |
62e76326 | 179 | return 0.0; |
180 | ||
5625c032 | 181 | f = (h - a) / (b - a); |
62e76326 | 182 | |
4541d989 | 183 | K = (unsigned int) floor(f * (double) (J - I) + I); |
62e76326 | 184 | |
4fa5ccf4 | 185 | return val(K); |
5625c032 | 186 | } |
187 | ||
188 | static void | |
189 | statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
190 | { | |
191 | if (count) | |
62e76326 | 192 | storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n", |
193 | idx, val, count, count / size); | |
5625c032 | 194 | } |
195 | ||
196 | void | |
96886986 | 197 | StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const |
5625c032 | 198 | { |
532efbb9 | 199 | double left_border = min_; |
62e76326 | 200 | |
5625c032 | 201 | if (!bd) |
62e76326 | 202 | bd = statHistBinDumper; |
203 | ||
4541d989 | 204 | for (unsigned int i = 0; i < capacity_; ++i) { |
96886986 | 205 | const double right_border = val(i + 1); |
62e76326 | 206 | assert(right_border - left_border > 0.0); |
96886986 | 207 | bd(sentry, i, left_border, right_border - left_border, bins[i]); |
62e76326 | 208 | left_border = right_border; |
5625c032 | 209 | } |
210 | } | |
211 | ||
212 | /* log based histogram */ | |
853310e4 | 213 | double |
20efa1c2 | 214 | Math::Log(double x) |
2ac76861 | 215 | { |
9689d97c | 216 | assert((x + 1.0) >= 0.0); |
217 | return log(x + 1.0); | |
2ac76861 | 218 | } |
853310e4 | 219 | |
853310e4 | 220 | double |
20efa1c2 | 221 | Math::Exp(double x) |
2ac76861 | 222 | { |
9689d97c | 223 | return exp(x) - 1.0; |
2ac76861 | 224 | } |
853310e4 | 225 | |
97d30a2e | 226 | void |
4541d989 | 227 | StatHist::logInit(unsigned int capacity, double min, double max) |
97d30a2e FC |
228 | { |
229 | init(capacity, Math::Log, Math::Exp, min, max); | |
230 | } | |
231 | ||
5625c032 | 232 | /* linear histogram for enums */ |
233 | /* we want to be have [-1,last_enum+1] range to track out of range enums */ | |
853310e4 | 234 | double |
20efa1c2 | 235 | Math::Null(double x) |
2ac76861 | 236 | { |
237 | return x; | |
238 | } | |
ba4f8e5a | 239 | |
d982012a | 240 | void |
4541d989 | 241 | StatHist::enumInit(unsigned int last_enum) |
d982012a | 242 | { |
a343943f | 243 | init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum)); |
d982012a FC |
244 | } |
245 | ||
173d54ab | 246 | void |
ba4f8e5a | 247 | statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count) |
173d54ab | 248 | { |
249 | if (count) | |
62e76326 | 250 | storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n", |
251 | idx, (int) val, count); | |
173d54ab | 252 | } |
ba4f8e5a | 253 | |
ba4f8e5a | 254 | void |
255 | statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count) | |
256 | { | |
257 | if (count) | |
62e76326 | 258 | storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count); |
ba4f8e5a | 259 | } |