📄 mc4.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Frameset//EN" "http://www.w3.org/TR/REC-html40/frameset.dtd">
<HTML>
<HEAD>
<TITLE>More Effective C++ | Chapter 4: Efficiency</TITLE>
<LINK REL=STYLESHEET HREF=../INTRO/ECMEC.CSS>
<SCRIPT LANGUAGE="Javascript" SRC="../JAVA/COOKIE.JS"></SCRIPT>
<SCRIPT LANGUAGE="Javascript">var imagemax = 9; setCurrentMax(9);</SCRIPT>
<SCRIPT LANGUAGE="Javascript" SRC="../JAVA/IMGDOC.JS"></SCRIPT>
<SCRIPT LANGUAGE="Javascript" SRC="../JAVA/NSIMGDOC.JS"></SCRIPT>
<SCRIPT LANGUAGE="Javascript" SRC="../JAVA/DINGBATS.JS"></SCRIPT>
<SCRIPT LANGUAGE="Javascript">var dingbase = "MC4_DIR.HTM"; var dingtext = "MEC++ Efficiency, P";
if (self == top) {
top.location.replace(dingbase + this.location.hash);
}</SCRIPT>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" ONLOAD="setResize()">
<!-- SectionName="MEC++ Chapter Intro: Efficiency" -->
<DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="./MC3_FR.HTM#40989" TARGET="_top" onMouseOver = "self.status ='Back to MEC++ Item 15'; return true" onMouseOut = "self.status = self.defaultStatus">Item 15: Understand the costs of exception handling</A> <BR> Continue to <A HREF="./MC4.HTM#40995" onMouseOver = "self.status ='Item 16: Remember the 80-20 rule.'; return true" onMouseOut = "self.status = self.defaultStatus">Item 16: Remember the 80-20 rule.</A></FONT></DIV>
<A NAME="66196"></A><A NAME="71807"> </A><A NAME="P81"></A>
<P><A NAME="dingp1"></A><font ID="mgtitle">Efficiency</font><SCRIPT>create_link(1);</SCRIPT>
</P>
<A NAME="71809"> </A>
<P><A NAME="dingp2"></A>
I harbor a suspicion that someone has performed secret <NOBR><FONT COLOR="#FF0000" SIZE="-2"><B>°</B></FONT><A HREF="http://www.awl.com/cseng/cgi-bin/cdquery.pl?name=pavlov" onMouseOver="self.status='Pavlovian Experiments Home Page'; return true" onMouseOut="self.status=self.defaultStatus" target="_top">Pavlovian</NOBR> experiments</A> on C++ software developers. How else can one explain the fact that when the word "efficiency" is mentioned, scores of programmers start to <NOBR>drool?<SCRIPT>create_link(2);</SCRIPT>
</NOBR></P><A NAME="49941"> </A>
<P><A NAME="dingp3"></A>
In fact, efficiency is no laughing matter. Programs that are too big or too slow fail to find acceptance, no matter how compelling their merits. This is perhaps as it should be. Software is supposed to help us do things better, and it's difficult to argue that slower is better, that demanding 32 megabytes of memory is better than requiring a mere 16, that chewing up 100 megabytes of disk space is better than swallowing only 50. Furthermore, though some programs take longer and use more memory because they perform more ambitious computations, too many programs can blame their sorry pace and bloated footprint on nothing more than bad design and slipshod <NOBR>programming.<SCRIPT>create_link(3);</SCRIPT>
</NOBR></P><A NAME="49923"> </A>
<P><A NAME="dingp4"></A>
Writing efficient programs in C++ starts with the recognition that C++ may well have nothing to do with any performance problems you've been having. If you want to write an efficient C++ program, you must first be able to write an efficient <I>program</I>. Too many developers overlook this simple truth. Yes, loops may be unrolled by hand and multiplications may be replaced by shift operations, but such micro-tuning leads nowhere if the higher-level algorithms you employ are inherently inefficient. Do you use quadratic algorithms when linear ones are available? Do you compute the same value over and over? Do you squander opportunities to reduce the average cost of expensive operations? If so, you can hardly be surprised if your programs are described like second-rate tourist attractions: worth a look, but only if you've got some extra <NOBR>time.<SCRIPT>create_link(4);</SCRIPT>
</NOBR></P><A NAME="50003"> </A>
<P><A NAME="dingp5"></A>
The material in this chapter attacks the topic of efficiency from two angles. The first is language-independent, focusing on things you can do in any programming language. C++ provides a particularly appealing <A NAME="P82"></A>implementation medium for these ideas, because its strong support for encapsulation makes it possible to replace inefficient class implementations with better algorithms and data structures that support the same <NOBR>interface.<SCRIPT>create_link(5);</SCRIPT>
</NOBR></P><A NAME="50028"> </A>
<P><A NAME="dingp6"></A>
The second focus is on C++ itself. High-performance algorithms and data structures are great, but sloppy implementation practices can reduce their effectiveness considerably. The most insidious mistake is both simple to make and hard to recognize: creating and destroying too many objects. Superfluous object constructions and destructions act like a hemorrhage on your program's performance, with precious clock-ticks bleeding away each time an unnecessary object is created and destroyed. This problem is so pervasive in C++ programs, I devote four separate items to describing where these objects come from and how you can eliminate them without compromising the correctness of your <NOBR>code.<SCRIPT>create_link(6);</SCRIPT>
</NOBR></P><A NAME="50050"> </A>
<P><A NAME="dingp7"></A>
Programs don't get big and slow only by creating too many objects. Other potholes on the road to high performance include library selection and implementations of language features. In the items that follow, I address these issues, <NOBR>too.<SCRIPT>create_link(7);</SCRIPT>
</NOBR></P><A NAME="64580"> </A>
<P><A NAME="dingp8"></A>
After reading the material in this chapter, you'll be familiar with several principles that can improve the performance of virtually any program you write, you'll know exactly how to prevent unnecessary objects from creeping into your software, and you'll have a keener awareness of how your compilers behave when generating <NOBR>executables.<SCRIPT>create_link(8);</SCRIPT>
</NOBR></P><A NAME="64646"> </A>
<P><A NAME="dingp9"></A>
It's been said that forewarned is forearmed. If so, think of the information that follows as preparation for <NOBR>battle.<SCRIPT>create_link(9);</SCRIPT>
</NOBR></p>
<!-- SectionName="M16: Remember the 80-20 rule" -->
<A NAME="40995"></A>
<DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="#66196">Efficiency</A> <BR> Continue to <A HREF="#41011">Item 17: Consider using lazy evaluation</A></FONT></DIV>
<P><A NAME="dingp10"></A><font ID="mititle">Item 16: Remember the 80-20 rule.</font><SCRIPT>create_link(10);</SCRIPT>
</P>
<A NAME="72142"></A><A NAME="40996"></A>
<P><A NAME="dingp11"></A>
The 80-20 rule states that 80 percent of a program's resources are used by about 20 percent of the code: 80 percent of the runtime is spent in approximately 20 percent of the code; 80 percent of the memory is used by some 20 percent of the code; 80 percent of the disk accesses are performed for about 20 percent of the code; 80 percent of the maintenance effort is devoted to around 20 percent of the code. The rule has been repeatedly verified through examinations of countless machines, operating systems, and applications. The 80-20 rule is more than just a catchy phrase; it's a guideline about system performance that has both wide applicability and a solid empirical <NOBR>basis.<SCRIPT>create_link(11);</SCRIPT>
</NOBR></P><A NAME="40997"></A>
<P><A NAME="dingp12"></A>
When considering the 80-20 rule, it's important not to get too hung up on numbers. Some people favor the more stringent 90-10 rule, and there's experimental evidence to back that, too. Whatever the precise <A NAME="p83"></A>numbers, the fundamental point is this: the overall performance of your software is almost always determined by a small part of its constituent <NOBR>code.<SCRIPT>create_link(12);</SCRIPT>
</NOBR></P><A NAME="40998"></A>
<P><A NAME="dingp13"></A>
As a programmer striving to maximize your software's performance, the 80-20 rule both simplifies and complicates your life. On one hand, the 80-20 rule implies that most of the time you can produce code whose performance is, frankly, rather mediocre, because 80 percent of the time its efficiency doesn't affect the overall performance of the system you're working on. That may not do much for your ego, but it should reduce your stress level a little. On the other hand, the rule implies that if your software has a performance problem, you've got a tough job ahead of you, because you not only have to locate the small pockets of code that are causing the problem, you have to find ways to increase their performance dramatically. Of these tasks, the more troublesome is generally locating the bottlenecks. There are two fundamentally different ways to approach the matter: the way most people do it and the right <NOBR>way.<SCRIPT>create_link(13);</SCRIPT>
</NOBR></P><A NAME="41000"></A>
<P><A NAME="dingp14"></A>
The way most people locate bottlenecks is to guess. Using experience, intuition, tarot cards and Ouija boards, rumors or worse, developer after developer solemnly proclaims that a program's efficiency problems can be traced to network delays, improperly tuned memory allocators, compilers that don't optimize aggressively enough, or some bonehead manager's refusal to permit assembly language for crucial inner loops. Such assessments are generally delivered with a condescending sneer, and usually both the sneerers and their prognostications are flat-out <NOBR>wrong.<SCRIPT>create_link(14);</SCRIPT>
</NOBR></P><A NAME="41001"></A>
<P><A NAME="dingp15"></A>
Most programmers have lousy intuition about the performance characteristics of their programs, because program performance characteristics tend to be highly unintuitive. As a result, untold effort is poured into improving the efficiency of parts of programs that will never have a noticeable effect on their overall behavior. For example, fancy algorithms and data structures that minimize computation may be added to a program, but it's all for naught if the program is I/O-bound. Souped-up I/O libraries (see <A HREF="#41253" onMouseOver = "self.status = 'Link to MEC++ Item 23'; return true" onMouseOut = "self.status = self.defaultStatus">Item 23</A>) may be substituted for the ones shipped with compilers, but there's not much point if the programs using them are <NOBR>CPU-bound.<SCRIPT>create_link(15);</SCRIPT>
</NOBR></P><A NAME="41005"></A>
<P><A NAME="dingp16"></A>
That being the case, what do you do if you're faced with a slow program or one that uses too much memory? The 80-20 rule means that improving random parts of the program is unlikely to help very much. The fact that programs tend to have unintuitive performance characteristics means that trying to guess the causes of performance bottlenecks is unlikely to be much better than just improving random parts of your program. What, then, <I>will</I> <NOBR>work?<SCRIPT>create_link(16);</SCRIPT>
</NOBR></P><A NAME="41006"></A>
<A NAME="p84"></A><P><A NAME="dingp17"></A>
What will work is to empirically identify the 20 percent of your program that is causing you heartache, and the way to identify that horrid 20 percent is to use a program profiler. Not just any profiler will do, however. You want one that <I>directly</I> measures the resources you are interested in. For example, if your program is too slow, you want a profiler that tells you how much <I>time</I> is being spent in different parts of the program. That way you can focus on those places where a significant improvement in local efficiency will also yield a significant improvement in overall <NOBR>efficiency.<SCRIPT>create_link(17);</SCRIPT>
</NOBR></P><A NAME="62890"></A>
<P><A NAME="dingp18"></A>
Profilers that tell you how many times each statement is executed or how many times each function is called are of limited utility. From a performance point of view, you do not care how many times a statement is executed or a function is called. It is, after all, rather rare to encounter a user of a program or a client of a library who complains that too many statements are being executed or too many functions are being called. If your software is fast enough, nobody cares how many statements are executed, and if it's too slow, nobody cares how few. All they care about is that they hate to wait, and if your program is making them do it, they hate you, <NOBR>too.<SCRIPT>create_link(18);</SCRIPT>
</NOBR></P><A NAME="62894"></A>
<P><A NAME="dingp19"></A>
Still, knowing how often statements are executed or functions are called can sometimes yield insight into what your software is doing. If, for example, you think you're creating about a hundred objects of a particular type, it would certainly be worthwhile to discover that you're calling constructors in that class thousands of times. Furthermore, statement and function call counts can indirectly help you understand facets of your software's behavior you can't directly measure. If you have no direct way of measuring dynamic memory usage, for example, it may be helpful to know at least how often memory allocation and deallocation functions (e.g., operators <CODE>new</CODE>, <CODE><NOBR>new[]</NOBR></CODE>, <CODE>delete</CODE>, and <CODE><NOBR>delete[]</NOBR></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>) are <NOBR>called.<SCRIPT>create_link(19);</SCRIPT>
</NOBR></P><A NAME="41007"></A>
<P><A NAME="dingp20"></A>
Of course, even the best of profilers is hostage to the data it's given to process. If you profile your program while it's processing unrepresentative input data, you're in no position to complain if the profiler leads you to fine-tune parts of your software — the parts making up some 80 percent of it — that have no bearing on its usual performance. Remember that a profiler can only tell you how a program behaved on a particular run (or set of runs), so if you profile a program using input data that is unrepresentative, you're going to get back a profile that is equally unrepresentative. That, in turn, is likely to lead to you to optimize your software's behavior for uncommon uses, and the overall impact on common uses may even be <NOBR>negative.<SCRIPT>create_link(20);</SCRIPT>
</NOBR></P><A NAME="75117"></A>
<P><A NAME="dingp21"></A>
The best way to guard against these kinds of pathological results is to profile your software using as many data sets as possible. Moreover, <A NAME="p85"></A>you must ensure that each data set is representative of how the software is used by its clients (or at least its most important clients). It is usually easy to acquire representative data sets, because many clients are happy to let you use their data when profiling. After all, you'll then be tuning your software to meet their needs, and that can only be good for both of <NOBR>you.<SCRIPT>create_link(21);</SCRIPT>
</NOBR></P>
<!-- SectionName="M17: Consider using lazy evaluation" -->
<A NAME="41011"></A><DIV ALIGN="CENTER"><FONT SIZE="-1">Back to <A HREF="#40995">Item 16: Remember the 80-20 rule</A> <BR> Continue to <A HREF="#41124">Item 18: Amortize the cost of expected computations</A></FONT></DIV>
<P><A NAME="dingp22"></A><font ID="mititle">Item 17: Consider using lazy evaluation.</font><SCRIPT>create_link(22);</SCRIPT>
</P>
<A NAME="72144"></A>
<A NAME="41012"></A>
<P><A NAME="dingp23"></A>
From the perspective of efficiency, the best computations are those you never perform at all. That's fine, but if you don't need to do something, why would you put code in your program to do it in the first place? And if you do need to do something, how can you possibly avoid executing the code that does <NOBR>it?<SCRIPT>create_link(23);</SCRIPT>
</NOBR></P><A NAME="41013"></A>
<P><A NAME="dingp24"></A>
The key is to be <NOBR>lazy.<SCRIPT>create_link(24);</SCRIPT>
</NOBR></P><A NAME="41014"></A>
<P><A NAME="dingp25"></A>
Remember when you were a child and your parents told you to clean your room? If you were anything like me, you'd say "Okay," then promptly go back to what you were doing. You would <I>not</I> clean your room. In fact, cleaning your room would be the last thing on your mind — <I>until</I> you heard your parents coming down the hall to confirm that your room had, in fact, been cleaned. Then you'd sprint to your room and get to work as fast as you possibly could. If you were lucky, your parents would never check, and you'd avoid all the work cleaning your room normally <NOBR>entails.<SCRIPT>create_link(25);</SCRIPT>
</NOBR></P><A NAME="41015"></A>
<P><A NAME="dingp26"></A>
It turns out that the same delay tactics that work for a five year old work for a C++ programmer. In Computer Science, however, we dignify such procrastination with the name <I>lazy evaluation</I>. When you employ lazy evaluation, you write your classes in such a way that they defer computations until the <I>results</I> of those computations are required. If the results are never required, the computations are never performed, and neither your software's clients nor your parents are any the <NOBR>wiser.<SCRIPT>create_link(26);</SCRIPT>
</NOBR></P><A NAME="41016"></A>
<P><A NAME="dingp27"></A>
Perhaps you're wondering exactly what I'm talking about. Perhaps an example would help. Well, lazy evaluation is applicable in an enormous variety of application areas, so I'll describe <NOBR>four.<SCRIPT>create_link(27);</SCRIPT>
</NOBR></P>
<P><A NAME="dingp28"></A><font ID="mhtitle">Reference Counting</font><SCRIPT>create_link(28);</SCRIPT>
</P>
<P><A NAME="dingp29"></A><A NAME="41017"></A>
Consider this <NOBR>code:<SCRIPT>create_link(29);</SCRIPT>
</NOBR></P>
<A NAME="41018"></A>
<UL><PRE>
class String { ... }; // a string class (the standard
// string type may be implemented
// as described below, but it
// doesn't have to be)
<A NAME="41019"></A>
<A NAME="p86"></A>String s1 = "Hello";
<A NAME="41020"></A>
String s2 = s1; // call String copy ctor
</PRE>
</UL>
<A NAME="41021"></A>
<P><A NAME="dingp30"></A>
A common implementation for the <CODE>String</CODE> copy constructor would result in <CODE>s1</CODE> and <CODE>s2</CODE> each having its own copy of <CODE>"Hello"</CODE> after <CODE>s2</CODE> is initialized with <CODE>s1</CODE>. Such a copy constructor would incur a relatively large expense, because it would have to make a copy of <CODE>s1</CODE>'s value to give to <CODE>s2</CODE>, and that would typically entail allocating heap memory via the <CODE>new</CODE> operator (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 calling <CODE>strcpy</CODE> to copy the data in <CODE>s1</CODE> into the memory allocated by <CODE>s2</CODE>. This is <i>eager evaluation:</i> making a copy of <CODE>s1</CODE> and putting it into <CODE>s2</CODE> just because the <CODE>String</CODE> copy constructor was <i>called</i>. At this point, however, there has been no real <i>need</i> for <CODE>s2</CODE> to have a copy of the value, because <CODE>s2</CODE> hasn't been used <NOBR>yet.<SCRIPT>create_link(30);</SCRIPT>
</NOBR></P><A NAME="41025"></A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -