为什么处理有序数组比处理无序数组更快？

为什么处理有序数组比处理无序数组更快？

技术背景

在编写程序时，我们经常会遇到需要对数组进行处理的场景。有时会发现，处理有序数组的速度明显快于处理无序数组。例如，在以下 C++ 和 Java 代码中，对数组进行排序后，主要循环的执行速度提升了数倍。

C++ 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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';
}

Java 示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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);
    }
}

在上述代码中，未排序时，C++ 代码运行时间为 11.54 秒，Java 代码也有类似但程度稍轻的结果；而排序后，C++ 代码运行时间降至 1.93 秒。这引发了我们的疑问：为什么处理有序数组会更快呢？

实现步骤

理解分支预测

分支预测是现代处理器中用于提高指令流水线效率的一种技术。在处理器执行代码时，遇到条件判断语句（如 if 语句）时，会面临不同的执行路径选择。由于处理器在执行到条件判断语句时，往往不能立即确定走哪条路径，为了避免等待条件判断结果而导致流水线停顿，处理器会尝试预测分支的走向。

分析有序数组和无序数组的分支情况

  • 有序数组：当数组有序时，条件判断语句 if (data[c] >= 128) 的结果会呈现出一定的规律。例如，数据均匀分布在 0 到 255 之间，排序后大致前半部分元素不满足条件，后半部分元素满足条件。这种连续的相同分支走向非常有利于分支预测器进行准确预测。
  • 无序数组：当数组无序时，条件判断语句的结果是随机的，分支预测器无法找到规律，导致预测准确率大幅下降，约为 50%，接近随机猜测的水平。

优化代码以减少分支预测的影响

如果编译器无法将分支优化为条件移动指令，可以尝试一些技巧来牺牲代码可读性换取性能。例如，将 if (data[c] >= 128) 替换为以下代码：

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

这种方法消除了分支，用位运算替代，从而避免了分支预测失败带来的性能损失。

核心代码

C++ 分支优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    //std::sort(data, data + arraySize);

    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {
            int t = (data[c] - 128) >> 31;
            sum += ~t & data[c];
        }
    }

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

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

Java 分支优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        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;

        //Arrays.sort(data);

        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {
                int t = (data[c] - 128) >> 31;
                sum += ~t & data[c];
            }
        }

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

最佳实践

  • 避免数据依赖的分支：在关键循环中，尽量避免使用数据依赖的分支语句，如上述的 if 语句。可以通过位运算、条件移动指令等方式替代，减少分支预测失败的可能性。
  • 利用编译器优化：不同的编译器对代码的优化能力不同。例如，GCC 4.6.1 等编译器在开启 -O3 或 -ftree-vectorize 选项时，能够将分支优化为条件移动指令，从而消除排序和未排序数据的性能差异。
  • 使用查找表：对于一些简单的条件判断，可以使用查找表来替代分支语句。例如，在判断数据是否大于等于 128 时，可以构建一个长度为 256 的查找表，根据数据值直接从表中获取结果。

常见问题

分支预测失败一定会导致性能下降吗？

不一定。在某些情况下，现代编译器能够对代码进行优化，如自动向量化、生成条件移动指令等，从而避免分支预测失败带来的性能损失。但在编译器无法优化的情况下，分支预测失败会显著降低程序性能。

排序本身的时间开销是否值得？

如果只需要对数组进行一次处理，排序本身的时间开销通常是不值得的，因为排序操作的时间复杂度通常为 $O(n log n)$，可能会比处理数组的时间还要长。但如果需要多次处理数组，排序带来的性能提升可能会弥补排序的时间开销。

如何检测代码中的分支预测问题？

可以使用一些工具来检测代码中的分支预测问题，如 Valgrind 的 cachegrind 工具，通过 --branch-sim=yes 选项开启分支预测模拟；在 Linux 系统中，还可以使用 perf 工具来统计分支预测的相关信息，如分支数量、分支预测失败率等。

后端开发 > 性能优化
#后端开发 #Java #性能优化 #C++ #分支预测
为什么处理有序数组比处理无序数组更快？
https://119291.xyz/posts/2025-04-15.why-is-processing-a-sorted-array-faster-than-an-unsorted-array/
作者
ww
发布于
2025年4月15日
许可协议