这是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);
    }
}

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


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

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

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


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


当前回答

C+++ 中经常使用的布尔操作在 C+++ 中生成了编译程序中的许多分支。 如果这些分支是内部循环,并且难以预测,它们可以大大放慢执行速度。布尔变量以8位整数和数值存储。0用于false1用于true.

布尔变量被超值确定为超值, 也就是说, 所有有布尔变量作为输入的运算符都检查输入是否有其它值, 而不是01,但将布林作为输出输出的操作器除01。这样,用布林变量作为输入的操作效率就低于必要的效率。例如:

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

此代码远非最佳。 分支分支在出现错误的情况下可能需要很长的时间。 如果可以肯定地知道, 操作家除了使用其他的值之外没有其他的值, 布尔操作可以更高效得多 。01。为什么汇编器没有做出这样的假设,其原因是,如果变量未初始化或来自未知来源,则变量可能还有其他值。如果ab已经初始化为有效值, 或者它们来自产生 Boolean 输出的运算符。 优化的代码看起来是这样 :

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char使用代替bool以便能够使用比特顺序运算符( B) 。&|而不是 Boolean 运算符 (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1)&&||)bitwith运算符是只使用一个时钟周期的单一指令。|工作,即使ab具有其他数值的数值01AAD 经营者(AD)&和例外或经营人(或经营人(或经营人))^)如果特有产品有其他价值,则可能得出不一致的结果,如果特有产品有其他价值,则结果可能不一致。01.

~无法用于 NST 。 相反, 您可以在已知的变量上生成布尔 。011:

bool a, b;
b = !a;

可优化到 :

char a = 0, b;
b = a ^ 1;

a && b无法替换为a & b如果b是一个表达式,如果afalse ( &&将不评价b, &同样地,a || b无法替换为a | b如果b是一个表达式,如果atrue.

如果操作符是变量, 则使用比位运算符更有利 :

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下最理想(除非预期&&表达式会生成多个分支错误) 。

其他回答

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

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

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

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

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

确实有三种不同的分支:

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

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

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

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

参考文献:

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

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

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

分部门预测。

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

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

C+++ 中经常使用的布尔操作在 C+++ 中生成了编译程序中的许多分支。 如果这些分支是内部循环,并且难以预测,它们可以大大放慢执行速度。布尔变量以8位整数和数值存储。0用于false1用于true.

布尔变量被超值确定为超值, 也就是说, 所有有布尔变量作为输入的运算符都检查输入是否有其它值, 而不是01,但将布林作为输出输出的操作器除01。这样,用布林变量作为输入的操作效率就低于必要的效率。例如:

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

此代码远非最佳。 分支分支在出现错误的情况下可能需要很长的时间。 如果可以肯定地知道, 操作家除了使用其他的值之外没有其他的值, 布尔操作可以更高效得多 。01。为什么汇编器没有做出这样的假设,其原因是,如果变量未初始化或来自未知来源,则变量可能还有其他值。如果ab已经初始化为有效值, 或者它们来自产生 Boolean 输出的运算符。 优化的代码看起来是这样 :

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char使用代替bool以便能够使用比特顺序运算符( B) 。&|而不是 Boolean 运算符 (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1)&&||)bitwith运算符是只使用一个时钟周期的单一指令。|工作,即使ab具有其他数值的数值01AAD 经营者(AD)&和例外或经营人(或经营人(或经营人))^)如果特有产品有其他价值,则可能得出不一致的结果,如果特有产品有其他价值,则结果可能不一致。01.

~无法用于 NST 。 相反, 您可以在已知的变量上生成布尔 。011:

bool a, b;
b = !a;

可优化到 :

char a = 0, b;
b = a ^ 1;

a && b无法替换为a & b如果b是一个表达式,如果afalse ( &&将不评价b, &同样地,a || b无法替换为a | b如果b是一个表达式,如果atrue.

如果操作符是变量, 则使用比位运算符更有利 :

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下最理想(除非预期&&表达式会生成多个分支错误) 。