src/StatHist.cc

   1
   2 /*
   3  * DEBUG: section 62    Generic Histogram
   4  * AUTHOR: Duane Wessels
   5  *
   6  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   7  * ----------------------------------------------------------
   8  *
   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.
  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.
  22  *
  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.
  27  *
  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
  30  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  31  *
  32  */
  33
  34 #include "config.h"
  35 #include "StatHist.h"
  36
  37 /* Local functions */
  38 static StatHistBinDumper statHistBinDumper;
  39
  40 namespace Math
  41 {
  42 hbase_f Log;
  43 hbase_f Exp;
  44 hbase_f Null;
  45 };
  46
  47 /* low level init, higher level functions has less params */
  48 void
  49 StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax)
  50 {
  51     /* check before we divide to get scale_ */
  52     assert(val_in_(newMax - newMin) > 0);
  53     min_ = newMin;
  54     max_ = newMax;
  55     capacity_ = newCapacity;
  56     val_in = val_in_;
  57     val_out = val_out_;
  58     bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type)));
  59     scale_ = capacity_ / val_in(max_ - min_);
  60 }
  61
  62 void
  63 StatHist::clear()
  64 {
  65     for (unsigned int i=0; i<capacity_; ++i)
  66         bins[i]=0;
  67 }
  68
  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 {
  73     if (src.bins!=NULL) {
  74         bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(int)));
  75         memcpy(bins,src.bins,capacity_*sizeof(*bins));
  76     }
  77 }
  78
  79 void
  80 StatHist::count(double val)
  81 {
  82     if (bins==NULL) //do not count before initialization or after destruction
  83         return;
  84     const unsigned int bin = findBin(val);
  85     ++bins[bin];
  86 }
  87
  88 unsigned int
  89 StatHist::findBin(double v)
  90 {
  91
  92     v -= min_;          /* offset */
  93
  94     if (v <= 0.0)               /* too small */
  95         return 0;
  96
  97     unsigned int bin;
  98     double tmp_bin=floor(scale_ * val_in(v) + 0.5);
  99
 100     if (tmp_bin < 0.0) // should not happen
 101         return 0;
 102     bin = static_cast <unsigned int>(tmp_bin);
 103
 104     if (bin >= capacity_)       /* too big */
 105         bin = capacity_ - 1;
 106
 107     return bin;
 108 }
 109
 110 double
 111 StatHist::val(unsigned int bin) const
 112 {
 113     return val_out((double) bin / scale_) + min_;
 114 }
 115
 116 double
 117 statHistDeltaMedian(const StatHist & A, const StatHist & B)
 118 {
 119     return statHistDeltaPctile(A, B, 0.5);
 120 }
 121
 122 double
 123 statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile)
 124 {
 125     return A.deltaPctile(B, pctile);
 126 }
 127
 128 double
 129 StatHist::deltaPctile(const StatHist & B, double pctile) const
 130 {
 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;
 139     double f;
 140
 141     assert(capacity_ == B.capacity_);
 142
 143     int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int)));
 144
 145     for (i = 0; i < capacity_; ++i) {
 146         D[i] = B.bins[i] - bins[i];
 147         assert(D[i] >= 0);
 148     }
 149
 150     for (i = 0; i < capacity_; ++i)
 151         s1 += D[i];
 152
 153     h = int(s1 * pctile);
 154
 155     for (i = 0; i < capacity_; ++i) {
 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];
 165     }
 166
 167     xfree(D);
 168
 169     if (s1 == 0)
 170         return 0.0;
 171
 172     if (a > h)
 173         return 0.0;
 174
 175     if (a >= b)
 176         return 0.0;
 177
 178     if (I >= J)
 179         return 0.0;
 180
 181     f = (h - a) / (b - a);
 182
 183     K = (unsigned int) floor(f * (double) (J - I) + I);
 184
 185     return val(K);
 186 }
 187
 188 static void
 189 statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 190 {
 191     if (count)
 192         storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
 193                           idx, val, count, count / size);
 194 }
 195
 196 void
 197 StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const
 198 {
 199     double left_border = min_;
 200
 201     if (!bd)
 202         bd = statHistBinDumper;
 203
 204     for (unsigned int i = 0; i < capacity_; ++i) {
 205         const double right_border = val(i + 1);
 206         assert(right_border - left_border > 0.0);
 207         bd(sentry, i, left_border, right_border - left_border, bins[i]);
 208         left_border = right_border;
 209     }
 210 }
 211
 212 /* log based histogram */
 213 double
 214 Math::Log(double x)
 215 {
 216     assert((x + 1.0) >= 0.0);
 217     return log(x + 1.0);
 218 }
 219
 220 double
 221 Math::Exp(double x)
 222 {
 223     return exp(x) - 1.0;
 224 }
 225
 226 void
 227 StatHist::logInit(unsigned int capacity, double min, double max)
 228 {
 229     init(capacity, Math::Log, Math::Exp, min, max);
 230 }
 231
 232 /* linear histogram for enums */
 233 /* we want to be have [-1,last_enum+1] range to track out of range enums */
 234 double
 235 Math::Null(double x)
 236 {
 237     return x;
 238 }
 239
 240 void
 241 StatHist::enumInit(unsigned int last_enum)
 242 {
 243     init(last_enum + 3, Math::Null, Math::Null, -1.0, (2.0 + last_enum));
 244 }
 245
 246 void
 247 statHistEnumDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 248 {
 249     if (count)
 250         storeAppendPrintf(sentry, "%2d\t %5d\t %5d\n",
 251                           idx, (int) val, count);
 252 }
 253
 254 void
 255 statHistIntDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 256 {
 257     if (count)
 258         storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
 259 }