lib0035.html

Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag

struct TestData td;
td.dptr = p;
td.lptr = x;
td.samplesize = 1024;
td.length = 8;<a name="444"></a><a name="IDX-220"></a>
PerformanceTest pt = PerformanceTest(&amp;td);
printf("milli-seconds=%lu\n",pt.runTest());
</pre>
</div>
<p class="para">The <span class="fixed">PerformanceTest</span> class, mentioned in the previous code snippet, has the following implementation:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* --perform.cpp-- */</span>

<span style="background-color:d9d9d9">/*holds setup data to pass to constructor*/</span>

<span style="background-color:d9d9d9">struct TestData</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">double *dptr;                 // probability array</span>
    <span style="background-color:d9d9d9">unsigned long *lptr;          // allocation sizes</span>
    <span style="background-color:d9d9d9">unsigned long samplesize;     // #malloc() calls</span>
    <span style="background-color:d9d9d9">unsigned long length;         // size of arrays</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">class PerformanceTest</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">public:</span>
    <span style="background-color:d9d9d9">PerformanceTest(struct TestData *tdptr);</span>
    <span style="background-color:d9d9d9">unsigned long runTest();</span>

    <span style="background-color:d9d9d9">private:</span>
    <span style="background-color:d9d9d9">unsigned long nAllocations;   // #of malloc() calls to make</span>
    <span style="background-color:d9d9d9">unsigned long arraySize;      // size of P(x) and x arrays</span>
    <span style="background-color:d9d9d9">double *p;                    // P(x) = probability for X=x</span>
    <span style="background-color:d9d9d9">unsigned long *x;             // X   = # bytes allocated</span>

    <span style="background-color:d9d9d9">double getU();</span>
    <span style="background-color:d9d9d9">unsigned long getRandomVariate();</span>
    <span style="background-color:d9d9d9">void getAllocArray(unsigned long *lptr);</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">PerformanceTest::PerformanceTest(struct TestData *tdptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">p = (*tdptr).dptr;</span>
    <span style="background-color:d9d9d9">x = (*tdptr).lptr;</span>
    <span style="background-color:d9d9d9">nAllocations = (*tdptr).samplesize;</span>
    <span style="background-color:d9d9d9">arraySize = (*tdptr).length;</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end constructor -------------------------------------------*/</span>


<span style="background-color:d9d9d9">double double PerformanceTest::getU()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">return(((double)rand())/((double)RAND_MAX));</span>

<span style="background-color:d9d9d9">}/*end getU--------------------------------------------------*/</span><a name="445"></a><a name="IDX-221"></a>

<span style="background-color:d9d9d9">unsigned long PerformanceTest::getRandomVariate()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">double U;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>
    <span style="background-color:d9d9d9">double total;</span>

    <span style="background-color:d9d9d9">U = getU();</span>

    <span style="background-color:d9d9d9">for(i=0,total=p[0];i&lt;=arraySize-2;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">if(U&lt;total){ return(x[i]); }</span>
        <span style="background-color:d9d9d9">total = total + p[i+1];</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">return(x[arraySize-1]);</span>

    <span style="background-color:d9d9d9">/*</span>
    <span style="background-color:d9d9d9">the above is a cleaner/slower way of doing something like:</span>
    <span style="background-color:d9d9d9">if(U &lt; p[0]){return(x[0]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[1])){return(x[1]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[l]+p[2])){return(x[2]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[1]+p[2]+p[3])){return(x[3]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[1]+p[2]+p[3]+p[4])){return(x[4]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[l]+p[2]+p[3]+p[4]+p[5])){return(x[5]);}</span>
    <span style="background-color:d9d9d9">else if(U &lt;(p[0]+p[l]+p[2]+p[3]+p[4]+p[5]+p[6]))</span>
               <span style="background-color:d9d9d9">{return (x[6]);}</span>
    <span style="background-color:d9d9d9">else{ return(x[7]);}</span>
    <span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">}/*end getRandomVariate---------------------------------------*/</span>

<span style="background-color:d9d9d9">void PerformanceTest::getAllocArray(unsigned long *lptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nAllocations;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">lptr[i]=getRandomVariate();</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end getAllocationArray-------------------------------------*/</span>

<span style="background-color:d9d9d9">unsigned long PerformanceTest::runTest()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long *allocs;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>
    <span style="background-color:d9d9d9">unsigned long ticks1,ticks2;</span><a name="446"></a><a name="IDX-222"></a>
    <span style="background-color:d9d9d9">char **addr;    /*pointer to an array of pointers*/</span>

    <span style="background-color:d9d9d9">/*create array of address holders to stockpile</span>
     <span style="background-color:d9d9d9">malloc() returns*/</span>

    <span style="background-color:d9d9d9">addr = (char **)malloc(sizeof(char *)*nAllocations);</span>
    <span style="background-color:d9d9d9">if(addr==NULL)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">printf("could not allocate address repository\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">/*create stream of allocation values*/</span>

    <span style="background-color:d9d9d9">allocs = (unsigned long *)malloc(sizeof(long)*nAllocations);</span>
    <span style="background-color:d9d9d9">if(allocs==NULL)</span>
    <span style="background-color:d9d9d9">{</span>

        <span style="background-color:d9d9d9">printf("could not allocate malloc() request stream\n");</span>
        <span style="background-color:d9d9d9">exit (1);</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">getAllocArray(allocs);</span>

    <span style="background-color:d9d9d9">/*start timer and do some work*/</span>

    <span style="background-color:d9d9d9">initMemMgr(1024*1024);</span>

    <span style="background-color:d9d9d9">printf("PerformanceTest::runTest(): time whistle blown\n");</span>

    <span style="background-color:d9d9d9">ticks1 = GetTickCount();</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;nAllocations;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">addr[i] = (char *)newMalloc(allocs[i]);</span>
        <span style="background-color:d9d9d9">if(addr[i]==NULL)</span>
        <span style="background-color:d9d9d9">{</span>
            <span style="background-color:d9d9d9">printf("mallco()=addr[%lu]=%lu failed\n",i,addr[i]);</span>
            <span style="background-color:d9d9d9">exit (1);</span>
        <span style="background-color:d9d9d9">}</span>
     <span style="background-color:d9d9d9">}</span>

     <span style="background-color:d9d9d9">for(i=0;i&lt;nAllocations;i++)</span>
     <span style="background-color:d9d9d9">{</span>
         <span style="background-color:d9d9d9">newFree(addr[i]);</span>
     <span style="background-color:d9d9d9">}</span>

     <span style="background-color:d9d9d9">ticks2 = GetTickCount();</span>

     <span style="background-color:d9d9d9">printf("PerformanceTest::runTest(): race has ended\n");</span>

     <span style="background-color:d9d9d9">closeMemMgr();</span><a name="447"></a><a name="IDX-223"></a>
     <span style="background-color:d9d9d9">free(addr);</span>
     <span style="background-color:d9d9d9">free(allocs);</span>

     <span style="background-color:d9d9d9">return(ticks2-ticks1);</span>

<span style="background-color:d9d9d9">}/*end runTest---------------------------------------------------*/</span>
</pre>
</div>
<p class="para">Depending on the source files that I <span class="fixed">#include</span>, different versions of <span class="fixed">newMalloc()</span> and <span class="fixed">newFree()</span> can be used. I can also replace <span class="fixed">newMalloc()/newFree()</span> with the native <span class="fixed">malloc()/free()</span> implementations to get a baseline measurement.</p>
<p class="para">You may notice that I defer time measurement until the last possible moment. I don't start measuring clock ticks until the instant directly before the memory allocation calls start occurring. This is because I don't want to include the time that was spent loading the application, constructing input values, and executing shutdown code.</p>
<p class="para">I will admit that my testing code is synthetic, but my crude approach is motivated by a need to keep my discussion limited. You could fill up several books with an explanation and analysis of more sophisticated performance testing methods. Per my initial design goal (keep it simple ... stupid), I have opted for the path of least resistance.</p>
<p class="para">There are a number of industrial-strength benchmark suites that have been built to provide a more accurate picture of how well a processor or application performs. For example, the TOP500 Supercomputer Sites portal (<a target="_top" class="url" href="http://www.top500.org"><span class="fixed">http://www.top500.org</span></a>) uses the LINPACK Benchmark to rank high-performance installations. The LINPACK Benchmark tests the horsepower of a system by asking it to solve a dense set of linear equations.</p>
<p class="last-para">SPEC, the Standard Performance Evaluation Corporation, is a nonprofit corporation registered in California that aims to "establish, maintain, and endorse a standardized set of relevant benchmarks that can be applied to the newest generation of high-performance computers" (quoted from SPEC's bylaws; see <a target="_top" class="url" href="http://www.spec.org">http://www.spec.org</a>). SPEC basically sells a number of benchmark suites that can be used to collect performance metrics. For example, SPEC sells a CPU2000 V1.2 package that can be used to benchmark processors. SPEC also sells a JVM98 suite to test the performance of Java virtual machines. If you have $1,800 to spare, you can purchase SPEC's MAIL2000 mail server benchmark suite.</p>
<a></a>
</div>
<a></a>
</div>
</div>
</div>
</div>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<td><div STYLE="MARGIN-LEFT: 0.15in;">
<a href="toc.html"><img src="images/teamlib.gif" width="62" height="15" border="0" align="absmiddle"  alt="Team LiB"></a></div></td>
<td valign="top" class="v2" align="right"><div STYLE="MARGIN-RIGHT: 0.15in"><a href="LiB0034.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0036.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>