java - 为什么处理排序数组比处理未排序数组更快?




10 Answers

分支预测。

对于排序数组,条件data[c] >= 128对于条纹值首先为false ,然后对于所有后续值变为true 。 这很容易预测。 使用未排序的数组,您需要支付分支成本。

java c++ performance optimization branch-prediction

这是一段看似非常特殊的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)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • 没有std::sort(data, data + arraySize); ,代码运行时间为11.54秒。
  • 使用排序数据,代码运行1.93秒。

最初,我认为这可能只是一种语言或编译器异常。 所以我用Java试了一下。

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)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

有点相似但不太极端的结果。

我的第一个想法是排序将数据带入缓存,但后来我认为这是多么愚蠢,因为数组刚刚生成。

  • 到底是怎么回事?
  • 为什么处理排序数组比处理未排序数组更快?
  • 代码总结了一些独立的术语,顺序无关紧要。



如果您对可以对此代码进行更多优化感到好奇,请考虑以下事项:

从原始循环开始:

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 out:

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

那个比以前快了100,000倍




我刚刚读到了这个问题及其答案,我觉得答案遗失了。

消除我发现在托管语言中工作特别好的分支预测的常用方法是查找表而不是使用分支(尽管在这种情况下我还没有测试过它)。

如果符合以下情况,此方法通用

  1. 它是一个小桌子,可能会被缓存在处理器中
  2. 您正在以非常紧凑的循环运行和/或处理器可以预加载数据

背景和原因

Pfew,那到底是什么意思呢?

从处理器的角度来看,你的记忆很慢。 为了弥补速度上的差异,他们在处理器(L1 / L2缓存)中构建了几个缓存来补偿这一点。 所以想象一下,你正在做你很好的计算,并发现你需要一块记忆。 处理器将进行“加载”操作并将内存加载到缓存中 - 然后使用缓存执行其余计算。 因为内存相对较慢,这种“加载”会降低程序的速度。

与分支预测一样,这在Pentium处理器中进行了优化:处理器预测它需要加载一段数据并尝试在操作实际到达缓存之前将其加载到缓存中。 正如我们已经看到的那样,分支预测有时会出现可怕的错误 - 在最坏的情况下,您需要返回并实际等待内存负载,这将需要永远( 换句话说:失败的分支预测是坏的,一个内存在分支预测失败后加载是非常可怕的! )。

幸运的是,如果内存访问模式是可预测的,处理器将把它加载到快速缓存中,一切都很好。

我们需要知道的第一件事是什么? 虽然较小通常更好,但经验法则是坚持查找大小<= 4096字节的表。 作为上限:如果您的查找表大于64K,则可能值得重新考虑。

构建一个表

所以我们已经发现我们可以创建一个小表。 接下来要做的是获得一个查找功能。 查找函数通常是使用几个基本整数运算的小函数(和,或者,xor,shift,add,remove和multiply)。 您希望通过查找功能将您的输入转换为表格中的某种“唯一键”,然后简单地为您提供您希望它完成的所有工作的答案。

在这种情况下:> = 128意味着我们可以保留值,<128意味着我们摆脱它。 最简单的方法是使用'AND':如果我们保留它,我们和它一起使用7FFFFFFF; 如果我们想摆脱它,我们和它为0.注意,128也是2的幂 - 所以我们可以继续制作一个32768/128整数的表并填充一个零和很多7FFFFFFFF的。

托管语言

您可能想知道为什么这在托管语言中运行良好。 毕竟,托管语言使用分支检查数组的边界,以确保您不会陷入困境......

好吧,不完全...... :-)

为管理语言消除此分支已经做了相当多的工作。 例如:

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

在这种情况下,编译器显然不会遇到边界条件。 至少Microsoft JIT编译器(但我希望Java做类似的事情)会注意到这一点,并完全取消检查。 哇 - 这意味着没有分支。 同样,它将处理其他明显的案例。

如果您在托管语言上查找时遇到麻烦 - 关键是在查找函数中添加& 0x[something]FFF以使边界检查可预测 - 并且观察它更快。

这种情况的结果

// 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.Next(256);

//To keep the spirit of the code in-tact 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();



避免分支预测错误的一种方法是构建查找表,并使用数据对其进行索引。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];

此代码浪费了一半的添加但从未有分支预测失败。随机数据的速度比具有实际if语句的版本快得多。

但在我的测试中,显式查找表略快于此,可能是因为索引到查找表的速度比位移略快。这显示了我的代码如何设置和使用查找表(lut代码中缺乏想象力的“LookUp表”)。这是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个值的表,这可能是实用的。

编辑:有一件事我忘记了。

索引到数组而不是使用if语句的技术可用于决定使用哪个指针。我看到一个实现二叉树的库,而不是有两个命名指针(pLeft和/ pRight或其他)有一个长度为2的指针数组,并使用“决策位”技术来决定遵循哪一个。例如,而不是:

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

这个库会做类似的事情:

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

这是这段代码的链接:红黑树永恒的混淆




由于分支预测,上述行为正在发生。

要理解分支预测,首先必须了解指令管道

任何指令都被分成一系列步骤,以便可以并行地同时执行不同的步骤。这种技术称为指令流水线,用于提高现代处理器的吞吐量。要更好地理解这一点,请在维基百科上查看此示例

通常,现代处理器具有相当长的流水线,但为了方便起见,我们只考虑这4个步骤。

  1. IF - 从内存中获取指令
  2. ID - 解码指令
  3. EX - 执行指令
  4. WB - 写回CPU寄存器

4级管道一般用于2条指令。

回到上面的问题,让我们考虑以下说明:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果没有分支预测,将发生以下情况:

为了执行指令B或指令C,处理器必须等到指令A没有到达流水线中的EX阶段,因为转到指令B或指令C的决定取决于指令A的结果。所以管道会是这样的。

当if条件返回true时:

当if条件返回false时:

作为等待指令A的结果的结果,在上述情况下花费的总CPU周期(没有分支预测;对于真和假)都是7。

那么什么是分支预测?

分支预测器将尝试猜测分支(if-then-else结构)将以何种方式确定之前。它不会等待指令A到达流水线的EX阶段,但是它会猜测决定并转到该指令(在我们的例子中是B或C)。

如果猜测正确,管道看起来像这样:

如果稍后检测到猜测错误则丢弃部分执行的指令,并且管道以正确的分支重新开始,从而引起延迟。在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段的数量。现代微处理器往往具有相当长的流水线,因此误预测延迟在10到20个时钟周期之间。管道越长,对分支预测器的需求就越大。

在OP的代码中,第一次有条件时,分支预测器没有任何基于预测的信息,所以第一次它会随机选择下一条指令。稍后在for循环中,它可以基于历史记录进行预测。对于按升序排序的数组,有三种可能性:

  1. 所有元素都小于128
  2. 所有元素都大于128
  3. 一些起始新元素小于128,后来大于128

让我们假设预测器将始终在第一次运行时假设真正的分支。

因此,在第一种情况下,它始终采用真正的分支,因为历史上它的所有预测都是正确的。在第二种情况下,最初它会预测错误,但经过几次迭代后,它会正确预测。在第三种情况下,它将最初正确地预测,直到元素小于128.之后它将失败一段时间并且当它看到历史中的分支预测失败时正确。

在所有这些情况下,故障的数量将会减少,因此,只需要几次就可以丢弃部分执行的指令并重新使用正确的分支,从而减少CPU周期。

但是在随机未排序的数组的情况下,预测将需要丢弃部分执行的指令并且在大多数时间重新开始使用正确的分支,并且与排序的数组相比产生更多的CPU周期。




在同一行(我认为没有任何答案突出显示),有时候(特别是在性能很重要的软件中,比如在Linux内核中)你可以找到一些if语句如下所示:

if (likely( everything_is_ok ))
{
    /* Do something */
}

或者类似的:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

双方likely()unlikely()在由使用像海湾合作委员会的定义其实宏__builtin_expect帮助编译器插入代码的预测偏向考虑到用户提供的信息的条件。 GCC支持其他可能改变正在运行的程序行为的内置函数或发出低级指令,如清除缓存等。请参阅此文档该文档通过可用的GCC内置函数。

通常,这种优化主要在硬实时应用程序或嵌入式系统中找到,其中执行时间很重要且非常重要。例如,如果您正在检查仅发生1/10000000次的错误情况,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假。




这是肯定的!...

分支预测会使逻辑运行速度变慢,因为代码中会发生切换!这就像你要走一条直街或一条有很多转弯的街道,肯定会直接做得更快!...

如果数组已排序,则第一步的条件为false:data[c] >= 128然后成为到街道尽头的整个路径的真值。这就是你如何更快地完成逻辑的结束。另一方面,使用未排序的数组,您需要进行大量的转换和处理,这会使您的代码运行速度变慢...

看下面我为你创建的图像。哪条街要快点完成?

因此,以编程方式,分支预测会导致进程变慢...

最后,我们很高兴知道我们有两种分支预测,每种预测都会以不同的方式影响您的代码:

1.静态

2.动态

微处理器在第一次遇到条件分支时使用静态分支预测,并且动态分支预测用于条件分支代码的后续执行。

为了有效地编写代码以利用这些规则,在编写if-elseswitch语句时,首先检查最常见的情况,然后逐步降低到最不常见的情况。循环不一定需要任何特殊的静态分支预测代码排序,因为通常只使用循环迭代器的条件。




分支预测增益!

重要的是要理解分支错误预测不会减慢程序的速度。错过预测的成本就像分支预测不存在一样,您等待表达式的评估以决定运行什么代码(在下一段中进一步说明)。

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

只要有if-else\ switch_语句,就必须计算表达式以确定应该执行哪个块。在编译器生成的汇编代码中,插入了条件branch指令。

分支指令可以使计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即,如果表达式为假,则程序跳过if块的代码),这取决于某些条件,即在我们的案例中的表达评估。

话虽这么说,编译器会尝试在实际评估之前预测结果。它会从if块中获取指令,如果表达式是真的,那就太好了!我们获得了评估它并在代码中取得进展所花费的时间; 如果没有,那么我们运行错误的代码,刷新管道,并运行正确的块。

可视化:

假设您需要选择路线1或路线2.等待您的伴侣检查地图,您已停在##并等待,或者您可以选择路线1,如果您幸运(路线1是正确路线),然后很棒,你不必等待你的伴侣检查地图(你节省了检查地图所需的时间),否则你只需要回头。

虽然冲洗管道速度非常快,但现在采取这种赌博是值得的。预测排序数据或变化缓慢的数据总是比预测快速变化更容易和更好。

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



这是关于分支预测。 它是什么?

  • 分支预测器是古老的性能改进技术之一,它仍然与现代建筑相关。虽然简单的预测技术提供快速查找和功率效率,但是它们具有高的误预测率。

  • 另一方面,复杂的分支预测 - 无论是基于神经的还是两级分支预测的变体 - 提供更好的预测准确性,但它们消耗更多的功率和复杂性以指数方式增加。

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

  • 分支预测本质上是一种优化(最小化)问题,其中重点在于以最少的资源实现最低可能的未命中率,低功耗和低复杂度。

确实有三种不同的分支:

转发条件分支 - 基于运行时条件,PC(程序计数器)被改变为指向指令流中的前向地址。

向后条件分支 - PC在指令流中变为指向后向。分支基于某些条件,例如,当循环结束时的测试表明循环应该再次执行时,向后分支到程序循环的开头。

无条件分支 - 包括跳转,过程调用和没有特定条件的返回。例如,无条件跳转指令可能用汇编语言编码为简单的“jmp”,并且指令流必须立即定向到跳转指令指向的目标位置,而条件跳转可能被编码为“jmpne”仅当先前“比较”指令中两个值的比较结果显示值不相等时,才会重定向指令流。 (x86架构使用的分段寻址方案增加了额外的复杂性,因为跳转可以是“接近”(在一个段内)或“远”(在段外)。每种类型对分支预测算法都有不同的影响。)

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

参考文献:




除了分支预测可能会降低您的速度之外,排序数组还有另一个优势:

您可以设置停止条件而不是仅检查值,这样您只需循环访问相关数据,并忽略其余数据。
分支预测只会遗漏一次。

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }



Related