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 "squid.h"
  35 #include "StatHist.h"
  36
  37 #if HAVE_MATH_H
  38 #include <math.h>
  39 #endif
  40 /* Local functions */
  41 static StatHistBinDumper statHistBinDumper;
  42
  43 namespace Math
  44 {
  45 hbase_f Log;
  46 hbase_f Exp;
  47 hbase_f Null;
  48 };
  49
  50 /* low level init, higher level functions has less params */
  51 void
  52 StatHist::init(unsigned int newCapacity, hbase_f * val_in_, hbase_f * val_out_, double newMin, double newMax)
  53 {
  54     /* check before we divide to get scale_ */
  55     assert(val_in_(newMax - newMin) > 0);
  56     min_ = newMin;
  57     max_ = newMax;
  58     capacity_ = newCapacity;
  59     val_in = val_in_;
  60     val_out = val_out_;
  61     bins = static_cast<bins_type *>(xcalloc(capacity_, sizeof(bins_type)));
  62     scale_ = capacity_ / val_in(max_ - min_);
  63 }
  64
  65 StatHist::StatHist(const StatHist &src) :
  66         capacity_(src.capacity_), min_(src.min_), max_(src.max_),
  67         scale_(src.scale_), val_in(src.val_in), val_out(src.val_out)
  68 {
  69     if (src.bins!=NULL) {
  70         bins = static_cast<bins_type *>(xcalloc(src.capacity_, sizeof(bins_type)));
  71         memcpy(bins,src.bins,capacity_*sizeof(*bins));
  72     }
  73 }
  74
  75 void
  76 StatHist::count(double v)
  77 {
  78     if (bins==NULL) //do not count before initialization or after destruction
  79         return;
  80     const unsigned int bin = findBin(v);
  81     ++bins[bin];
  82 }
  83
  84 unsigned int
  85 StatHist::findBin(double v)
  86 {
  87
  88     v -= min_;          /* offset */
  89
  90     if (v <= 0.0)               /* too small */
  91         return 0;
  92
  93     unsigned int bin;
  94     double tmp_bin=floor(scale_ * val_in(v) + 0.5);
  95
  96     if (tmp_bin < 0.0) // should not happen
  97         return 0;
  98     bin = static_cast <unsigned int>(tmp_bin);
  99
 100     if (bin >= capacity_)       /* too big */
 101         bin = capacity_ - 1;
 102
 103     return bin;
 104 }
 105
 106 double
 107 StatHist::val(unsigned int bin) const
 108 {
 109     return val_out((double) bin / scale_) + min_;
 110 }
 111
 112 double
 113 statHistDeltaMedian(const StatHist & A, const StatHist & B)
 114 {
 115     return statHistDeltaPctile(A, B, 0.5);
 116 }
 117
 118 double
 119 statHistDeltaPctile(const StatHist & A, const StatHist & B, double pctile)
 120 {
 121     return A.deltaPctile(B, pctile);
 122 }
 123
 124 double
 125 StatHist::deltaPctile(const StatHist & B, double pctile) const
 126 {
 127     unsigned int i;
 128     bins_type s1 = 0;
 129     bins_type h = 0;
 130     bins_type a = 0;
 131     bins_type b = 0;
 132     unsigned int I = 0;
 133     unsigned int J = capacity_;
 134     unsigned int K;
 135     double f;
 136
 137     assert(capacity_ == B.capacity_);
 138
 139     int *D = static_cast<int *>(xcalloc(capacity_, sizeof(int)));
 140
 141     for (i = 0; i < capacity_; ++i) {
 142         D[i] = B.bins[i] - bins[i];
 143         assert(D[i] >= 0);
 144     }
 145
 146     for (i = 0; i < capacity_; ++i)
 147         s1 += D[i];
 148
 149     h = int(s1 * pctile);
 150
 151     for (i = 0; i < capacity_; ++i) {
 152         J = i;
 153         b += D[J];
 154
 155         if (a <= h && h <= b)
 156             break;
 157
 158         I = i;
 159
 160         a += D[I];
 161     }
 162
 163     xfree(D);
 164
 165     if (s1 == 0)
 166         return 0.0;
 167
 168     if (a > h)
 169         return 0.0;
 170
 171     if (a >= b)
 172         return 0.0;
 173
 174     if (I >= J)
 175         return 0.0;
 176
 177     f = (h - a) / (b - a);
 178
 179     K = (unsigned int) floor(f * (double) (J - I) + I);
 180
 181     return val(K);
 182 }
 183
 184 static void
 185 statHistBinDumper(StoreEntry * sentry, int idx, double val, double size, int count)
 186 {
 187     if (count)
 188         storeAppendPrintf(sentry, "\t%3d/%f\t%d\t%f\n",
 189                           idx, val, count, count / size);
 190 }
 191
 192 void
 193 StatHist::dump(StoreEntry * sentry, StatHistBinDumper * bd) const
 194 {
 195     double left_border = min_;
 196
 197     if (!bd)
 198         bd = statHistBinDumper;
 199
 200     for (unsigned int i = 0; i < capacity_; ++i) {
 201         const double right_border = val(i + 1);
 202         assert(right_border - left_border > 0.0);
 203         bd(sentry, i, left_border, right_border - left_border, bins[i]);
 204         left_border = right_border;
 205     }
 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 size, 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 idx, double val, double size, int count)
 252 {
 253     if (count)
 254         storeAppendPrintf(sentry, "%9d\t%9d\n", (int) val, count);
 255 }