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

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


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

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

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


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


当前回答

你是受害者子分支预测失败 。


分会的预测是什么?

考虑铁路交叉点:

Image showing a railroad junction 图像图像图像图像依据创用CC BY-ND 2.CC-By-SA 3.0 CC-By-SA 3.0许可证。

现在,为了争论起见,假设这是在1800年代, 在长途或无线电通信之前。

您是连接点的盲人接线员, 听到火车来电的声音。 您不知道该走哪条路。 您停止了火车, 询问司机他们想要的方向 。 然后您将开关设置得当 。

火车很重,而且有很多惰性, 所以它们需要永远的启动 并放慢速度。

有更好的办法吗?

  • 如果你猜对了,它会继续下去。
  • 如果你猜错了,船长会停下来,后退,喊你开开关。然后它就可以从另一条路重新开始。

如果你每次猜对火车永远不会停下来
如果你猜错太频繁火车会花很多时间停下来 备份 重新开始


考虑如果报表:在加工一级,它是一个分支指令:

Screenshot of compiled code containing an if statement

你是一个处理者,你看见一个分支。你不知道它会走哪条路。你做什么?你停止执行,等待以前的指令完成。然后,你继续走正确的道路。

现代处理器复杂,管道长。 这意味着它们永远需要“暖和”和“慢下来 ” 。

有更好的办法吗?

  • 如果你猜对了,你继续执行。
  • 如果您猜错了, 您需要冲洗管道, 然后滚回分支。 然后您就可以重新启动另一条路径 。

如果你每次猜对死刑将永远不会停止
如果你猜错太频繁,你花了很多时间拖延, 后退,重新开始。


这是分支预测。 我承认这不是最好的比喻, 因为火车只能用旗帜发出方向信号。 但在电脑上, 处理器不知道分支会朝哪个方向前进, 直到最后一刻。

您在战略上如何猜测如何将列车必须返回并沿着另一条路行驶的次数最小化 ? 您看看过去的历史 。 如果列车离开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];

这将清除分支, 并替换为一些位元操作 。

(注意这个黑客并不完全等同原始的如果声明。 但在这种情况下,它对于所有输入值都有效。data[].)

基准:核心i7 920@3.5千兆赫

C++ - 2010 - x64 释放

假设情景 时间( 秒)
分处 - 随机数据 11.777
分支 - 分类数据 2.352
无分支 - 随机数据 2.564
无分支 - 排序数据 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

假设情景 时间( 秒)
分处 - 随机数据 10.93293813
分支 - 分类数据 5.643797077
无分支 - 随机数据 3.113581453
无分支 - 排序数据 3.186068823

意见:

  • 与该处:分类和未分类数据之间存在巨大差异。
  • 与哈克人:分类的数据和未分类的数据没有区别。
  • 在 C++ 案中, 黑客的进位实际上比数据排序时的分支慢。

拇指的一般规则是避免在关键循环(如本例)中出现依赖数据的分支。


更新 :

  • GCC 4.6.1 和-O3-ftree-vectorize在 x64 上能够生成一个有条件的移动, 所以分类的数据和未分类的数据之间没有区别, 两者都是快速的 。

    (或稍快:对于已经分类的案件,cmov特别是如果海合会将海合会置于关键道路上,而不是公正add特别是英特尔 之前的英特尔 Broadwellcmov有2个周期的延迟:gcc 优化标记 -O3 使代码慢于 -O2)

  • VC++/2010 即使在/Ox.

  • Intel C+++ 编译器(ICC) 11 做了奇迹般的事情。交换两个循环从而将无法预测的分支拉到外环。 它不仅能避免错误, 而且速度是 VC++ 和 GCC 所能生成的两倍。 换句话说, ICC 利用试流击败基准...

  • 如果您给 Intel 编译者无分支代码, 它会直接向导它... 并且和分支( 循环交换) 一样快 。

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

其他回答

分流收益!

重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)

尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。

可视化:

假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。

尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

如果您对这个代码可以做的更多优化感到好奇, 请考虑 :

以原始循环开始 :

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

通过循环互换,我们可以安全地将这一循环改为:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

然后,你可以看到,if条件条件在始终执行时为常数。i循环,这样你就可以升起if外出 :

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

假设浮点模型允许, 内环会崩溃成一个单一的表达式( 假设浮点模型允许的话 ) 。/fp:fast被抛出,例如)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

这比以前快了十万倍

分部门预测。

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

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

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

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

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

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

确实有三种不同的分支:

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

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

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

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

参考文献:

官方的回答是来自

  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()口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交

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