这是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


当前回答

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

以下代码不排序整个阵列,但只排序其中的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 (expression)
{
    // Run 1
} else {
    // Run 2
}

当出现 if-else \ 切换语句时, 表达式必须被评估以确定要执行哪个区块。 在编译者生成的组装代码中, 插入有条件的分支指令 。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其默认的按顺序执行指令的行为(即如果表达式是虚假的,程序会跳过区块的代码),这取决于某些条件,即我们情况下的表达式评价。

尽管如此, 编译者试图预测结果, 然后再对结果进行实际评估。 它会从区块中获取指示, 如果表达方式是真实的, 那么就太好了! 我们得到了时间来评估它, 并在代码中取得了进步; 如果不是那样, 我们运行错误的代码, 管道就会被冲洗, 正确的区块会运行 。

可视化:

假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。

尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。

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

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

现在,如果我们看看代码

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节的预测和错误处罚处的特殊待遇。

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

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

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

或类似:

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

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

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

以上行为之所以发生 是因为分局的预测

要了解分支预测,首先必须了解指示管道。

运行一个指令的步骤可以与运行上一个和下一个指令的步骤顺序重叠,这样可以同时同时执行不同的步骤。 这个技术被称为指令管线, 用来增加现代处理器的输送量。 要更好地了解这一点, 请在维基百科上看到这个例子 。

一般来说,现代处理器有相当长(和宽)的管道,因此许多指令都可以在飞行中。 见现代微处理器 A 90-Minute 指南!该指南首先引入基本的自序管线,然后从那里开始。

但为了方便起见,让我们考虑一个简单的单行输油管,只有这4个步骤。 (像典型的5级RISC一样,但省略了单独的 MEM 阶段。 )

IF -- -- 从内存 ID 获取指令 -- -- 解码指令 EX -- -- 执行指令 WB -- 写回到 CPU 注册簿

一般为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的结果(即从何处获取)。

没有预测:如果情况属实:

不预言:如果情况不实:

由于等待指示A的结果,在上述情况下(没有分支预测;对真实和假的预测)所花的CPU周期总数为7个。

那么什么是分支预测?

分支预测器将尝试猜测分支( 如果- 如果- 如果- 如果- else 结构) 将往哪个方向走, 然后再确定这一点。 它不会等待指令 A 到达管道的 EX 阶段, 而是会猜测决定并转到该指令( 以我们为例 ) ( B 或 C ) 。

如果猜对了,输油管看起来是这样的:

如果后来发现猜测是错误的,那么部分执行的指示就会被丢弃,管道从正确的分支开始,造成延误。当分支错误时浪费的时间相当于从获取阶段到执行阶段的管道阶段的数量。现代微处理器往往有相当长的管道,因此错误预防的延迟时间在10到20小时的周期之间。管道越长,对良好的分支预测器的需求就越大。

在OP的代码中,当有条件的分支预测器第一次没有任何信息可以作为预测的基础,因此第一次它会随机选择下一个指令。 (或者返回静态预测,通常不前进,后退)。在循环中,它可以在历史的基础上进行预测。对于按升序排序的阵列,有三种可能性:

所有要件均大于128 有些开始的新要件小于128,稍晚则大于128

让我们假设预测器 将总是假设 真正的分支 在第一个运行。

因此,在第一种情况下,它总是要真正的分支,因为历史上它所有的预测都是正确的。 在第二种情况下,它最初预测错误,但经过几次反复,它会正确预测。 在第二种情况下,它最初将正确预测,直到元素低于128。 之后,它会失败一段时间,当它看到分支预测在历史上失败时,它会失败一段时间,它会正确。

在所有这些情况下,失败的数量将太少,因此,只需放弃部分执行的指示,从正确的分支重新开始,就只需要放弃部分执行的指示的几次,导致CPU周期减少。

但如果是随机的未排序数组,预测将需要丢弃部分执行的指示,然后大部分时间以正确的分支重新开始,结果与分类数组相比,CPU周期会增加。


进一步读作:

现代微处理器 A 90- Minute 指南! Dan Luuu 的关于分支预测的文章( 包括较老的分支预测器, 不是现代IT- TAGE 或 Perceptron) https:// en. wikipedia.org/ wiki/ Branch_ predictor 分支预测和解释器的性能 https:// en. wikipedia. org/ wiki/ Branch_ predictor 分支预测器 - 不要信任 Followlore - 2015 显示 Intel's Haswell 在预测 Python 翻译主循环的间接分支( 由不简单模式造成历史问题) , 与没有使用 IT- TAGE 的早期 CPUs 相比, 早期的CPUs presenterv( 类似循环) 没有帮助完全使用这个完全随机的 。 当源代码时, 最不可能的C- train lishing lishal listal lives liver 已经使用了, liver 。

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

以下代码不排序整个阵列,但只排序其中的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;
}

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