为什么处理有序数组比无序数组要快?

为什么处理有序数组比无序数组要快?

来自GManNickG的提问

Why is it faster to process a sorted array than an unsorted array?

下面这段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)
    {
        // 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;
}
  • 上述代码的运行时间为1.93秒
  • 如果将代码std::sort(data, data + arraySize);去掉,运行时间为11.54秒

开始我以为这是由于语言或者编译器造成的,所以又使用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);
    }
}

但是得到了相似的结果,虽然速度差别没有C++那么大。

我首先想到的原因是排序后数据被加载到了cache,但是转念一想数组是刚刚生成的,所以这个想法不成立。

这段代码是将彼此无关的数据项相加,数组是否有序不应该影响运行速度。那么为什么有序数组要比无序数组快很多呢?

来自Mysticial的最佳回答

你是分支预测失败的受害者

什么是分支预测?

enter image description here Image by Mecanismo, via Wikimedia Commons. Used under the CC-By-SA 3.0 license.

出于讨论需要,假设回到19世纪-此时还没有远程或者无线通讯工具。

你是铁路分支点的操作员,听到火车正在开过来。你不知道火车将会走哪条路。你喊停火车询问驾驶员他们要去哪个方向。然后你将铁路切换到相应的位置。

火车很重,惯性很大。所以火车启动和减速要费很长时间。

那么是否有更好的方法呢?答案就是你来猜测火车将会去哪个方向!

  • 如果你猜对了,火车就会正常跑下去。
  • 如果你猜错了,列车长会让火车停下来,退回去,并让你切换铁路。然后火车沿着另一条路启动。

如果你每次都能猜对,火车永远都不用停下来。

如果你经常猜错,火车将会花很多时间停下来,退回去,重新启动。


考虑if语句,从处理器的层次来看,它是一条分支指令:

enter image description here

你就是一个处理器,看到了一条分支。你不知道将会执行哪条指令。你会怎么做?你可以停止执行,等待前面的指令都执行完毕。然后你继续执行正确的指令。

现代处理器是很复杂的,有很长的指令流水线。所以让处理器重启和减速是要花很长时间的。

是否有更好的方法呢?答案就是猜测将会执行哪条分支指令!

  • 如果猜对了,就会继续执行下去。
  • 如果猜错了,就需要清掉流水线,回退到到分支,然后重新执行另一条分支。

这就是分支预测。不得不承认这并不是最好的类比,因为火车可以用指示灯指示其方向。但是在计算机中,处理器直到最后时刻才能知道将要执行哪条分支。

现在问题是应该采用何种策略,使得火车退回来然后沿另一条路走的次数最小呢?答案就是你根据过往的历史来预测!如果火车100次有99次都往左走,则预测下次还是往左。如果以前是两个方向交替走的,则预测也是交替的。如果以前是每3次换一次方向,则按相同的规律预测……

也就是说,你需要尝试总结出一种规律并且按这种规律预测。这基本上就是分支预测的工作方式。

大部分程序的分支都是有规律的。所以现代分支预测一般都能达到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)

那我们能做什么?

如果编译器不能将分支优化成条件移动,你可以尝试一些hack方式,前提是你愿意为了性能牺牲一些程序的可读性。

将代码:

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

替换为:

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

这样就用位操作代替了分支。

(注意这种hack方式并不严格等价于原始if语句。但是在这个案例中,它对data[]中的所有数据都是有效的。)

Benchmarks: Core i7 920 @ 3.5 GHz

C++ – Visual Studio 2010 – x64 Release

//  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方式比分支稍微慢一点

一个通用的原则是在特定的循环中避免使用数据依赖分支。(例如这个案例)

更新

  • 64位机器下,GCC 4.6.1附带-O3或者-ftree-vectorize选项可以产生条件移动。因此有序数组和无序数组就没有区别了,二者都很快。
  • VC++ 2010无法产生条件移动,即使在/Ox情况下也不行。
  • Intel Compiler 11在这方面可以做些不可思议的事情。它交换了两个循环,将无法预测的分支提升到了循环外面。因此它不仅消除了错误预测的问题,并且运行速度是VC++和GCC的两倍。也就是说,ICC使用测试循环打破了benchmark。
  • 如果使用Intel Compiler编译无分支的代码,则它仅仅出右向量化,和有分支情况下速度一样(采用交换循环)。

可以看出现代编译器在优化代码的能力方面还是有很大不同的。

参考资料

本文译自Why is it faster to process a sorted array than an unsorted array?

发表评论

电子邮件地址不会被公开。 必填项已用*标注