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


当前回答

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


分会的预测是什么?

考虑铁路交叉点:

依据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 生成的任意 还要快一倍 。 。 。 。 换 。

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

其他回答

由于一种被称为分支预测的现象,分类的阵列的处理速度要快于未排序的阵列。

分支预测器是一个数字电路(在计算机结构中),它试图预测一个分支会走哪条路,从而改善教学管道的流量。电路/计算机预测下一步并进行执行。

错误的预测导致回到前一步,执行另一个预测。 假设预测是正确的,代码将持续到下一步骤。 错误的预测导致重复同一步骤,直到出现正确的预测。

你问题的答案很简单

在未排列的阵列中,计算机进行多次预测,导致误差的可能性增加。而在分类的阵列中,计算机的预测减少,误差的可能性减少。 做更多的预测需要更多的时间。

排序的数组: 直路

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

未排列的队列: 曲线路

______   ________
|     |__|

部门预测: 猜测/预测哪条道路是直的,未检查就沿着这条道路走

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条道路都到达同一目的地,但直路更短,另一条更长。如果你错误地选择另一条道路,就没有回头路,所以如果你选择更长的路,你就会浪费一些更多的时间。这与计算机中发生的事情相似,我希望这能帮助你更好地了解。


@Simon_Weaver在评论中也提到:

它不会减少预测数量 — — 它会减少不正确的预测。 它仍然必须通过循环预测每一次...

在 ARM 中,不需要分支, 因为每个指令都有一个 4 位条件字段, 它( 零成本) 测试处理器状态登记册中可能出现的16种不同条件中的任何一种, 如果指令条件不实, 则跳过指令。 这就消除了对短分支的需求, 并且不会为此算法找到分支预测 。 因此, 此算法的分类版本会比ARM 上未分类版本的运行慢, 因为排序的间接成本增加 。

这个算法的内环在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

但这其实是大局的一部分:

处理器状态登记册(PSR)中的状态位元总是更新 OP 代码, 因为这是它的目的, 但大多数其他指令都没有触动 PSR , 除非您在指令中添加一个可选的后缀, 并明确指出 PSR 应该根据指令的结果更新 。 就像 4 位条件后缀一样, 能够执行指令而不影响 PSR 是一种机制, 减少了对 ARM 上分支的需求, 并且也便利了硬件级的异常发送, 因为执行了 X 操作后, 您可以在随后( 或平行) 执行一系列其他工作, 明确不应该影响( 或受) 状态位元的影响 。 然后您可以测试 X 先前设定的状态位的状态状态 。

条件测试字段和可选的“ 设定状态位” 字段可以合并, 例如 :

ADDR R1、R2、R3在不更新任何状态位数的情况下执行R1 = R2 + R3。ADDGE R1、R2、R3仅在影响状态位数的先前指令导致大于或等于条件时才执行相同的操作。ADDDS R1、R2、R3在处理器状态登记册中进行添加并随后更新N、Z、C和V国旗,依据是结果是否为负、Ze、C(未签名添加)或oVerflowed(供签名添加)。ADDDDSGE R1、R2、R3仅在GE测试属实的情况下执行添加,然后根据添加结果更新状态位数。

大多数处理器结构没有这种能力来说明是否应该为特定操作更新状态位元,这可能需要写入额外的代码来保存和随后恢复状态位元,或者可能需要额外的分支,或者可能限制处理器的异常执行效率:大多数CPU指令设置的架构的副作用之一是,在大多数指令之后强制更新状态位元,是很难分离哪些指令可以平行运行而不相互干扰的。更新状态位元具有副作用,因此对代码具有线性效果。ARM在任何指令上混合和匹配无分支条件测试的能力,在任何指令非常强大之后,可以对组合语言程序员和编译员更新或不更新状态位,并生成非常高效的代码。

当您不需要分行时, 您可以避免冲刷管道的时间成本, 否则就是短的分支, 您也可以避免许多投机性蒸发形式的设计复杂性。 缓解最近发现的很多处理器弱点( 特例等)的最初天真效果影响 表明现代处理器的性能在多大程度上取决于复杂的投机性评估逻辑。 由于输油管很短,对分支的需求也大大减少, ARM不需要像 CISC 处理器那样依赖投机性评估。 ( 当然, 高端的ARM 实施过程包括投机性评估, 但是它只是绩效故事中的一小部分 ) 。

如果你曾经想过为什么ARM如此成功,那么这两种机制(加上另一个允许你“轮回”左转或右转的机制,任何算术操作员的两个论点之一或以零额外费用抵消内存存存取操作员的两种论点之一)的辉煌效力和互动作用是故事的一大部分,因为它们是ARM结构效率的最大来源。 1983年ARM ISA原设计师Steve Furber和Roger(现为Sophie)Wilson的聪明才智无论怎样强调都不为过。

Bjarne Stroustrup对此问题的答复:

这听起来像面试问题。是真的吗?你怎么知道?回答效率问题而不首先做一些测量是不明智的,所以知道如何衡量是很重要的。

于是,我用百万整数的矢量尝试过,然后得到:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

我跑了好几次才确定。 是的,这个现象是真实的。我的关键代码是:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

至少这个编译器、 标准库和优化设置是真实存在的。 不同的执行可以而且确实提供了不同的答案。 事实上,有人做了更系统的研究( 快速的网络搜索会找到它) , 而大多数执行都显示了这种效果。

原因之一是分支预测:类式算法中的关键操作是“if(v)(i) < pivot] ” 或等效。对于一个分类序列,测试总是真实的,而对于随机序列,选择的分支则随机变化。

另一个原因是,当矢量已经分类后,我们从不需要将元素移到正确位置。这些小细节的影响是我们看到的5或6个系数。

Quicksort(以及一般分类)是一项复杂的研究,吸引了计算机科学中最伟大的一些思想。 一种良好的功能是选择良好的算法和关注硬件的运行效果的结果。

如果您想要写入高效代码, 您需要了解一些关于机器结构的知识 。

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

现在,如果我们看看代码

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

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

分部门预测。

使用分类数组, 条件数据 [c] 128 首先对于一系列值来说是虚假的, 然后对所有后期值都变成真实的。 这很容易预测。 使用未排序数组, 您支付分支成本 。