src/StatHist.cc

   1 /*
   2  * Copyright (C) 1996-2014 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         capacity_(src.capacity_), min_(src.min_), max_(src.max_),
  43         scale_(src.scale_), val_in(src.val_in), val_out(src.val_out)
  44 {
  45     if (src.bins!=NULL) {
  46         bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type)));
  47         memcpy(bins,src.bins,capacity_*sizeof(*bins));
  48     }
  49 }
  50
  51 void
  52 StatHist::count(double v)
  53 {
  54     if (bins==NULL) //do not count before initialization or after destruction
  55         return;
  56     const unsigned int bin = findBin(v);
  57     ++bins[bin];
  58 }
  59
  60 unsigned int
  61 StatHist::findBin(double v)
  62 {
  63
  64     v -= min_;          /* offset */
  65
  66     if (v <= 0.0)               /* too small */
  67         return 0;
  68
  69     unsigned int bin;
  70     double tmp_bin=floor(scale_ * val_in(v) + 0.5);
  71
  72     if (tmp_bin < 0.0) // should not happen
  73         return 0;
  74     bin = static_cast <unsigned int>(tmp_bin);
  75
  76     if (bin >= capacity_)       /* too big */
  77         bin = capacity_ - 1;
  78
  79     return bin;
  80 }
  81
  82 double
  83 StatHist::val(unsigned int bin) const
  84 {
  85     return val_out((double) bin / scale_) + min_;
  86 }
  87
  88 double
  89 statHistDeltaMedian(const StatHist & A, const StatHist & B)
  90 {
  91     return statHistDeltaPctile(A, B, 0.5);
  92 }
  93
  94 double
  95 statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile)
  96 {
  97     return A.deltaPctile(B, pctile);
  98 }
  99
 100 double
 101 StatHist::deltaPctile(const StatHist & B, double pctile) const
 102 {
 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;
 111     double f;
 112
 113     assert(capacity_ == B.capacity_);
 114
 115     int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int)));
 116
 117     for (i = 0; i < capacity_; ++i) {
 118         D[i] = B.bins[i] - bins[i];
 119         assert(D[i] >= 0);
 120     }
 121
 122     for (i = 0; i < capacity_; ++i)
 123         s1 += D[i];
 124
 125     h = int(s1 * pctile);
 126
 127     for (i = 0; i < capacity_; ++i) {
 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];
 137     }
 138
 139     xfree(D);
 140
 141     if (s1 == 0)
 142         return 0.0;
 143
 144     if (a > h)
 145         return 0.0;
 146
 147     if (a >= b)
 148         return 0.0;
 149
 150     if (I >= J)
 151         return 0.0;
 152
 153     f = (h - a) / (b - a);
 154
 155     K = (unsigned int) floor(f * (double) (J - I) + I);
 156
 157     return val(K);
 158 }
 159
 160 static void
 161 statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 162 {
 163     if (count)
 164         storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
 165                           idx, val, count, count / size);
 166 }
 167
 168 void
 169 StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const
 170 {
 171     double left_border = min_;
 172
 173     if (!bd)
 174         bd = statHistBinDumper;
 175
 176     for (unsigned int i = 0; i < capacity_; ++i) {
 177         const double right_border = val(i + 1);
 178         assert(right_border - left_border > 0.0);
 179         bd(sentry, i, left_border, right_border - left_border, bins[i]);
 180         left_border = right_border;
 181     }
 182 }
 183
 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
 204 /* log based histogram */
 205 double
 206 Math::Log(double x)
 207 {
 208     assert((x + 1.0) >= 0.0);
 209     return log(x + 1.0);
 210 }
 211
 212 double
 213 Math::Exp(double x)
 214 {
 215     return exp(x) - 1.0;
 216 }
 217
 218 void
 219 StatHist::logInit(unsigned int capacity, double min, double max)
 220 {
 221     init(capacity, Math::Log, Math::Exp, min, max);
 222 }
 223
 224 /* linear histogram for enums */
 225 /* we want to be have [-1,last_enum+1] range to track out of range enums */
 226 double
 227 Math::Null(double x)
 228 {
 229     return x;
 230 }
 231
 232 void
 233 StatHist::enumInit(unsigned int last_enum)
 234 {
 235     init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum));
 236 }
 237
 238 void
 239 statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 240 {
 241     if (count)
 242         storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
 243                           idx, (int) val, count);
 244 }
 245
 246 void
 247 statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 248 {
 249     if (count)
 250         storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
 251 }