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


当前回答

在分类的情况下,你可以做的比依靠成功的分支预测或任何无分支比较的把戏:完全删除分支。

事实上,阵列被分割在一个毗连区,数据小于128,另一个数据小于128。 因此,你应该用二组搜索(使用 Lg(数组)=15 比较)找到分区点,然后从该点进行直线积累。

类似的东西( 未检查 )

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或, 略微糊涂

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种既快又快的方法,为分类或未分类两种方法提供了大致的解决办法,即:总和=3137536;(假设真正统一分布,预计价值为191.5的16384个样品:-)

其他回答

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

分支预测器是一种古老的改进性能的技术,在现代建筑中仍然具有相关性。 虽然简单的预测技术提供了快速的外观和电力效率,但它们受到高误用率的影响。 另一方面,复杂的分支预测 — — 无论是基于神经的预测还是两级分支预测的变体 — — 提供了更好的预测准确性,但是它们消耗的动力和复杂性也成倍增加。 此外,在复杂的预测技术中,预测分支所需的时间也非常长 — — 从2到5个周期不等 — — 这与实际分支的执行时间相当。 分支预测基本上是一个优化(最小化 ) 问题, 重点是实现尽可能最低的误用率、低电耗和最低资源低的复杂度。

确实有三种不同的分支:

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

后向有条件的分支 - PC 被修改为指令流中的后向点。 分支基于某些条件, 例如当循环结尾的测试显示循环应该再次执行时, 将程序循环的起始处向后转至程序循环的起始处 。

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

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

参考文献:

预测处预测处(Ussing回背机器)

避免分支预测错误的一种方法是建立一个搜索表,并用数据来编制索引。 Stefan de Bruijn在答复中讨论了这一点。

但在此情况下,我们知道值在范围[0,255],我们只关心值 128。这意味着我们可以很容易地提取一小块来说明我们是否想要一个值:通过将数据移到右边的7位数,我们只剩下0位或1位数,我们只有1位数时才想要增加值。让我们把这个位数称为“决定位数 ” 。

将决定位数的 0/1 值作为索引输入一个阵列, 我们就可以生成一个代码, 无论数据是排序还是未排序, 都同样快速。 我们的代码总是会添加一个值, 但是当决定位数为 0 时, 我们将会添加一个值, 我们并不关心的地方 。 以下是代码 :

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代码浪费了一半的添加值, 但从未出现分支预测失败 。 随机数据比有实际的如果声明的版本要快得多 。

但在我的测试中,一个清晰的查看表比这个稍快一些, 可能是因为对查看表的索引比位移略快一点。 这显示了我的代码是如何设置和使用搜索表的( 在代码中“ 查看表” 中, 不可想象地称之为润滑 ) 。 以下是 C++ 代码 :

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在此情况下, 查看表只有256 字节, 所以它在一个缓存中非常适合, 并且非常快。 如果数据是 24 位值, 而我们只想要其中一半的话, 这个技术就不会有效... 搜索表会太大而不切实际。 另一方面, 我们可以将上面显示的两种技术结合起来: 首先将比特移开, 然后将一个查看表索引。 对于一个仅需要顶端半值的 24 位值, 我们可能会将数据右移12 位值, 并留下一个 12 位值的表格索引。 12 位表指数意味着一个有 4096 个值的表格, 这可能是实用的 。

将技术指数化为数组,而不是使用“如果”的语句,可以用来决定使用哪个指针。 我看到了一个图书馆,它安装了二进制树,而不是有两个名为指针(Pleft and pRight or whatever)的指针有长至2的指针阵列,并且使用“决定位”技术来决定要遵循哪个指针。例如,没有:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个图书馆会做一些事情,比如:

i = (x < node->value);
node = node->link[i];

这是这个代码的链接: 红黑树,永远封存

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

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

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

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

分部门预测。

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