当前位置: 首页 > 面试题库 >

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

江礼骞
2023-03-14
问题内容

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

具有类似但不太极端的结果。

我首先想到的是排序将数据带入缓存,但是后来我想到这是多么愚蠢,因为刚刚生成了数组。

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

问题答案:

您是分支预测失败的受害者。

什么是分支预测?
考虑一个铁路枢纽:

该图显示了铁路枢纽 Mecanismo的图片,通过Wikimedia Commons。在CC-By-SA 3.0许可下使用。

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

您是路口的操作员,并且听到火车驶入。您不知道应该走哪条路。您停下火车,询问驾驶员他们想要哪个方向。然后您适当地设置开关。

火车很重,惯性很大。因此,它们花了永远的时间来启动和减速。

有没有更好的办法?您猜火车将朝哪个方向行驶!

  • 如果您猜对了,它将继续进行。
  • 如果您猜错了,机长会停下来,后退并大喊大叫,以拨动开关。然后,它可以沿着其他路径重新启动。
  • 如果您每次都猜对了,火车将永远不会停止。
  • 如果您经常猜错,火车将花费大量时间停止,备份和重新启动。

考虑一个if语句:在处理器级别,它是一条分支指令:

包含if语句的已编译代码的屏幕截图

您是处理器,并且看到一个分支。您不知道它将走哪条路。你是做什么?您停止执行并等待之前的指令完成。然后,您沿着正确的路径继续。

现代处理器很复杂,而且流程很长。因此,他们需要永远“热身”和“放慢脚步”。

有没有更好的办法?您猜分支将朝哪个方向前进!

  • 如果猜对了,则继续执行。
  • 如果您猜错了,则需要刷新管道并回滚到分支。然后,您可以沿着其他路径重新启动。
  • 如果您每次都猜对了,执行将永远不会停止。
  • 如果您经常猜错,那么您将花费大量时间来拖延,回滚和重新启动。

这是分支预测。我承认这不是最好的类比,因为火车可以只用一个标志来指示方向。但是在计算机中,处理器直到最后一刻才知道分支的方向。

那么,您如何从战略上猜测如何将火车必须倒退和走另一条路的次数降至最低?您看看过去的历史!如果火车有99%的时间向左行驶,那么您就猜到了。如果它交替出现,那么您将交替猜测。如果它每三回​​去一次,您会猜到相同…

换句话说,您尝试识别模式并遵循它。这或多或少是分支预测变量的工作方式。

大多数应用程序具有行为良好的分支。因此,现代分支预测器通常将达到90%以上的命中率。但是,当面对没有可识别模式的不可预测分支时,分支预测变量实际上是无用的。

从上面暗示,罪魁祸首是这个if陈述:

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, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

那该怎么办呢?

如果编译器无法将分支优化为有条件的移动,那么如果您愿意牺牲可读性来提高性能,则可以尝试一些破解。

更换:

if (data[c] >= 128)
    sum += data[c];

与:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这消除了分支,并用一些按位运算将其替换。

(请注意,这种破解并不完全等同于原始的if语句。但是在这种情况下,它对于的所有输入值均有效data[]。)

基准:Core i7 920 @ 3.5 GHz

C ++-Visual Studio 2010-x64版本

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java-NetBeans 7.1.1 JDK 7-x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

观察结果:

  • 使用分支:排序和未排序的数据之间存在巨大差异。
  • 使用Hack:排序和未排序的数据之间没有区别。
  • 在C ++情况下,对数据进行排序时,hack实际上比分支慢一点。
    一般的经验法则是避免在关键循环中避免依赖数据的分支(例如在此示例中)。

更新:

  • x64上-O3或-ftree-vectorizex64上的GCC 4.6.1能够产生条件移动。因此,已排序和未排序的数据之间没有区别-两者都很快速。

(或者有点快:对于已经排序的情况,cmov可能会变慢,特别是如果GCC将其放在关键路径上而不是仅仅在add,尤其是在Broadwell之前cmov有2个周期延迟的Intel上:gcc优化标志-O3会使代码比-O2慢)

  • VC ++ 2010即使在.NET下也无法为该分支生成条件移动/Ox。

  • 英特尔C 编译器(ICC)11起到了神奇的作用。它互换两个循环,从而将不可预测的分支提升到外部循环。因此,它不仅可以避免错误预测,而且还比VC 和GCC生成的速度快两倍!换句话说,ICC利用测试循环击败了基准测试…

  • 如果给Intel编译器提供无分支的代码,它就直接对其进行矢量化处理……并且与分支(通过循环交换)一样快。



 类似资料:
  • 在这篇文章中,为什么处理排序数组比处理随机数组更快,它说分支预测是排序数组性能提升的原因。 但是我刚刚使用Python尝试了这个例子;我认为排序数组和随机数组没有区别(我尝试了字节数组和数组;并使用line_profile来分析计算)。 我遗漏了什么吗? 这是我的代码:

  • 我发现了这个流行的9岁左右的问题,并决定重新检查它的结果。 所以,我有AMD Ryzen 9 595 0x、Clang++10和Linux,我从问题中复制粘贴了代码,下面是我得到的: 分类-0.549702秒: 未排序-0.546554s: 我很确定的事实是,未经排序的版本被证明是快了3ms,只是噪音,但它似乎不再慢了。 那么,CPU的架构发生了什么变化(以至于不再慢一个数量级)? 以下是多次运行

  • 根据items数组里面num的值去arr数组里面拿数据,按竖向排序 期望得到数据格式: 麻烦各位大佬看看,感激不尽

  • 假设我有一个二维像素网格(4乘4像素)——我有一个和我草图一样大小的图像,它被切割成16个部分。现在我将所有16个部分加载到一个数组中。我想依次将这个数组映射到2D网格上,这样我的整体图像就可以再次正确地组合在一起。也就是说,左上角图像0.png右下角图像16.png. 我就是找不到能让我这么做的公式。例如,我知道使用可以在所有像素中运行,从左上到右下,所以我试过了。如果没有它就不能正确地坐在一起

  • 我有2列制表符分隔的整数,其中第一列是随机整数,第二列是标识组的整数,可以由此程序生成。() 然后,我使用第二个程序()计算每个组的和。 如果我在给定大小的数据集上运行这些程序,然后打乱相同数据集的行的顺序,打乱的数据计算总和的速度比有序数据快2倍或更多。 我本来希望按组排序的原始数据具有更好的数据局部性并且速度更快,但我观察到相反的行为。我想知道是否有人可以假设原因?

  • 本文向大家介绍JavaScript对象数组的排序处理方法,包括了JavaScript对象数组的排序处理方法的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了JavaScript对象数组的排序处理方法。分享给大家供大家参考,具体如下: javascript的数组排序函数 sort方法,默认是按照ASCII 字符顺序进行升序排列。 arrayobj.sort(sortfunction); 参数: