C++编程丨为什么解决有序数组比无序数组快?

作者 : 开心源码 本文共4693个字,预计阅读时间需要12分钟 发布时间: 2022-05-12 共240人阅读

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

C++

#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语言写了个例子,如下:

Java

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)失败的受害者。

什么是分支预测?

考虑一个铁路枢纽:

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

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

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

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

假如猜对了,火车继续往前走;

假如猜错了,列车长会让火车停下来,并后退,而后告诉你正确的方向,而后火车重新启动开往正确的方向。

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

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

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

假如猜对了,继续执行;

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

假如每次都能猜对,整个执行过程就不会中止。

假如经常猜错,就需要在中止、回退、重新执行上花费非常多的时间。

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

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

简而言之,你需要尝试寻觅出一个规则(模式)而后按照它进行预测即可以了。分支预测基本上就是这样工作的。

大部分应用程序的分支是很规律的。这也是为什么现代的分支预测的精确率基本上都在90%以上。但是当没有规律、不可预测的分支时候,分支预测就显得比较拙鸡了。

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

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

C++

if (data[c] >= 128)

um += data[c];

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

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

快速可视化

C++

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%的错误预测。

C++

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 ,假如能够可以牺牲可读性的体现。

将下面代码

C++

if (data[c] >= 128)

????sum += data[c];

替换为:

C++

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

C++

//??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

C++

//??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),并且和带分支同样快。

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

另外,假如有想学习C语言和c++的程序员,可来我们的C语言c++学习扣群:741818652免费送C语言的视频教程噢!我整理了一份适合大学生学习的c++干货,送给每一位想学的小伙伴,并且每天晚上8点还会有行业内7年经验资深金牌讲师在群内直播讲解c/c++知识,欢迎大家前来学习哦。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » C++编程丨为什么解决有序数组比无序数组快?

发表回复