src/StatHist.cc

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