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


当前回答

这个问题已经回答过很多次了。我还是想提醒大家注意另一个有趣的分析。

最近,这个例子(稍作修改)也被用来演示如何在 Windows 上显示一个代码在程序本身中被剖析。 顺便提一下, 作者还展示了如何使用结果来确定代码的大部分时间用于分解和未排序的案例中。 最后, 文章还展示了如何使用HAL( Hardware Empaction Develople) 的一个鲜为人知的特征来确定未分类案例中的分支错误发生多少。

连结就在这里:自我辩护示范

其他回答

在 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的聪明才智无论怎样强调都不为过。

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


分会的预测是什么?

考虑铁路交叉点:

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

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

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;

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

官方的回答是来自

英特尔 -- -- 避免误用英特尔分公司的成本 -- -- 分公司和循环重组以防止误用科学论文 -- -- 分公司预测计算机建筑书籍:J.L. Hennessy, D.A. Patterson:计算机结构:定量方法 科学出版物中的文章:T.Y. Yeh, Y.N. Patt在分支预测方面做了许多这些。

你也可以从这张可爱的图表中看到 树枝预测器为什么会被混淆。

原始代码中的每个元素都是随机值

data[c] = std::rand() % 256;

所以预测器会随着 : rand () 的打击而改变两边。

另一方面,一旦对预测进行分类, 预测器将首先进入一个 强烈未被采纳的状态, 当值变化到高值时, 预测器将分三步走, 从强烈未被采纳到强烈被采纳。


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

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

 // 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];               
 }