base/statistics.cc

   1 /*
   2  * Copyright (c) 2003 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include <iomanip>
  30 #include <iostream>
  31 #include <list>
  32 #include <map>
  33 #include <string>
  34 #include <sstream>
  35
  36 #include <math.h>
  37
  38 #include "cprintf.hh"
  39 #include "intmath.hh"
  40 #include "misc.hh"
  41 #include "statistics.hh"
  42 #include "str.hh"
  43 #include "universe.hh"
  44
  45 #ifdef __M5_NAN
  46 float
  47 __nan()
  48 {
  49     union {
  50         uint32_t ui;
  51         float f;
  52     } nan;
  53
  54     nan.ui = 0x7fc00000;
  55     return nan.f;
  56 }
  57 #endif
  58
  59 #ifdef STAT_DEBUG
  60 static int total_stats = 0;
  61 #endif
  62
  63 using namespace std;
  64
  65 // This is a hack to get this parameter from the old stats package.
  66 namespace Statistics {
  67 bool PrintDescriptions = true;
  68
  69 namespace Detail {
  70 struct SubData
  71 {
  72     string name;
  73     string desc;
  74 };
  75
  76 struct StatData
  77 {
  78     StatData();
  79     ~StatData();
  80
  81     bool init;
  82     bool print;
  83     string name;
  84     vector<SubData> *subdata;
  85     string desc;
  86     int precision;
  87     FormatFlags flags;
  88     const Stat *prereq;
  89 };
  90
  91 StatData::StatData()
  92     : init(false), print(false), subdata(NULL), precision(-1), flags(none),
  93       prereq(NULL)
  94 {
  95 }
  96
  97 StatData::~StatData()
  98 {
  99     if (subdata)
 100         delete subdata;
 101 }
 102
 103 class Database
 104 {
 105   private:
 106     Database(const Database &) {}
 107
 108   private:
 109     typedef list<Stat *> list_t;
 110     typedef map<const Stat *, StatData *> map_t;
 111
 112     list_t allStats;
 113     list_t printStats;
 114     map_t map;
 115
 116   public:
 117     Database();
 118     ~Database();
 119
 120     void dump(ostream &stream);
 121
 122     StatData *find(const Stat *stat);
 123     void check();
 124     void regStat(Stat *stat);
 125     StatData *print(Stat *stat);
 126 };
 127
 128 Database::Database()
 129 {}
 130
 131 Database::~Database()
 132 {}
 133
 134 void
 135 Database::dump(ostream &stream)
 136 {
 137     list_t::iterator i = printStats.begin();
 138     list_t::iterator end = printStats.end();
 139
 140     while (i != end) {
 141         Stat *stat = *i;
 142         if (stat->dodisplay())
 143             stat->display(stream);
 144         ++i;
 145     }
 146 }
 147
 148 StatData *
 149 Database::find(const Stat *stat)
 150 {
 151     map_t::const_iterator i = map.find(stat);
 152
 153     if (i == map.end())
 154         return NULL;
 155
 156     return (*i).second;
 157 }
 158
 159 void
 160 Database::check()
 161 {
 162     list_t::iterator i = allStats.begin();
 163     list_t::iterator end = allStats.end();
 164
 165     while (i != end) {
 166         Stat *stat = *i;
 167         StatData *data = find(stat);
 168         if (!data || !data->init) {
 169 #ifdef STAT_DEBUG
 170             cprintf("this is stat number %d\n",(*i)->number);
 171 #endif
 172             panic("Not all stats have been initialized");
 173         }
 174
 175         if (data->print) {
 176             if (data->name.empty())
 177                 panic("all printable stats must be named");
 178
 179             list_t::iterator j = printStats.insert(printStats.end(), *i);
 180             inplace_merge(printStats.begin(), j,
 181                           printStats.end(), Stat::less);
 182         }
 183
 184         ++i;
 185     }
 186 }
 187
 188 void
 189 Database::regStat(Stat *stat)
 190 {
 191     if (map.find(stat) != map.end())
 192         panic("shouldn't register stat twice!");
 193
 194     allStats.push_back(stat);
 195
 196     StatData *data = new StatData;
 197     bool success = (map.insert(make_pair(stat, data))).second;
 198     assert(map.find(stat) != map.end());
 199     assert(success && "this should never fail");
 200 }
 201
 202 bool
 203 Stat::less(Stat *stat1, Stat *stat2)
 204 {
 205     const string &name1 = stat1->myname();
 206     const string &name2 = stat2->myname();
 207
 208     vector<string> v1;
 209     vector<string> v2;
 210
 211     tokenize(v1, name1, '.');
 212     tokenize(v2, name2, '.');
 213
 214     int last = min(v1.size(), v2.size()) - 1;
 215     for (int i = 0; i < last; ++i)
 216         if (v1[i] != v2[i])
 217             return v1[i] < v2[i];
 218
 219     // Special compare for last element.
 220     if (v1[last] == v2[last])
 221         return v1.size() < v2.size();
 222     else
 223         return v1[last] < v2[last];
 224
 225     return false;
 226 }
 227
 228 StatData *
 229 Database::print(Stat *stat)
 230 {
 231     StatData *data = find(stat);
 232     assert(data);
 233
 234     data->print = true;
 235
 236     return data;
 237 }
 238
 239 Database &
 240 StatDB()
 241 {
 242     static Database db;
 243     return db;
 244 }
 245
 246 Stat::Stat(bool reg)
 247 {
 248 #if 0
 249     // This assert can help you find that pesky stat.
 250     assert(this != (void *)0xbffff5c0);
 251 #endif
 252
 253     if (reg)
 254         StatDB().regStat(this);
 255 #ifdef STAT_DEBUG
 256     number = ++total_stats;
 257     cprintf("I'm stat number %d\n",number);
 258 #endif
 259 }
 260
 261 void
 262 Stat::setInit()
 263 { mydata()->init = true; }
 264
 265 StatData *
 266 Stat::mydata()
 267 {
 268     StatData *data = StatDB().find(this);
 269     assert(data);
 270
 271     return data;
 272 }
 273
 274 const StatData *
 275 Stat::mydata() const
 276 {
 277     StatData *data = StatDB().find(this);
 278     assert(data);
 279
 280     return data;
 281 }
 282
 283 const SubData *
 284 Stat::mysubdata(int index) const
 285 {
 286     assert(index >= 0);
 287     if (index >= size())
 288         return NULL;
 289
 290     const StatData *data = this->mydata();
 291     if (!data->subdata || data->subdata->size() <= index)
 292         return NULL;
 293
 294     return &(*data->subdata)[index];
 295 }
 296
 297 SubData *
 298 Stat::mysubdata_create(int index)
 299 {
 300     int size = this->size();
 301     assert(index >= 0 && (size == 0 || size > 0 && index < size));
 302
 303     StatData *data = this->mydata();
 304     if (!data->subdata) {
 305         if (!data->subdata) {
 306             if (size == 0)
 307                 size = index + 1;
 308
 309             data->subdata = new vector<SubData>(size);
 310         }
 311     } else if (data->subdata->size() <= index)
 312             data->subdata->resize(index + 1);
 313
 314     SubData *sd = &(*data->subdata)[index];
 315     assert(sd);
 316
 317     return sd;
 318 }
 319
 320 string
 321 Stat::myname() const
 322 { return mydata()->name; }
 323
 324 string
 325 Stat::mysubname(int index) const
 326 {
 327     const SubData *sd = mysubdata(index);
 328     return sd ? sd->name : "";
 329 }
 330
 331 string
 332 Stat::mydesc() const
 333 { return mydata()->desc; }
 334
 335 string
 336 Stat::mysubdesc(int index) const
 337 {
 338     const SubData *sd = mysubdata(index);
 339     return sd ? sd->desc : "";
 340 }
 341
 342 int
 343 Stat::myprecision() const
 344 { return mydata()->precision; }
 345
 346 FormatFlags
 347 Stat::myflags() const
 348 { return mydata()->flags; }
 349
 350 bool
 351 Stat::dodisplay() const
 352 { return !mydata()->prereq || !mydata()->prereq->zero(); }
 353
 354 StatData *
 355 Stat::print()
 356 {
 357     StatData *data = StatDB().print(this);
 358     assert(data && data->init);
 359
 360     return data;
 361 }
 362
 363 Stat &
 364 Stat::name(const string &name)
 365 {
 366     print()->name = name;
 367     return *this;
 368 }
 369
 370 Stat &
 371 Stat::desc(const string &desc)
 372 {
 373     print()->desc = desc;
 374     return *this;
 375 }
 376
 377 Stat &
 378 Stat::precision(int precision)
 379 {
 380     print()->precision = precision;
 381     return *this;
 382 }
 383
 384 Stat &
 385 Stat::flags(FormatFlags flags)
 386 {
 387     if (flags & __reserved)
 388         panic("Cannot set reserved flags!\n");
 389
 390     print()->flags |= flags;
 391     return *this;
 392 }
 393
 394 Stat &
 395 Stat::prereq(const Stat &prereq)
 396 {
 397     print()->prereq = &prereq;
 398     return *this;
 399 }
 400
 401 Stat &
 402 Stat::subname(int index, const string &name)
 403 {
 404     print();
 405     mysubdata_create(index)->name = name;
 406     return *this;
 407 }
 408 Stat &
 409 Stat::subdesc(int index, const string &desc)
 410 {
 411     print();
 412     mysubdata_create(index)->desc = desc;
 413     return *this;
 414 }
 415
 416 bool
 417 ScalarStat::zero() const
 418 {
 419     return val() == 0.0;
 420 }
 421
 422 bool
 423 VectorStat::zero() const
 424 {
 425     return val()[0] == 0.0;
 426 }
 427
 428 string
 429 ValueToString(result_t value, int precision)
 430 {
 431     stringstream val;
 432
 433     if (!isnan(value)) {
 434         if (precision != -1)
 435             val.precision(precision);
 436         else if (value == rint(value))
 437             val.precision(0);
 438
 439         val.unsetf(ios::showpoint);
 440         val.setf(ios::fixed);
 441         val << value;
 442     } else {
 443 #ifndef STAT_DISPLAY_COMPAT
 444         val << "no value";
 445 #else
 446         val << "<err: div-0>";
 447 #endif
 448     }
 449
 450     return val.str();
 451 }
 452
 453 void
 454 PrintOne(ostream &stream, result_t value,
 455          const string &name, const string &desc, int precision,
 456          FormatFlags flags, result_t pdf = NAN, result_t cdf = NAN)
 457 {
 458     if (flags & nozero && value == 0.0 ||
 459         flags & nonan && isnan(value))
 460         return;
 461
 462     stringstream pdfstr, cdfstr;
 463
 464     if (!isnan(pdf))
 465         ccprintf(pdfstr, "%.2f%%", pdf * 100.0);
 466
 467     if (!isnan(cdf))
 468         ccprintf(cdfstr, "%.2f%%", cdf * 100.0);
 469
 470 #ifdef STAT_DISPLAY_COMPAT
 471     if (flags & __substat) {
 472         ccprintf(stream, "%32s%12s%10s%10s", name,
 473                  ValueToString(value, precision),
 474                  pdfstr, cdfstr);
 475     } else
 476 #endif
 477     {
 478         ccprintf(stream, "%-40s%12s%10s%10s", name,
 479                  ValueToString(value, precision), pdfstr, cdfstr);
 480     }
 481
 482     if (PrintDescriptions) {
 483         if (!desc.empty())
 484             ccprintf(stream, " # %s", desc);
 485     }
 486     stream << endl;
 487 }
 488
 489 void
 490 ScalarStat::display(ostream &stream) const
 491 {
 492     PrintOne(stream, val(), myname(), mydesc(), myprecision(), myflags());
 493 }
 494
 495 void
 496 VectorStat::display(ostream &stream) const
 497 {
 498     bool have_subname = false;
 499     bool have_subdesc = false;
 500     int size = this->size();
 501     for (int i = 0; i < size; ++i) {
 502         if (!mysubname(i).empty())
 503             have_subname = true;
 504         if (!mysubdesc(i).empty())
 505             have_subdesc = true;
 506     }
 507
 508     vector<string> *subnames = 0;
 509     vector<string> *subdescs = 0;
 510     if (have_subname) {
 511         subnames = new vector<string>(size);
 512         for (int i = 0; i < size; ++i)
 513             (*subnames)[i] = mysubname(i);
 514     }
 515     if (have_subdesc) {
 516         subdescs = new vector<string>(size);
 517         for (int i = 0; i < size; ++i)
 518             (*subdescs)[i] = mysubdesc(i);
 519     }
 520
 521     VectorDisplay(stream, myname(), subnames, mydesc(), subdescs,
 522                   myprecision(), myflags(), val(), total());
 523 }
 524
 525 #ifndef STAT_DISPLAY_COMPAT
 526 #define NAMESEP "::"
 527 #else
 528 #define NAMESEP "_"
 529 #endif
 530
 531 #ifndef STAT_DISPLAY_COMPAT
 532 void
 533 VectorDisplay(std::ostream &stream,
 534               const std::string &myname,
 535               const std::vector<std::string> *mysubnames,
 536               const std::string &mydesc,
 537               const std::vector<std::string> *mysubdescs,
 538               int myprecision, FormatFlags myflags,
 539               const rvec_t &vec, result_t mytotal)
 540 {
 541     int _size = vec.size();
 542     result_t _total = 0.0;
 543     result_t _pdf, _cdf = 0.0;
 544
 545     if (myflags & (pdf | cdf)) {
 546         for (int i = 0; i < _size; ++i) {
 547             _total += vec[i];
 548         }
 549     }
 550
 551     if (_size == 1) {
 552         PrintOne(stream, vec[0], myname, mydesc, myprecision, myflags);
 553     } else {
 554         for (int i = 0; i < _size; ++i) {
 555             string subname;
 556             if (mysubnames) {
 557                 subname = (*mysubnames)[i];
 558                 if (subname.empty())
 559                     continue;
 560             } else {
 561                 subname = to_string(i);
 562             }
 563
 564             string name = myname + NAMESEP + subname;
 565             if (!(myflags & pdf))
 566                 PrintOne(stream, vec[i], name, mydesc, myprecision, myflags);
 567             else {
 568                 _pdf = vec[i] / _total;
 569                 _cdf += _pdf;
 570                 PrintOne(stream, vec[i], name, mydesc, myprecision, myflags,
 571                          _pdf, _cdf);
 572             }
 573         }
 574
 575         if (myflags & total)
 576             PrintOne(stream, mytotal, myname + NAMESEP + "total",
 577                      mydesc, myprecision, myflags);
 578     }
 579 }
 580 #else
 581 void
 582 VectorDisplay(std::ostream &stream,
 583               const std::string &myname,
 584               const std::vector<std::string> *mysubnames,
 585               const std::string &mydesc,
 586               const std::vector<std::string> *mysubdescs,
 587               int myprecision, FormatFlags myflags,
 588               const rvec_t &vec, result_t mytotal)
 589 {
 590     int _size = vec.size();
 591     result_t _total = 0.0;
 592     result_t _pdf, _cdf = 0.0;
 593
 594     if (myflags & (pdf | cdf)) {
 595         for (int i = 0; i < _size; ++i) {
 596             _total += vec[i];
 597         }
 598     }
 599
 600     if (_size == 1) {
 601         PrintOne(stream, vec[0], myname, mydesc, myprecision, myflags);
 602     } else {
 603         if (myflags & total)
 604             PrintOne(stream, mytotal, myname, mydesc, myprecision, myflags);
 605
 606         if (myflags & dist) {
 607             ccprintf(stream, "%s.start_dist\n", myname);
 608             for (int i = 0; i < _size; ++i) {
 609                 string subname, subdesc;
 610                 subname = to_string(i);
 611                 if (mysubnames) {
 612                     if (!subname.empty()) {
 613                         subname = (*mysubnames)[i];
 614                     }
 615                 }
 616                 if (mysubdescs) {
 617                     subdesc = (*mysubdescs)[i];
 618                 }
 619                 if (!(myflags & (pdf | cdf))) {
 620                     PrintOne(stream, vec[i], subname, subdesc, myprecision,
 621                              myflags | __substat);
 622                 } else {
 623                     if (_total) {
 624                         _pdf = vec[i] / _total;
 625                         _cdf += _pdf;
 626                     } else {
 627                         _pdf = _cdf = 0.0;
 628                     }
 629                     if (!(myflags & cdf)) {
 630                         PrintOne(stream, vec[i], subname, subdesc, myprecision,
 631                                  myflags | __substat, _pdf);
 632                     } else {
 633                         PrintOne(stream, vec[i], subname, subdesc, myprecision,
 634                                  myflags | __substat, _pdf, _cdf);
 635                     }
 636                 }
 637             }
 638             ccprintf(stream, "%s.end_dist\n", myname);
 639         } else {
 640             for (int i = 0; i < _size; ++i) {
 641                 string subname;
 642                 if (mysubnames) {
 643                     subname = (*mysubnames)[i];
 644                     if (subname.empty())
 645                         continue;
 646                 } else {
 647                     subname = to_string(i);
 648                 }
 649
 650                 string name = myname + NAMESEP + subname;
 651                 if (!(myflags & pdf)) {
 652                     PrintOne(stream, vec[i], name, mydesc, myprecision,
 653                              myflags);
 654                 } else {
 655                     if (_total) {
 656                         _pdf = vec[i] / _total;
 657                         _cdf += _pdf;
 658                     } else {
 659                         _pdf = _cdf = 0.0;
 660                     }
 661                     _pdf = vec[i] / _total;
 662                     _cdf += _pdf;
 663                     PrintOne(stream, vec[i], name, mydesc, myprecision,
 664                              myflags, _pdf, _cdf);
 665                 }
 666             }
 667         }
 668     }
 669 }
 670 #endif
 671
 672 #ifndef STAT_DISPLAY_COMPAT
 673 void
 674 DistDisplay(ostream &stream, const string &name, const string &desc,
 675             int precision, FormatFlags flags,
 676             result_t min_val, result_t max_val,
 677             result_t underflow, result_t overflow,
 678             const rvec_t &vec, int min, int max, int bucket_size, int size);
 679 {
 680     assert(size == vec.size());
 681
 682     result_t total = 0.0;
 683     result_t pdf, cdf = 0.0;
 684
 685     total += underflow;
 686     for (int i = 0; i < size; ++i)
 687         total += vec[i];
 688     total += overflow;
 689
 690     pdf = underflow / total;
 691     cdf += pdf;
 692
 693     PrintOne(stream, underflow, name + NAMESEP + "underflow", desc,
 694              precision, myflags, pdf, cdf);
 695
 696     for (int i = 0; i < size; ++i) {
 697         stringstream namestr;
 698         namestr << name;
 699
 700         int low = i * bucket_size + min;
 701         int high = ::std::min((i + 1) * bucket_size + min - 1, max);
 702         namestr << low;
 703         if (low < high)
 704             namestr << "-" << high;
 705
 706         pdf = vec[i] / total;
 707         cdf += pdf;
 708         PrintOne(stream, vec[i], namestr.str(), desc, precision, myflags,
 709                  pdf, cdf);
 710     }
 711
 712     pdf = overflow / total;
 713     cdf += pdf;
 714     PrintOne(stream, overflow, name + NAMESEP + "overflow", desc,
 715              precision, myflags, pdf, cdf);
 716     PrintOne(stream, total, name + NAMESEP + "total", desc,
 717              precision, myflags);
 718 }
 719 #else
 720 void
 721 DistDisplay(ostream &stream, const string &name, const string &desc,
 722             int precision, FormatFlags flags,
 723             result_t min_val, result_t max_val,
 724             result_t underflow, result_t overflow,
 725             const rvec_t &vec, int min, int max, int bucket_size, int size)
 726 {
 727     assert(size == vec.size());
 728     string blank;
 729
 730     result_t total = 0.0;
 731
 732     total += underflow;
 733     for (int i = 0; i < size; ++i)
 734         total += vec[i];
 735     total += overflow;
 736
 737     ccprintf(stream, "%-42s", name + ".start_dist");
 738     if (PrintDescriptions && !desc.empty())
 739         ccprintf(stream, "                     # %s", desc);
 740     stream << endl;
 741
 742     PrintOne(stream, total, name + ".samples", blank, precision, flags);
 743     PrintOne(stream, min_val, name + ".min_value", blank, precision, flags);
 744
 745     if (underflow > 0)
 746         PrintOne(stream, min_val, name + ".underflows", blank, precision,
 747                  flags);
 748
 749     int _min;
 750     result_t _pdf, _cdf, mypdf, mycdf;
 751
 752     _cdf = 0.0;
 753     for (int i = 0; i < size; ++i) {
 754         if (flags & nozero && vec[i] == 0.0 ||
 755             flags & nonan && isnan(vec[i]))
 756             return;
 757
 758         _min = i * bucket_size + min;
 759         _pdf = vec[i] / total * 100.0;
 760         _cdf += _pdf;
 761
 762         mypdf = (flags & pdf) ? _pdf : NAN;
 763         mycdf = (flags & cdf) ? _cdf : NAN;
 764
 765         PrintOne(stream, vec[i], ValueToString(_min, 0), blank, precision,
 766                  flags | __substat, mypdf, mycdf);
 767     }
 768
 769     if (overflow > 0)
 770         PrintOne(stream, overflow, name + ".overflows", blank, precision,
 771                  flags);
 772     PrintOne(stream, max_val, name + ".max_value", blank, precision, flags);
 773     ccprintf(stream, "%s.end_dist\n\n", name);
 774 }
 775 #endif
 776
 777 void
 778 FancyDisplay(ostream &stream, const string &name, const string &desc,
 779              int precision, FormatFlags flags, result_t mean,
 780              result_t variance)
 781 {
 782     result_t stdev = isnan(variance) ? NAN : sqrt(variance);
 783     PrintOne(stream, mean, name + NAMESEP + "mean", desc, precision, flags);
 784     PrintOne(stream, stdev, name + NAMESEP + "stdev", desc, precision, flags);
 785 }
 786
 787 BinBase::BinBase(size_t size)
 788     : memsize(CeilPow2(size)), mem(NULL)
 789 {
 790 }
 791
 792 BinBase::~BinBase()
 793 {
 794     if (mem)
 795         delete [] mem;
 796 }
 797
 798 char *
 799 BinBase::memory()
 800 {
 801     if (!mem) {
 802         mem = new char[memsize];
 803         memset(mem, 0, memsize);
 804     }
 805
 806     return mem;
 807 }
 808
 809 } // namespace Detail
 810
 811 void
 812 check()
 813 {
 814     Detail::StatDB().check();
 815 }
 816
 817 void
 818 dump(ostream &stream)
 819 {
 820     Detail::StatDB().dump(stream);
 821 }
 822
 823 } // namespace Statistics