这是C++代码的一块 显示一些非常特殊的行为

出于某种原因,对数据进行分类(之前奇迹般地使主环速度快近六倍:

#include <algorithm>
#include <ctime>
#include <iostream>

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<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
  • 不无std::sort(data, data + arraySize);代码在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);
    }
}

其结果类似,但不太极端。


我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。

  • 这是怎么回事?
  • 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?

守则正在总结一些独立的术语,因此命令不应重要。


相关/后续行动不同/以后的编译者和选项的相同效果:


当前回答

官方的回答是来自

  1. 英特尔 -- -- 避免因部门错误而承担的费用
  2. 英特尔 - 分行和循环重组以防止误判
  3. 科学论文 -- -- 分支预测计算机结构
  4. 书籍:J.L.Hennnesy、D.A. Patterson:计算机结构:定量方法
  5. 发表在科学出版物上的文章:T.Y.Yeh、Y.N.Patt在分支预测中做了许多这些文章。

你也可以从这个可爱的图表图为什么树枝预测器被弄糊涂了

2-bit state diagram

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

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

所以预测器会变形为std::rand()口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交

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


其他回答

分部门预测。

以排序数组数组, 条件data[c] >= 128第一个是false一连串的数值,然后变成true后期所有值。 这很容易预测。 使用一个未排序的阵列, 您支付分支成本 。

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

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

链接在此 :自我辩护示范

在ARARAR上,不需要分支,因为每项教学都有一个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

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

CMP处理器状态登记册(PSR)中的状态位数总是更新,因为这是它们的目的,但大多数其他指令都不触动 PSR,除非添加一个选项S指示的后缀,规定应根据指示的结果更新PSR。就像4位条件的后缀一样,能够执行指示而不影响PSR,这个机制减少了对ARM分支的需求,也便利了硬件一级的不按订单发送,因为执行一些操作X更新状态位数后,随后(或平行)你可以做一系列其他工作,这些工作显然不应影响(或受到)状态位数的影响,然后可以测试X早先设定的状态位数状态状态。

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

  • ADD R1, R2, R3表演 表演R1 = R2 + R3不更新任何状态位元 。
  • ADDGE R1, R2, R3仅在影响状态位数的先前指令导致大于或等于条件时,才执行相同的操作。
  • ADDS R1, R2, R3执行添加,然后更新N, Z, CV根据结果是否为负、零、载(未签字添加)或oVerflowed(已签署添加),在处理者地位登记册中的标记。
  • ADDSGE R1, R2, R3仅在以下情况下执行添加:GE测试是真实的, 然后根据添加结果更新状态比特 。

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

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

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

我刚读过这个问题及其答案,我觉得缺少答案。

消除我发现在管理下语言中特别出色的分支预测的一个常见方法是, 表格搜索而不是使用分支(虽然我还没有在本案中测试过它 ) 。

如果:

  1. 它是一个小桌子 很可能在处理器中隐藏
  2. 您正在一个非常紧凑的循环中运行着一些东西和/或处理器可以预加载数据。

背景和原因

从处理器的角度来看,您的内存是慢的。为了弥补速度的差异,在您的处理器( L1/L2 缓存) 中嵌入了几个缓存。 想象一下, 您正在做你的好计算, 并发现您需要一个内存。 处理器会得到它的“ 装载” 操作, 并将内存部分装入缓存中, 然后用缓存来进行其余的计算。 因为内存相对缓慢, 此“ 装载” 将会减缓您的程序 。

像分支预测一样,这在Pentium处理器中被优化了:处理器预测,它需要在操作实际到达缓存之前装入一个数据,并试图将数据装入缓存中。我们已经看到,分支预测有时会发生可怕的错误 -- -- 在最坏的情况下,你需要回去等待一个记忆负荷,这将需要永远的时间(我们已看到,分支预测有时会发生可怕的错误)。换句话说,失败的分支预测是坏的,在分支预测失败之后的记忆负荷实在是太可怕了!).

幸运的是,对于我们来说,如果记忆存取模式可以预测,处理器将装在快速缓存中,一切都很好。

我们首先需要知道的是? 虽然小一点一般比较好,但大拇指规则是坚持使用大小为 4096 字节的搜索表格。作为一个上限:如果您查看的表格大于 64K, 可能值得重新考虑 。

构建表格

因此我们发现我们可以创建一个小表格。 接下来要做的是设置一个查找功能。 查找功能通常是使用几个基本整数操作( 以及, 或者, xor, 转换, 转换, 添加, 删除, 或倍增) 的小型函数。 您想要将您的输入通过外观功能转换为表格中某种“ 独一无二的密钥 ” , 这样就可以简单给出您想要它做的所有工作的答案 。

在此情况下 : 128 表示我们可以保留这个值, < 128 表示我们摆脱它。 最简单的方法就是使用“ 和 ” : 如果我们保留它, 我们和它使用 7FFFFFFF; 如果我们想要摆脱它, 我们和它使用 0。 注意 128 也是一种2 的功率, 所以我们可以继续制作一个32768/128 整数的表格, 并填满它 1 0 和很多 7FFFFFFFFFFFF。

受管理语言

毕竟,管理下的语言会用分支来检查阵列的界限,以确保你不会搞砸...

嗯,不确切地说... : -)

在取消管理下语文的这一分支方面,已经做了相当多的工作。

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在此情况下, 编译者明显知道边界条件永远不会被击中 。 至少微软 JIT 编译者( 但我预计爪哇会做类似的事情) 将会注意到这一点并完全取消检查 。 WOW 表示没有分支 。 同样, 它也会处理其他明显的例子 。

如果您遇到管理下语言的查询问题 -- -- 关键是添加 a& 0x[something]FFF使边界检查可以预测, 并且看着它更快地发展。

本案的结果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

是关于分支预测的 是什么?

  • 分支预测器是古老的改进性能的技术之一,在现代建筑中仍然具有相关性。 虽然简单的预测技术能提供快速搜索和电力效率,但它们的误判率很高。

  • 另一方面,复杂的分支预测 — — 无论是基于神经的预测还是两级分支预测的变异 — — 提供了更好的预测准确性,但是它们消耗更多的能量和复杂性会成倍增加。

  • 此外,在复杂的预测技术中,预测分支所需的时间本身非常高 — — 从2到5个周期不等 — — 这与实际分支的执行时间相当。

  • 部门预测基本上是一个优化(最小化)问题,重点是实现尽可能低的误差率、低电耗和最低资源复杂性低。

确实有三种不同的分支:

附加条件的分支- 根据运行时间条件,PC(程序表计数器)被修改为指示流中前方的地址。

后向附加条件分支- PC被修改为指令流的后向点。分支基于某种条件,例如当循环结束时的测试显示循环应该再次执行时,分支会向后到程序循环开始处。

无条件分支- 包括跳跃、程序呼叫和没有特定条件的返回。 例如, 无条件跳跃指令可能以组合语言编码为简单的“ jmp ” , 且指令流必须直接指向跳跃指令指向的目标位置, 而有条件跳跃, 代号为“ jmpne ” , 只有在对先前“ 比较” 指令中两个数值进行比较的结果显示数值不相等时, 才会改变教学流的方向。 (x86 结构使用的分段处理方案增加了额外的复杂度, 因为跳跃可以是“ 接近” (在段内) , 也可以是“ 远” (在段外) 。 每种类型都对分支预测算法有不同的影响 。

静态/动力支部:微处理器在第一次遇到有条件的分支时使用静态分支预测,而动态分支预测用于随后执行有条件的分支代码。

参考文献: