home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1997 February / PCO2_97.ISO / filesbbs / os2 / sysb091c.arj / SYSBENCH / SRC / PMB_HEAP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-21  |  14.2 KB  |  610 lines
  1. /*-------------------Start heapsort.c program-------------------*/
  2.  
  3. /****************************************************************/
  4. /*                         HEAPSORT                             */
  5. /*                     C Program Source                         */
  6. /*          Heapsort program for variable sized arrays          */
  7. /*                 Version 1.0, 04 Oct 1992                     */
  8. /*             Al Aburto (aburto@marlin.nosc.mil)               */
  9. /*                      ('ala' on BIX)                          */
  10. /*                                                              */
  11. /* Based on the Heap Sort code in 'Numerical Recipes in C' by   */
  12. /* William H. Press, Brian P. Flannery, Saul A. Teukolsky, and  */
  13. /* William T. Vetterling, Cambridge University Press, 1990,     */
  14. /* ISBN 0-521-35465-X.                                          */
  15. /*                                                              */
  16. /* The MIPS rating is based upon the program run time (runtime) */
  17. /* for one iteration and a gcc 2.1 unoptimized (gcc -DUNIX)     */
  18. /* assembly dump count of instructions per iteration for a i486 */
  19. /* machine (assuming 80386 code).  This is the reference used.  */
  20. /*                                                              */
  21. /* The maximum amount of memory allocated is based on the 'imax'*/
  22. /* variable in main(). Memory size = (2000*sizeof(long))*2^imax.*/
  23. /* imax is currently set to 8, but this value may be increased  */
  24. /* or decreased depending upon your system memory limits. For   */
  25. /* standard Intel PC CPU machines a value of imax = 3 must be   */
  26. /* used else your system may crash or hang up despite code in   */
  27. /* the program to prevent this.                                 */
  28. /****************************************************************/
  29.  
  30. /****************************************************/
  31. /* Example Compilation:                             */
  32. /* (1) UNIX Systems:                                */
  33. /*     cc -DUNIX -O heapsort.c -o heapsort          */
  34. /*     cc -DUNIX heapsort.c -o heapsort             */
  35. /****************************************************/
  36.  
  37. #include <stdio.h>
  38. #include <os2.h>
  39. #include <stdlib.h>
  40. #include <math.h>
  41.  
  42. /***************************************************************/
  43. /* Timer options. You MUST uncomment one of the options below  */
  44. /* or compile, for example, with the '-DUNIX' option.          */
  45. /***************************************************************/
  46. /* #define Amiga       */
  47. /* #define UNIX        */
  48. /* #define UNIX_Old    */
  49. /* #define VMS         */
  50. /* #define BORLAND_C   */
  51. /* #define MSC         */
  52. /* #define MAC         */
  53. /* #define IPSC        */
  54. /* #define FORTRAN_SEC */
  55. /* #define GTODay      */
  56. /* #define CTimer      */
  57. /* #define UXPM        */
  58.  
  59. #ifdef Amiga
  60. #include <exec/types.h>
  61. #include <ctype.h>
  62. #endif
  63.  
  64. #ifdef BORLAND_C
  65. #include <ctype.h>
  66. #include <dos.h>
  67. #endif
  68.  
  69. #ifdef MSC
  70. #include <ctype.h>
  71. #endif
  72.  
  73. static double nulltime,runtime,sta,stb;
  74. extern double dtime(void);
  75. static double emips,hmips,lmips,smips[21];
  76. static HSORT(long, long, long);
  77. void err(char* s);
  78.  
  79. static long bplong,ErrorFlag;
  80.  
  81. static long NLoops[21];
  82.  
  83.  
  84. double pmb_heaps(void)
  85. {
  86.  
  87. long  i,j,k,p,imax;
  88.  
  89. bplong = sizeof(long);
  90.  
  91. /*printf("\n   Heap Sort C Program\n");
  92. printf("   Version 1.0, 04 Oct 1992\n\n");
  93.  
  94. printf("   Size of long (bytes): %d\n\n",bplong);
  95.  
  96. printf("   Array Size    RunTime      Scale    MIPS\n");
  97. printf("    (bytes)       (sec)\n");
  98. */
  99.                    /* NLoops[] holds number of loops  */
  100.                    /* (iterations) to conduct. Preset */
  101.                    /* to 1 iteration.                 */
  102. for( i=0 ; i<= 20 ; i++)
  103. {
  104.  NLoops[i] = 1;
  105. }
  106.                    /* Predetermine runtime (sec) for  */
  107.                    /* memory size 2000 * sizeof(long),*/
  108.                    /* and 256 iterations. p = 0 means */
  109.                    /* don't print the result.         */
  110. j = 2000;
  111. k = 256;
  112. p = 0;
  113. HSORT(j,k,p);
  114.                    /* Set number of iterations (loops)*/
  115.                    /* based on runtime above --- so   */
  116.                    /* program won't take forever on   */
  117.                    /* the slower machines.            */
  118. i = 8;
  119. if ( runtime > 0.125 ) i = 1;
  120.  
  121. NLoops[0] =  32 * i;
  122. NLoops[1] =  16 * i;
  123. NLoops[2] =   8 * i;
  124. NLoops[3] =   4 * i;
  125. NLoops[4] =   2 * i;
  126. NLoops[5] =       i;
  127. NLoops[6] =   i / 2;
  128. NLoops[7] =   i / 4;
  129.  
  130. if ( i == 1 )
  131. {
  132. NLoops[6]  = 1;
  133. NLoops[7]  = 1;
  134. }
  135.                    /* Redo the first run and print    */
  136.                    /* the results.                    */
  137. j = 2000;
  138. k = NLoops[0];
  139. p = 1;
  140. HSORT(j,k,p);
  141.                    /* Save estimated mips result      */
  142. smips[0] = emips;
  143.  
  144. j = 2000;
  145. ErrorFlag = 0;
  146.                    /* Now do it for memory sizes up to */
  147.                    /* (2000*sizeof(long)) * (2 ** imax)*/
  148.                    /* where imax determines maximum    */
  149.                    /* amount of memory allocated.      */
  150.                    /* Currently I set imax = 8, so if  */
  151.                    /* sizeof(long) = 4 program will run*/
  152.                    /* from 8000, 16000, ..., and up to */
  153.                    /* 2048000 byte memory size. You can*/
  154.                    /* increase imax, but imax = 8 is   */
  155.                    /* limit for this test program.     */
  156. imax = 7;
  157. for( i=1 ; i<= imax ; i++)
  158. {
  159.    j = 2 * j;
  160.  
  161.    k = NLoops[i];
  162.  
  163.    HSORT(j,k,p);
  164.    smips[i] = emips;
  165.  
  166.    if( ErrorFlag > 0L ) break;
  167.  
  168. }
  169.  
  170. if( ErrorFlag == 2L )
  171. {
  172.   err("Heapsort: Could Not Allocate Memory for Array\n");
  173. }
  174.  
  175. hmips = 0.0;
  176. lmips = 1.0e+06;
  177. for( k = 0; k < i; k++)
  178. {
  179. if( smips[k] > hmips ) hmips = smips[k];
  180. if( smips[k] < lmips ) lmips = smips[k];
  181. }
  182.  
  183. /*printf("\n   Runtime is the average for 1 iteration.\n");
  184. printf("   High MIPS = %8.2lf\n",hmips);
  185. printf("   Low  MIPS = %8.2lf\n\n",lmips);*/
  186.   return (hmips+lmips)/2.0*1.0e6;
  187.  
  188. }                                  /* End of main */
  189.  
  190.  
  191. /*************************/
  192. /*  Heap Sort Program    */
  193. /*************************/
  194.  
  195. static HSORT(m,n,p)
  196. long m,n,p;
  197. {
  198.  
  199. register long *base;
  200. register long i,j,k,l;
  201. register long size;
  202.  
  203. long  iter,msize,iran,ia,ic,im,ih,ir;
  204. long  count,ca,cb,cc,cd,ce,cf;
  205.  
  206. msize = m * bplong;
  207. size  = m - 1;
  208. base  = (long *)malloc((unsigned)msize);
  209.  
  210. ia = 106;
  211. ic = 1283;
  212. im = 6075;
  213. ih = 1001;
  214.  
  215.    ErrorFlag = 0L;
  216.  
  217.    if( !base )
  218.      {
  219.      ErrorFlag = 2L;
  220.      return 0;
  221.      }
  222.  
  223.    sta = dtime();
  224.    stb = dtime();
  225.    nulltime = stb - sta;
  226.    if ( nulltime < 0.0 ) nulltime = 0.0;
  227.  
  228.    count = 0;
  229.    sta = dtime();                       /* Start timing */
  230.    for(iter=1 ; iter<=n ; iter++)       /* Do 'n' iterations */
  231.  
  232.    {
  233.       iran = 47;                        /* Fill with 'random' numbers */
  234.       for(i=1 ; i<=size ; i++)
  235.       {
  236.     iran = (iran * ia + ic) % im;
  237.     *(base+i) = 1 + (ih * iran) / im;
  238.       }
  239.  
  240.       k = (size >> 1) + 1;              /* Heap sort the array */
  241.       l = size;
  242.       ca = 0; cb = 0; cc = 0;
  243.       cd = 0; ce = 0; cf = 0;
  244.  
  245.       for (;;)
  246.       {
  247.       ca++;
  248.     if (k > 1)
  249.     {
  250.        cb++;
  251.        ir = *(base+(--k));
  252.     }
  253.     else
  254.     {
  255.        cc++;
  256.        ir = *(base+l);
  257.        *(base+l) = *(base+1);
  258.        if (--l == 1)
  259.        {
  260.           *(base+1) = ir;
  261.           goto Done;
  262.        }
  263.     }
  264.  
  265.     i = k;
  266.     j = k << 1;
  267.  
  268.     while (j <= l)
  269.     {
  270.        cd++;
  271.        if ( (j < l) && (*(base+j) < *(base+j+1)) ) ++j;
  272.        if (ir < *(base+j))
  273.        {
  274.           ce++;
  275.           *(base+i) = *(base+j);
  276.           j += (i=j);
  277.        }
  278.        else
  279.        {
  280.           cf++;
  281.           j = l + 1;
  282.        }
  283.     }
  284.     *(base+i) = ir;
  285.       }
  286. Done:
  287.    count = count + ca;
  288.    }
  289.    stb = dtime();                       /* Stop timing */
  290.    runtime = stb - sta;
  291.    if ( runtime < 0.0 ) runtime = 0.0;
  292.                     /* Scale runtime per iteration */
  293.    runtime = (runtime - nulltime) / (double)n;
  294.  
  295.    ir = count / n;
  296.    ir = (ir + ca) / 2;
  297.                     /* Estimate MIPS rating */
  298.    emips = 24.0 * (double)size + 10.0 * (double)ir;
  299.    emips = emips + 6.0 * (double)cb + 9.0 * (double)cc;
  300.    emips = emips + 10.0 * (double)cd + 7.0 * (double)ce;
  301.    emips = emips + 4.0 * (double)cf;
  302.    sta   = 1.0e-06 * emips;
  303.    emips = sta / runtime;
  304.  
  305.    if ( p != 0L )
  306.    {
  307. //   printf("   %10ld %10.4lf %10.4lf %7.2lf\n",msize,runtime,sta,emips);
  308.    }
  309. free(base);
  310. return 0;
  311. }
  312.  
  313. /*****************************************************/
  314. /* Various timer routines.                           */
  315. /* Al Aburto, aburto@marlin.nosc.mil, 26 Sep 1992    */
  316. /*                                                   */
  317. /* t = dtime() outputs the current time in seconds.  */
  318. /* Use CAUTION as some of these routines will mess   */
  319. /* up when timing across the hour mark!!!            */
  320. /*                                                   */
  321. /* For timing I use the 'user' time whenever         */
  322. /* possible. Using 'user+sys' time is a separate     */
  323. /* issue.                                            */
  324. /*                                                   */
  325. /*****************************************************/
  326.  
  327. /*********************************/
  328. /* Timer code.                   */
  329. /*********************************/
  330. /*******************/
  331. /*  Amiga dtime()  */
  332. /*******************/
  333. #ifdef Amiga
  334. #include <ctype.h>
  335. #define HZ 50
  336.  
  337. double dtime()
  338. {
  339.    double q;
  340.  
  341.    struct   tt {
  342.       long  days;
  343.       long  minutes;
  344.       long  ticks;
  345.    } tt;
  346.  
  347.    DateStamp(&tt);
  348.  
  349.    q = ((double)(tt.ticks + (tt.minutes * 60L * 50L))) / (double)HZ;
  350.  
  351.    return q;
  352. }
  353. #endif
  354.  
  355. /*****************************************************/
  356. /*  UNIX dtime(). This is the preferred UNIX timer.  */
  357. /*  Provided by: Markku Kolkka, mk59200@cc.tut.fi    */
  358. /*  HP-UX Addition by: Bo Thide', bt@irfu.se         */
  359. /*****************************************************/
  360. #ifdef UNIX
  361. #include <sys/time.h>
  362. #include <sys/resource.h>
  363.  
  364. #ifdef __hpux
  365. #include <sys/syscall.h>
  366. #define getrusage(a,b) syscall(SYS_getrusage,a,b)
  367. #endif
  368.  
  369. struct rusage rusage;
  370.  
  371. double dtime()
  372. {
  373.    double q;
  374.  
  375.    getrusage(RUSAGE_SELF,&rusage);
  376.  
  377.    q = (double)(rusage.ru_utime.tv_sec);
  378.    q = q + (double)(rusage.ru_utime.tv_usec) * 1.0e-06;
  379.  
  380.    return q;
  381. }
  382. #endif
  383.  
  384. /***************************************************/
  385. /*  UNIX_Old dtime(). This is the old UNIX timer.  */
  386. /*  Use only if absolutely necessary as HZ may be  */
  387. /*  ill defined on your system.                    */
  388. /***************************************************/
  389. #ifdef UNIX_Old
  390. #include <sys/types.h>
  391. #include <sys/times.h>
  392. #include <sys/param.h>
  393.  
  394. #ifndef HZ
  395. #define HZ 60
  396. #endif
  397.  
  398. struct tms tms;
  399.  
  400. double dtime()
  401. {
  402.    double q;
  403.  
  404.    times(&tms);
  405.  
  406.    q = (double)(tms.tms_utime) / (double)HZ;
  407.  
  408.    return q;
  409. }
  410. #endif
  411.  
  412. /*********************************************************/
  413. /*  VMS dtime() for VMS systems.                         */
  414. /*  Provided by: RAMO@uvphys.phys.UVic.CA                */
  415. /*  Some people have run into problems with this timer.  */
  416. /*********************************************************/
  417. #ifdef VMS
  418. #include time
  419.  
  420. #ifndef HZ
  421. #define HZ 100
  422. #endif
  423.  
  424. struct tbuffer_t
  425.        {
  426.     int proc_user_time;
  427.     int proc_system_time;
  428.     int child_user_time;
  429.     int child_system_time;
  430.        };
  431. struct tbuffer_t tms;
  432.  
  433. double dtime()
  434. {
  435.    double q;
  436.  
  437.    times(&tms);
  438.  
  439.    q = (double)(tms.proc_user_time) / (double)HZ;
  440.  
  441.    return q;
  442. }
  443. #endif
  444.  
  445. /******************************/
  446. /*  BORLAND C dtime() for DOS */
  447. /******************************/
  448. #ifdef BORLAND_C
  449. #include <ctype.h>
  450. #include <dos.h>
  451. #include <time.h>
  452.  
  453. #define HZ 100
  454. struct time tnow;
  455.  
  456. double dtime()
  457. {
  458.    double q;
  459.  
  460.    gettime(&tnow);
  461.  
  462.    q = 60.0 * (double)(tnow.ti_min);
  463.    q = q + (double)(tnow.ti_sec);
  464.    q = q + (double)(tnow.ti_hund)/(double)HZ;
  465.  
  466.    return q;
  467. }
  468. #endif
  469.  
  470. /**************************************/
  471. /*  Microsoft C (MSC) dtime() for DOS */
  472. /**************************************/
  473. #ifdef MSC
  474. #include <time.h>
  475. #include <ctype.h>
  476.  
  477. #define HZ CLK_TCK
  478. clock_t tnow;
  479.  
  480. double dtime()
  481. {
  482.    double q;
  483.  
  484.    tnow = clock();
  485.  
  486.    q = (double)tnow / (double)HZ;
  487.  
  488.    return q;
  489. }
  490. #endif
  491.  
  492. /*************************************/
  493. /*  Macintosh (MAC) Think C dtime()  */
  494. /*************************************/
  495. #ifdef MAC
  496. #include <time.h>
  497.  
  498. #define HZ 60
  499.  
  500. double dtime()
  501. {
  502.    double q;
  503.  
  504.    q = (double)clock() / (double)HZ;
  505.  
  506.    return q;
  507. }
  508. #endif
  509.  
  510. /************************************************************/
  511. /*  iPSC/860 (IPSC) dtime() for i860.                       */
  512. /*  Provided by: Dan Yergeau, yergeau@gloworm.Stanford.EDU  */
  513. /************************************************************/
  514. #ifdef IPSC
  515. extern double dclock();
  516.  
  517. double dtime()
  518. {
  519.    double q;
  520.  
  521.    q = dclock();
  522.  
  523.    return q;
  524. }
  525. #endif
  526.  
  527. /**************************************************/
  528. /*  FORTRAN dtime() for Cray type systems.        */
  529. /*  This is the preferred timer for Cray systems. */
  530. /**************************************************/
  531. #ifdef FORTRAN_SEC
  532.  
  533. fortran double second();
  534.  
  535. double dtime()
  536. {
  537.    double q;
  538.  
  539.    second(&q);
  540.  
  541.    return q;
  542. }
  543. #endif
  544.  
  545. /***********************************************************/
  546. /*  UNICOS C dtime() for Cray UNICOS systems.  Don't use   */
  547. /*  unless absolutely necessary as returned time includes  */
  548. /*  'user+system' time.  Provided by: R. Mike Dority,      */
  549. /*  dority@craysea.cray.com                                */
  550. /***********************************************************/
  551. #ifdef CTimer
  552. #include <time.h>
  553.  
  554. double dtime()
  555. {
  556.    double    q;
  557.    clock_t   t;
  558.  
  559.        t = clock();
  560.  
  561.        q = (double)t / (double)CLOCKS_PER_SEC;
  562.  
  563.        return q;
  564. }
  565. #endif
  566.  
  567. /********************************************/
  568. /* Another UNIX timer using gettimeofday(). */
  569. /* However, getrusage() is preferred.       */
  570. /********************************************/
  571. #ifdef GTODay
  572. #include <sys/time.h>
  573.  
  574. struct timeval tnow;
  575.  
  576. double dtime()
  577. {
  578.    double q;
  579.  
  580.    gettimeofday(&tnow,NULL);
  581.    q = (double)tnow.tv_sec + (double)tnow.tv_usec * 1.0e-6;
  582.  
  583.    return q;
  584. }
  585. #endif
  586.  
  587. /*****************************************************/
  588. /*  Fujitsu UXP/M timer.                             */
  589. /*  Provided by: Mathew Lim, ANUSF, M.Lim@anu.edu.au */
  590. /*****************************************************/
  591. #ifdef UXPM
  592. #include <sys/types.h>
  593. #include <sys/timesu.h>
  594. struct tmsu rusage;
  595.  
  596. double dtime()
  597. {
  598.    double q;
  599.  
  600.    timesu(&rusage);
  601.  
  602.    q = (double)(rusage.tms_utime) * 1.0e-06;
  603.  
  604.    return q;
  605. }
  606. #endif
  607.  
  608. /*------------- End of heapsort.c, say goodnight Becky! --------------*/
  609.  
  610.