lib0028.html

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

    <span style="background-color:d9d9d9">free(cptr1); /* whoops! */</span><a name="349"></a><a name="IDX-160"></a>
    <span style="background-color:d9d9d9">cptr2 = malloc(10) ;</span>
    <span style="background-color:d9d9d9">printf("address=%p\n", cptr2) ;</span>

    <span style="background-color:d9d9d9">cptr2[0]='c'; cptr2[1]='d'; cptr2[2]=0;</span>
    <span style="background-color:d9d9d9">printf("cptr1=%s\n",cptr1);</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">This program will produce the following output when it is run:</p>
<div class="informalexample">
<pre class="literallayout">
address=00770670
cptrl=ab
address=007706A0
cptr1=
</pre>
</div>
<p class="last-para">As expected, the contents of memory pointed to by <span class="fixed">cptr1</span> were corrupted after it was prematurely set free. Imagine what would happen with a dangling pointer to a database handle in a large ERP application...</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Automatic Memory Management</h4>
<p class="first-para">Automatic memory management, also called <i class="emphasis">garbage collection,</i> takes care of all the memory recycling details. This allows the programmer to focus on domain-specific problem solving. An analyst who is writing a purchase-order system already has enough complexity to deal with just trying to get the logic of the purchase-order application to function. Having to manage low-level details like memory only makes the job more difficult.</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">Scientists like George Miller have claimed that the average human can only keep track of about seven things at any point in time. By forcing the developer to keep track of memory recycling, the number of things the developer has to juggle increases. Garbage collection is an effective solution to this problem.</p>
<p class="para">Don't take my word for it. Here is what Bertrand Meyer, the inventor of Eiffel, has to say:</p>
<p class="last-para">"Manual memory management &mdash; that is to say, the absence of automatic garbage collection &mdash; suffers from two fatal flaws: it is dangerous (as it is all too easy to make a mistake, causing errors that are often missed during testing and arise only when the system goes operational, usually in erratic and hard-to-reproduce conditions); and it is extremely tedious, forcing the developer to concentrate on mundane yet complex tasks of bookkeeping and garbage collection instead of working on their application. These deficiencies are bad enough to cancel out any benefit that is claimed for the application of object-oriented techniques."</p>
</td>
</tr>
</table>
<p class="para">A significant benefit of using a garbage collector is that the recycling problems that plague manual memory management are eliminated. Memory leaks and dangling pointers do not exist in a program that <a name="350"></a><a name="IDX-161"></a>uses automatic memory management. Automatic memory takes care of freeing allocated memory so the programmer isn't given the opportunity to make a recycling error.</p>
<p class="para">Garbage collection was entirely theoretical until 1959, when Dan Edwards implemented the first garbage collection facilities. It just so happened that Dan was involved with John McCarthy in the development of the LISP programming language. LISP, which was intended for algebraic LISt Processing, started off as a notational concept that evolved into a computer language. When compared to other programming languages that existed during its development, LISP was way ahead of its time.</p>
<p class="para">There were, however, problems with LISP's performance, and this was probably the price that LISP paid for its advanced features. The garbage collection schemes in early implementations of LISP were notoriously slow. One response to this problem was to push basic operations down to the hardware level. There were companies that attempted to follow this route, like Symbolics, which sold LISP machines. LISP machines were manufactured in the 1970s and 1980s. The idea, unfortunately, never really caught on. In the mid-1990s, Symbolics went bankrupt.</p>
<p class="last-para">There are a number of programming environments that support automatic memory management. This includes popular virtual machines like Java's and more obscure run times, like the one that Smalltalk utilizes. There are even garbage collectors than can be plugged into native code via user mode libraries. This brings us to the Boehm-Demers-Weiser conservative garbage collector.</p>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Example: The BDW Conservative Garbage Collector</h4>
<p class="first-para">The Boehm-Demers-Weiser (BDW) conservative garbage collector is a drop-in replacement for <span class="fixed">malloc()</span> that eliminates the need to call <span class="fixed">free()</span>. This allows old, moldy C programs to have their memory management scheme upgraded with minimal effort. The only catch is that the BDW collector has to be ported, which is to say that the collector has platform dependencies. If you are working on an obscure platform, like Trusted Xenix, you will not be able to use it.</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">The BDW garbage collector can also be modified to detect memory leaks.</p>
</td>
</tr>
</table>
<a name="351"></a><a name="IDX-162"></a>
<p class="para">You can download a copy of the distribution and view additional information by visiting <a target="_top" class="url" href="http://reality.sgi.com/boehm/gc.html"><span class="fixed">http://reality.sgi.com/boehm/gc.html</span></a>.</p>
<p class="para">The BDW distribution has been ported to a number of different platforms. Each one has its own makefile. On Windows, the BDW garbage collector can be built into a single-threaded, static library (<span class="fixed">gc.lib</span>) using the following command:</p>
<div class="informalexample">
<pre class="literallayout">
       C:\DOCS\bdw\gc6.0&gt;nmake /F NT_MAKEFILE
</pre>
</div>
<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">You will need to make sure that the necessary environmental variables have been set up. You can do so by executing the <span class="fixed">VCVARS32.BAT</span> batch file before you invoke <span class="fixed">NMAKE</span>.</p>
</td>
</tr>
</table>
<p class="para">Here is a short example to demonstrate the BDW collector in action:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/* &mdash;testbdw.c&mdash; */</span>

<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">unsigned long oldmem=0;</span>

<span style="background-color:d9d9d9">void printMemSize()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long nfree;</span>
    <span style="background-color:d9d9d9">nfree = GC_get_free_bytes();</span>

    <span style="background-color:d9d9d9">printf("total heap=%71u\t",GC_get_heap_size());</span>
    <span style="background-color:d9d9d9">printf("free bytes=%7lu\t", nfree);</span>
    <span style="background-color:d9d9d9">if (oldmem!=0)</span>
    <span style="background-color:d9d9d9">{</span>
         <span style="background-color:d9d9d9">printf("change=%ld", (oldmem-nfree));</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">printf("\n");</span>
    <span style="background-color:d9d9d9">oldmem = nfree;</span>
    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}/*end printHeapSize*/</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><a name="352"></a><a name="IDX-163"></a>
        <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">printMemSize();</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">printf("\nforcing collection\n");</span>
    <span style="background-color:d9d9d9">GC_gcollect();</span>
    <span style="background-color:d9d9d9">printMemSize();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end main*/</span>
</pre>
</div>
<p class="para">In the previous code example, I reuse the <span class="fixed">bdwptr</span> pointer repeatedly in an effort to create a memory leak. If you compile and run this program on Windows, you will get output like the following:</p>
<div class="informalexample">
<pre class="literallayout">
total heap=  65536    free bytes=  45056
total heap=  65536    free bytes=  24576   change=20480
total heap=  65536    free bytes=   4096   change=20480
total heap=  65536    free bytes=  24576   change=-20480
total heap=  65536    free bytes=   4096   change=20480
total heap= 131072    free bytes=  49152   change=-45056
total heap= 131072    free bytes=  28672   change=20480
total heap= 131072    free bytes=   8192   change=20480
total heap= 131072    free bytes=  90112   change=-81920
total heap= 131072    free bytes=  69632   change=20480
total heap= 131072    free bytes=  49152   change=20480
total heap= 131072    free bytes=  28672   change=20480
total heap= 131072    free bytes=   8192   change=20480
total heap= 131072    free bytes=  90112   change=-81920
total heap= 131072    free bytes=  69632   change=20480

forcing collection
total heap= 131072      free bytes= 110592
change=-40960
Press any key to continue
</pre>
</div>
<p class="para">As you can see, the amount of free memory does not just descend downward, as it normally would if you were using <span class="fixed">malloc()</span>. Instead, it increases a couple of times, which indicates that garbage collection has occurred. At the end of the sample code, I explicitly force collection to illustrate this.</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">You will need to make sure that the linker includes <span class="fixed">gc.lib</span> in its list of libraries. Also, I could only get this to work with the <i class="emphasis">release</i> version of Visual Studio's libraries. Trying to link <span class="fixed">gc.lib</span> to Microsoft's debug libraries gave my linker a fit.</p>
</td>
</tr>
</table>
<a name="353"></a><a name="IDX-164"></a>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Manual Versus Automatic?</h4>
<p class="first-para">I cannot think of a better way to start a heated argument at an engineering meeting than to bring up this topic. Within minutes, people will go from calm and deliberate to emotional and violent. Although I have my own opinion, I am going to back up my conclusions with source code that you can test yourself. Nothing beats empirical evidence.</p>
<p class="para">Both explicit memory management and automatic memory management involve explicit allocation of memory; the difference between the two methods is how they deal with memory that isn't needed anymore and must be discarded back into the heap.</p>
<p class="para">Garbage collection advocates claim that the energy committed to dealing with memory leaks and dangling pointers would be better spent on building a garbage collection mechanism. This is a very powerful argument &mdash; if the performance hit from garbage collection bookkeeping is not noticeable.</p>
<p class="para">This is a big "if."</p>
<p class="para">Early garbage collection implementations like the one for LISP were notoriously slow, sometimes accounting for almost 50% of execution time. Not to mention that explicit memory management proponents will argue that the emergence of tools that detect memory leaks have eliminated traditional problems. Thus, performance is a key issue.</p>
<p class="para">Garbage collection supporters will jump up and down in an effort to demonstrate that the performance problems that plagued LISP are no longer an issue. It is as though they are personally insulted that you are questioning their position.</p>
<p class="para">Let's try to avoid arm waving and examine some published results.</p>
<p class="para">I found two articles that take a good look at the Boehm-Demers-Weiser conservative garbage collector. The first, a 1992 paper by Benjamin Zorn, demonstrates that the BDW collector is, on average, about 20% slower than the fastest explicit memory manager in each experimental trial. The second, published by <a href="LiB0031.html#416" target="_parent" class="chapterjump">Detlefs et. al. in 1993</a>, indicates that the BDW collector is, on average, about 27% slower than the fastest explicit memory manager in each experimental trial. In these articles, this was what the authors claimed was the "comparable" performance of the BDW garbage collector.</p>
<p class="para">
<a class="internaljump" href="#ch03table04">Table 3.4</a> presents a comparison of manual and automatic memory management.</p>
<a name="354"></a><a name="ch03table04"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 3.4</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">&nbsp;</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Manual Memory</b> <b class="bold">Management</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Automatic Memory</b> <b class="bold">Management</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Benefits</b>