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.10  1994/06/29 02:48:31  hollings
  20  * Added destructor to Histogram class.
  21  *
  22  * Revision 1.9  1994/05/10  03:56:47  hollings
  23  * Changed hist data upcall to return array of buckets not single value.
  24  *
  25  * Revision 1.8  1994/04/30  21:00:03  hollings
  26  * Fixed bug in fold callback that caused all fold message to go to the
  27  * Histogram that caused the fold not the correct ones.
  28  *
  29  * Revision 1.7  1994/04/20  15:19:30  hollings
  30  * Added method to get histogram buckets.
  31  *
  32  * Revision 1.6  1994/04/12  22:11:22  hollings
  33  * removed special case of bucket a zero value since it caused upcalls not to
  34  * happen.
  35  *
  36  * Revision 1.5  1994/03/08  17:12:29  hollings
  37  * Added fold callback and changed from multiple data callbacks to one per
  38  * histogram instance.  Also made the data callbacks happen once per bucket.
  39  *
  40  * Revision 1.4  1994/02/10  23:08:26  hollings
  41  * Fixed list.h ++ function to work when a hash table has an element at
  42  * slot zero in the table.
  43  *
  44  * Removed unused fields in hist class.
  45  *
  46  * Revision 1.3  1994/02/08  00:30:39  hollings
  47  * Make libutil more compatable with ATT CC.
  48  *
  49  * Revision 1.2  1994/01/26  04:53:42  hollings
  50  * Change to using <module>/h/.h
  51  *
  52  * Revision 1.1  1994/01/25  20:50:25  hollings
  53  * First real version of utility library.
  54  *
  55  * Revision 1.4  1993/12/15  21:06:23  hollings
  56  * changed initial bucket width to 0.1.
  57  *
  58  * Revision 1.3  1993/08/11  18:03:54  hollings
  59  * removed printf for folding hist.
  60  *
  61  * Revision 1.2  1993/08/05  18:55:08  hollings
  62  * general fixups and include format.
  63  *
  64  * Revision 1.1  1993/05/07  20:19:17  hollings
  65  * Initial revision
  66  *
  67  *
  68  */
  69
  70 #include <stdio.h>
  71 #include <assert.h>
  72 #include <string.h>
  73 #include <stdlib.h>
  74
  75 #include "util/h/hist.h"
  76
  77 /* number of intervals at which we switch to regular histograms */
  78 #define MAX_INTERVALS   15
  79
  80 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
  81
  82 int Histogram::numBins = 1000;
  83 timeStamp Histogram::bucketSize = 0.1;
  84 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
  85 Histogram *Histogram::allHist = NULL;
  86 int Histogram::lastGlobalBin = 0;
  87
  88 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c)
  89 {
  90     smooth = False;
  91     lastBin = 0;
  92     metricType = type;
  93     intervalCount = 0;
  94     intervalLimit = MAX_INTERVALS;
  95     storageType = HistInterval;
  96     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
  97     next = allHist;
  98     allHist = this;
  99     dataFunc = d;
 100     foldFunc = f;
 101     cData = c;
 102 }
 103
 104 /*
 105  * Given an array of buckets - turn them into a histogram.
 106  *
 107  */
 108 Histogram::Histogram(Bin *buckets,
 109                      metricStyle type,
 110                      dataCallBack d,
 111                      foldCallBack f,
 112                      void *c)
 113 {
 114     // First call default constructor.
 115     (void) Histogram(type, d, f, c);
 116
 117     storageType = HistBucket;
 118     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 119     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
 120 }
 121
 122 Histogram::~Histogram()
 123 {
 124     Histogram *lag;
 125     Histogram *curr;
 126
 127     // remove us from allHist
 128     for (curr=allHist, lag=NULL; curr; curr = curr->next) {
 129         if (curr == this) {
 130             break;
 131         }
 132         lag = curr;
 133     }
 134
 135     if (!lag) {
 136         allHist = curr->next;
 137     } else {
 138         lag->next = curr->next;
 139     }
 140
 141 }
 142
 143 #define MAX(a, b)       ((a) > (b) ? (a):(b))
 144
 145 /*
 146  * addInterval - add a value to a histogram from start to end.
 147  *
 148  * start, and end are relative to the global start time (i.e. 0.0 is the
 149  *   left side of the first hist bin).
 150  */
 151 void Histogram::addInterval(timeStamp start,
 152                             timeStamp end,
 153                             sampleValue value,
 154                             Boolean smooth)
 155 {
 156     Histogram *h;
 157
 158     while ((end >= total_time) || (start >= total_time)) {
 159         // colapse histogram.
 160         foldAllHist();
 161     }
 162
 163     lastBin = (int) (end / bucketSize);
 164     lastGlobalBin = lastBin;
 165     for (h=allHist; h; h=h->next) {
 166         if ((h->lastBin < lastGlobalBin)) {
 167             lastGlobalBin = h->lastBin;
 168         }
 169     }
 170
 171     if (storageType == HistInterval) {
 172         /* convert to buckets */
 173         convertToBins();
 174     }
 175     bucketValue(start, end, value, smooth);
 176 }
 177
 178 void Histogram::convertToBins()
 179 {
 180     int i;
 181     Interval *intervals;
 182     Interval *currentInterval;
 183
 184     if (storageType == HistBucket) return;
 185
 186     intervals = dataPtr.intervals;
 187     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 188     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
 189     for (i=0; i < intervalCount; i++) {
 190         currentInterval = &(intervals[i]);
 191         bucketValue(currentInterval->start, currentInterval->end,
 192             currentInterval->value, smooth);
 193     }
 194     free(intervals);
 195     intervalCount = -1;
 196     intervalLimit = 0;
 197     storageType = HistBucket;
 198 }
 199
 200 void Histogram::foldAllHist()
 201 {
 202     int i;
 203     Bin *bins;
 204     Histogram *curr;
 205
 206     bucketSize *= 2.0;
 207     total_time = (numBins * bucketSize);
 208
 209     lastGlobalBin = 0;
 210     for (curr=allHist; curr; curr= curr->next) {
 211         // fold individual hist.
 212         if (curr->storageType == HistBucket) {
 213             bins = curr->dataPtr.buckets;
 214             for (i=0; i < numBins/2; i++) {
 215                 bins[i] = (bins[i*2] + bins[i*2+1]) / 2.0;
 216             }
 217             curr->lastBin = i-1;
 218             memset(&bins[i], '\0', (numBins - i) * sizeof(Bin));
 219         }
 220         if (curr->foldFunc) (curr->foldFunc)(bucketSize, curr->cData);
 221     }
 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;
 257         }
 258     } else {
 259         // normalize by bucket size.
 260         value /= bucketSize;
 261         if (last_bin == first_bin) {
 262             dataPtr.buckets[first_bin] += value;
 263             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
 264                 /* value > 100% */
 265                 smoothBins(dataPtr.buckets, first_bin, bucketSize);
 266             }
 267             return;
 268         }
 269
 270         /* determine how much of the first & last bins were in this interval */
 271         time_in_first_bin = bucketSize - (start_clock - first_bin_start);
 272         time_in_last_bin = end_clock - last_bin_start;
 273         time_in_other_bins =
 274             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
 275
 276         /* determine how much of value should be in each bin in the interval */
 277         amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
 278         amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
 279         amt_other_bins = (time_in_other_bins / elapsed_clock) * value;
 280         if (last_bin > first_bin+1)
 281             amt_other_bins /= (last_bin - first_bin) - 1.0;
 282
 283         /* add the appropriate amount of time to each bin */
 284         dataPtr.buckets[first_bin] += amt_first_bin;
 285         dataPtr.buckets[last_bin]  += amt_last_bin;
 286         for (i=first_bin+1; i < last_bin; i++)
 287             dataPtr.buckets[i]  += amt_other_bins;
 288     }
 289
 290     /* limit absurd time values - anything over 100% is pushed back into
 291        previous buckets */
 292     if (smooth) {
 293         for (i = first_bin; i <= last_bin; i++) {
 294             if (dataPtr.buckets[i] > bucketSize)
 295                 smoothBins(dataPtr.buckets, i, bucketSize);
 296         }
 297     }
 298
 299     // inform users about the data.
 300     // make sure they want to hear about it (dataFunc)
 301     //  && that we have a full bin (last_bin>first_bin)
 302     if (dataFunc && (last_bin-first_bin)) {
 303         (dataFunc)(&dataPtr.buckets[first_bin],
 304                    last_bin-first_bin,
 305                    first_bin,
 306                    cData);
 307     }
 308 }
 309
 310
 311 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
 312 {
 313     int j;
 314     sampleValue extra_time;
 315
 316     extra_time = (bins[i] - bucketSize);
 317     bins[i] = bucketSize;
 318     j = i - 1;
 319     while ((j >= 0) && (extra_time > 0.0)) {
 320         bins[j] += extra_time;
 321         extra_time = 0.0;
 322         if (bins[j] > bucketSize) {
 323             extra_time = (bins[j] - bucketSize);
 324             bins[j] = bucketSize;
 325         }
 326         j--;
 327     }
 328     if (extra_time > 0.0) {
 329         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
 330         abort();
 331     }
 332 }
 333
 334
 335 static double splitTime(timeStamp startInterval,
 336                         timeStamp endInterval,
 337                         timeStamp startLimit,
 338                         timeStamp endLimit,
 339                         sampleValue value)
 340 {
 341     sampleValue time;
 342     timeStamp inv_length;
 343
 344     inv_length = endInterval-startInterval;
 345     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {
 346         time = value;
 347     } else if (startInterval == endInterval) {
 348         /* can't split delta functions */
 349         time = 0.0;
 350     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
 351         /* overlaps the end */
 352         time = value * (endLimit - startInterval) / inv_length;
 353     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) {
 354         /* overlaps the end */
 355         time = value * (endInterval - startLimit) / inv_length;
 356     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
 357         /* detail contains interval */
 358         time = value * (endLimit - startLimit) / inv_length;
 359     } else {
 360         /* no overlap of time */
 361         time = 0.0;
 362     }
 363     return(time);
 364 }
 365
 366 /*
 367  * Get the component of the histogram from start to end.
 368  *
 369  */
 370 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
 371 {
 372     int i;
 373     Interval *cp;
 374     sampleValue retVal = 0.0;
 375     int first_bin, last_bin;
 376     double pct_first_bin, pct_last_bin;
 377
 378     if (storageType == HistInterval) {
 379         if (metricType == SampledFunction) {
 380             // compute weight average of sample.
 381             for (i=0; i < intervalCount; i++) {
 382                 cp = &(dataPtr.intervals[i]);
 383                 retVal += cp->value * (cp->end - cp->start);
 384             }
 385         } else {
 386             // total over the interval.
 387             for (i=0; i < intervalCount; i++) {
 388                 cp = &(dataPtr.intervals[i]);
 389                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
 390             }
 391         }
 392     } else {
 393         first_bin = (int) (start/bucketSize);
 394         /* round up */
 395         last_bin = (int) (end/bucketSize+0.5);
 396         if (last_bin >= numBins) last_bin = numBins-1;
 397         if (first_bin == last_bin) {
 398             retVal = dataPtr.buckets[first_bin];
 399         } else {
 400             /* (first_bin+1)*bucketSize == time at end of first bucket */
 401             pct_first_bin = (((first_bin+1)*bucketSize)-start)/bucketSize;
 402             retVal += pct_first_bin * dataPtr.buckets[first_bin];
 403             /* last_bin+*bucketSize == time at start of last bucket */
 404             pct_last_bin = (end - last_bin*bucketSize)/bucketSize;
 405             retVal += pct_last_bin * dataPtr.buckets[last_bin];
 406             for (i=first_bin+1; i <= last_bin-1; i++) {
 407                 retVal += dataPtr.buckets[i];
 408             }
 409         }
 410     }
 411     return(retVal * bucketSize);
 412 }
 413
 414 sampleValue Histogram::getValue()
 415 {
 416     return(getValue(0.0, numBins * bucketSize));
 417 }
 418
 419 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
 420 {
 421     int i;
 422     int last;
 423
 424     last = first + numberOfBuckets;
 425     if (lastBin < last) last = lastBin;
 426
 427     // make sure its in bin form.
 428     convertToBins();
 429
 430     for (i=first; i < last; i++) {
 431         buckets[i-first] = dataPtr.buckets[i];
 432     }
 433     return(last-first);
 434 }