lib0027.html

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

<span style="background-color:d9d9d9">; Line 23</span>
       <span style="background-color:d9d9d9">mov    BYTE PTR _arr3$35[ebp], 99    ; 00000063H $L34:</span>
<span style="background-color:d9d9d9">; Line 25</span>
       <span style="background-color:d9d9d9">mov    esp, ebp</span>
       <span style="background-color:d9d9d9">pop    ebp</span>
       <span style="background-color:d9d9d9">ret    0</span>
<span style="background-color:d9d9d9">_main  ENDP</span>
<span style="background-color:d9d9d9">_TEXT  ENDS</span>
<span style="background-color:d9d9d9">END</span>
</pre>
</div>
<p class="para">The compiler places all of the local variables, even the ones that may not be used, on the procedure's activation record. We end up with an activation record like the one in <a class="internaljump" href="#ch03fig10">Figure 3.10</a>. Notice how the compiler pads entries so that they always begin on an address that is a multiple of 4 bytes. This is particularly true for the <span class="fixed">arr2[]</span> and <span class="fixed">arr3[]</span> arrays.</p>
<div class="figure">
<a name="328"></a><a name="ch03fig10"></a><span class="figuremediaobject"><a href="images/fig176%5F01%5F0%2Ejpg" NAME="IMG_59" target="_parent"><img src="images/fig176_01.jpg" height="277" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 3.10</span></span>
</div>
<a name="329"></a><a name="IDX-149"></a>
<p class="para">The alternative to the all-at-once approach is to give each sub-block its own private activation record. In the "<a class="internaljump" href="#ch03lev3sec1">Activation Records</a>" section, we saw how procedure-based scope was implemented. By using the stack, we were able to create storage that had a scope and life span limited to the function. By using this same type of technique on a smaller scale, we can implement visibility and life span on a block-by-block basis.</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 a way, stacks are really about storage life span. Visibility restrictions follow naturally as a result of life span constraints. Recall that stacks are good for situations in which you need to do, and then undo, an operation. This makes them perfect for creating temporary storage. The limited visibility is more of a side effect of the limited life span. Once a variable has been popped off the stack, it is gone and any reference to it can yield garbage.</p>
</td>
</tr>
</table>
<p class="para">The easiest way to think of a block of code is like a stripped-down type of function that has no return value and no return address. It only has local variables. <a class="internaljump" href="#ch03table01">Table 3.1</a> presents a basic comparison of functions and code blocks.</p>
<a name="330"></a><a name="ch03table01"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 3.1</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">Saved</b> <b class="bold">State</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Return</b> <b class="bold">Value</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Arguments</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Return</b> <b class="bold">Address</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Variables</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Function</b>
</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Sub-block</b>
</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">no</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td><td class="td" align="left">
<p class="table-para">no</p>
</td><td class="td" align="left">
<p class="table-para">yes</p>
</td>
</tr>
</tbody>
</table>
<p class="para">As you can see from the table, a code block has saved program state information and local variables in its stack frame. Local variables declared outside the block but accessed inside the block can be treated as arguments. <a class="internaljump" href="#ch03fig11">Figure 3.11</a> displays a comparison of the stack frames used by a function and a code block.</p>
<div class="figure">
<a name="331"></a><a name="ch03fig11"></a><span class="figuremediaobject"><a href="images/fig177%5F01%5F0%2Ejpg" NAME="IMG_60" target="_parent"><img src="images/fig177_01.jpg" height="147" width="227" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 3.11</span></span>
</div>
<a name="332"></a><a name="IDX-150"></a>
<div class="qandaset">
<table border="0" cellpadding="0">
<tr class="qandaentry">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a name="LiB15"><b>1.&nbsp;</b></a>
</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">
</p>
</td><td class="td" valign="top" width="8%">
<p class="first-para">
<a href="#LiB13"><img src="images/question.gif" height="24" width="24" alt="" border="0"></a>
</p>
</td>
</tr>
<tr class="qandaentry">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a name="LiB16"><b>2.&nbsp;</b></a>
</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">What are the trade-offs between the all-at-once approach and the additional stack frame approach?</p>
</td><td class="td" valign="top" width="8%">
<p class="first-para">
<a href="#LiB14"><img src="images/question.gif" height="24" width="24" alt=" The extra stack frame technique requires that stack manipulation be performed every time a block is entered or exited. If a section of code has a heavily nested set of blocks, this translates into a lot of extra push and pop operations. This means the extra stack frame tactic will create an executable that is larger and slower because more instructions will need to be executed. Another downside of using the all-at-once tactic is that it requires a lot of storage overhead. Space in the activation record will be reserved even if a variable is not used. If a function has several different possible execution paths, a lot of storage is wasted.  Table 3.2 summarizes a comparison of these two techniques.      All-at-once Allocation   Extra Stack Frames    Speed  faster slower  Stack memory usage  more less  Executable size  smaller larger In the final analysis, real estate on the stack is relatively cheap compared to execution speed, which is why most compilers opt for the all-at-once approach. " border="0"></a>
</p>
</td>
</tr>
</table>
<p class="bold">Answers</p>
<table border="0" cellpadding="0">
<tr class="qandaentry-answer">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a class="internaljump" name="answer.nr-qandaentry.034B48CB-24A8-4648-B92C-973BAEE2FE4E" href="#LiB15"><b>1.</b></a>&nbsp;</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">
</p>
</td>
</tr>
<tr class="qandaentry-answer">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a class="internaljump" name="answer.nr-qandaentry.4108F94E-8740-47CE-A1A0-2FC7E7C02C50" href="#LiB16"><b>2.</b></a>&nbsp;</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">
<p class="first-para">The extra stack frame technique requires that stack manipulation be performed every time a block is entered or exited. If a section of code has a heavily nested set of blocks, this translates into a lot of extra push and pop operations. This means the extra stack frame tactic will create an executable that is larger and slower because more instructions will need to be executed.</p>
<p class="para">Another downside of using the all-at-once tactic is that it requires a lot of storage overhead. Space in the activation record will be reserved even if a variable is not used. If a function has several different possible execution paths, a lot of storage is wasted.</p>
<p class="para">
<a class="internaljump" href="#ch03table02">Table 3.2</a> summarizes a comparison of these two techniques.</p>
<a name="333"></a><a name="ch03table02"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 3.2</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">All-at-once Allocation</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Extra Stack Frames</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Speed</b>
</p>
</td><td class="td" align="left">
<p class="table-para">faster</p>
</td><td class="td" align="left">
<p class="table-para">slower</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Stack memory usage</b>
</p>
</td><td class="td" align="left">
<p class="table-para">more</p>
</td><td class="td" align="left">
<p class="table-para">less</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<b class="bold">Executable size</b>
</p>
</td><td class="td" align="left">
<p class="table-para">smaller</p>
</td><td class="td" align="left">
<p class="table-para">larger</p>
</td>
</tr>
</tbody>
</table>
<p class="last-para">In the final analysis, real estate on the stack is relatively cheap compared to execution speed, which is why most compilers opt for the all-at-once approach.</p>
</p>
</td>
</tr>
</table>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">Static or Dynamic?</h4>
<p class="first-para">The stack is a hybrid between a purely static and a purely dynamic form of storage. It is not purely static because the amount of occupied storage on a stack varies with each function call. Each time a function is invoked, a new activation record is pushed on to the stack. When a functio