CodeInside：为什么处理已排序数组比处理未排序数组更快？

很久以前在stackoverflow上看到下面这段代码，今天忍不住把它摘录过来。

成都创新互联自2013年起，先为邛崃等服务建站，邛崃等地企业，进行企业商务咨询服务。为邛崃企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

 
 
  
  #include  
  
  #include  
  
  #include  
  
    
  
  int main() 
  
  { 
  
      // Generate data 
  
      const unsigned arraySize = 32768; 
  
      int data[arraySize]; 
  
    
  
      for (unsigned c = 0; c < arraySize; ++c) 
  
          data[c] = std::rand() % 256; 
  
    
  
      // !!! With this, the next loop runs faster 
  
      std::sort(data, data + arraySize); 
  
    
  
      // Test 
  
      clock_t start = clock(); 
  
      long long sum = 0; 
  
    
  
      for (unsigned i = 0; i < 100000; ++i) 
  
      { 
  
          // Primary loop 
  
          for (unsigned c = 0; c < arraySize; ++c) 
  
          { 
  
              if (data[c] >= 128) 
  
                  sum += data[c]; 
  
          } 
  
      } 
  
    
  
      double elapsedTime = static_cast(clock() - start) / CLOCKS_PER_SEC; 
  
    
  
      std::cout << elapsedTime << std::endl; 
  
      std::cout << "sum = " << sum << std::endl; 
  
  }

上面的程序在保留std::sort(data, data + arraySize);语句时，程序运行时间是1.93 秒

但去掉排序语句后，程序运行时间是11.54秒

问题：为什么会出现这种情况？

解答：分支预测。

[[119029]]

程序分支

考虑以下if语句块。对于处理器来说，就是一个分支指令，如下：

处理器每次遇到一条分支时，它都不知道该走哪一条道。这时候该怎么办？程序停下来，等待前面的指令执行完，得到确切的结果后，再接着走某一条分支。

现代处理器都支持指令并行处理和超流水线作业。因此，当处理器遇到程序分支时，都会去猜测应该走哪一条分支。

如果猜对了，程序接着流畅运行。如果猜错了，则处理器需要做一些额外的工作，再次回到那条正确的分支。

因此，如果处理器每次都猜错，那程序的运行时间就会边长。

这就是上面的代码为什么运行时间会相差那么大的原因。

对于分支语句：

 
 
  
  if (data[c] >= 128) 
  
      sum += data[c];

在保留std::sort(data, data + arraySize);的情况下。数组data中的内容是这样的：

 
 
  
  T = branch taken 
  
  N = branch not taken 
  
    
  
  data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... 
  
  branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ... 
  
    
  
         = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

在未排序的情况下，数组data中的内容是这样的：

 
 
  
  data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ... 
  
  branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ... 
  
    
  
         = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

也就是说，在已经排序的情况下，处理器便能更好的预测分支了。因此，程序也运行的更快。

关于分支预测

阅读linux源代码时，你会发现if(likely( )){}或是if(unlikely( ))这样的语句。对于条件选择语句，gcc内建了一条指令用于优化，在一个条件经常出现，或者该条件很少出现的时候，编译器可以根据这条指令对条件分支选择进行优化。而Linux内核把这条指令封装成了宏likely()和unlikely()。

因此，在编写程序时，如果一个分支条件只有在很少数的情况下才出现时，我们使用unlikely( )和likely( )能够加快程序的运行,这也是一种优化程序的手段。

比如这样：

 
 
  
  if ( unlikely(statement) ) { //这里便是告诉编译器，这个条件只在少数情况下发生 
  
  
  
  dosomething(); 
  
  
  
  }

本文标题：CodeInside：为什么处理已排序数组比处理未排序数组更快？
文章出自：http://www.csdahua.cn/qtweb/news18/36468.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：快上网

成都快上网为您推荐相关内容