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


当前回答

这是肯定的!

部门预测使得逻辑运行速度放慢, 因为代码中的转换会发生! 就像你走一条直街或一条街, 转得很多,

If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure...

看看我在下面为你们创造的图象,哪条街会更快完工?

因此,在程序上,分支预测导致过程的慢化...

最后,很高兴知道 我们有两种分支预测 每个分支将对你的代码产生不同的影响:

1. 静态

2. 动态

微处理器在第一次遇到有条件分支时使用静态分支预测,在随后执行有条件分支代码时则使用动态分支预测。为了有效编写代码以利用这些规则,在撰写 if-else 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。

其他回答

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

现在,如果我们看看代码

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

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

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

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

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

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

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

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

一般来说,现代处理器有相当长(和宽)的管道,因此许多指令都可以在飞行中。 见现代微处理器 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 。

除了树枝预测可能会减慢你的速度之外 分解阵列还有另一个优势

您可以有一个停止状态, 而不是仅仅检查值, 这样您只能环绕相关数据, 忽略其它数据 。 分支预测只差一次 。

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

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

这是肯定的!

部门预测使得逻辑运行速度放慢, 因为代码中的转换会发生! 就像你走一条直街或一条街, 转得很多,

If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure...

看看我在下面为你们创造的图象,哪条街会更快完工?

因此,在程序上,分支预测导致过程的慢化...

最后,很高兴知道 我们有两种分支预测 每个分支将对你的代码产生不同的影响:

1. 静态

2. 动态

微处理器在第一次遇到有条件分支时使用静态分支预测,在随后执行有条件分支代码时则使用动态分支预测。为了有效编写代码以利用这些规则,在撰写 if-else 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。