为什么处理排序数组比处理未排序数组更快?

GManNickG 22648 c++ java optimization performance branch-prediction

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

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<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • 没有std::sort(data, data + arraySize);,代码运行11.54秒.
  • 使用排序数据,代码运行1.93秒.

最初,我认为这可能只是一种语言或编译器异常.所以我在Java中尝试过它.

import java.util.Arrays;
import java.util.Random;

public class Main
{
    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);
    }
}

有点相似但不太极端的结果.


我的第一个想法是排序将数据带入缓存,但后来我认为这是多么愚蠢,因为数组刚刚生成.

  • 到底是怎么回事?
  • 为什么处理排序数组比处理未排序数组更快?
  • 代码总结了一些独立的术语,顺序无关紧要.

Mysticial.. 29716

您是分支预测失败的受害者.


什么是分支预测?

考虑一个铁路交界处:

图像显示铁路枢纽 图片来自Mecanismo,来自Wikimedia Commons.在CC-By-SA 3.0许可下使用.

现在为了争论,假设这是在19世纪 - 在长途或无线电通信之前.

您是交叉路口的运营商,您会听到火车即将到来.你不知道应该走哪条路.你停下火车去询问司机他们想要的方向.然后适当地设置开关.

火车很重,有很多惯性.所以他们需要永远的启动和放慢速度.

有没有更好的办法?你猜猜火车往哪个方向走!

  • 如果你猜对了,它会继续下去.
  • 如果你猜对了,机长会停下来,然后向你大喊大叫,然后翻转开关.然后它可以重新启动另一条路径.

如果你每次都猜对了,火车将永远不会停下来.
如果您经常猜错,列车将花费大量时间停止,备份和重新启动.


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

包含if语句的已编译代码的屏幕截图

你是一个处理器,你看到一个分支.你不知道它会走哪条路.你是做什么?您暂停执行并等待前面的指令完成.然后继续沿着正确的路径前进.

现代处理器很复杂,管道很长.所以他们永远地"热身"和"慢下来".

有没有更好的办法?你猜这个分支会走向哪个方向!

  • 如果你猜对了,你继续执行.
  • 如果您猜错了,则需要刷新管道并回滚到分支.然后,您可以重新启动其他路径.

如果你每次都猜对了,执行将永远不会停止.
如果你经常猜错,你会花很多时间停滞,回滚和重新启动.


这是分支预测.我承认这不是最好的比喻,因为火车只能用旗帜向方向发出信号.但是在计算机中,处理器直到最后一刻才知道分支将朝哪个方向发展.

那么你如何战略性地猜测火车必须备份并沿着另一条路走下去的次数呢?你看看过去的历史!如果火车99%的时间都离开,那么你猜对了.如果它交替,那么你交替猜测.如果它每3次走一条路,你就猜相同......

换句话说,您尝试识别模式并遵循它.这或多或少是分支预测器的工作方式.

大多数应用程序具有良好的分支.因此,现代分支预测器通常会达到> 90%的命中率.但是当面对不可预测的分支而没有可识别的模式时,分支预测器实际上是无用的.

进一步阅读:维基百科上的"分支预测"一文.


如上所述,罪魁祸首就是这句if语句:

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

请注意,数据均匀分布在0到255之间.当数据排序时,大约前半部分的迭代不会进入if语句.之后,他们都将进入if语句.

这对分支预测器非常友好,因为分支连续多次朝同一方向运行.即使是简单的饱和计数器也会正确预测分支,除非在切换方向后进行少量迭代.

快速可视化:

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)

但是,当数据完全随机时,分支预测器变得无用,因为它无法预测随机数据.因此可能会有大约50%的错误预测.(不比随机猜测好)

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)

那可以做些什么呢?

如果编译器无法将分支优化为条件移动,那么如果您愿意牺牲性能的可读性,则可以尝试一些黑客攻击.

更换:

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

有:

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

这消除了分支并用一些按位操作替换它.

(请注意,此hack并不严格等同于原始的if语句.但在这种情况下,它对所有输入值都有效data[].)

基准测试:酷睿i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64发行版

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

观察:

  • 使用分支:已排序和未排序的数据之间存在巨大差异.
  • 使用Hack:排序和未排序数据之间没有区别.
  • 在C++的情况下,当数据排序时,hack实际上比分支慢一点.

一般的经验法则是避免在关键循环中依赖数据进行分支.(例如在这个例子中)


更新:

  • 带有-O3-ftree-vectorize在x64上的GCC 4.6.1 能够生成条件移动.因此,排序和未排序数据之间没有区别 - 两者都很快.

  • VC++ 2010无法为此分支生成条件移动/Ox.

  • 英特尔编译器11做了一些奇迹.它交换两个循环,从而将不可预测的分支提升到外循环.因此,它不仅可以免受错误预测的影响,而且速度也是VC++和GCC产生的速度的两倍!换句话说,ICC利用测试循环来击败基准......

  • 如果你给英特尔编译器提供无分支代码,那么它就是向右矢量化它......并且与分支一样快(使用循环交换).

这表明即使是成熟的现代编译器在优化代码的能力方面也会有很大差异......

  • @Mysticial为了避免转移黑客你可以编写类似`int t = - ((data [c]> = 128))`来生成掩码.这应该更快.知道编译器是否足够聪明以插入条件移动会很有趣. (282认同)
  • @phonetagger看看这个后续问题:http://stackoverflow.com/questions/11276291/why-cant-or-doesnt-the-compiler-optimize-a-predictable-addition-loop-into-a英特尔编译器非常接近完全摆脱外循环. (197认同)
  • 我的语法要求我认为这应该是"...分支预测的受害者失败*尿素*",而不仅仅是"......分支预测的受害者失败". (171认同)
  • @Mysticial非常感谢链接.看起来很有希望.我会去的.最后一个请求.对不起,但请不要介意,你能告诉我你怎么做吗?int t =(data [c] - 128)>> 31; sum + = ~t&data [c];`替换上面的原始if条件? (128认同)
  • @Novelocrat只有一半是正确的.当它为零时将1移入符号位确实是UB.那是因为它是有符号整数溢出.但是,从符号位移出1是IB.右移有负有符号整数是IB.您可以进入这样的论点,即C/C++不要求顶部位是符号指示符.但实施细节是IB. (100认同)
  • @Unheilig对于合法位操作以外的任何其他操作使用按位运算,或者使用可变幂次数乘以/除以不是我通常建议的,因为它经常是混淆的.尽管如此,这里有一个很好的参考资料:http://graphics.stanford.edu/~seander/bithacks.html (26认同)
  • 请注意,这种优化恰恰是Spectre和Meltdown导致大安全漏洞的原因.简而言之,某些操作(如缓存)实际上并未回滚(出于性能原因),这会导致某些可能敏感的数据被其他进程读取. (26认同)
  • @引入方法可以增加'hack'的可读性.例如在java`priv int sumIfGreaterThan128(int curSum,int value)`中.无论如何,JIT编译器将在运行时内联它.我想在其他语言中可以获得相同的优化. (23认同)
  • @obe:鉴于分层内存结构,不可能说出缓存未命中的代价是多少.它可能在L1中丢失并在较慢的L2中解析,或在L3中丢失并在系统内存中解析.但是,除非出于某些奇怪的原因,这个缓存未命中导致非驻留页面中的内存从磁盘加载,你有一个好点...内存在大约25 - 30年内没有访问时间在毫秒范围内;) (20认同)
  • @Mysticial火车/编译器如何知道它进入了错误的路径? (19认同)
  • @FilipBartuzi分支预测在处理器运行代码时发生.这种语言什么都不知道.在你的例子中,它仍然会很快,因为你只在3和3周围添加了1或2个错误预测. (19认同)
  • 在现代的C和C++标准下,转换黑客实际上不是实现定义的行为,而是未定义的行为!不再允许将"1"移入或移出有符号整数的符号位. (17认同)
  • 如果没有分支预测,条件是否会比黑客更快?条件将是(检查)(跳转)(添加),而黑客使用4个连续的算术运算 (17认同)
  • @Sandeep是的.处理器仍然具有分支预测.如果有任何改变,那就是编译器.如今,我打赌他们更有可能做ICC和GCC(在-O3下)在这里做的事情 - 也就是说,删除分支.鉴于这个问题有多高调,编译器很可能已经更新以专门处理这个问题中的案例.绝对要注意SO.它发生在[这个问题](http://stackoverflow.com/a/25089720/922184),其中GCC在3周内更新.我不明白为什么它不会发生在这里. (17认同)
  • @ woojoo666这取决于4个操作相对于分支处理逻辑的成本.所以它可能会根据具体情况而有所不同. (16认同)
  • **经验法则**用于编写在现代处理器上高效的代码:使程序执行更加规则(更少不均匀)的一切都会使其更有效率.由于分支预测,此示例中的排序具有此效果.由于缓存,访问位置(而不是远程和随机访问)具有此效果. (16认同)
  • 是不是可以并行执行两个分支,然后停止执行一个错误的分支,而不是预测一个分支? (15认同)
  • 何时进行分支预测?什么时候语言会知道数组是排序的?我正在考虑数组的情况,如:[1,2,3,4,5,... 998,999,1000,3,10001,10002]?这个模糊的3会增加运行时间吗?它会和未排序的数组一样长吗? (15认同)
  • @Tuğrul我会假设对于给定的粒子,它与另一个粒子碰撞的可能性小于1%.然后,分支预测可以始终预测无碰撞,并且无论是否排序,都将> 99%正确.最后,对于快速碰撞检查,您仍然希望使用树结构. (14认同)
  • 我想知道为什么分支预测概念到位,(分支预测)概念的用途是什么?我的意思是没有它我们将得到有序和未排序数组的明确结果. (13认同)
  • @BJHomer我用Clang 3.5尝试了它:调试排序9.3s,调试未分类24.6s.O2排序5.0s,O2排序也5.0s.所以看起来Clang能够很好地优化循环.来自帖子的无分支版本需要13s用于调试,4.1s用于O2,在排序/未排序之间几乎没有区别. (13认同)
  • 这可能超出了这个Q/A的范围,但是当分支预测报告每个分支的相似几率时,现代处理器是否会在两条路径上继续下行?如果没有,为什么不呢?看起来备用周期确保分支准备就绪,比猜测错误或只是等待更好. (10认同)
  • GCC有许多默认情况下未启用的优化,它可以执行以下操作: (8认同)
  • 它可以拆分循环(使用`-ftree-loop-distribution`和`-ftree-loop-distribute-patterns`),移动不变的部分(默认情况下),将不变条件移出循环(使用`-funswitch-loops` ,但会导致重复),将条件跳转转换为条件存储或删除它们(`-ftree-loop-if-convert`和`-ftree-loop-if-convert-stores`).遗憾的是,很多这些选项都有不安全的副作用,只对天真编写的代码做了很好的改进. (8认同)
  • @ SlippD.Thompson可能不是因为我在[早先的评论中]提到的原因.(http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted -array/11227902#comment38162647_11227902). (6认同)
  • 例如,在Java的情况下,分支预测是在处理器级别还是在Java运行时中进行的? (6认同)
  • 我刚刚在VS 2015中运行了代码,并且排序不再提高性能.由于TurboBoost,我使用具有3.6GHz的英特尔酷睿i5测量了32768个元素的大约1.1秒和327680个元素的大约11个(移动到全局变量以防止堆栈溢出).我查看了一个反汇编,除了一个终止循环之外我没有找到任何分支 - 它实际上使用了通常用于浮点运算的`cdq`和`movlpd`等指令. (6认同)
  • @EdwardBlack进行预测的不是编译器.这是处理器.其次,处理器不能"只是决定",因为它同时做了很多事情.为了过分简化一些事情,当处理器正在执行当前指令时,它已经提前读取了20多条指令并准备执行.如果你有一个分支,处理器需要决定*哪个*方面做"预读".如果出现误预测,那么"提前阅读和准备"的所有内容都需要丢弃并重新启动. (6认同)
  • @NicholasHamilton三元运算符*是*一个分支.虽然有些编译器(即MSVC)在优化它们方面似乎比普通的if语句更好. (5认同)
  • @EdwardBlack对于这种"预读"事情的恰当比喻是航空公司的航班时刻表.航班时刻表提前几个月.但是,当出现意外情况时(如风暴关闭主要枢纽),航班将被取消,并且该计划会暂时上升.结果?大规模的延误传播到许多甚至没有碰到那个机场的航班.当然对于处理器而言,"预先计划"窗口是纳秒级和最多几百个指令而不是数千个覆盖数月的飞行. (5认同)
  • @ One-One预测在管道的开始处完成,操作流经管道并到达其操作数的等待区域.一旦其操作数可用,指令就会执行,并且指令有资格退出(提交到实际状态).分支的退出检查猜测是否正确.如果没有,请按正确的指令刷新管道并重新启动指令提取器.如果预测是正确的,那就继续吧.此时,预测分支之后的许多指令已经开始但尚未提交状态. (4认同)
  • 这里有另一个事实.数据和时间局部性.当您随后多次访问相同位置时,其值仍在寄存器中,因此这就是循环交换使原始排序版本的性能翻倍的原因. (3认同)
  • @Mysticial,鉴于2015/6处理器的变化,这个答案是否仍然有效? (3认同)
  • @Adjit不,这太具体了.要带走的是*导致执行流程有条件地改变的*任何*由于分支错误预测而受到性能损失.这包括if语句,循环条件,开关,三元运算符,短路布尔逻辑,对函数指针的调用,对lambdas的调用,对虚拟/多态方法的调用等......(其中最后3个不是与分支预测本身有关,但同样的概念适用于处理器下一步"不知道去哪里".) (3认同)
  • 那么三元运算符呢?`sum + = data [i]> 128?data [i]:0` (2认同)
  • @Atul [维基百科关于分支预测的文章](https://en.wikipedia.org/wiki/Branch_predictor)有一些分支预测算法的例子.是否要将它们称为"AI"取决于您.对于您同时关于多个指令的其他问题,它被称为[Superscalar Execution](https://en.wikipedia.org/wiki/Superscalar_processor). (2认同)
  • 作为旁注,已经进行了一些研究,其中分支预测器能够"找出兰特()的模式".他们有一个基本上是'if(rand.nextInt(100)<50)`的分支,并正确地预测了99%的时间. (2认同)
  • @elfan No.分支预测不影响正确性.当处理器运行一组指令时,它必须表现为"好像"它逐行运行它们.它可以在下面使用技巧来加快速度(例如分支预测),但最后,它仍然必须尊重程序.对于您的其他问题,处理器将在分支指令执行后知道预测何时正确并确定它应该采用哪种方式. (2认同)
  • @elfan No.作为一个假设的例子:如果没有预测,它总是需要10秒.通过良好的预测,它将是2秒.由于预测一直不好,它将是12秒.额外的2秒是回头的开销.在大多数情况下,它将接近2秒,所以这是一场净胜利. (2认同)
  • GCC中还有__builtin_expect来帮助编译器.请参阅http://stackoverflow.com/questions/109710/likely-unlikely-macros-in-the-linux-kernel-how-do-they-work-whats-their (2认同)
  • @Evusas我不是硬件设计师,所以我肯定不知道答案.但回滚逻辑肯定不是免费的.即使CPU设计者设法完全隐藏误预测回滚的*性能*影响,仍然存在浪费计算的功耗方面的成本.今天的芯片经过了功率优化,可以改变时钟速度以保持功率限制.因此,错误预测造成的过度浪费会间接损害绩效,这当然有可能发生. (2认同)

Daniel Fisch.. 3833

分支预测.

对于排序数组,条件data[c] >= 128首先false是条纹值,然后true是所有后面的值.这很容易预测.使用未排序的数组,您需要支付分支成本.

  • @AgrimPathak这取决于.对于不太大的输入,当具有较高复杂度的算法的常数较小时,具有较高复杂度的算法比具有较低复杂度的算法更快.收支平衡点很难预测.此外,[比较此](http://stackoverflow.com/questions/14023988/why-is-processing-a-sorted-array-slower-than-an-unsorted-array?lq=1),地点很重要.Big-O很重要,但它不是表现的唯一标准. (114认同)
  • 所以基本上我通常学到的关于big-O的一切都不在窗外了?分拣成本高于分支成本会更好吗? (104认同)
  • 分支预测对排序数组与具有不同模式的数组的效果是否更好?例如,对于数组 - > {10,5,20,10,40,20,...},模式中数组中的下一个元素是80.这种数组是否会被分支预测加速如果遵循模式,下一个元素是80?或者它通常只对排序数组有帮助吗? (88认同)
  • 何时进行分支预测?什么时候语言会知道数组是排序的?我正在考虑数组的情况,如:[1,2,3,4,5,... 998,999,1000,3,10001,10002]?这个模糊的3会增加运行时间吗?它会和未排序的数组一样长吗? (53认同)
  • @FilipBartuzi分支预测发生在处理器中,低于语言级别(但语言可能提供告诉编译器可能性的方法,因此编译器可以发出适合于此的代码).在您的示例中,乱序3将导致分支错误预测(对于适当的条件,其中3给出的结果与1000不同),因此处理该数组可能比一个数组长几十或几百纳秒排序的数组几乎不会引人注意.花费时间的是错误预测率高,每千人一次误预测不多. (50认同)

WiSaGaN.. 3079

当数据被排序时,性能显着提高的原因是分支预测惩罚被删除,正如Mysticial的答案中精美地解释的那样.

现在,如果我们看一下代码

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

我们可以发现这个特定if... else...分支的含义是在条件满足时添加一些东西.这种类型的分支可以很容易地转换为条件移动语句,它将被编译成条件移动指令:cmovlx86系统中.分支以及因此潜在的分支预测惩罚被移除.

C,因此C++,语句,这将在直接编译(无任何优化)到条件移动指令x86,是三元运算符... ? ... : ....所以我们将上面的语句重写为等价的语句:

sum += data[c] >=128 ? data[c] : 0;

在保持可读性的同时,我们可以检查加速因子.

在Intel Core i7 -2600K @ 3.4 GHz和Visual Studio 2010发布模式下,基准测试是(从Mysticial复制的格式):

86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

64位

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

结果在多个测试中是稳健的.当分支结果不可预测时,我们得到了很大的加速,但是当它是可预测的时候我们会受到一点点的影响.事实上,在使用条件移动时,无论数据模式如何,性能都是相同的.

现在让我们通过调查x86他们生成的组件来更仔细地观察.为简单起见,我们使用两个函数max1max2.

max1使用条件分支if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2使用三元运算符... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

在x86-64计算机上,GCC -S生成下面的程序集.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2由于使用指令,使用的代码少得多cmovge.但真正的好处是max2不涉及分支跳转,jmp如果预测结果不正确,则会产生显着的性能损失.

那么为什么有条件的移动表现更好?

在典型的x86处理器中,指令的执行被分成几个阶段.粗略地说,我们有不同的硬件来处理不同的阶段.因此,我们不必等待一条指令完成开始新指令.这称为流水线.

在分支情况下,以下指令由前一个指令确定,因此我们不能进行流水线操作.我们必须等待或预测.

在条件移动的情况下,执行条件移动指令被分成几个阶段,但是早期阶段喜欢FetchDecode不依赖于前一个指令的结果; 只有后期才需要结果.因此,我们等待一个指令执行时间的一小部分.这就是为什么当预测很容易时,条件移动版本比分支慢.

" 计算机系统:程序员视角 "一书第二版详细解释了这一点.您可以检查章节移动指令的第3.6.6节,处理器架构的整个第4章,以及关于分支预测和错误预测惩罚的特殊处理的第5.11.2节.

有时,一些现代编译器可以优化我们的代码以便以更好的性能进行汇编,有时一些编译器不能(有问题的代码使用Visual Studio的本机编译器).在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化时更好地编写代码.

  • 除非您在GCC命令行中添加-O,否则没有默认的优化级别.(你的英语不会超过我的;) (122认同)
  • @WiSaGaN代码没有任何说明,因为你的两段代码编译成相同的机器代码.至关重要的是,人们不会认为你的例子中的if语句与你的例子中的terenary有所不同.你确实拥有你最后一段中的相似之处,但这并不能抹掉这个例子其余部分有害的事实. (86认同)
  • 我发现很难相信编译器可以比等效的if语句更好地优化三元运算符.您已经证明GCC将三元运算符优化为条件运算; 你*没有*表明它对if语句没有做同样的事情.事实上,根据上面的Mystical,GCC*确实*将if语句优化为条件移动,这将使得这个答案完全不正确. (76认同)
  • @WiSaGaN如果您修改了删除误导性`-O0`示例的答案并在两个测试用例中显示*optimized*asm的差异,我的downvote肯定会成为一个upvote. (44认同)
  • @UpAndAdam在测试的那一刻,即使在指定高优化级别时,VS2010也无法将原始分支优化为条件移动,而gcc可以. (44认同)
  • 这种三元运算符技巧可以很好地用于Java.在阅读了Mystical的答案后,我想知道如何为Java避免错误的分支预测,因为Java没有任何与-O3相同的东西.三元运算符:2.1943s和原始:6.0303s. (5认同)
  • @ BlueRaja-DannyPflughoeft这是未经优化的版本.编译器没有优化三元运算符,它只是转换它.如果给定足够的优化级别,GCC可以优化if-then,然而,这个显示了条件移动的力量,并且手动优化有所不同. (3认同)

vulcan raven.. 2115

如果您对可以对此代码进行的更多优化感到好奇,请考虑以下事项:

从原始循环开始:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

通过循环交换,我们可以安全地将此循环更改为:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

然后,您可以看到if条件在i循环执行过程中是不变的,因此您可以将其提升if:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

然后,您会看到内部循环可以折叠成一个单独的表达式,假设浮点模型允许它(例如,/ fp:fast被抛出)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

那个比以前快了100,000倍

  • 如果你想作弊,你也可以在循环外进行乘法,并在循环后求和*= 100000. (250认同)
  • @Michael-我相信这个例子实际上是[循环不变的提升](http://en.wikipedia.org/wiki/Loop-invariant_code_motion)(LIH)优化的一个例子,而不是[loop swap](http: //en.wikipedia.org/wiki/Loop_interchange).在这种情况下,整个内环独立于外环,因此可以从外环中提升,因此结果简单地乘以一个单位= 1e5的"i"的和.它对最终结果没有任何影响,但我只是想直接设置记录,因为这是一个经常光顾的页面. (62认同)
  • 虽然不是交换循环的简单精神,但此时内部的"if"可以转换为:`sum + =(data [j]> = 128)?data [j]*100000:0;`编译器可以将其缩减为`cmovge`或等效的. (43认同)
  • 外循环是为了使内环足够大的时间来分析.那你为什么要循环交换呢?最后,无论如何都会删除该循环. (31认同)
  • @saurabheights:错误的问题:为什么编译器会循环交换.Microbenchmarks很难;) (21认同)

caf.. 1764

毫无疑问,我们中的一些人会对识别对CPU的分支预测器有问题的代码感兴趣.Valgrind工具cachegrind有一个分支预测模拟器,通过使用--branch-sim=yes标志启用.在这个问题的例子中运行它,将外部循环的数量减少到10000并用其编译g++,得到以下结果:

排序方式:

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

未排序:

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

深入研究cg_annotate我们在相关循环中看到的逐行输出:

排序方式:

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

未排序:

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

这使您可以轻松识别有问题的行 - 在未排序的版本中,该if (data[c] >= 128)行在Bcmcachegrind的分支预测模型下导致164,050,007个错误预测的条件分支(),而它仅在排序版本中导致10,006.


或者,在Linux上,您可以使用性能计数器子系统来完成相同的任务,但使用CPU计数器具有本机性能.

perf stat ./sumtest_sorted

排序方式:

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

未排序:

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

它还可以使用反汇编来执行源代码注释.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

有关详细信息,请参阅性能教程.

  • @ tall.b.lo:25%属于所有分支 - 循环中有*两个*分支,一个用于`data [c]> = 128`(其中有50%的未命中率)和一个对于具有~0%未命中率的循环条件`c <arraySize`. (106认同)
  • 这是可怕的,在未排序的列表中,应该有50%的机会击中添加.不知何故,分支预测只有25%的失误率,它怎么能比50%的失误更好? (61认同)

atlaste.. 1229

我刚刚读到了这个问题及其答案,我觉得答案遗失了.

消除我发现在托管语言中工作特别好的分支预测的常用方法是查找表而不是使用分支(尽管在这种情况下我还没有测试过).

这种方法通常适用于:

  1. 它是一个小桌子,可能会被缓存在处理器中,并且
  2. 你在一个非常紧凑的循环中运行和/或处理器可以预加载数据.

背景和原因

从处理器的角度来看,你的记忆很慢.为了弥补速度的差异,处理器(L1/L2缓存)中内置了几个缓存.所以想象一下,你正在进行漂亮的计算并弄清楚你需要一块内存.处理器将获得其"加载"操作并将内存加载到缓存中 - 然后使用缓存执行其余计算.因为内存相对较慢,这种"加载"会降低程序的速度.

与分支预测一样,这在Pentium处理器中进行了优化:处理器预测它需要加载一段数据并尝试在操作实际到达缓存之前将其加载到缓存中.正如我们已经看到的那样,分支预测有时会出现严重错误 - 在最坏的情况下,您需要返回并实际等待内存负载,这将需要永远(换句话说:失败的分支预测是坏的,一个内存在分支预测失败后加载是非常可怕的!).

幸运的是,如果内存访问模式是可预测的,处理器将把它加载到快速缓存中,一切都很顺利.

我们需要知道的第一件事是什么是小的?虽然较小通常更好,但经验法则是坚持查找大小<= 4096字节的表.作为上限:如果您的查找表大于64K,则可能值得重新考虑.

构建一个表

所以我们已经发现我们可以创建一个小表.接下来要做的是获得一个查找功能.查找函数通常是使用几个基本整数运算的小函数(和,或者,xor,shift,add,remove和multiply).您希望通过查找功能将您的输入转换为表格中的某种"唯一键",然后简单地为您提供您希望它完成的所有工作的答案.

在这种情况下:> = 128意味着我们可以保留值,<128意味着我们摆脱它.最简单的方法是使用'AND':如果我们保留它,我们和7FFFFFFF; 如果我们想要摆脱它,我们和它的0.注意另外128是2的幂 - 所以我们可以继续制作一个32768/128整数的表并填充一个零和很多7FFFFFFFF的.

托管语言

您可能想知道为什么这在托管语言中运行良好.毕竟,托管语言使用分支检查数组的边界,以确保您不会陷入困境......

好吧,不完全...... :-)

为管理语言删除此分支已经做了相当多的工作.例如:

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在这种情况下,编译器显然不会遇到边界条件.至少Microsoft JIT编译器(但我希望Java做类似的事情)会注意到这一点,并完全删除检查.哇,这意味着没有分支.同样,它将处理其他明显的情况.

如果您在托管语言中查找时遇到问题 - 关键是& 0x[something]FFF要在查找函数中添加一个以使边界检查可预测 - 并观察它更快.

这种情况的结果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

  • 因为没有分支比分支更好:-)在很多情况下,这只是快得多......如果你正在优化,那绝对值得一试.他们在f.ex中也使用了相当多的东西.http://graphics.stanford.edu/~seander/bithacks.html (94认同)
  • 你想绕过分支预测器,为什么?这是一个优化. (49认同)
  • 为什么不`sum + = lookup [data [j]]`其中`lookup`是一个包含256个条目的数组,第一个是零,最后一个是否等于索引? (35认同)
  • @Zain如果你真的想知道......是的:分支机构15秒,我的版本10分钟.无论如何,知道任何一种方式都是一种有用的技术. (28认同)
  • 通常,查找表可以很快,但是您是否针对此特定条件运行了测试?你的代码中仍然会有一个分支条件,现在它只被移动到查找表生成部分.你仍然不会得到你的性能提升 (27认同)

Saqlain.. 1099

当数组排序时,数据分布在0到255之间,迭代的前半部分将不会进入if-statement(if语句在下面共享).

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

问题是:在某些情况下,如果排序数据,上述语句不执行的原因是什么?这是"分支预测器".分支预测器是一种数字电路,它试图在确定分支(例如if-then-else结构)之前猜测分支的方向.分支预测器的目的是改善指令流水线中的流量.分支预测器在实现高效性能方面发挥着关键作用!

让我们做一些基准测试来更好地理解它

if-statement 的表现取决于其条件是否具有可预测的模式.如果条件始终为真或始终为假,则处理器中的分支预测逻辑将获取模式.另一方面,如果模式不可预测,那么 - if陈述将更加昂贵.

让我们用不同的条件来衡量这个循环的性能:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

以下是具有不同真假模式的循环的时序:

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

一个" 糟糕的 "真假模式可以使if声明的速度比" "模式慢六倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令.

因此,分支预测对性能的影响毫无疑问!

  • 您没有显示"随机"TF模式的时间. (46认同)
  • @MooingDuck'因为它不会产生任何影响 - 该值可以是任何值,但它仍将处于这些阈值的范围内.那么为什么在你已经知道限制时会显示随机值?虽然我同意你可以为了完整性而展示一个,并且"只是为了它的he". (17认同)
  • @ cst1992:现在他最慢的时间是TTFFTTFFTTFF,在我的人眼看来,这似乎是可以预测的.随机本身就是不可预测的,所以完全有可能它会更慢,因此超出了这里所示的限制.OTOH,可能是TTFFTTFF完全击中了病理情况.分不清楚,因为他没有显示随机的时间. (17认同)
  • @MooingDuck对于人眼来说,"TTFFTTFFTTFF"是一个可预测的序列,但我们在这里讨论的是内置在CPU中的分支预测器的行为.分支预测器不是AI级模式识别; 这很简单.当你只是交替分支时,它不能很好地预测.在大多数代码中,分支几乎始终以相同的方式运行; 考虑一个执行一千次的循环.循环结束时的分支返回到循环的开始999次,然后第1000次执行不同的操作.通常,一个非常简单的分支预测器运行良好. (14认同)
  • @steveha:我认为你正在假设CPU分支预测器是如何工作的,我不同意这种方法.我不知道该分支预测器有多先进,但我似乎认为它比你更先进.你可能是对的,但测量肯定会很好. (13认同)
  • @steveha:两级自适应预测器可以锁定TTFFTTFF模式,没有任何问题."这种预测方法的变体用于大多数现代微处理器".局部分支预测和全局分支预测基于两级自适应预测器,它们也可以."全局分支预测用于AMD处理器,以及基于Intel Pentium M,Core,Core 2和Silvermont的Atom处理器"还将同意预测器,混合预测器,间接跳转预测添加到该列表中.循环预测器不会锁定,但达到75%.只留下2个无法锁定的东西 (4认同)
  • @MooingDuck:Surt的图[下面的回答](http://stackoverflow.com/a/33070112/4509583)我想解释为什么TTFFTTFF实际上是Saqlain的例子中的"病态案例". (4认同)
  • @MooingDuck我确实不是处理器设计方面的专家.但我邀请您阅读有关分支预测变量的维基百科页面.所讨论的设计中没有一个可以锁定TTFFTTFF模式......并正确预测.(除了可能用于神经网络,具有足够先进的神经网络,我敢打赌你现金,你没有拥有在其处理器中具有这种分支预测器的计算设备.)https:// en. wikipedia.org/wiki/Branch_predictor (3认同)

steveha.. 1023

避免分支预测错误的一种方法是构建查找表,并使用数据对其进行索引.Stefan de Bruijn在他的回答中讨论了这个问题.

但在这种情况下,我们知道值在[0,255]范围内,我们只关心值> = 128.这意味着我们可以轻松地提取一个位,告诉我们是否需要一个值:通过移位数据向右7位,我们留下0位或1位,我们只想在有1位时加上该值.我们称这个位为"决策位".

通过使用决策位的0/1值作为数组的索引,无论数据是排序还是未排序,我们都可以制作同样快速的代码.我们的代码总是会添加一个值,但是当决策位为0时,我们会将值添加到我们不关心的地方.这是代码:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代码浪费了一半的添加但从未有分支预测失败.随机数据的速度比具有实际if语句的版本快得多.

但在我的测试中,显式查找表略快于此,可能是因为索引到查找表的速度比位移略快.这显示了我的代码如何设置和使用查找表(lut代码中缺乏想象力的"LookUp表").这是C++代码:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在这种情况下,查找表只有256个字节,因此它非常适合缓存,而且速度很快.如果数据是24位值并且我们只想要它们中的一半,这种技术将无法正常工作......查找表太大而不实用.另一方面,我们可以结合上面显示的两种技术:首先将位移位,然后索引查找表.对于我们只需要上半部分值的24位值,我们可能将数据右移12位,并为表索引留下12位值.12位表索引意味着一个包含4096个值的表,这可能是实用的.

索引到数组而不是使用if语句的技术可用于决定使用哪个指针.我看到一个实现二叉树的库,而不是有两个命名指针(pLeft和/ pRight或其他)有一个长度为2的指针数组,并使用"决策位"技术来决定遵循哪一个.例如,而不是:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个库会做类似的事情:

i = (x < node->value);
node = node->link[i];

这是这段代码的链接:红黑树,永恒的混淆

  • 是的,您也可以直接使用该位并乘以(`data [c] >> 7` - 这也在这里讨论过); 我故意将此解决方案排除在外,但当然你是对的.只是一个小注释:查找表的经验法则是,如果它适合4KB(因为缓存),它将起作用 - 最好使表尽可能小.对于托管语言,我将其推到64KB,对于像C++和C这样的低级语言,我可能会重新考虑(这只是我的经验).由于`typeof(int)= 4`,我试着坚持最多10位. (25认同)
  • 我认为使用0/1值进行索引可能会比整数乘法更快,但我想如果性能真的很重要,你应该对其进行分析.我同意小的查找表对于避免缓存压力是必不可少的,但很明显,如果你有更大的缓存,你可以使用更大的查找表,所以4KB更像是经验法则而不是硬规则.我想你的意思是'sizeof(int)== 4`?这对32位来说是正确的.我两岁的手机有一个32KB的L1缓存,所以即使4K查找表也可以工作,特别是如果查找值是一个字节而不是一个int. (16认同)
  • 可能我错过了一些东西,但是在你的`j`等于0或1的方法中为什么不在添加它之前将你的值乘以`j`而不是使用数组索引(可能应该乘以`1-j`而不是`j`) (11认同)
  • @steveha PS:另一个可能的答案是`int c = data [j]; sum + = c& - (c >> 7);`它根本不需要乘法. (10认同)
  • @steveha乘法应该更快,我试着在英特尔书籍中查找它,但找不到它......无论哪种方式,基准测试也给我这个结果. (6认同)

Yves Daoust.. 927

在排序的情况下,您可以做得比依赖成功的分支预测或任何无分支比较技巧更好:完全删除分支.

实际上,阵列被分隔在一个连续的区域data < 128和另一个区域data >= 128.因此,您应该使用二分法搜索找到分区点(使用Lg(arraySize) = 15比较),然后从该点进行直接累积.

像(未经检查)的东西

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或者,稍微混淆一点

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种更快的方法,它给出了排序或未排序的近似解决方案:( sum= 3137536;假设真正均匀分布,16384个样本,期望值为191.5):-)

  • `sum = 3137536` - 聪明.这显然不是问题的重点.问题显然是解释令人惊讶的性能特征.我倾向于说添加`std :: partition`而不是`std :: sort`是有价值的.虽然实际问题不仅限于给出的综合基准. (22认同)
  • @DeadMG:这确实不是给定密钥的标准二分法搜索,而是搜索分区索引; 每次迭代需要一次比较.但是不要依赖这个代码,我还没有检查过它.如果您对保证正确的实施感兴趣,请告诉我. (12认同)

Harsh Sharma.. 749

由于分支预测,上述行为正在发生.

要理解分支预测,首先必须了解指令管道:

任何指令都被分成一系列步骤,以便可以并行地同时执行不同的步骤.这种技术称为指令流水线,用于提高现代处理器的吞吐量.要更好地理解这一点,请在维基百科上查看此示例.

通常,现代处理器具有相当长的流水线,但为了方便起见,我们仅考虑这4个步骤.

  1. IF - 从内存中获取指令
  2. ID - 解码指令
  3. EX - 执行指令
  4. WB - 写回CPU寄存器

4级管道一般用于2条指令. 一般为4级管道

回到上面的问题,让我们考虑以下说明:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果没有分支预测,将发生以下情况:

为了执行指令B或指令C,处理器必须等到指令A没有到达流水线中的EX阶段,因为转到指令B或指令C的决定取决于指令A的结果.所以管道会是这样的.

当if条件返回true时: 在此输入图像描述

当if条件返回false时: 在此输入图像描述

作为等待指令A的结果的结果,在上述情况下花费的总CPU周期(没有分支预测;对于真和假)都是7.

那么什么是分支预测?

分支预测器将尝试猜测分支(if-then-else结构)将以何种方式确定之前.它不会等待指令A到达流水线的EX阶段,但它会猜测决定并转到该指令(在我们的例子中是B或C).

如果猜测正确,管道看起来像这样: 在此输入图像描述

如果稍后检测到猜测错误则丢弃部分执行的指令,并且管道以正确的分支重新开始,从而引起延迟.在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段的数量.现代微处理器往往具有相当长的流水线,因此误预测延迟在10到20个时钟周期之间.管道越长,对分支预测器的需求就越大.

在OP的代码中,第一次有条件时,分支预测器没有任何基于预测的信息,所以第一次它会随机选择下一条指令.稍后在for循环中,它可以基于历史记录进行预测.对于按升序排序的数组,有三种可能性:

  1. 所有元素都小于128
  2. 所有元素都大于128
  3. 一些起始新元素小于128,后来大于128

让我们假设预测器将在第一次运行时始终采用真分支.

因此,在第一种情况下,它始终采用真正的分支,因为历史上它的所有预测都是正确的.在第二种情况下,最初它会预测错误,但经过几次迭代后,它会正确预测.在第三种情况下,它将最初正确预测,直到元素小于128.之后它将失败一段时间并且当它看到历史中的分支预测失败时正确.

在所有这些情况下,故障的数量将会减少,因此,只需要几次就可以丢弃部分执行的指令并重新使用正确的分支,从而减少CPU周期.

但是在随机未排序的数组的情况下,预测将需要丢弃部分执行的指令并且在大多数时间重新开始使用正确的分支,并且与排序的数组相比产生更多的CPU周期.


Surt.. 656

官方的答案是来自

  1. 英特尔 - 避免分支机构错误预测的成本
  2. 英特尔 - 分支和循环重组以防止错误预测
  3. 科学论文 - 分支预测计算机结构
  4. 书籍:JL Hennessy,DA Patterson:计算机体系结构:定量方法
  5. 科学出版物中的文章:TY Yeh,YN Patt在分支预测上做了很多这些.

您还可以从这个可爱的图表中看到为什么分支预测器会混淆.

2位状态图

原始代码中的每个元素都是随机值

data[c] = std::rand() % 256;

因此,预测因素将会改变方向std::rand().

另一方面,一旦它被排序,预测器将首先进入强烈未被采用的状态,并且当值变为高值时,预测器将在三次运行中通过从强烈不采取到强烈采取的一直改变.



rkachach.. 622

在同一行(我认为没有任何答案突出显示),有时候(特别是在性能很重要的软件中,比如在Linux内核中),你可以找到一些if语句,如下所示:

if (likely( everything_is_ok ))
{
    /* Do something */
}

或类似的:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

双方likely()unlikely()在由使用像海湾合作委员会的定义其实宏__builtin_expect帮助编译器插入代码的预测偏向考虑到用户提供的信息的条件.GCC支持其他可能改变正在运行的程序行为的内置函数或发出低级指令,如清除缓存等.请参阅此文档,该文档介绍了可用的GCC内置函数.

通常,这种优化主要在硬实时应用程序或嵌入式系统中找到,其中执行时间很重要且非常重要.例如,如果您正在检查仅发生1/10000000次的错误情况,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假.


Maciej.. 592

在C++中经常使用的布尔运算在编译的程序中产生许多分支.如果这些分支是在循环内部并且很难预测它们会显着减慢执行速度.布尔变量存储为8位整数,其值为0for false1for true.

布尔变量是超定的,因为所有具有布尔变量作为输入的运算符检查输入是否具有除0or 之外的任何其他值1,但是具有布尔值作为输出的运算符不能产生除0or 之外的其他值1.这使得使用布尔变量作为输入的操作效率低于必要的.考虑示例:

bool a, b, c, d;
c = a && b;
d = a || b;

这通常由编译器以下列方式实现:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

这段代码远非最优.如果误预测,分支机构可能需要很长时间.如果确定操作数没有其他值而不是0和,则可以使布尔运算更有效1.编译器没有做出这样的假设的原因是,如果变量未初始化或来自未知来源,则变量可能具有其他值.上面的代码可以被优化,如果ab都被初始化为有效值,或者如果它们来自运营商产生布尔输出.优化的代码如下所示:

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char而不是bool为了使得可以使用按位运算符(&|)而不是布尔运算符(&&||).按位运算符是单个指令,只需一个时钟周期.OR运算符(|)即使a并且b具有除0or 之外的其他值也可以工作1.如果操作数具有除和之外的其他值,AND运算符(&)和EXCLUSIVE OR运算符(^)可能会给出不一致的结果.01

~不能用于NOT.相反,你可以对已知的变量01通过XOR对其进行布尔值1:

bool a, b;
b = !a;

可以优化为:

char a = 0, b;
b = a ^ 1;

a && b不能替换为a & bif b是一个不应该被评估的表达式,如果afalse(&&将不会评估b,&将).同样地,a || b不能被替换a | b,如果b是,如果不应该被计算的表达式atrue.

如果操作数是变量而不是操作数是比较,则使用按位运算符更有利:

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下是最佳的(除非您希望&&表达式生成许多分支错误预测).


Alireza.. 269

这是肯定的!...

分支预测会使逻辑运行速度变慢,因为代码中会发生切换!这就像你要走一条直街或一条有很多转弯的街道,肯定会直接做得更快!...

如果对数组进行排序,则在第一步中您的条件为false:data[c] >= 128然后成为到街道尽头的整个路径的真值.这就是你如何更快地完成逻辑的结束.另一方面,使用未排序的数组,您需要进行大量的转换和处理,这会使您的代码运行得更慢...

看下面我为你创建的图片.哪条街要快点完成?

分支预测

因此,以编程方式,分支预测会导致进程变慢...

最后,我们很高兴知道我们有两种分支预测,每种分支预测都会以不同的方式影响您的代码:

1.静态

2.动态

分支预测

微处理器在第一次遇到条件分支时使用静态分支预测,并且动态分支预测用于条件分支代码的后续执行.

为了有效地编写代码以利用这些规则,在编写if-elseswitch语句时,首先检查最常见的情况,然后逐步处理最不常见的情况.循环不一定需要任何特殊的代码排序用于静态分支预测,因为通常只使用循环迭代器的条件.


ForeverLearn.. 252

这个问题已经多次得到了很好的回答.我仍然希望将该小组的注意力吸引到另一个有趣的分析上.

最近这个例子(稍微修改过)也被用来演示如何在Windows上的程序本身中分析一段代码.在此过程中,作者还展示了如何使用结果来确定代码在排序和未排序的情况下花费大部分时间的位置.最后,该文章还展示了如何使用HAL(硬件抽象层)的一个鲜为人知的特征来确定在未排序的情况下发生了多少分支错误预测.

链接在这里:http: //www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

  • 这是一篇非常有趣的文章(事实上,我刚读完了所有文章),但它是如何回答这个问题的? (2认同)

Gearon.. 164

正如其他人已经提到的那样,神秘的背后是分支预测器.

我不是想添加一些东西,而是以另一种方式解释这个概念.维基上有一个简明的介绍,其中包含文本和图表.我喜欢下面的解释,它使用图表直观地阐述了分支预测器.

在计算机体系结构中,分支预测器是一种数字电路,它试图猜测分支(例如if-then-else结构)在确定之前会走哪条路.分支预测器的目的是改善指令流水线中的流量.分支预测器在许多现代流水线微处理器架构(如x86)中实现高效性能方面发挥着关键作用.

双向分支通常使用条件跳转指令来实现.条件跳转可以"不采用"并继续执行第一个代码分支,紧接在条件跳转之后,或者可以"采取"并跳转到程序存储器中的不同位置,其中第二个代码分支是存储.在计算条件并且条件跳转已经通过指令流水线中的执行阶段之前,不确定是否采取条件跳转是未知的(见图1).

图1

基于所描述的场景,我编写了一个动画演示,以显示在不同情况下如何在管道中执行指令.

  1. 没有分支预测器.

在没有分支预测的情况下,处理器必须等到条件跳转指令已经通过执行阶段,然后下一条指令才能进入流水线中的提取阶段.

该示例包含三个指令,第一个是条件跳转指令.后两条指令可以进入流水线,直到执行条件跳转指令.

没有分支预测器

完成3条指令需要9个时钟周期.

  1. 使用分支预测器,不要进行条件跳转.让我们假设预测没有采取条件跳跃.

在此输入图像描述

完成3条指令需要7个时钟周期.

  1. 使用分支预测器并进行条件跳转.让我们假设预测没有采取条件跳跃.

在此输入图像描述

完成3条指令需要9个时钟周期.

在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段的数量.现代微处理器往往具有相当长的流水线,因此误预测延迟在10到20个时钟周期之间.因此,使管道更长时间增加了对更高级分支预测器的需求.

如您所见,似乎我们没有理由不使用Branch Predictor.

这是一个非常简单的演示,阐明了分支预测器的基本部分.如果这些GIF很烦人,请随时将它们从答案中删除,访问者也可以从git获取演示


Tony Tannous.. 159

分支预测增益!

重要的是要理解分支错误预测不会减慢程序的速度.错过预测的成本就像分支预测不存在一样,您等待表达式的评估以决定运行什么代码(在下一段中进一步解释).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

只要有if-else\ switch_语句,就必须计算表达式以确定应该执行哪个块.在编译器生成的汇编代码中,插入条件分支指令.

分支指令可以使计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即,如果表达式为假,则程序跳过if块的代码),这取决于某些条件,即在我们的案例中的表达评估.

话虽这么说,编译器会尝试在实际评估之前预测结果.它将从if块中获取指令,如果表达式结果为真,那就太棒了!我们获得了评估它并在代码中取得进展所花费的时间; 如果没有,那么我们运行错误的代码,刷新管道,并运行正确的块.

可视化:

假设您需要选择路线1或路线2.等待您的伴侣检查地图,您已停在##并等待,或者您可以选择路线1,如果您幸运(路线1是正确路线),然后很棒,你不必等待你的伴侣检查地图(你节省了检查地图的时间),否则你只需要回头.

虽然冲洗管道速度非常快,但现在采取这种赌博是值得的.预测排序数据或变化缓慢的数据总是比预测快速变化更容易和更好.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------


aghilpro.. 105

这是关于分支预测.它是什么?

  • 分支预测器是古老的性能改进技术之一,它仍然与现代建筑相关.虽然简单的预测技术提供快速查找和功率效率,但是它们具有高的误预测率.

  • 另一方面,复杂的分支预测 - 无论是基于神经的还是两级分支预测的变体 - 提供更好的预测准确性,但它们消耗更多的功率和复杂性呈指数增长.

  • 除此之外,在复杂的预测技术中,预测分支所花费的时间本身非常高,从2到5个周期 - 这与实际分支的执行时间相当.

  • 分支预测本质上是一种优化(最小化)问题,其中重点在于以最少的资源实现最低可能的未命中率,低功耗和低复杂度.

确实有三种不同的分支:

转发条件分支 - 基于运行时条件,PC(程序计数器)被改变为指向指令流中的前向地址.

向后条件分支 - PC在指令流中变为指向后向.分支基于某些条件,例如,当循环结束时的测试表明循环应该再次执行时,向后分支到程序循环的开头.

无条件分支 - 包括跳转,过程调用和没有特定条件的返回.例如,无条件跳转指令可能用汇编语言编码为简单的"jmp",并且指令流必须立即定向到跳转指令指向的目标位置,而条件跳转可能被编码为"jmpne"仅当先前"比较"指令中两个值的比较结果显示值不相等时,才会重定向指令流.(x86体系结构使用的分段寻址方案增加了额外的复杂性,因为跳转可以是"近"(在一个段内)或"远"(在段外).每种类型对分支预测算法都有不同的影响.)

静态/动态分支预测:微处理器在第一次遇到条件分支时使用静态分支预测,并且动态分支预测用于条件分支代码的后续执行.

参考文献:


Luke Hutchis.. 94

在ARM上,不需要分支,因为每条指令都有一个4位条件字段,它以零成本进行测试.这消除了对短分支的需要,并且不会出现分支预测.因此,由于排序的额外开销,排序版本将比ARM上的未排序版本运行得慢.内部循环看起来如下所示:

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize


Yochai Timme.. 90

除了分支预测可能会降低您的速度之外,排序数组还有另一个优势:

您可以设置停止条件而不是仅检查值,这样您只需循环查看相关数据,并忽略其余数据.
分支预测只会遗漏一次.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }


Omkaar.K.. 83

由于称为分支预测的现象,排序的阵列比未排序的阵列处理得更快.

分支预测器是一种数字电路(在计算机体系结构中),试图预测分支将以哪种方式运行,从而改善指令流水线中的流量.电路/计算机预测下一步并执行它.

做出错误的预测会导致返回上一步,并执行另一个预测.假设预测正确,代码将继续下一步.错误的预测导致重复相同的步骤,直到发生正确的预测.

你的问题的答案很简单.

在未排序的数组中,计算机会进行多次预测,从而导致错误发生的可能性增加.然而,在排序中,计算机进行的预测更少,从而减少了出错的可能性.进行更多预测需要更多时间.

分类阵列:直道

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排序的阵列:弯曲的道路

______   ________
|     |__|

分支预测:猜测/预测哪条道路是直的并且在没有检查的情况下跟随它

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条道路都到达同一目的地,但直道较短,而另一条较长.如果那时你错误地选择了另一个,那么就没有回头了,所以如果你选择更长的路,你会浪费一些额外的时间.这与计算机上发生的情况类似,我希望这有助于您更好地理解.


另外我想从评论中引用@Simon_Weaver:

它不会减少预测 - 它会减少不正确的预测.它仍然必须通过循环每次预测..

  • *"用简单的话说"* - 我发现你的解释不像火车那么简单,而且远不如其他任何答案准确,尽管我不是初学者.我很好奇为什么会有这么多的赞成,或许未来的一位赞助人可以告诉我? (9认同)
  • @Sinatr它可能真的是以意见为基础,我自己发现它足以支持它,它不像其他例子那样准确,这就是重点:放弃答案(因为我们都同意这里涉及分支预测)没有让读者像其他人那样(很好地)进行技术解释.我认为他做得很好. (6认同)
  • 哦,你的正确,我的不好,谢谢你@Simon_Weaver,我会在一段时间内纠正它,或者请你可以编辑它然后我会批准它,在此先感谢... (4认同)
  • 它不会减少预测 - 它会减少不正确的预测.它仍然必须通过循环每次预测. (3认同)

user2297550.. 5

需要对数据进行排序的其他答案的假设是不正确的.

以下代码不对整个数组进行排序,而是仅对其中的200个元素进行排序,从而运行得最快.

仅对k元素部分进行排序以线性时间完成预处理而不是n.log(n).

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

这也"证明"它与任何算法问题无关,例如排序顺序,它确实是分支预测.


提问时间:

查看次数:

1314912 次

最近活跃:

6 月,3 周 前