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