这是C++代码的一块 显示一些非常特殊的行为

由于某种原因,对数据进行分类(在时间区之前)奇迹般地使主要循环速度快近六倍:

#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)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop.
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

没有 std: sort( 数据, 数据+数组Size); 代码在 11. 54 秒内运行。 有了分类数据, 代码在 1. 93 秒内运行 。

(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)


起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:

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)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop.
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

其结果类似,但不太极端。


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

为什么处理一个分类阵列的速度要快于处理一个未分类阵列的速度?

守则正在总结一些独立的术语,因此命令不应重要。


与不同的/后来的汇编者和备选办法具有相同效果:

为什么处理一个未排列的阵列的速度与处理一个用现代 x86-64 叮当的排序阵列的速度相同? gcc 优化标记 -O3 使代码慢于 -O2


当前回答

C++ 中经常使用的布尔操作在编译的程序中产生许多分支。 如果这些分支是内部循环, 且难以预测, 则它们可以大大减缓执行速度。 布尔变量以8位数整数存储, 值为 0, 值为假值, 值为 1 值为真值 。

布尔变量被超额确定,因为所有以布尔变量作为输入变量的操作员都检查输入值是否有比 0 或 1 的其他值,但以布尔值作为输出的操作员不能产生比 0 或 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 的其他值, 则可以使布林操作效率更高。 原因是, 编译者没有做出这样的假设, 如果变量未初始化或者来自未知来源, 则这些变量可能有其他值。 如果 a 和 b 被初始化为有效值, 或者如果它们来自产生布林输出的操作员, 则上述代码可以优化。 最优化的代码看起来是这样 :

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

使用字符代替布尔, 以便使用比位操作员( & 和 & ) 而不是布尔操作员( 和 ) 。 比位操作员是单项指令, 只需要一个时钟周期 。 OR 操作员( 和 ) 工作, 即使 a 和 b 的值比 0 或 1. 操作员( ) 和 Exclusive 或 操作员( ) 可能会产生不一致的结果, 如果操作员的值比 0 和 1 不同 , 操作员( ) 和 Exclusive 或操作员( ) 可能会产生不一致的结果 。

~ 无法用于非。 相反, 您可以在变量上做一个布尔, 变量为 0 或 1 , 使用 XOR, 使用 1 :

bool a, b;
b = !a;

可优化到 :

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

a \\ b 无法被 & b 替换为 & b 表达式, 如果 b 是假的表达式, 则该表达式不应被评估( \ \ 将不评估 b, & will) 。 同样, a \ b 也不能被 \ b 替换为 \ b , 如果 b 是真实的, 则该表达式不应被评估 。

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

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

在大多数情况下是最佳的(除非您预期 表达式会产生很多分支错误)。

其他回答

其他答复的假设是,一个人需要对数据进行分类是不正确的。

以下代码不排序整个阵列,但只排序其中的200个元素部分,因此运行速度最快。

只排序 k- 元素区域时, 以线性时间( O(n)) 完成预处理, 而不是以 O( 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;
}

这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。

快速和简单理解的答案(阅读其他细节)

这个概念叫做分支预测

分支预测是一种优化技术,它预言代码在被确知之前将走的道路。 这一点很重要,因为在代码执行过程中,机器预设了几条代码声明并将其储存在管道中。

问题出在有条件的分支中,有两种可能的路径或代码部分可以执行。

当预测是真实的, 优化技术 完成。

当预测是虚假的,用简单的方式解释, 管道中储存的代码声明被证明是错误的, 而实际的代码必须全部重新加载, 这需要很多时间。

正如常识所显示的,对某类物品的预测比对某类未分类物品的预测更准确。

分支预测可视化:

未排序

在对数据进行分类时,绩效大幅提高的原因是,如神秘论的回答所很好地解释的那样,分支预测罚款已经取消。

现在,如果我们看看代码

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

如果... 其它... 分支是指在满足条件时添加某种内容。 这种分支可以很容易地转换成有条件的移动说明, 并汇编成有条件的移动指示: cmovl, 在 x86 系统中。 分支和可能的分支预测处罚将被删除 。

因此,在C中,C++C中,将直接(不作任何优化)汇编成x86中有条件移动指令的语句是永久操作员.? :.。 因此,我们将上述语句改写为同等语句:

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

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

在英特尔核心i7-2600K @3.4 GHz和视觉工作室2010释放模式上,基准是:

x86x86

Scenario Time (seconds)
Branching - Random data 8.885
Branching - Sorted data 1.528
Branchless - Random data 3.716
Branchless - Sorted data 3.71

x64 x64

Scenario Time (seconds)
Branching - Random data 11.302
Branching - Sorted data 1.830
Branchless - Random data 2.736
Branchless - Sorted data 2.737

结果在多个测试中是稳健的。 当分支结果无法预测时, 我们得到一个巨大的加速, 但是当它可以预测时, 我们遭受了一点点痛苦。 事实上, 当使用有条件的动作时, 无论数据模式如何, 性能都是一样的 。

现在让我们通过调查它们生成的 x86 组装来更仔细地看一看。 为了简单起见, 我们使用两个函数 最大 1 和 最大 2 。

最大 1 使用有条件分支, 如果... 其他... :

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

最大值2 使用永久操作员... ... ?

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

在一台X86-64型机器上,海合会-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

最大值2 使用代码要少得多, 原因是使用指令 cmovge 。 但真正的收益是 最大值2 不涉及分支跳跃, jmp , 如果预测结果不对, 则会有很大的性能处罚 。

那么,为什么有条件的行动效果更好呢?

在典型的 x86 处理器中,执行指令分为几个阶段。 大致上, 我们有不同的硬件可以处理不同阶段。 因此, 我们不必等待一个指令才能开始一个新的指令。 这被称为管道 。

在一个分支中,下列的训导是由前面的训导决定的,所以我们不得管线。我们不是等待的,就是预告的。

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

《计算机系统:程序员的观点》一书第二版对此作了详细解释。您可以查看3.6.6节的有条件移动指示,整个第四章的处理结构,以及5.11.2节的预测和错误处罚处的特殊待遇。

有时,一些现代编译者可以以更好的性能优化我们的代码组装,有时有些编译者无法(有关代码是使用视觉工作室的本地编译者 ) 。 当无法预测的情况变得如此复杂,以至于编译者无法自动优化代码时,他们知道分支和有条件的动作之间的性能差异。

你是树枝预测失败的受害者


分会的预测是什么?

考虑铁路交叉点:

依据CC-By-SA 3.

现在,为了争论起见,假设这是在1800年代, 在长途或无线电通信之前。

您是连接点的盲人接线员, 听到火车来电的声音。 您不知道该走哪条路。 您停止了火车, 询问司机他们想要的方向 。 然后您将开关设置得当 。

火车很重,而且有很多惰性, 所以它们需要永远的启动 并放慢速度。

有更好的办法吗?

如果你猜对了,它会继续。如果你猜错,船长会停下来,后退,喊你按开关。然后它就可以从另一条路重新开始。

如果你每次猜对一次,火车就永远不会停止。如果你猜错太频繁,火车就会花很多时间停下来、备份和重新开始。


考虑是否说明:在加工者一级,它是分支指令:

你是一个处理者,你看见一个分支。你不知道它会走哪条路。你做什么?你停止执行,等待以前的指令完成。然后,你继续走正确的道路。

现代处理器复杂,管道长。 这意味着它们永远需要“暖和”和“慢下来 ” 。

有更好的办法吗?

如果您猜对了, 您将继续执行 。 如果您猜错, 您需要冲洗管道并滚回分支 。 然后您就可以重新启动另一条路径 。

如果你每次都猜对了,处决永远不会停止。如果你猜错太频繁,你就会花很多时间拖延、倒退和重新开始。


这是分支预测。 我承认这不是最好的比喻, 因为火车只能用旗帜发出方向信号。 但在电脑上, 处理器不知道分支会朝哪个方向前进, 直到最后一刻。

您在战略上如何猜测如何将列车必须返回并沿着另一条路行驶的次数最小化 ? 您看看过去的历史 。 如果列车离开99%的时间, 那么您会猜到离开 。 如果列车转行, 那么您会换个猜想 。 如果列车每走三次, 您也会猜到同样的情况 。

换句话说,你尝试确定一个模式并遵循它。这或多或少是分支预测器的工作方式。

大多数应用程序都有良好的分支。 因此,现代分支预测器通常会达到超过90%的冲击率。 但是,当面对无法预见且没有可识别模式的分支时,分支预测器几乎毫无用处。

继续读到维基百科上的“Branch 预测家”文章。


正如上面所暗示的,罪魁祸首就是这个说法:

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, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)

能够做些什么?

如果编译者无法将分支优化为有条件的动作, 您可以尝试一些黑客, 如果您愿意牺牲可读性来表现 。

替换:

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

与:

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

这将清除分支, 并替换为一些位元操作 。

(注意这个黑客并不完全等同原始的假称。 但在此情况下, 它对于数据的所有输入值都是有效的 。 )

基准:核心i7 920@3.5千兆赫

C++ - 2010 - x64 释放

Scenario Time (seconds)
Branching - Random data 11.777
Branching - Sorted data 2.352
Branchless - Random data 2.564
Branchless - Sorted data 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

Scenario Time (seconds)
Branching - Random data 10.93293813
Branching - Sorted data 5.643797077
Branchless - Random data 3.113581453
Branchless - Sorted data 3.186068823

意见:

分支 : 分类的数据和未分类的数据之间有很大的差别。 在 Hack 中: 分类的数据和未分类的数据之间没有差别。 在 C++ 中, 黑客实际上比数据分类时的分支要慢一点 。

拇指的一般规则是避免在关键循环(如本例)中出现依赖数据的分支。


更新 :

GCC 4. 6.1 在 x64 上使用 -O3 或 -free-victorization 能够生成一个有条件的移动, 因此分解和未分解的数据之间没有差别, 两者都是快速的。 (或者说快速的 : 对于已经分解的个案, cmov 可以慢一些, 特别是如果 GCC 将其置于关键路径上而不是仅仅添加, 尤其是在 Broadwell 之前的Intel , 那里 cmov 有2个周期的悬浮 : gcc 优化旗 - O3 使代码慢于 - O2 ) VC+/ 2010 即使在 / Ox 下也无法为这个分支生成有条件的动作 。 Intel C++ Commonder (ICC) 11 也无法生成奇迹性的东西 。 它将两个环切换, 从而将不可预测的分支拉动到外部环 。 不仅能避免错误, , 而且它也比 VC++ 和 GC 生成的任意 还要快一倍 。 。 。 。 换 。

这表明即使是成熟的现代编译者 在优化代码的能力上 也会大不相同...

在同一行中(我认为没有任何答案强调这一点),最好提到有时(特别是在软件中,在软件中,性能很重要——如Linux内核),如果声明如下,你可以找到一些:

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

或类似:

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

可能性 () 和 可能性 () 实际上都是宏, 其定义是使用海合会的 ` 内建_ 期望 ' 来帮助编译者插入预测代码, 以考虑到用户提供的信息, 从而有利于该条件。 海合会支持其他能够改变运行程序的行为或发布低级别指令, 如清除缓存等 。 请参见此文档, 内容可以通过海合会的现有内建 。

通常这种优化主要在硬实时应用程序或内嵌系统中找到,在这些系统中,执行时间很重要且至关重要。例如,如果您正在检查某些错误条件,而错误条件只发生1/10000 000次,那么为什么不通知编译者?这样,默认情况下,分支预测会假设该条件是假的。