mc4.htm

高效c++编程

</PRE>
</UL>

<A NAME="41152"></A>
<P><A NAME="dingp80"></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(80);</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="dingp81"></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="./MC2_FR.HTM#33985" TARGET="_top" onMouseOver = "self.status = 'Link to MEC++ Item 8'; return true" onMouseOut = "self.status = self.defaultStatus">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(81);</SCRIPT>
</NOBR></P><A NAME="41161"></A>
<P><A NAME="dingp82"></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(82);</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="dingp83"></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(83);</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="dingp84"></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(84);</SCRIPT>
</NOBR></P><A NAME="41171"></A>
<P><A NAME="dingp85"></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="#40995" onMouseOver = "self.status = 'Link to MEC++ Item 16'; return true" onMouseOut = "self.status = self.defaultStatus">Item 16</A>).)<SCRIPT>create_link(85);</SCRIPT>
</P><A NAME="41172"></A>
<P><A NAME="dingp86"></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="#41011" onMouseOver = "self.status = 'Link to MEC++ Item 17'; return true" onMouseOut = "self.status = self.defaultStatus">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(86);</SCRIPT>
</NOBR></P>
<!-- SectionName="M19: Understand the origin of temporary objects" -->
<A NAME="41177"></A><DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="#41124">Item 18: Amortize the cost of expected computations</A> &nbsp;&nbsp;<BR>&nbsp;&nbsp;Continue to <A HREF="#45310">Item 20: Facilitate the return value optimization</A></FONT></DIV>
<P><A NAME="dingp87"></A><font ID="mititle">Item 19: &nbsp;Understand the origin of temporary objects.</font><SCRIPT>create_link(87);</SCRIPT>
</P>

<A NAME="72148"></A><A NAME="45491"></A>
<P><A NAME="dingp88"></A>
When programmers speak amongst themselves, they often refer to variables that are needed for only a short while as "temporaries." For example, in this <CODE>swap</CODE> <NOBR>routine,<SCRIPT>create_link(88);</SCRIPT>
</NOBR></P>

<A NAME="45509"></A>
<UL><PRE><A NAME="p99"></A>template&lt;class T&gt;
void swap(T&amp; object1, T&amp; object2)
{
  T temp = object1;
  object1 = object2;
  object2 = temp;
}
</PRE>
</UL>

<A NAME="45510"></A><P><A NAME="dingp89"></A>
it's common to call <CODE>temp</CODE> a "temporary." As far as C++ is concerned, however, <CODE>temp</CODE> is not a temporary at all. It's simply an object local to a <NOBR>function.<SCRIPT>create_link(89);</SCRIPT>
</NOBR></P><A NAME="45520"></A>
<P><A NAME="dingp90"></A>
True temporary objects in C++ are invisible &#151; they don't appear in your source code. They arise whenever a non-heap object is created but not named. Such <I>unnamed</I> objects usually arise in one of two situations: when implicit type conversions are applied to make function calls succeed and when functions return objects. It's important to understand how and why these temporary objects are created and destroyed, because the attendant costs of their construction and destruction can have a noticeable impact on the performance of your <NOBR>programs.<SCRIPT>create_link(90);</SCRIPT>
</NOBR></P><A NAME="45532"></A>
<P><A NAME="dingp91"></A>
Consider first the case in which temporary objects are created to make function calls succeed. This happens when the type of object passed to a function is not the same as the type of the parameter to which it is being bound. For example, consider a function that 	counts the number of occurrences of a character in a <NOBR>string:<SCRIPT>create_link(91);</SCRIPT>
</NOBR></P>

<A NAME="45565"></A>
<UL><PRE>// returns the number of occurrences of ch in str
size_t countChar(const string&amp; str, char ch);
<A NAME="45544"></A>
char buffer[MAX_STRING_LEN];
char c;
<A NAME="45548"></A>
// read in a char and a string; use setw to avoid
// overflowing buffer when reading the string
cin &gt;&gt; c &gt;&gt; setw(MAX_STRING_LEN) &gt;&gt; buffer;
<A NAME="45578"></A>
cout &lt;&lt; "There are " &lt;&lt; countChar(buffer, c)
     &lt;&lt; " occurrences of the character " &lt;&lt; c
     &lt;&lt; " in " &lt;&lt; buffer &lt;&lt; endl;
</PRE>
</UL>

<A NAME="45579"></A>
<P><A NAME="dingp92"></A>
Look at the call to <CODE>countChar</CODE>. The first argument passed is a <CODE>char</CODE> array, but the corresponding function parameter is of type <CODE>const</CODE> <CODE>string&amp;</CODE>. This call can succeed only if the type mismatch can be eliminated, and your compilers will be happy to eliminate it by creating a temporary object of type <CODE>string</CODE>. That temporary object is initialized by calling the <CODE>string</CODE> constructor with <CODE>buffer</CODE> as its argument. The <CODE>str</CODE> parameter of <CODE>countChar</CODE> is then bound to this temporary <CODE>string</CODE> object. When <CODE>countChar</CODE> returns, the temporary object is automatically <NOBR>destroyed.<SCRIPT>create_link(92);</SCRIPT>
</NOBR></P><A NAME="45607"></A>
<A NAME="p100"></A><P><A NAME="dingp93"></A>
Conversions such as these are convenient (though dangerous &#151; see <A HREF="./MC2_FR.HTM#5970" TARGET="_top" onMouseOver = "self.status = 'Link to MEC++ Item 5'; return true" onMouseOut = "self.status = self.defaultStatus">Item 5</A>), but from an efficiency point of view, the construction and destruction of a temporary <CODE>string</CODE> object is an unnecessary expense. There are two general ways to eliminate it. One is to redesign your code so conversions like these can't take place. That strategy is examined in <A HREF="./MC2_FR.HTM#5970" TARGET="_top" onMouseOver = "self.status = 'Link to MEC++ Item 5'; return true" onMouseOut = "self.status = self.defaultStatus">Item 5</A>. An alternative tack is to modify your software so that the conversions are unnecessary. <A HREF="#41187" onMouseOver = "self.status = 'Link to MEC++ Item 21'; return true" onMouseOut = "self.status = self.defaultStatus">Item 21</A> describes how you can do <NOBR>that.<SCRIPT>create_link(93);</SCRIPT>
</NOBR></P><A NAME="45763"></A>
<P><A NAME="dingp94"></A>
These conversion