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


当前回答

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

其他回答

这是肯定的!

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

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 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。

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

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

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

分部门预测。

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

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;

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

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

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

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