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.15  1995/08/01 01:56:32  newhall
  20  * fix to how global time is computed
  21  *
  22  * Revision 1.14  1995/07/20 22:30:13  rbi
  23  * Fixed a folding bug
  24  *
  25  * Revision 1.13  1995/07/06  01:52:13  newhall
  26  * support for Histograms with non-zero start time
  27  *
  28  * Revision 1.12  1995/06/02  21:00:08  newhall
  29  * added a NaN value generator
  30  * fixed memory leaks in Histogram class
  31  * added newValue member with a vector<sampleInfo *> to class sampleInfo
  32  *
  33  * Revision 1.11  1995/02/16  09:28:02  markc
  34  * Removed compiler warnings.
  35  * Changed Boolean to bool
  36  *
  37  * Revision 1.10  1994/06/29  02:48:31  hollings
  38  * Added destructor to Histogram class.
  39  *
  40  * Revision 1.9  1994/05/10  03:56:47  hollings
  41  * Changed hist data upcall to return array of buckets not single value.
  42  *
  43  * Revision 1.8  1994/04/30  21:00:03  hollings
  44  * Fixed bug in fold callback that caused all fold message to go to the
  45  * Histogram that caused the fold not the correct ones.
  46  *
  47  * Revision 1.7  1994/04/20  15:19:30  hollings
  48  * Added method to get histogram buckets.
  49  *
  50  * Revision 1.6  1994/04/12  22:11:22  hollings
  51  * removed special case of bucket a zero value since it caused upcalls not to
  52  * happen.
  53  *
  54  * Revision 1.5  1994/03/08  17:12:29  hollings
  55  * Added fold callback and changed from multiple data callbacks to one per
  56  * histogram instance.  Also made the data callbacks happen once per bucket.
  57  *
  58  * Revision 1.4  1994/02/10  23:08:26  hollings
  59  * Fixed list.h ++ function to work when a hash table has an element at
  60  * slot zero in the table.
  61  *
  62  * Removed unused fields in hist class.
  63  *
  64  * Revision 1.3  1994/02/08  00:30:39  hollings
  65  * Make libutil more compatable with ATT CC.
  66  *
  67  * Revision 1.2  1994/01/26  04:53:42  hollings
  68  * Change to using <module>/h/.h
  69  *
  70  * Revision 1.1  1994/01/25  20:50:25  hollings
  71  * First real version of utility library.
  72  *
  73  * Revision 1.4  1993/12/15  21:06:23  hollings
  74  * changed initial bucket width to 0.1.
  75  *
  76  * Revision 1.3  1993/08/11  18:03:54  hollings
  77  * removed printf for folding hist.
  78  *
  79  * Revision 1.2  1993/08/05  18:55:08  hollings
  80  * general fixups and include format.
  81  *
  82  * Revision 1.1  1993/05/07  20:19:17  hollings
  83  * Initial revision
  84  *
  85  *
  86  */
  87
  88 #include <stdio.h>
  89 #include <assert.h>
  90 #include <string.h>
  91 #include <stdlib.h>
  92
  93 #include "util/h/hist.h"
  94
  95 /* number of intervals at which we switch to regular histograms */
  96 #define MAX_INTERVALS   15
  97
  98 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
  99
 100 #ifdef n_def
 101 int Histogram::numBins = 1000;
 102 timeStamp Histogram::bucketSize = 0.1;
 103 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
 104 Histogram *Histogram::allHist = NULL;
 105 int Histogram::lastGlobalBin = 0;
 106 #endif
 107
 108 int Histogram::numBins = 1000;
 109 int Histogram::lastGlobalBin = 0;
 110 timeStamp Histogram::baseBucketSize = 0.1;
 111 timeStamp Histogram::globalBucketSize = 0.1;
 112 vector<Histogram *> Histogram::allHist;
 113
 114 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c)
 115 {
 116     smooth = false;
 117     lastBin = 0;
 118     metricType = type;
 119     intervalCount = 0;
 120     intervalLimit = MAX_INTERVALS;
 121     storageType = HistInterval;
 122     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
 123     allHist += this;
 124     dataFunc = d;
 125     foldFunc = f;
 126     cData = c;
 127     active = true;
 128     bucketWidth = globalBucketSize;
 129     total_time = bucketWidth*numBins;
 130     startTime = 0.0;
 131 }
 132
 133 /*
 134  * Given an array of buckets - turn them into a histogram.
 135  *
 136  */
 137 Histogram::Histogram(Bin *buckets,
 138                      metricStyle type,
 139                      dataCallBack d,
 140                      foldCallBack f,
 141                      void *c)
 142 {
 143     // First call default constructor.
 144     (void) Histogram(type, d, f, c);
 145
 146     storageType = HistBucket;
 147     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 148     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
 149 }
 150
 151
 152 // constructor for histogram that doesn't start at time 0
 153 Histogram::Histogram(timeStamp start, metricStyle type, dataCallBack d,
 154                      foldCallBack f, void *c)
 155 {
 156     smooth = false;
 157     lastBin = 0;
 158     metricType = type;
 159     intervalCount = 0;
 160     intervalLimit = MAX_INTERVALS;
 161     storageType = HistInterval;
 162     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
 163     allHist += this;
 164     dataFunc = d;
 165     foldFunc = f;
 166     cData = c;
 167     active = true;
 168     startTime = start;
 169
 170     // compute bucketwidth based on start time
 171     timeStamp minBucketWidth =
 172             ((lastGlobalBin*globalBucketSize)  - startTime) / numBins;
 173     for(timeStamp i = baseBucketSize; i < minBucketWidth; i *= 2.0) ;
 174     bucketWidth = i;
 175     total_time = startTime + bucketWidth*numBins;
 176 }
 177
 178
 179 Histogram::Histogram(Bin *buckets,
 180                      timeStamp start,
 181                      metricStyle type,
 182                      dataCallBack d,
 183                      foldCallBack f,
 184                      void *c)
 185 {
 186     // First call default constructor.
 187     (void) Histogram(start, type, d, f, c);
 188     storageType = HistBucket;
 189     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 190     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
 191 }
 192
 193 Histogram::~Histogram(){
 194
 195     // remove from allHist
 196     for(unsigned i=0; i < allHist.size(); i++){
 197         if(allHist[i] == this){
 198             break;
 199         }
 200     }
 201     for(unsigned j = i; j < (allHist.size() - 1); j++){
 202         allHist[j] = allHist[j+1];
 203     }
 204     allHist.resize(allHist.size() - 1);
 205
 206     // free bin space
 207     if (storageType == HistInterval) {
 208         free(dataPtr.intervals);
 209     }
 210     else {
 211         free(dataPtr.buckets);
 212     }
 213 }
 214
 215
 216 #define MAX(a, b)       ((a) > (b) ? (a):(b))
 217
 218 /*
 219  * addInterval - add a value to a histogram from start to end.
 220  *
 221  * start, and end are relative to the global start time (i.e. 0.0 is the
 222  *   left side of the first hist bin).
 223  */
 224 void Histogram::addInterval(timeStamp start,
 225                             timeStamp end,
 226                             sampleValue value,
 227                             bool smooth)
 228 {
 229     while ((end >= total_time) || (start >= total_time)) {
 230         // colapse histogram.
 231         foldAllHist();
 232     }
 233
 234     lastBin = (int) ((end - startTime) / bucketWidth);
 235
 236 #ifdef n_def
 237     // update global info. if this histogram started at time 0
 238     if(startTime == 0.0){
 239         lastGlobalBin = lastBin;
 240         for (unsigned i=0; i < allHist.size(); i++) {
 241             if((allHist[i])->startTime == 0.0){
 242                 if (((allHist[i])->lastBin < lastGlobalBin)) {
 243                     lastGlobalBin = (allHist[i])->lastBin;
 244             }}
 245         }
 246     }
 247 #endif
 248
 249     // TODO: this should be replaced with the above code when
 250     // the performance consultant is changed to correctly
 251     // delete histograms that it is no longer collection
 252     // data values for
 253     // change this so that lastGlobalbin is max of all lastBins
 254     if(startTime == 0.0){
 255         if(lastBin > lastGlobalBin)
 256             lastGlobalBin = lastBin;
 257         for (unsigned i=0; i < allHist.size(); i++) {
 258             if(((allHist[i])->startTime == 0.0)
 259                && ((allHist[i])->isActive())){
 260                 if (((allHist[i])->lastBin > lastGlobalBin)) {
 261                     lastGlobalBin = (allHist[i])->lastBin;
 262             }}
 263         }
 264     }
 265
 266     if (storageType == HistInterval) {
 267         /* convert to buckets */
 268         convertToBins();
 269     }
 270     bucketValue(start, end, value, smooth);
 271 }
 272
 273 void Histogram::convertToBins()
 274 {
 275     int i;
 276     Interval *intervals;
 277     Interval *currentInterval;
 278
 279     if (storageType == HistBucket) return;
 280
 281     intervals = dataPtr.intervals;
 282     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
 283     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
 284     for (i=0; i < intervalCount; i++) {
 285         currentInterval = &(intervals[i]);
 286         bucketValue(currentInterval->start, currentInterval->end,
 287             currentInterval->value, smooth);
 288     }
 289     free(intervals);
 290     intervalCount = -1;
 291     intervalLimit = 0;
 292     storageType = HistBucket;
 293 }
 294
 295 void Histogram::foldAllHist()
 296 {
 297     // update global info.
 298     if(startTime == 0.0){
 299         globalBucketSize *= 2.0;
 300         lastGlobalBin = numBins/2 - 1;
 301     }
 302
 303     // fold all histograms with the same time base
 304     for(unsigned i = 0; i < allHist.size(); i++){
 305         if(((allHist[i])->startTime == startTime)
 306            && (allHist[i])->active){
 307             (allHist[i])->bucketWidth *= 2.0;
 308             if((allHist[i])->storageType == HistBucket){
 309                 Bin *bins = (allHist[i])->dataPtr.buckets;
 310                 for(unsigned j=0; j < numBins/2; j++){
 311                     bins[j] = (bins[j*2] + bins[j*2+1]) / 2.0;
 312                 }
 313                 (allHist[i])->lastBin = j - 1;
 314                 memset(&bins[j], '\0', (numBins - j) * sizeof(Bin));
 315             }
 316             (allHist[i])->total_time = startTime +
 317                                        numBins*(allHist[i])->bucketWidth;
 318             if((allHist[i])->foldFunc)
 319                 ((allHist[i])->foldFunc)((allHist[i])->bucketWidth,
 320                                         (allHist[i])->cData,
 321                                         (allHist[i])->startTime);
 322         }
 323     }
 324 }
 325
 326 void Histogram::bucketValue(timeStamp start_clock,
 327                            timeStamp end_clock,
 328                            sampleValue value,
 329                            bool smooth)
 330 {
 331     register int i;
 332
 333     // don't add values to an inactive histogram
 334     if(!active) return;
 335
 336     timeStamp elapsed_clock = end_clock - start_clock;
 337
 338     /* set starting and ending bins */
 339     int first_bin = (int) ((start_clock - startTime )/ bucketWidth);
 340     // ignore bad values
 341     if((first_bin < 0) || (first_bin > numBins)) return;
 342     //assert(first_bin >= 0);
 343     //assert(first_bin <= numBins);
 344     if (first_bin == numBins)
 345         first_bin = numBins-1;
 346     int last_bin = (int) ((end_clock - startTime) / bucketWidth);
 347     // ignore bad values
 348     if((last_bin < 0) || (last_bin > numBins)) return;
 349     // assert(last_bin >= 0);
 350     // assert(last_bin <= numBins);
 351     if (last_bin == numBins)
 352         last_bin = numBins-1;
 353     /* set starting times for first & last bins */
 354     timeStamp first_bin_start = bucketWidth * first_bin;
 355     timeStamp last_bin_start = bucketWidth  * last_bin;
 356
 357     if (metricType == SampledFunction) {
 358         for (i=first_bin; i <= last_bin; i++) {
 359             dataPtr.buckets[i] = value;
 360         }
 361     } else {
 362         // normalize by bucket size.
 363         value /= bucketWidth;
 364         if (last_bin == first_bin) {
 365             dataPtr.buckets[first_bin] += value;
 366             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
 367                 /* value > 100% */
 368                 smoothBins(dataPtr.buckets, first_bin, bucketWidth);
 369             }
 370             return;
 371         }
 372
 373         /* determine how much of the first & last bins were in this interval */
 374         timeStamp time_in_first_bin =
 375                         bucketWidth - ((start_clock - startTime)- first_bin_start);
 376         timeStamp time_in_last_bin = (end_clock- startTime) - last_bin_start;
 377         timeStamp time_in_other_bins =
 378             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
 379         // ignore bad values
 380         if((time_in_first_bin < 0) ||
 381            (time_in_last_bin < 0) ||
 382            (time_in_other_bins < 0))
 383             return;
 384
 385         /* determine how much of value should be in each bin in the interval */
 386         sampleValue amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
 387         sampleValue amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
 388         sampleValue amt_other_bins =
 389                                 (time_in_other_bins / elapsed_clock) * value;
 390         if (last_bin > first_bin+1)
 391             amt_other_bins /= (last_bin - first_bin) - 1.0;
 392
 393         /* add the appropriate amount of time to each bin */
 394         dataPtr.buckets[first_bin] += amt_first_bin;
 395         dataPtr.buckets[last_bin]  += amt_last_bin;
 396         for (i=first_bin+1; i < last_bin; i++)
 397             dataPtr.buckets[i]  += amt_other_bins;
 398     }
 399
 400     /* limit absurd time values - anything over 100% is pushed back into
 401        previous buckets */
 402     if (smooth) {
 403         for (i = first_bin; i <= last_bin; i++) {
 404             if (dataPtr.buckets[i] > bucketWidth)
 405                 smoothBins(dataPtr.buckets, i, bucketWidth);
 406         }
 407     }
 408
 409     // inform users about the data.
 410     // make sure they want to hear about it (dataFunc)
 411     //  && that we have a full bin (last_bin>first_bin)
 412     if (dataFunc && (last_bin-first_bin)) {
 413         (dataFunc)(&dataPtr.buckets[first_bin],
 414                    startTime,
 415                    last_bin-first_bin,
 416                    first_bin,
 417                    cData);
 418     }
 419 }
 420
 421
 422 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
 423 {
 424     int j;
 425     sampleValue extra_time;
 426
 427     extra_time = (bins[i] - bucketSize);
 428     bins[i] = bucketSize;
 429     j = i - 1;
 430     while ((j >= 0) && (extra_time > 0.0)) {
 431         bins[j] += extra_time;
 432         extra_time = 0.0;
 433         if (bins[j] > bucketSize) {
 434             extra_time = (bins[j] - bucketSize);
 435             bins[j] = bucketSize;
 436         }
 437         j--;
 438     }
 439     if (extra_time > 0.0) {
 440         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
 441         abort();
 442     }
 443 }
 444
 445
 446 static double splitTime(timeStamp startInterval,
 447                         timeStamp endInterval,
 448                         timeStamp startLimit,
 449                         timeStamp endLimit,
 450                         sampleValue value)
 451 {
 452     sampleValue time;
 453     timeStamp inv_length;
 454
 455     inv_length = endInterval-startInterval;
 456     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {
 457         time = value;
 458     } else if (startInterval == endInterval) {
 459         /* can't split delta functions */
 460         time = 0.0;
 461     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
 462         /* overlaps the end */
 463         time = value * (endLimit - startInterval) / inv_length;
 464     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) {
 465         /* overlaps the end */
 466         time = value * (endInterval - startLimit) / inv_length;
 467     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
 468         /* detail contains interval */
 469         time = value * (endLimit - startLimit) / inv_length;
 470     } else {
 471         /* no overlap of time */
 472         time = 0.0;
 473     }
 474     return(time);
 475 }
 476
 477 /*
 478  * Get the component of the histogram from start to end.
 479  *
 480  */
 481 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
 482 {
 483     int i;
 484     Interval *cp;
 485     sampleValue retVal = 0.0;
 486     int first_bin, last_bin;
 487     double pct_first_bin, pct_last_bin;
 488
 489     if (storageType == HistInterval) {
 490         if (metricType == SampledFunction) {
 491             // compute weight average of sample.
 492             for (i=0; i < intervalCount; i++) {
 493                 cp = &(dataPtr.intervals[i]);
 494                 retVal += cp->value * (cp->end - cp->start);
 495             }
 496         } else {
 497             // total over the interval.
 498             for (i=0; i < intervalCount; i++) {
 499                 cp = &(dataPtr.intervals[i]);
 500                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
 501             }
 502         }
 503     } else {
 504         first_bin = (int) (start/bucketWidth);
 505         /* round up */
 506         last_bin = (int) (end/bucketWidth+0.5);
 507         if (last_bin >= numBins) last_bin = numBins-1;
 508         if (first_bin == last_bin) {
 509             retVal = dataPtr.buckets[first_bin];
 510         } else {
 511             /* (first_bin+1)*bucketWidth == time at end of first bucket */
 512             pct_first_bin = (((first_bin+1)*bucketWidth)-start)/bucketWidth;
 513             retVal += pct_first_bin * dataPtr.buckets[first_bin];
 514             /* last_bin+*bucketWidth == time at start of last bucket */
 515             pct_last_bin = (end - last_bin*bucketWidth)/bucketWidth;
 516             retVal += pct_last_bin * dataPtr.buckets[last_bin];
 517             for (i=first_bin+1; i <= last_bin-1; i++) {
 518                 retVal += dataPtr.buckets[i];
 519             }
 520         }
 521     }
 522     return(retVal * bucketWidth);
 523 }
 524
 525 sampleValue Histogram::getValue()
 526 {
 527     return(getValue(0.0, numBins * bucketWidth));
 528 }
 529
 530 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
 531 {
 532     int i;
 533     int last;
 534
 535     last = first + numberOfBuckets;
 536     if (lastBin < last) last = lastBin;
 537
 538     // make sure its in bin form.
 539     convertToBins();
 540
 541     for (i=first; i < last; i++) {
 542         buckets[i-first] = dataPtr.buckets[i];
 543     }
 544     return(last-first);
 545 }