home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mallocte.zip / MALLOC.CPP next >
C/C++ Source or Header  |  1996-08-29  |  9KB  |  406 lines
  1. // $Id$
  2. //
  3. // Copyright (c) 1996 Tarma Software Research. All rights reserved.
  4. //
  5. // Project:    C++ compiler tests
  6. // Author:    Ron van der Wal
  7. // Created:    31-07-1996 16:45
  8. //
  9. // Test program for speed of memory allocation routines.
  10. //
  11. // Original:    Arthur D. Applegate: "Rethinking Memory Management", 
  12. //        Dr. Dobb's Journal, June 1994, pp. 52-55.
  13. //
  14. //! Usage:    MALLOC  [iters  [maxblock  [minblock]]]
  15. // Usage:    MALLOC  [total  [maxblock  [minblock]]]
  16. //
  17. // Output format in CSV files
  18. // --------------------------
  19. //! "Compiler name",iters,minblock,maxblock,insertion,search,deletion
  20. // "Compiler name",total,minblock,maxblock,insertion,search,deletion,alloc,count
  21.  
  22. #include <assert.h>
  23. #include <fstream.h>
  24. #include <iostream.h>
  25. #include <iomanip.h>
  26. #include <string.h>
  27. #include <stdlib.h>
  28. #include <time.h>
  29.  
  30. //#define WITH_BUCKETS        // Define to use frequency distribution buckets
  31. //#define WITH_BUGS        // Define to insert bugs
  32.  
  33. // Compiler names
  34.  
  35. #define _STR(x)        #x
  36. #define STR(x)        _STR(x)
  37.  
  38. #if defined(__BORLANDC__)
  39. const char gCCName[] = "Borland C++ " STR(__BORLANDC__);
  40. #elif defined(__IBMCPP__)
  41. const char gCCName[] = "IBM CSet++ " STR(__IBMCPP__);
  42. #elif defined(_MSC_VER)
  43. const char gCCName[] = "Microsoft C++ " STR(_MSC_VER);
  44. #elif defined(__SC__)
  45. const char gCCName[] = "Symantec C++ " STR(__SC__);
  46. #elif defined(__WATCOMC__)
  47. const char gCCName[] = "Watcom C++ " STR(__WATCOMC__);
  48. #else
  49. #error Unknown compiler
  50. #endif
  51.  
  52. // CSV output file
  53.  
  54. ostream *gCSV = 0;
  55.  
  56. // Random range
  57.  
  58. const int cMaxMaxBlock = 4096;    // Absolute maximum
  59. int gMinBlock = 1;        // Default minimum block size
  60. int gMaxBlock = 512;        // Default maximum block size
  61. long gNoIters = 1000;        // Default number of iterations
  62. long gMaxAlloc = 1000000L;    // Default total allocation size
  63. long gTotalAlloc = 0;        // Size of allocations thus far
  64. long gTotalCount = 0;        // Number of allocations thus far
  65.  
  66. #ifdef WITH_BUCKETS
  67. // Global buckets variable
  68. class Buckets;
  69. Buckets *gBuckets = 0;
  70. #endif
  71.  
  72. // Minimal standard RNG (see Numerical Recipes).
  73.  
  74. double Rand0()
  75. {
  76.     static long _gSeed = 0;
  77.  
  78.     const long IA = 16807L;
  79.     const long IM = 2147483647L;
  80.     const double AM = 1.0 / IM;
  81.     const long IQ = 127773L;
  82.     const long IR = 2836L;
  83.     const long MASK = 123459876L;
  84.  
  85.     _gSeed ^= MASK;
  86.     long k = _gSeed / IQ;
  87.     _gSeed = IA * (_gSeed - k * IQ) - IR * k;
  88.     if (_gSeed < 0) _gSeed += IM;
  89.     double result = AM * _gSeed;
  90.     _gSeed ^= MASK;
  91.     return result;
  92. }
  93.  
  94. // Define the following to use standard rand() generator
  95. //#define USE_STANDARD 1
  96.  
  97. #ifdef USE_STANDARD
  98. #define rng()        ((double)rand()/(RAND_MAX + 1L))
  99. #else
  100. #define rng()        Rand0()
  101. #endif
  102.  
  103. // Generate random number in certain range. Modulo operator is not used, 
  104. // since it would lead to non-uniformly distributed values.
  105.  
  106. inline int RandBetween(int aLow, int aHigh)
  107. {
  108. #ifdef WITH_BUGS
  109.     return (int)(rng() * (aHigh - aLow + 2)) + aLow;
  110. #else    // WITH_BUGS
  111. #ifdef NDEBUG
  112.     return (int)(rng() * (aHigh - aLow + 1)) + aLow;
  113. #else
  114.     int result = (int)(rng() * (aHigh - aLow + 1)) + aLow;
  115.     assert(result >= aLow);
  116.     assert(result <= aHigh);
  117.     return result;
  118. #endif    // NDEBUG
  119. #endif    // WITH_BUGS
  120. }
  121.  
  122. #ifdef WITH_BUCKETS
  123. // Buckets to remember frequency distributions
  124.  
  125. class Buckets
  126. {
  127.     int *        mBuckets;    // Array of buckets
  128.     int            mSize;        // Number of buckets
  129.     int            mLow;        // Lower bound
  130.     
  131.     // Statistics
  132.     long        mCount;
  133.     long        mSum;
  134.     long        mSumSquare;
  135.  
  136. public:
  137.     Buckets(int aLow, int aHigh);
  138.     ~Buckets();
  139.  
  140.     // Bucket operations
  141.     void        AddValue(int);
  142.     void        Clear();
  143.  
  144.     // Bucket statistics
  145.     long        Count() const { return mCount; }
  146.     long        Sum() const { return mSum; }
  147.     long        Average() const { return mCount ? mSum / mCount : 0; }
  148.  
  149.     // Output operations
  150.     void        Print(ostream &) const;
  151. };
  152.  
  153. Buckets::Buckets(int aLow, int aHigh)
  154. {
  155.     assert(aLow <= aHigh);
  156.     mLow = aLow;
  157.     mSize = aHigh - aLow + 1;
  158.     mBuckets = new int[mSize];
  159.     Clear();
  160. }
  161.  
  162. Buckets::~Buckets()
  163. {
  164.     delete [] mBuckets;
  165. }
  166.  
  167. void Buckets::AddValue(int aValue)
  168. {
  169. #ifndef WITH_BUGS
  170.     assert(mLow <= aValue && aValue < mLow + mSize);
  171. #endif
  172.     ++mBuckets[aValue - mLow];
  173.  
  174.     // Update statistics
  175.     ++mCount;
  176.     mSum += aValue;
  177.     mSumSquare += aValue * aValue;
  178. }
  179.  
  180. void Buckets::Clear()
  181. {
  182.     memset(mBuckets, 0, sizeof(int) * mSize);
  183.     mCount = mSum = mSumSquare = 0;
  184. }
  185.  
  186. void Buckets::Print(ostream &os) const
  187. {
  188.     os << mCount << " values, average = " << Average() << ", sum = "
  189.     << Sum() << ", Frequencies:\n";
  190.     for (int i = 0; i < mSize; ++i)
  191.         os << setw(8) << (i + mLow) << ": " << mBuckets[i] << "\n";
  192. }
  193. #endif    // WITH_BUCKETS
  194.  
  195. class Timer
  196. {
  197.     const char *m;
  198.     clock_t startTime;
  199.  
  200. public:
  201.     Timer(const char *msg): m(msg), startTime(clock()) {}
  202.     ~Timer() 
  203.     {
  204.     double elapsed = ((double)(clock() - startTime) /
  205.         (double)CLOCKS_PER_SEC);
  206.  
  207.     cout << m << ": " << elapsed << " seconds.\n";
  208.     if (gCSV) *gCSV << "," << elapsed;
  209.     }
  210. };
  211.  
  212. class Link
  213. {
  214.     friend class List;
  215.     char *value;
  216.     Link *prev, *next;
  217.  
  218. public:
  219.     Link(const char *, Link *, Link *);
  220.     ~Link();
  221. };  
  222.  
  223. class List
  224. {
  225.     Link *head, *tail;
  226.  
  227. public:
  228.     List();
  229.     ~List();
  230.     Link *        Insert(Link *, const char *);
  231.     void        Delete(Link *);
  232.     void        RandomOp();
  233.     const Link *    Find(const char *) const;
  234. };
  235.  
  236. Link::Link(const char *val, Link *p, Link *n)
  237. {
  238.     value = new char[strlen(val) + 1];
  239.     strcpy(value, val);
  240.  
  241.     if ((prev = p) != 0) prev->next = this;
  242.     if ((next = n) != 0) next->prev = this;
  243. }
  244.  
  245. Link::~Link()
  246. {
  247.     delete [] value;        // Original omitted []
  248.  
  249.     if (prev) prev->next = next;
  250.     if (next) next->prev = prev;
  251. }
  252.  
  253. List::List()
  254. {
  255.     head = tail = 0;
  256. }
  257.  
  258. List::~List()
  259. {
  260.     while (head)
  261.     Delete(head);
  262. }
  263.  
  264. Link *List::Insert(Link *prev, const char *val)
  265. {
  266.     Link *next = prev ? prev->next : head;
  267.     Link *l = new Link(val, prev, next);
  268.  
  269.     if (!prev) head = l;
  270.     if (!next) tail = l;
  271.  
  272.     return l;
  273. }
  274.  
  275. void List::Delete(Link *l)
  276. {
  277.     if (!l) return;
  278.     if (head == l) head = l->next;
  279.     if (tail == l) tail = l->prev;
  280.     delete l;
  281. }
  282.  
  283. void List::RandomOp()
  284. {
  285.     if (rng() < 0.8)
  286.     {
  287.     static char buf[cMaxMaxBlock + 1];
  288.  
  289.     int len = RandBetween(gMinBlock, gMaxBlock);
  290. #ifdef WITH_BUCKETS
  291.     gBuckets->AddValue(len);
  292. #endif
  293.     memset(buf, RandBetween(1, 127), len);
  294.     buf[len] = 0;
  295.  
  296.     Insert(tail, buf);
  297.     gTotalAlloc += len;
  298.     ++gTotalCount;
  299.     }
  300.     else
  301.     Delete(head);
  302. }
  303.  
  304. const Link *List::Find(const char *val) const
  305. {
  306.     for (Link *l = head; l; l = l->next)
  307.     {
  308.     if (strcmp(l->value, val) == 0)
  309.         break;
  310.     }
  311.     return l;
  312.     
  313. }   
  314.  
  315. int main(int argc, char *argv[])
  316. {
  317.     if (argc < 2)
  318.     {
  319. //!    cout << "usage:  MALLOC  iters  [maxblock  [minblock]]\n";
  320.     cout << "usage:  MALLOC  total  [maxblock  [minblock]]\n";
  321.     return -1;
  322.     }
  323.  
  324.     gCSV = new ofstream("malloc.csv", ios::out | ios::app);
  325.  
  326. //!    if (argc >= 2)
  327. //!    gNoIters = atol(argv[1]);
  328.  
  329.     if (argc >= 2)
  330.     gMaxAlloc = atol(argv[1]);
  331.  
  332.     if (argc >= 3)
  333.     gMaxBlock = atoi(argv[2]);
  334.  
  335.     if (argc >= 4)
  336.     gMinBlock = atoi(argv[3]);
  337.  
  338. //!    cout << "Test parameters:  iterations=" << gNoIters << ", maxblock="
  339. //!    << gMaxBlock << ", minblock=" << gMinBlock << "\n";
  340. //!    if (gCSV)
  341. //!    *gCSV << "\"" << gCCName << "\"," << gNoIters << "," << gMaxBlock 
  342. //!    << "," << gMinBlock;
  343.     cout << "Test parameters:  max alloc=" << gMaxAlloc << ", maxblock="
  344.     << gMaxBlock << ", minblock=" << gMinBlock << "\n";
  345.     if (gCSV)
  346.     *gCSV << "\"" << gCCName << "\"," << gMaxAlloc << "," << gMaxBlock 
  347.     << "," << gMinBlock;
  348.  
  349. #ifdef WITH_BUCKETS
  350.     // Create buckets for correct range
  351.     gBuckets = new Buckets(gMinBlock, gMaxBlock);
  352. #endif
  353.  
  354.     Timer t("Overall application");
  355.     List *list1 = new List, *list2 = new List, *list3 = new List,
  356.     *list4 = new List, *list5 = new List;
  357.  
  358.     {
  359.     Timer t("Insertion");
  360. //!    while (gTotalCount < gNoIters)
  361.     while (gTotalAlloc < gMaxAlloc)
  362.     {
  363.         list1->RandomOp();
  364.         list2->RandomOp();
  365.         list3->RandomOp();
  366.         list4->RandomOp();
  367.         list5->RandomOp();
  368.     }
  369.     }    
  370.     {
  371.     Timer t("Search");
  372.     list1->Find("not present");
  373.     list2->Find("not present");
  374.     list3->Find("not present");
  375.     list4->Find("not present");
  376.     list5->Find("not present");
  377.     }    
  378.     {
  379.     Timer t("Deletion");
  380.     delete list1;
  381.     delete list2;
  382.     delete list3;
  383.     delete list4;
  384.     delete list5;
  385.     }
  386.  
  387.     cout << "Total allocated size: " << gTotalAlloc << "\nTotal # blocks: "
  388.     << gTotalCount << "\n";
  389.     if (gCSV) *gCSV << "," << gTotalAlloc << "," << gTotalCount << "\n";
  390.  
  391. #ifdef WITH_BUCKETS
  392.     gBuckets->Print(cout);
  393. #endif
  394.  
  395. #ifndef WITH_BUGS
  396. #ifdef WITH_BUCKETS
  397.     delete gBuckets;
  398.     gBuckets = 0;
  399. #endif    // WITH_BUCKETS
  400. #endif    // WITH_BUGS
  401.     delete gCSV;
  402.     gCSV = 0;
  403.  
  404.     return 0;
  405. }
  406.