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

在此 C++ 代码中,对数据进行排序(在定时区域之前)使主循环速度加快约 6 倍:

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


文章来源地址https://www.toymoban.com/diary/problem/276.html

  • 如果没有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)
        {
            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);
    }}

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



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

  • 到底是怎么回事?

  • 为什么处理已排序的数组比处理未排序的数组更快?

该代码总结了一些独立的术语,因此顺序并不重要。


什么是分支预测?


考虑一个铁路枢纽:

现在为了便于讨论,假设现在是 1800 年代——远距离或无线电通信出现之前。

你是路口的盲人操作员,你听到火车驶来。你不知道它应该走哪条路。你停下火车询问司机他们想要哪个方向。然后你适当地设置开关。

火车很重并且有很大的惯性,因此它们需要很长时间才能启动和减速。

有没有更好的办法?你猜火车会开往哪个方向!


  • 如果你猜对了,就继续。

  • 如果你猜错了,船长会停下来,后退,并对你大喊,要求你打开开关。然后它可以沿着另一条路径重新启动。

如果你每次都猜对了,火车就永远不会停下来。
如果您经常猜错,火车将花费大量时间停车、倒车和重新启动。


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

pyfwC.png

你是一个处理器,你看到一个分支。你不知道它会走向何方。你做什么工作?您停止执行并等待前面的指令完成。然后你继续沿着正确的道路前进。

现代处理器很复杂并且管道很长。这意味着他们需要永远“热身”和“放慢速度”。

有没有更好的办法?你猜分支会走向哪个方向!

  • 如果你猜对了,你就继续执行。

  • 如果你猜错了,你需要刷新管道并回滚到分支。然后您可以沿着另一条路径重新启动。

如果你每次都猜对了,执行就永远不必停止。
如果你经常猜错,你就会花费大量时间停顿、回滚和重新启动。


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

您如何从策略上猜测以尽量减少火车必须倒车并沿另一条路线行驶的次数?你看看过去的历史吧!如果火车 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, ...
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];

这消除了分支并用一些按位运算代替它。

(请注意,此 hack 并不严格等同于原始 if 语句。但在这种情况下,它对 的所有输入值都有效data[]。)

基准测试:酷睿 i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 版本

设想时间(秒)
分支 - 随机数据11.777
分支 - 排序数据2.352
无分支 - 随机数据2.564
Branchless - 排序数据2.587

Java - NetBeans 7.1.1 JDK 7 - x64

设想时间(秒)
分支 - 随机数据10.93293813
分支 - 排序数据5.643797077
无分支 - 随机数据3.113581453
Branchless - 排序数据3.186068823

观察结果:

  • 使用分支:排序数据和未排序数据之间存在巨大差异。

  • 使用 Hack:排序数据和未排序数据之间没有区别。

  • 在 C++ 情况下,当数据排序时, hack 实际上比分支慢一点。

一般的经验法则是避免关键循环中的数据相关分支(例如本例中)。


更新:

  • -O3x64上的 GCC 4.6.1-ftree-vectorize能够生成条件移动,因此排序数据和未排序数据之间没有区别 - 两者都很快。

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

  • 即使在/Ox.

  • 英特尔 C++ 编译器(ICC) 11 创造了奇迹。它交换两个循环,从而将不可预测的分支提升到外循环。它不仅不受错误预测的影响,而且速度是 VC++ 和 GCC 生成速度的两倍!换句话说,ICC 利用测试循环击败了基准测试......

  • 如果您为英特尔编译器提供无分支代码,它会直接对其进行矢量化......并且与分支(使用循环交换)一样快。

这表明即使是成熟的现代编译器优化代码的能力也可能有很大差异......



到此这篇关于为什么处理已排序的数组比处理未排序的数组更快?的文章就介绍到这了,更多相关内容可以在右上角搜索或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://www.toymoban.com/diary/problem/276.html

如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用
上一篇 2023年08月19日 16:46
下一篇 2023年08月19日 16:46

相关文章

  • 一个操作让数组处理速度快了5倍,到底是为什么

      概述: 通过对数组进行排序,代码更好地利用了缓存,从而提高了程序的性能。这种现象通常被称为\\\"缓存友好\\\"(cache-friendly)或\\\"空间局部性\\\"(spatial locality) 今天做一个数组数据计算时,发现一个效率问题,给大家分享一下 一个数组排序和不排序时同样的逻辑处理速度是

    2024年03月24日
    浏览(54)
  • 【排序算法】插入排序与希尔排序,你不想知道为什么希尔比插入更快吗?

    大家好啊!本文阿辉讲介绍插入排序和希尔排序,并将解释为什么希尔排序比插入排序更快。 插入排序,实际上是我们平时都使用过的排序,为什么这么说呢😆?想必大家都玩过扑克牌吧,大家是如何整理手中的牌的呢?一定是想下面这样对吧👇 没错,插入排序也是的么实

    2024年02月02日
    浏览(46)
  • Redis的速度不够用?为什么你应该考虑使用 KeyDB,一个更快、更强大、更灵活的开源数据库

    你是否正在使用 Redis 作为您的数据结构存储,享受它的高性能、高可用的特性?如果是这样,那么你可能会对 KeyDB 感兴趣。 KeyDB 一个由 Snap 提供支持、专为扩展而构建的开源数据库。它是 Redis 的高性能分支,专注于多线程、内存效率和高吞吐量。KeyDB 采用 MVCC 体系

    2024年02月08日
    浏览(66)
  • 为什么 Python 代码在函数中运行得更快?

    哈喽大家好,我是咸鱼 当谈到编程效率和性能优化时,Python 常常被调侃为“慢如蜗牛” 有趣的是,Python 代码在函数中运行往往比在全局范围内运行要快得多 小伙伴们可能会有这个疑问:为什么在函数中运行的 Python 代码速度更快? 今天这篇文章将会解答大家心中的疑惑 原

    2024年02月08日
    浏览(58)
  • 为什么list.sort()比Stream().sorted()更快?

    真的更好吗? 先简单写个demo 输出 由此可见list原生排序性能更好。 能证明吗? 证据错了。 再把demo变换一下,先输出stream.sort 此时输出变成了 这能证明上面的结论错误了吗? 都不能。 两种方式都不能证明什么。 使用这种方式在很多场景下是不够的,某些场景下,JVM会对代

    2024年02月14日
    浏览(33)
  • 为什么 list.sort() 比 stream().sorted() 要更快?测试结果把我惊呆了!

    作者:是奉壹呀 来源:juejin.cn/post/7262274383287500860 看到一个评论,里面提到了list.sort()和list.strem().sorted()排序的差异。 说到list sort()排序比stream().sorted()排序性能更好,但没说到为什么。 有朋友也提到了这一点。本文重新开始,先问是不是,再问为什么。 推荐一个开源免费的

    2024年02月09日
    浏览(40)
  • ElasticSearch(七):ES查询速度为什么那么快

    介绍给大家一个开源SpringCloud项目。整合了大部分开源中间件,详情信息可以查看文档: spring cloud开源组件开发 另外自己以后博客所讲解的代码内容,都会我的Git上同步(GitHub同步)GIT地址 ES使用的数据结构是倒排索引,在对搜索内容进行分词的时候,会根据搜索内容分词结

    2023年04月08日
    浏览(78)
  • Windows 程序开机自启动速度优化,为什么腾讯会议自启动速度那么高?

    目录 一、问题的说明和定义 二、问题的分析 1.问题初步分析 2.详细的分析: 2.1Windows常见的自启动方式 2.2Windows常见的自启动方式的细节分析 三、问题的解决方案 1、为什么腾讯会议Rooms那么快 2.我们是否可以跟腾讯会议一样快 这两天有个优化项需要做个技术调研,就是我们

    2024年02月02日
    浏览(87)
  • ElasticSearch第七讲:ES查询速度为什么那么快

    介绍给大家一个开源SpringCloud项目。整合了大部分开源中间件,详情信息可以查看文档: spring cloud开源组件开发 另外自己以后博客所讲解的代码内容,都会我的Git上同步(GitHub同步)GIT地址 ES使用的数据结构是倒排索引,在对搜索内容进行分词的时候,会根据搜索内容分词结

    2023年04月19日
    浏览(48)
  • ElasticSearch第七讲 ES查询速度为什么那么快

    介绍给大家一个开源SpringCloud项目。整合了大部分开源中间件,详情信息可以查看文档: spring cloud开源组件开发 另外自己以后博客所讲解的代码内容,都会我的Git上同步(GitHub同步)GIT地址 ES使用的数据结构是倒排索引,在对搜索内容进行分词的时候,会根据搜索内容分词结

    2023年04月25日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包