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


这是一段看似非常特殊的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);
    }
}

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


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

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

21674
2018-06-27 13:51


起源


只是为了记录。在Windows / VS2017 / i7-6700K 4GHz上,两个版本之间没有区别。两种情况都需要0.6秒。如果外部循环中的迭代次数增加10倍,则两种情况下执行时间也增加10倍至6秒。 - mp31415
@ user194715:任何使用a的编译器 cmov 或其他无分支实现(如自动向量化) pcmpgtd)将具有不依赖于任何CPU的数据的性能。但是,如果它是分支的,它将依赖于任何具有无序推测执行的CPU。 (即使是高性能的有序CPU也使用分支预测来避免在所采用的分支上获取/解码气泡;未命中损失更小)。 - Peter Cordes
Woops ... re:Meltdown和Spectre - KyleMit
@KyleMit是否与两者有关?我对两者都没有太多了解 - mohitmun
@mohitmun,这两个安全漏洞都属于广泛的漏洞类别 “分支目标注射”攻击 - KyleMit


答案:


你是受害者 分支预测 失败。


什么是分支预测?

考虑一个铁路交界处:

Licensed Image 图片 通过Mecanismo,通过Wikimedia Commons。使用下 CC-By-SA 3.0 执照。

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

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

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

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

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

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


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

image2

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

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

有没有更好的办法?你猜猜分支的方向!

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

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


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

那么你如何战略性地猜测火车必须备份并沿着另一条路走下去的次数呢?你看看过去的历史!如果火车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

观察:

  • 与分公司: 排序和未排序的数据之间存在巨大差异。
  • 随着黑客: 排序数据和未排序数据之间没有区别。
  • 在C ++的情况下,当数据被排序时,hack实际上比分支慢一点。

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


更新:

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

  • 即使在VC ++ 2010中,VC ++ 2010也无法为此分支生成条件移动 /Ox

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

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

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


28593
2018-06-27 13:56



@Mysticial为了避免转移黑客,你可以写出像 int t=-((data[c]>=128)) 生成掩码。这也应该更快。知道编译器是否足够聪明以插入条件移动会很有趣。 - Mackie Messer
@phonetagger看看这个后续问题: stackoverflow.com/questions/11276291/...英特尔编译器非常接近完全摆脱外循环。 - Mysticial
@Novelocrat只有一半是正确的。当它为零时将1移入符号位确实是UB。那是因为它是有符号整数溢出。但是,从符号位移出1是IB。右移有负有符号整数是IB。您可以进入这样的论点,即C / C ++不要求顶部位是符号指示符。但实施细节是IB。 - Mysticial
@Mysticial非常感谢链接。看起来很有希望。我会去的。最后一个请求。对不起,但请不要介意,你能告诉我你怎么做到这一点 int t = (data[c] - 128) >> 31; sum += ~t & data[c]; 替换上面的原始if条件? - Unheilig
我的语法要我认为这应该是“...分支预测的受害者失败URE“而不仅仅是”......分支预测的受害者失败了。“ - jdero


分支预测。

使用排序数组,条件 data[c] >= 128 是第一个 false 对于一连串的价值观,然后成为 true 对于所有后来的值。这很容易预测。使用未排序的数组,您需要支付分支成本。


3640
2018-06-27 13:54



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


当数据被排序时性能显着提高的原因在于去除了分支预测惩罚,如精细地解释的那样 Mysticial的答案。

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

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

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

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

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

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

在英特尔 酷睿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 它们产生的组装。为简单起见,我们使用两个函数 max1 和 max2

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 处理器,指令的执行分为几个阶段。粗略地说,我们有不同的硬件来处理不同的阶段。因此,我们不必等待一条指令完成开始新指令。这就是所谓的 流水线

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

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

这本书 计算机系统:程序员的观点,第二版 详细解释了这一点。您可以查看第3.6.6节了解 有条件的移动指令,整个第4章 处理器架构和第5.11.2节的特殊处理 分支预测与错误预测处罚

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


2961
2018-06-28 02:14



除非您在GCC命令行中添加-O,否则没有默认的优化级别。 (你的英语不会超过我的;) - Yann Droneaud
我发现很难相信编译器可以比等效的if语句更好地优化三元运算符。您已经证明GCC将三元运算符优化为条件运算;您 没有 表明它对if语句没有做同样的事情。事实上,根据上面的神秘主义,GCC 不 优化if语句到条件移动,这将使这个答案完全不正确。 - BlueRaja - Danny Pflughoeft
@WiSaGaN代码没有任何说明,因为你的两段代码编译成相同的机器代码。至关重要的是,人们不会认为你的例子中的if语句与你的例子中的terenary有所不同。你确实拥有你上一段中的相似之处,但这并不能抹掉这个例子其余部分有害的事实。 - Justin L.
@WiSaGaN如果你修改你的答案以消除误导,我的downvote肯定会变成一个upvote -O0 示例并显示其中的差异 优化 asm在你的两个测试用例上。 - Justin L.
@UpAndAdam在测试的那一刻,即使在指定高优化级别时,VS2010也无法将原始分支优化为条件移动,而gcc可以。 - WiSaGaN


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

从原始循环开始:

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倍


2026
2017-07-03 02:25



如果你想作弊,你也可以在循环外进行乘法,并在循环后求和* = 100000。 - Jyaif
@Michael - 我相信这个例子实际上是一个例子 循环不变的提升 (LIH)优化,而不是 循环交换。在这种情况下,整个内环独立于外环,因此可以从外环中提升,因此结果简单地乘以一个总和。 i 一个单位= 1e5。它对最终结果没有任何影响,但我只是想直接设置记录,因为这是一个经常光顾的页面。 - Yair Altman
虽然不是简单的交换循环,内在的精神 if 此时可以转换为: sum += (data[j] >= 128) ? data[j] * 100000 : 0; 编译器可能会减少到 cmovge 或同等学历。 - Alex North-Keys
外环是使内环足够大的时间来分析。那你为什么要循环交换呢?最后,无论如何都会删除该循环。 - saurabheights
@saurabheights:错误的问题:为什么编译器会循环交换。微观标记很难;) - Matthieu M.


毫无疑问,我们中的一些人会对识别对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) 该行造成164,050,007个错误预测的条件分支(Bcm)在cachegrind的分支预测模型下,它只在排序版本中导致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)
...

看到 性能教程 更多细节。


1690
2017-10-12 05:53



这是可怕的,在未排序的列表中,应该有50%的机会点击添加。不知何故,分支预测只有25%的遗漏率,它怎么能比50%的遗漏更好? - TallBrianL
@ tall.b.lo:25%属于所有分支 - 有 二 循环中的分支,一个用于 data[c] >= 128 (如你所说,它有50%的未命中率)和一个用于循环条件 c < arraySize 错误率约为0%。 - caf


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

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

如果符合以下情况,此方法通用

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

背景和原因

Pfew,那到底是什么意思呢?

从处理器的角度来看,你的记忆很慢。为了弥补速度上的差异,他们在处理器(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 rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact 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();

1160
2018-04-24 06:26



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


当数组在排序时,数据分布在0到255之间,迭代的前半部分将不会进入 if - 陈述( 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 - 陈述速度比“慢”慢六倍“模式!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令。

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


1035
2018-02-15 07:24



您没有显示“随机”TF模式的时间。 - Mooing Duck
@MooingDuck'因为它不会产生任何影响 - 该值可以是任何值,但它仍将处于这些阈值的范围内。那么为什么当你已经知道限制时显示随机值?虽然我同意你可以为了完整性而展示一个,并且“只是为了它的he”。 - cst1992
@ cst1992:现在他最慢的时间是TTFFTTFFTTFF,在我的人眼看来,这似乎是可以预测的。随机本质上是不可预测的,所以完全有可能它会更慢,因此超出了这里所示的限制。 OTOH,可能是TTFFTTFF完全击中了病理情况。分不清楚,因为他没有显示随机的时间。 - Mooing Duck
@MooingDuck对于人眼来说,“TTFFTTFFTTFF”是一个可预测的序列,但我们在这里讨论的是内置在CPU中的分支预测器的行为。分支预测器不是AI级模式识别;这很简单。当你只是交替分支时,它不能很好地预测。在大多数代码中,分支几乎始终以相同的方式运行;考虑一个执行一千次的循环。循环结束时的分支返回到循环的开始999次,然后第1000次执行不同的操作。通常,一个非常简单的分支预测器运行良好。 - steveha
@steveha:我认为你正在假设CPU分支预测器是如何工作的,我不同意这种方法。我不知道那个分支预测器是多么先进,但我似乎认为它比你做得更先进。你可能是对的,但测量肯定会很好。 - Mooing Duck