common/src/hist.C

   1 /*
   2  * Copyright (c) 1992 Barton P. Miller, Morgan Clark, Timothy Torzewski,
   3  *     Jeff Hollingsworth, and Bruce Irvin. All rights reserved.
   4  *
   5  * This software is furnished under the condition that it may not
   6  * be provided or otherwise made available to, or used by, any
   7  * other person.  No title to or ownership of the software is
   8  * hereby transferred.  The name of the principals
   9  * may not be used in any advertising or publicity related to this
  10  * software without specific, written prior authorization.
  11  * Any use of this software must include the above copyright notice.
  12  *
  13  */
  14
  15 /*
  16  * hist.C - routines to manage hisograms.
  17  *
  18  * $Log: hist.C,v $
  19  * Revision 1.4  1994/02/10 23:08:26  hollings
  20  * Fixed list.h ++ function to work when a hash table has an element at
  21  * slot zero in the table.
  22  *
  23  * Removed unused fields in hist class.
  24  *
  25  * Revision 1.3  1994/02/08  00:30:39  hollings
  26  * Make libutil more compatable with ATT CC.
  27  *
  28  * Revision 1.2  1994/01/26  04:53:42  hollings
  29  * Change to using <module>/h/*.h
  30  *
  31  * Revision 1.1  1994/01/25  20:50:25  hollings
  32  * First real version of utility library.
  33  *
  34  * Revision 1.4  1993/12/15  21:06:23  hollings
  35  * changed initial bucket width to 0.1.
  36  *
  37  * Revision 1.3  1993/08/11  18:03:54  hollings
  38  * removed printf for folding hist.
  39  *
  40  * Revision 1.2  1993/08/05  18:55:08  hollings
  41  * general fixups and include format.
  42  *
  43  * Revision 1.1  1993/05/07  20:19:17  hollings
  44  * Initial revision
  45  *
  46  *
  47  */
  48
  49 #include <stdio.h>
  50 #include <assert.h>
  51 #include <string.h>
  52 #include <stdlib.h>
  53
  54 #include "util/h/hist.h"
  55
  56 /* number of intervals at which we switch to regular histograms */
  57 #define MAX_INTERVALS   15
  58
  59 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
  60
  61 int Histogram::numBins = 1000;
  62 timeStamp Histogram::bucketSize = 0.1;
  63 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
  64 Histogram *Histogram::allHist = NULL;
  65 int Histogram::lastGlobalBin = 0;
  66
  67 Histogram::Histogram(metricStyle type)
  68 {
  69     smooth = False;
  70     lastBin = 0;
  71     metricType = type;
  72     intervalCount = 0;
  73     intervalLimit = MAX_INTERVALS;
  74     storageType = HistInterval;
  75     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
  76     next = allHist;
  77     allHist = this;
  78 }
  79
  80 /*
  81  * Given an array of buckets - turn them into a histogram.
  82  *
  83  */
  84 Histogram::Histogram(Bin *buckets, metricStyle type)
  85 {
  86     // First call default constructor.
  87     (void) Histogram(type);
  88
  89     storageType = HistBucket;
  90     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
  91     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
  92 }
  93
  94 #define MAX(a, b)       ((a) > (b) ? (a):(b))
  95
  96 /*
  97  * addInterval - add a value to a histogram from start to end.
  98  *
  99  * start, and end are relative to the global start time (i.e. 0.0 is the
 100  *   left side of the first hist bin).
 101  */
 102 void Histogram::addInterval(timeStamp start,
 103                             timeStamp end,
 104                             sampleValue value,
 105                             Boolean smooth)
 106 {
 107     Histogram *h;
 108     List<HistogramSubscriber*> currS;
 109     Interval *currentInterval;
 110
 111
 112     while ((end >= total_time) || (start >= total_time)) {
 113         // colapse histogram.
 114         foldAllHist();
 115     }
 116
 117     lastBin = (int) (end / bucketSize);
 118     lastGlobalBin = lastBin;
 119     for (h=allHist; h; h=h->next) {
 120         if ((h->lastBin < lastGlobalBin)) {
 121             lastGlobalBin = h->lastBin;
 122         }
 123     }
 124
 125     if (value == 0.0) return;
 126
 127     if (storageType == HistInterval) {
 128         if (intervalCount == intervalLimit) {
 129             intervalLimit *= 2;
 130             if (intervalLimit * sizeof(Interval) <
 131                 numBins * sizeof(Bin)) {
 132                 dataPtr.intervals = (Interval *)
 133                     realloc(dataPtr.intervals,
 134                     sizeof(Interval)*intervalLimit);
 135                     goto normal;
 136             } else {
 137                 /* convert to buckets */
 138                 convertToBins();
 139                 bucketValue(start, end, value, smooth);
 140             }
 141         } else {
 142 normal:
 143             currentInterval = &(dataPtr.intervals[intervalCount]);
 144             assert(start >= 0.0);
 145             assert(start <= total_time);
 146             currentInterval->start = start;
 147
 148             assert(end >= 0.0);
 149             assert(end <= total_time);
 150             currentInterval->end = end;
 151
 152             currentInterval->value = value;
 153             intervalCount++;
 154         }
 155     } else {
 156         bucketValue(start, end, value, smooth);
 157     }
 158     for (currS = subscribers; *currS; currS++) {
 159         (*currS)->callBack(HistNewValue, end, (*currS)->userData);
 160     }
 161 }
 162
 163 void Histogram::convertToBins()
 164 {
 165     int i;
 166     Interval *intervals;
 167     Interval *currentInterval;
 168
 169     if (storageType == HistBucket) return;
 170
 171     intervals = dataPtr.intervals;
 172     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 173     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
 174     for (i=0; i < intervalCount; i++) {
 175         currentInterval = &(intervals[i]);
 176         bucketValue(currentInterval->start, currentInterval->end,
 177             currentInterval->value, smooth);
 178     }
 179     free(intervals);
 180     intervalCount = -1;
 181     intervalLimit = 0;
 182     storageType = HistBucket;
 183 }
 184
 185 void Histogram::foldAllHist()
 186 {
 187     int i;
 188     Bin *bins;
 189     Histogram *curr;
 190     List<HistogramSubscriber*> currS;
 191
 192
 193     bucketSize *= 2.0;
 194     total_time = (numBins * bucketSize);
 195
 196     lastGlobalBin = 0;
 197     for (curr=allHist; curr; curr= curr->next) {
 198         // fold individual hist.
 199         if (curr->storageType == HistBucket) {
 200             bins = curr->dataPtr.buckets;
 201             for (i=0; i < numBins/2; i++) {
 202                 bins[i] = bins[i*2] + bins[i*2+1];
 203             }
 204             curr->lastBin = i-1;
 205             memset(&bins[i], '\0', (numBins - i) * sizeof(Bin));
 206         }
 207         for (currS = curr->subscribers; *currS; currS++) {
 208             (*currS)->callBack(HistNewTimeBase, bucketSize, (*currS)->userData);
 209         }
 210     }
 211 }
 212
 213 int Histogram::subscribe(timeStamp maxRate,
 214                            subscriberCallBack func,
 215                            void *userData)
 216 {
 217     HistogramSubscriber *curr;
 218
 219     curr = new HistogramSubscriber(maxRate, func, userData);
 220     subscribers.add(curr);
 221     return((int) curr);
 222 }
 223
 224 void Histogram::bucketValue(timeStamp start_clock,
 225                            timeStamp end_clock,
 226                            sampleValue value,
 227                            Boolean smooth)
 228 {
 229     register int i;
 230     int first_bin, last_bin;
 231     timeStamp elapsed_clock = (timeStamp) 0.0;
 232     timeStamp first_bin_start, last_bin_start;
 233     sampleValue amt_first_bin, amt_last_bin, amt_other_bins;
 234     timeStamp time_in_first_bin, time_in_last_bin, time_in_other_bins;
 235
 236
 237     elapsed_clock = end_clock - start_clock;
 238
 239     /* set starting and ending bins */
 240     first_bin = (int) (start_clock / bucketSize);
 241     assert(first_bin >= 0);
 242     assert(first_bin <= numBins);
 243     if (first_bin == numBins)
 244         first_bin = numBins-1;
 245     last_bin = (int) (end_clock / bucketSize);
 246     assert(last_bin >= 0);
 247     assert(last_bin <= numBins);
 248     if (last_bin == numBins)
 249         last_bin = numBins-1;
 250     /* set starting times for first & last bins */
 251     first_bin_start = bucketSize * first_bin;
 252     last_bin_start = bucketSize  * last_bin;
 253
 254     if (metricType == SampledFunction) {
 255         for (i=first_bin; i <= last_bin; i++) {
 256             dataPtr.buckets[i] = value * bucketSize;
 257         }
 258     } else {
 259         if (last_bin == first_bin) {
 260             dataPtr.buckets[first_bin] += value;
 261             if (smooth && (dataPtr.buckets[first_bin] > bucketSize)) {
 262                 /* value > 100% */
 263                 smoothBins(dataPtr.buckets, first_bin, bucketSize);
 264             }
 265             return;
 266         }
 267
 268         /* determine how much of the first & last bins were in this interval */
 269         time_in_first_bin = bucketSize - (start_clock - first_bin_start);
 270         time_in_last_bin = end_clock - last_bin_start;
 271         time_in_other_bins =
 272             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
 273
 274         /* determine how much of value should be in each bin in the interval */
 275         amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
 276         amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
 277         amt_other_bins = (time_in_other_bins / elapsed_clock) * value;
 278         if (last_bin > first_bin+1)
 279             amt_other_bins /= (last_bin - first_bin) - 1.0;
 280
 281         /* add the appropriate amount of time to each bin */
 282         dataPtr.buckets[first_bin] += amt_first_bin;
 283         dataPtr.buckets[last_bin]  += amt_last_bin;
 284         for (i=first_bin+1; i < last_bin; i++)
 285             dataPtr.buckets[i]  += amt_other_bins;
 286     }
 287
 288     /* limit absurd time values - anything over 100% is pushed back into
 289        previous buckets */
 290     if (smooth) {
 291         for (i = first_bin; i <= last_bin; i++) {
 292             if (dataPtr.buckets[i] > bucketSize)
 293                 smoothBins(dataPtr.buckets, i, bucketSize);
 294         }
 295     }
 296 }
 297
 298
 299 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
 300 {
 301     int j;
 302     sampleValue extra_time;
 303
 304     extra_time = (bins[i] - bucketSize);
 305     bins[i] = bucketSize;
 306     j = i - 1;
 307     while ((j >= 0) && (extra_time > 0.0)) {
 308         bins[j] += extra_time;
 309         extra_time = 0.0;
 310         if (bins[j] > bucketSize) {
 311             extra_time = (bins[j] - bucketSize);
 312             bins[j] = bucketSize;
 313         }
 314         j--;
 315     }
 316     if (extra_time > 0.0) {
 317         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
 318         abort();
 319     }
 320 }
 321
 322
 323 static double splitTime(timeStamp startInterval,
 324                         timeStamp endInterval,
 325                         timeStamp startLimit,
 326                         timeStamp endLimit,
 327                         sampleValue value)
 328 {
 329     sampleValue time;
 330     timeStamp inv_length;
 331
 332     inv_length = endInterval-startInterval;
 333     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {
 334         time = value;
 335     } else if (startInterval == endInterval) {
 336         /* can't split delta functions */
 337         time = 0.0;
 338     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
 339         /* overlaps the end */
 340         time = value * (endLimit - startInterval) / inv_length;
 341     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) {
 342         /* overlaps the end */
 343         time = value * (endInterval - startLimit) / inv_length;
 344     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
 345         /* detail contains interval */
 346         time = value * (endLimit - startLimit) / inv_length;
 347     } else {
 348         /* no overlap of time */
 349         time = 0.0;
 350     }
 351     return(time);
 352 }
 353
 354 /*
 355  * Get the component of the histogram from start to end.
 356  *
 357  */
 358 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
 359 {
 360     int i;
 361     Interval *cp;
 362     sampleValue retVal = 0.0;
 363     int first_bin, last_bin;
 364     double pct_first_bin, pct_last_bin;
 365
 366     if (storageType == HistInterval) {
 367         if (metricType == SampledFunction) {
 368             // compute weight average of sample.
 369             for (i=0; i < intervalCount; i++) {
 370                 cp = &(dataPtr.intervals[i]);
 371                 retVal += cp->value * (cp->end - cp->start);
 372             }
 373         } else {
 374             // total over the interval.
 375             for (i=0; i < intervalCount; i++) {
 376                 cp = &(dataPtr.intervals[i]);
 377                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
 378             }
 379         }
 380     } else {
 381         first_bin = (int) (start/bucketSize);
 382         /* round up */
 383         last_bin = (int) (end/bucketSize+0.5);
 384         if (last_bin >= numBins) last_bin = numBins-1;
 385         if (first_bin == last_bin) {
 386             retVal = dataPtr.buckets[first_bin];
 387         } else {
 388             /* (first_bin+1)*bucketSize == time at end of first bucket */
 389             pct_first_bin = (((first_bin+1)*bucketSize)-start)/bucketSize;
 390             retVal += pct_first_bin * dataPtr.buckets[first_bin];
 391             /* last_bin+*bucketSize == time at start of last bucket */
 392             pct_last_bin = (end - last_bin*bucketSize)/bucketSize;
 393             retVal += pct_last_bin * dataPtr.buckets[last_bin];
 394             for (i=first_bin+1; i <= last_bin-1; i++) {
 395                 retVal += dataPtr.buckets[i];
 396             }
 397         }
 398     }
 399     return(retVal);
 400 }
 401
 402 sampleValue Histogram::getValue()
 403 {
 404     return(getValue(0.0, numBins * bucketSize));
 405 }
 406
 407 HistogramSubscriber::HistogramSubscriber(timeStamp max,
 408                                          subscriberCallBack func,
 409                                          void *u)
 410 {
 411     interval = max;
 412     userData = u;
 413     callBack = func;
 414 }