lib0028.html

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

</p>
</td><td class="td" align="left">
<p class="table-para">size (smaller)</p>
<p class="table-para">speed (faster)</p>
<p class="table-para">control (you decide when to free)</p>
</td><td class="td" align="left">
<p class="table-para">constrains complexity</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Costs</b>
</p>
</td><td class="td" align="left">
<p class="table-para">complexity</p>
<p class="table-para">memory leaks</p>
<p class="table-para">dangling pointers</p>
</td><td class="td" align="left">
<p class="table-para">larger total memory footprint "comparable" performance</p>
</td>
</tr>
</tbody>
</table>
<a name="355"></a><a name="IDX-165"></a>
<p class="para">Garbage collection is not a simple task. It requires the garbage collector to ferret out memory regions that were allocated but are no longer needed. The bookkeeping procedures are complicated, and this extra complexity translates into executable code. Hence, the total memory image of a program using garbage collection will be larger than one that uses automatic memory management.</p>
<p class="para">Let us look at an example. This way, I cannot be accused of supporting my conclusions with arm waving. Consider the following program that uses traditional memory management facilities:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>

<span style="background-color:d9d9d9">#define KB    16*1024      /* 16KB = 16384 bytes */</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">short j;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>

    <span style="background-color:d9d9d9">for(j=0;j&lt;15;j++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">unsigned char *bdwptr;</span>
        <span style="background-color:d9d9d9">bdwptr = malloc(KB);</span>
        <span style="background-color:d9d9d9">for(i=0;i&lt;KB;i++){ bdwptr[i]='a'; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main*/</span>
</pre>
</div>
<p class="para">Now look at one that uses the BDW collector:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#define GC_NOT_DLL</span>
<span style="background-color:d9d9d9">#include&lt;gc.h&gt;</span>

<span style="background-color:d9d9d9">#define KB    16*1024 /*      16KB = 16384 bytes */</span><a name="356"></a><a name="IDX-166"></a>
<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">short j;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>

    <span style="background-color:d9d9d9">for(j=0;j&lt;15;j++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">unsigned char *bdwptr;</span>
        <span style="background-color:d9d9d9">bdwptr = GC_malloc(KB);</span>
        <span style="background-color:d9d9d9">for(i=0;i&lt;KB;i++){ bdwptr[i]='a'; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main*/</span>
</pre>
</div>
<p class="para">When I built both of these programs on Windows, the executable that used manual memory management calls was 27,648 bytes in size. The executable that used the BDW collector was 76,800 bytes in size. This is over twice the size of the other program. <i class="emphasis">QED.</i>
</p>
<p class="para">With manual memory management, the programmer is responsible for keeping track of allocated memory. None of the bookkeeping manifests itself in the source code as extra instructions. When the programmer wants to release memory, they call <span class="fixed">free()</span>. There is no need to execute a lengthy series of functions to sweep through memory looking for "live" pointers.</p>
<p class="para">In the process of hunting down memory to free, the garbage collector will also find many allocated regions of memory that are still needed, and it will not free these blocks of memory. However, this means that the collector will repeatedly perform unnecessary procedures every time it attempts collection. This suggests to me that these superfluous actions will cause automatic memory collection to be necessarily slower than manual memory management.</p>
<p class="para">Again, I would like to rely on empirical data instead of just appealing to your sense of intuition. Consider the following source code:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>

<span style="background-color:d9d9d9">#define KB 1024</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">short j;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>
    <span style="background-color:d9d9d9">long msecs1,msecs2;</span>
    <span style="background-color:d9d9d9">unsigned char *bdwptr[16*KB];</span><a name="357"></a><a name="IDX-167"></a>
    <span style="background-color:d9d9d9">msecs1 = msecs2 = 0;</span>
    <span style="background-color:d9d9d9">msecsl = GetTickCount();</span>

    <span style="background-color:d9d9d9">for(j=0;j&lt;(16*KB);j++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">bdwptr[j] = malloc(KB);</span>
        <span style="background-color:d9d9d9">for(i=0;i&lt;KB;i++){ (bdwptr[j])[i]='a'; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">msecs2 = GetTickCount();</span>
    <span style="background-color:d9d9d9">printf("msec elapsed=%ld\n",(msecs2-msecsl));</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main*/</span>
</pre>
</div>
<p class="para">Now consider another program that uses the BDW collector:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</span>
<span style="background-color:d9d9d9">#define GC_NOT_DLL</span>
<span style="background-color:d9d9d9">#include&lt;gc.h&gt;</span>

<span style="background-color:d9d9d9">#define KB    1024</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">short j;</span>
    <span style="background-color:d9d9d9">unsigned long i;</span>
    <span style="background-color:d9d9d9">long msecs1,msecs2;</span>

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

    <span style="background-color:d9d9d9">for(j=0;j&lt;(16*1024);j++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">unsigned char *bdwptr;</span>
        <span style="background-color:d9d9d9">bdwptr = GC_malloc(KB);</span>
        <span style="background-color:d9d9d9">for(i=0;i&lt;KB;i++){ bdwptr[i]='a'; }</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">msecs2 = GetTickCount();</span>
    <span style="background-color:d9d9d9">printf("msec elapsed=%ld\n",(msecs2-msecsl));</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main*/</span>
</pre>
</div>
<p class="para">The program that used <span class="fixed">malloc ()</span> completed execution in 427 milliseconds. The program that used the BDW garbage collector took 627 milliseconds to execute. I ran each of these programs several times to prove to myself that this wasn't some kind of fluke.</p>
<a name="358"></a><a name="IDX-168"></a>
<ul class="itemizedlist">
<li class="first-listitem">
<p class="first-para">Manual memory program times: 432, 427, 426, 443, 435, 430, 437, 430</p>
</li>
<li class="listitem">
<p class="first-para">BDW collector program times: 633, 622, 624, 650, 615, 613, 630, 627</p>
</li>
</ul>
<p class="para">Time units are in milliseconds. I could have performed more trials and included an extended statistical analysis of mean values, but I think the results are already pretty clear.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">I ran the previous two programs on a 700MHz Pentium. If you used more recent (GHz) processors, you would still see the same degree of lag.</p>
</td>
</tr>
</table>
<p class="para">Finally, garbage collection takes control away from the developer. The heap manager decides when to free memory back to the heap continuum, not the developer. For example, Java has a <span class="fixed">System.gc()</span> call, which can be used to <i class="emphasis">suggest</i> to the Java virtual machine that it free its surplus memory. However, the JVM itself still has the final say as to when memory is actually set free. This can be a good thing for an engineer who doesn't want to be bothered with details, but it is a bad thing if you actually do want to dictate when an allocated block of memory is released.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">In the end, using explicit or automatic memory management is a <i class="emphasis">religious question,</i> which is to say that deciding to use explicit or automatic methods reflects the fundamental beliefs, values, and priorities of the developer. As I've stated before, there are no perfect solutions. Every approach involves making some sort of concession. Explicit memory management offers speed and control at the expense of complexity. Manual memory management forsakes performance in order to restrain complexity.</p>
</td>
</tr>
</table>
<a></a>
</div>
<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="LiB0027.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0029.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>