src/StatHist.cc

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