13.4  80-20法则：加快常用路径的速度

80-20法则适用于很多场合：80%的程序执行只遍历20%代码；80%的程序运行时间耗费在执行路径的所遇到的20%函数上。80-20法则有力地证明了过于草率的判断是一种错误这个观点。如果想到什么就改什么，不仅仅浪费了80%的努力，而且也会造成设计的无法修复。

HTTP规范是一份有100页的文档，该文档描述了Web服务器必须处理的所有可能的HTTP请求。但如今在Web上使用的绝大部分HTTP请求是极其简单的。这些请求仅仅是所有可能的HTTP报文头的一个子集。找出这些常见的报文头是很容易的：由于Microsoft和Netscape共同统治了浏览器市场，我们所要做的就是获取由这两个浏览器所发出的报文头。这也是80-20法则的另一种体现--所有可能的20%输入会占用80%的时间。

HTTP报文头决定了请求的类型以及不同的执行路径。所以，有效地利用程序员资源的方法是调整那些占用80%时间的20%的请求类型。

80-20法则还有另一种表现方式。我们不仅要将注意力放在程序的典型执行路径上，同时应该充分利用大多数输入数据一般都限制在整个输入空间的狭窄范围里这个事实，下面列举一些典型的例子。

在HTTP请求里有一个HTTP Accept报文头。该报文头表明浏览器所接受的是哪一种类型的文档格式。在HTTP规范里，Accept头可以是任意的大小写字母组合。当读取一个字符串并且要判断是否是Accept报文头时，可执行下面的代码：

memcmp("Accept:" , header , 7) 

但这是不够的，还需要一个区分大小写字母的函数。下面是一个由笔者实现的区分大小写的字符串匹配函数：

Int memCaseCmp(char* , char * , int) {…} 

符合HTTP规范的正确写法如下：

if ( 0 == memCaseCmp("accept:" , header, 7)) {  
    //这才是 Accept 报文头  
    } 

然而，调用memCaseCmp()的代价是昂贵的。它需要将字符串的字符全部变为大写，然后再调用memcmp()。而这正是领域专家发挥作用的地方。如上面所说，Microsoft和Netscape共同分享了浏览器市场。它们的浏览器所发出的Accept报文头正好是"Accept:"。这虽然只是HTTP规范所允许的Accept报文头的其中一个，但这同时也是所接收到的95%的Accept报文头，这种情况才是应该关注的。下面的代码利用了这一点：

if(( 0 == memcmp("Accept:",header,7)) ||    //聪明的冒险  
    (0 == memCaseCmp("accept:",header,7))) {  
 
   //这就是 Accept 报文头  
   }  

对于95% 的输入，memcmp()函数将会返回成功，所以不必调用耗费时间的memCaseCmp()。

最后的代码引入了另一个80-20问题，即求值顺序。常见的逻辑表达式是由一些子逻辑表达式组合而成。考虑下面的表达式：

if( e1 || e2) {…} 

或者

if( e1 && e2) {…} 

在上面的表达式中，求值顺序与性能有着莫大的关系。以第一个if语句作为例子：

if( e1 || e2) {…} 

当(e1 || e2)为假的时候，那么就要做两次计算，e1和e2都必须进行求值。然而，在(e1 || e2)为真的时候，只要e1为真，那么e2就不必计算，这减少了表达式的计算时间。在下面的讨论中，我们将关注(e1 || e2)为真的情况。

如果e1和e2均有可能为真，那么计算量小的表达式应该放在前面先计算。另一方面，如果e1和e2有相同的计算量，那么为真的可能性较大的表达式应该放在前面。在通常情况下，可以令：

p1 = 当(e1 || e2)为真时el为真的条件概率。

c1 = e1的计算量。

我们尽量减少计算(e1 || e2)的值所需的代价：

c1 + (1-p1)*c2 

虽然上面的例子只涉及两个子表达式，但很容易就可以扩展到拥有任意数量子表达式的OR逻辑表达式。

回到前面的判断HTTP Accept报文头的条件语句：

if(( 0 == memcmp("Accept:",str,7)) ||  
    (0 == memCaseCmp("accept:",str,7))) {  
 
   //这就是Accept报文头   
   } 

这种情况下，

e1为( 0 == memcmp("Accept:",str,7))  
e2为(0 == memCaseCmp("accept:",str,7)) 

在if语句为真的情况下，由于e2是区分大小写字符串的匹配函数，所以e2总是会100%判断为真，即p2 = 1.0。子表达式e1在90%的情况下被判别为真。因此p1 = 0.9。而执行函数的时间可粗略估计为：

c1 = 10个指令  
c2 = 100个指令 

期望代价为：

10 + 0.1 * 100 = 20 

如果交换e1和e2的顺序，代价为：

c2 + (1 p2) * c1 = 100 + 0*10 = 100 

因此，if(e1 || e2)是比if(e2 || e1)更好的选择。

类似的，AND表达式如：

if(e1 && e2) 

假定整个表达式判断为假，而我们希望能尽早判断整个表达式为假，而不是将各个子表达式都计算一遍后再判断。这种情况的概率定义与上面有一点不同：

p1 = 当(e1 && e2)为假时el为假的条件概率。

在实践中可以常遇到这类决策，例如，下面的代码需要检查并处理一些很少发生的事件组合：

if(rareCondintion_1() && rareCondition_2()){  
    //处理  
    } 

由于这种组合条件判断并不常见，所以在绝大多数时间里条件判断都为假。我们希望尽快在第一个表达式里判断为假。顺便讲一下，这也是兼容HTTP 1.1的服务器会比一些只符合HTTP 1.0标准服务器慢的原因。因为HTTP 1.1规范更为复杂，这就导致了一些符合HTTP 1.1标准的服务器要做很多但却很少出现的复杂的检查。但为了满足HTTP 1.1规范，又不得不做这种检查。例如，一个符合HTTP 1.1的浏览器可能会请求一个很大的文档的一小部分，而不是整个文档。而在实践中，浏览器在绝大部分时间里都是请求完整的文档，但服务器仍然要判断是否只是请求部分文档，然后才做出恰当的处理。