首页
登录 | 注册

为什么处理有序数组比无序数组快?

声明:本文转自 伯乐在线 - Jerry ,原文地址:http://blog.jobbole.com/68023/

由于某些怪异的原因,下面这段C++代码表现的异乎寻常—-当这段代码作用于有序数据时其速度可以提高将近6倍,这真是令人惊奇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <ctime>
#include <iostream>
 
int _tmain (int argc , _TCHAR * argv [])
{
        //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 eclapsedTime = static_cast<double >(clock() - start) / CLOCKS_PER_SEC;
 
       std::cout << eclapsedTime << std::endl;
       std::cout << "sum = " << sum << std::endl;
        return 0;
}
  • 如果把 std::sort(data, data+arraySize) 去掉,这段代码耗时11.54秒。
  • 对于有序数据,这段代码耗时1.93秒

起初我以为这可能是某一种语言或某一个编译器发生的异常的事件,后来我在java语言写了个例子,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Arrays;
import java.util.Random;
 
public class Test_Sorted_UnSorted_Array {
       public static void main(String[] args) {
             //Generate data
             int arraySize = 32768;
             int data[] = new int[arraySize];
 
            Random rnd = new Random(0);
             for( int c = 0; c<arraySize; ++c)
                  data[c] = rnd.nextInt()%256;
 
             //!!! With this, the next loop runs faster
            Arrays. sort(data);
 
             //Test
             long start = System. nanoTime();
             long sum = 0;
 
             for( int i=0; i<100000; ++i){
                   //Primary loop
                   for( int c = 0; c<arraySize; ++c){
                         if(data[c] >=128)
                              sum += data[c];
                  }
            }
 
            System. out.println((System. nanoTime() - start) / 1000000000.0);
            System. out.println( "sum = " + sum);
      }
}

上述例子运行结果和前面C++例子运行的结果差异,虽然没有C++中那么大,但是也有几分相似。

对于上面的问题,我首先想的原因是排序可能会导致数据有缓存,但是转念一想之前原因有点不切实际,因为上面的数组都是刚刚生成的,所以我的问题是:

  • 上述代码运行时到底发生了什么?
  • 为什么运行排好序的数组会比乱序数组快?
  • 上述代码求和都是独立的,而顺序不应该会产生影响。

 

来自 Mysticial 的最佳回复

你是分支预测(branch prediction )失败的受害者。

什么是分支预测?

考虑一个铁路枢纽:

为什么处理有序数组比无序数组快?

为什么处理有序数组比无序数组快?

by Mecanismo, via Wikimedia Commons. Used under theCC-By-SA 3.0license.

 

为了便于讨论,假设现在是1800年,这时候还没有出现远程或广播通讯工具。

你是一个铁路枢纽的工人。当你听到火车开来时,你不知道这个火车要走哪一条路,只有让火车停下来询问列车长火车要开往哪,最后你将轨道切换到相应的方向。

火车的质量非常大,固惯性很大,因此火车需要经常性的加速减速。

有没有更好的方法喃?可以猜火车将行驶的方向应该是可行的!

  • 如果猜对了,火车继续往前走;
  • 如果猜错了,列车长会让火车停下来,并后退,然后告诉你正确的方向,然后火车重新启动开往正确的方向。

考虑一个if语句:在处理器级别上,他是一个分支指令:

为什么处理有序数组比无序数组快?

你来扮演处理器,当你遇到一个分支,你不知道它要走哪条路,该怎么办?你可以停止执行并等待直到之前的指令执行完。然后继续执行正确路径的指令。

有没有更好的方法喃?可以猜测哪个分支将要被执行!

  • 如果猜对了,继续执行;
  • 如果猜错了,你需要刷新管道并且回退到该分支,重新启动执行正确的方向。

如果每次都能猜对,整个执行过程就不会停止。
如果经常猜错,就需要在停止、回退、重新执行上花费非常多的时间。

这就是分支预测。不得不承认这不是一个最好的比喻因为火车可以仅仅使用一个标志表示其前进的方向。但是对于计算机,直到最后时刻,处理器是不知道哪条分支被执行。

想想可以使用什么预测策略使得火车回退的次数最少?哈哈,可以利用历史数据!如果火车100次有99次都是向左,那么下次预测结果仍向左。如果过去数据是交替的,那么预测结果也是交替的。如果它每3次都换一个方向,那么预测也采用相同的方法。

简而言之,你需要尝试寻找出一个规则(模式)然后按照它进行预测就可以了。分支预测基本上就是这样工作的。
大部分应用程序的分支是很规律的。这也是为什么现代的分支预测的准确率基本上都在90%以上。但是当没有规律、不可预测的分支时候,分支预测就显得比较拙鸡了。

关于分支预测更多详细的内容可参阅:维基百科


从上面可以得到启发,这个问题的“罪魁祸首”就是 if 语句

1
2
if (data[c] >= 128)
    um += data[c];

注意到数据是在0到255均匀分布的。当排好序后,小于等于128的前半部分是不会执行if语句的,大于128的后半部分都会进入if语句。

这是非常有好的分支预测因为分支会连续多次执行相同的分支。即使是一个简单的饱和计数器也会预测正确除去当变换方向后的少数几个。

快速可视化

1
2
3
4
5
6
7
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)</span></code>

然而,如果数据是完全随机的,分支预测则毫无用处因为它不能预测随机数据。这种情况下可能会有50%的错误预测。

1
2
3
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)

那这种情况下该怎么做呢?

如果编译器不能将分支优化为有条件的移动,这时候可以尝试一些 Hacks ,如果能够可以牺牲可读性的表现。
将下面代码

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

替换为:

1
2
int t = (data[c] - 128) >> 31;
    sum += ~t & data[c];

用一些按位操作取代分支判断,这样就去除了分支。(注意:这个 hacks 并不是和if语句严格相等,但是在我们这个例子里,对输入数组data的所有值都是正确的)

Benchmarks: Core i7 920 @ 3.5 GHz
C++ – Visual Studio 2010 – x64 Release

1
2
3
4
5
6
7
8
9
10
11
//  Branch - Random
seconds = 11.777
 
//  Branch - Sorted
seconds = 2.352
 
//  Branchless - Random
seconds = 2.564
 
//  Branchless - Sorted
seconds = 2.587</span></code>

Java – Netbeans 7.1.1 JDK 7 – x64

1
2
3
4
5
6
7
8
9
10
11
//  Branch - Random
seconds = 10.93293813
 
//  Branch - Sorted
seconds = 5.643797077
 
//  Branchless - Random
seconds = 3.113581453
 
//  Branchless - Sorted
seconds = 3.186068823</span></code>

观察可得:

  • 在分支情况下:排序数组和乱序数组之间的结果有着巨大的差异。
  • 在 Hack 方式下:对于排序和乱序的结果则没有差异。
  • 在C++中,对于排序数组,Hack 会比分支有一点点慢。

一般的经验法则是避免数据依赖分支在一些特殊的循环中。

64位机器下,GCC 4.6.1附带选项-O3或者-ftree-vectorize可以产生一个条件移动。因此对于有序和乱序数据都是一样快。

VC++2010不能够产生条件移动对于这样的分支。

英特尔编译器11同样可以做一些神奇的事。它通过互换两个循环,从而提升了不可预测的分支外循环。因此,它不但能够避免误预测,而且速度上可以达到VC++和GCC的两个快。换句话说,ICC利用了测试回路打破了benchmark。

如果用英特尔编译器执行没有分支的代码,它仅仅出右向量化(out-right vectorizes it),并且和带分支同样快。

通过上面说明,即使比较成熟的现代编译器在优化代码的上可以有很大的不同。

 

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3979538.html


相关文章

  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 实验4
    Part1: #include <stdio.h> const int N=5; int main() { int a[N] = {1, 2, 3, 4, 5}; int i; for(i=0; i<N; i++) pri ...
  • foreach绑定对于数组中的每一个元素复制一节标记语言,也就是html,并且将这节标记语言和数组里面的每一个元素绑定.当我们呈现一组list数据,或者一个表格的时候,十分有用. 如果你绑定的数组是一个"监控数组" ,o ...
  • 第四次上机实验
    实验结论: part 1-4:当数组名作为形式参数时,数组名后面要加[ ]:当数组名作为实际参数时,直接写数组名,后面不要加[ ]:              关于函数的调用及参数传递过程:在程序运行到函数调用这一步骤时,实参会将值赋值给调 ...
  • 实验四(数组)
    实验的总结: int型和float型都用4个字节,char型用一个字节,double型用8个字节.但是在输出5.00和5.000000的时候都没有区别的. 还有就是要注意数组元素的索引号是从零开始的,所以在用for语句的时候<注意它的 ...
  • 代码审查作业
    代码审查 我对结对同伴的代码进行了审查,他的有关括号匹配的代码 审查结果 功能模块名称 括号匹配问题 审查人 牛斌帅 审查日期 2019年4月25日 代码名称 括号匹配问题 代码作者 房旭 文件结构 重要性 审查项 结论 头文件和定义文件的 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.079 s.
京ICP备10005923号