mi18.htm

一个非常适合初学者入门的有关c++的文档

<P><A NAME="dingp11"></A>
Excuse me? You say you don't worry about such low-level things as disk controllers or CPU caches? No problem. Prefetching can yield dividends for even one as high-level as you. Imagine, for example, you'd like to implement a template for dynamic arrays, i.e., arrays that start with a size of one and automatically extend themselves so that all nonnegative indices are <NOBR>valid:<SCRIPT>create_link(11);</SCRIPT>
</NOBR></P>
<A NAME="41148"></A>
<UL><PRE>
template&lt;class T&gt;                            // template for dynamic
class DynArray { ... };                      // array-of-T classes
<A NAME="41149"></A>
DynArray&lt;double&gt; a;                          // at this point, only a[0]
                                             // is a legitimate array
                                             // element
<A NAME="41150"></A>
a[22] = 3.5;                                 // a is automatically
                                             // extended: valid indices
                                             // are now 0-22
<A NAME="41151"></A>
a[32] = 0;                                   // a extends itself again;
                                             // now a[0]-a[32] are valid
</PRE>
</UL>
<A NAME="41152"></A>

<P><A NAME="dingp12"></A>How does a <CODE>DynArray</CODE> object go about extending itself when it needs to? A straightforward strategy would be to allocate only as much additional memory as needed, something like <NOBR>this:<SCRIPT>create_link(12);</SCRIPT>
</NOBR></P>

<A NAME="41154"></A>
<UL><PRE><A NAME="p97"></A>template&lt;class T&gt;
T&amp; DynArray&lt;T&gt;::operator[](int index)
{
  if (index &lt; 0) {
    <i>throw an exception;</i>                     // negative indices are
  }                                         // still invalid
<A NAME="41155"></A>
  if (index &gt; <i>the current maximum index value</i>) {
    <I>call new to allocate enough additional memory so that
    index is valid;</I>
  }
<A NAME="41156"></A>
  return <I>the indexth element of the array;</I>
}
</PRE>
</UL>
<A NAME="60235"></A>
<P><A NAME="dingp13"></A>
This approach simply calls <CODE>new</CODE> each time it needs to increase the size of the array, but calls to <CODE>new</CODE> invoke <CODE>operator</CODE> <CODE>new</CODE> (see <A HREF="./MI8_FR.HTM#33985" TARGET="_top">Item 8</A>), and calls to <CODE>operator</CODE> <CODE>new</CODE> (and <CODE>operator</CODE> <CODE>delete</CODE>) are usually expensive. That's because they typically result in calls to the underlying operating system, and system calls are generally slower than are in-process function calls. As a result, we'd like to make as few system calls as <NOBR>possible.<SCRIPT>create_link(13);</SCRIPT>
</NOBR></P><A NAME="41161"></A>
<P><A NAME="dingp14"></A>
An over-eager evaluation strategy employs this reasoning: if we have to increase the size of the array now to accommodate index <i>i</i>, the locality of reference principle suggests we'll probably have to increase it in the future to accommodate some other index a bit larger than <i>i</i>. To avoid the cost of the memory allocation for the second (anticipated) expansion, we'll increase the size of the <CODE>DynArray</CODE> now by <I>more</I> than is required to make <I>i</I> valid, and we'll hope that future expansions occur within the range we have thereby provided for. For example, we could write <CODE>DynArray</CODE>::<CODE>operator[]</CODE> like <NOBR>this:<SCRIPT>create_link(14);</SCRIPT>
</NOBR></P>

<A NAME="41162"></A>
<UL><PRE>template&lt;class T&gt;
T&amp; DynArray&lt;T&gt;::operator[](int index)
{
  if (index &lt; 0) <i>throw an exception;</i>
<A NAME="41163"></A>
  if (index &gt; <i>the current maximum index value</i>) {
    int diff = index - <I>the current maximum index value;</I>
<A NAME="41164"></A>
    <I>call new to allocate enough additional memory so that
    index+diff is valid;</I>
  }
<A NAME="41165"></A>
  return <I>the indexth element of the array;</I>
}
</PRE>
</UL>
<A NAME="41166"></A>

<P><A NAME="dingp15"></A>
This function allocates twice as much memory as needed each time the array must be extended. If we look again at the usage scenario we saw earlier, we note that the <CODE>DynArray</CODE> must allocate additional memory only once, even though its logical size is extended <NOBR>twice:<SCRIPT>create_link(15);</SCRIPT>
</NOBR></P>

<A NAME="41167"></A>
<UL><PRE><A NAME="p98"></A>
DynArray&lt;double&gt; a;                          // only a[0] is valid
<A NAME="41168"></A>
a[22] = 3.5;                                 // new is called to expand
                                             // a's storage through
                                             // index 44; a's logical
                                             // size becomes 23
<A NAME="41169"></A>
a[32] = 0;                                   // a's logical size is
                                             // changed to allow a[32],
                                             // but new isn't called
</PRE>
</UL>

<A NAME="41170"></A>
<P><A NAME="dingp16"></A>
If <CODE>a</CODE> needs to be extended again, that extension, too, will be inexpensive, provided the new maximum index is no greater than <NOBR>44.<SCRIPT>create_link(16);</SCRIPT>
</NOBR></P><A NAME="41171"></A>
<P><A NAME="dingp17"></A>
There is a common theme running through this Item, and that's that greater speed can often be purchased at a cost of increased memory usage. Keeping track of running minima, maxima, and averages requires extra space, but it saves time. Caching results necessitates greater memory usage but reduces the time needed to regenerate the results once they've been cached. Prefetching demands a place to put the things that are prefetched, but it reduces the time needed to access those things. The story is as old as Computer Science: you can often trade space for time. (Not always, however. Using larger objects means fewer fit on a virtual memory or cache page. In rare cases, making objects bigger <I>reduces</I> the performance of your software, because your paging activity increases, your cache hit rate decreases, or both. How do you find out if you're suffering from such problems? You profile, profile, profile (see <A HREF="./MI16_FR.HTM#40995" TARGET="_top">Item 16</A>).)<SCRIPT>create_link(17);</SCRIPT>
</P><A NAME="41172"></A>
<P><A NAME="dingp18"></A>
The advice I proffer in this Item &#151; that you amortize the cost of anticipated computations through over-eager strategies like caching and prefetching &#151; is not contradictory to the advice on lazy evaluation I put forth in <A HREF="./MI17_FR.HTM#41011" TARGET="_top">Item 17</A>. Lazy evaluation is a technique for improving the efficiency of programs when you must support operations whose results are<I> not always</I> needed. Over-eager evaluation is a technique for improving the efficiency of programs when you must support operations whose results are <I>almost always</I> needed or whose results are often needed more than once. Both are more difficult to implement than run-of-the-mill eager evaluation, but both can yield significant performance improvements in programs whose behavioral characteristics justify the extra programming <NOBR>effort.<SCRIPT>create_link(18);</SCRIPT>
</NOBR></P>
<DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="./MI17_FR.HTM" TARGET="_top">Item 17: Consider using lazy evaluation</A> &nbsp;&nbsp;<BR>&nbsp;&nbsp;Continue to <A HREF="./MI19_FR.HTM" TARGET="_top">Item 19: Understand the origin of temporary objects</A></FONT></DIV>

<HR>
<A NAME="dingp19"></A>
<sup>6</sup> <A NAME="81381"></A>In July 1995, the <NOBR><FONT COLOR="#FF0000" SIZE="-2"><B>&deg;</B></FONT><A HREF="http://www.awl.com/cseng/cgi-bin/cdquery.pl?name=committee" onMouseOver="self.status='ISO/ANSI Standardization Committee Home Page'; return true" onMouseOut="self.status=self.defaultStatus" target="_top">ISO/ANSI</NOBR> committee standardizing C++</A> added a requirement that STL iterators support the "<CODE>-&gt;</CODE>" operator, so <CODE>it-&gt;second</CODE> should now work. Some STL implementations fail to satisfy this requirement, however, so <CODE>(*it).second</CODE> is still the more portable construct.<SCRIPT>create_link(19);</SCRIPT>
<BR>
<A HREF="#81306">Return</A>

</BODY>
</HTML>