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

在此 C++ 代码中，对数据进行排序（在定时区域之前）使主循环速度加快约 6 倍：

#include #include #include int main(){
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];
    for (unsigned c = 0; c = 128)
                sum += data[c];
        }
    }
    double elapsedTime = static_cast(clock()-start) / CLOCKS_PER_SEC;
    std::cout 

文章来源地址 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 = 128)
                    sum += data[c];
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum =" + sum);
    }}
具有类似但不那么极端的结果。

我的第一个想法是排序将数据带入缓存 ， 但这很愚蠢，因为数组刚刚生成。
该代码总结了一些独立的术语，因此顺序并不重要。
什么是分支预测？

考虑一个铁路枢纽：
现在为了便于讨论，假设现在是 1800 年代——远距离或无线电通信出现之前。
你是路口的盲人操作员，你听到火车驶来。你不知道它应该走哪条路。你停下火车询问司机他们想要哪个方向。然后你适当地设置开关。
火车很重并且有很大的惯性，因此它们需要很长时间才能启动和减速。
有没有更好的办法？你猜火车会开往哪个方向！


如果你猜对了，就继续。


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


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

考虑一个 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, ...
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 模板网！