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