在这段C++代码中，对数据进行排序（在计时区域之前）使得主要循环运行速度提高了约6倍：

#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)
        {   // 主要循环。
            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';
}

如果没有 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)
    {
        // 生成数据
        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)
            {   // 主要循环。
                if (data[c] >= 128)
                    sum += data[c];
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

结果类似，但差异不那么极端。 我最初的想法是排序会将数据带入缓存，但这很愚蠢，因为数组是刚刚生成的。 到底是怎么回事？ 为什么处理已排序的数组比处理未排序的数组更快？ 代码只是对一些独立项进行求和，因此顺序应该不重要。 回答： 你观察到的现象与CPU的分支预测机制有关。现代CPU使用复杂的分支预测逻辑来猜测条件语句（如if）的结果，以便提前获取和执行随后的指令。当数据是随机的，如未排序的数组，if (data[c] >= 128)的结果很难预测，导致CPU经常误判，造成流水线停滞和性能下降。 然而，当数据被排序时，if语句的结果变得更容易预测。例如，一旦数组中的值开始超过128，CPU可以合理地预测后续的值也将超过128，从而提高分支预测的准确性并减少误判。这大大提高了代码的执行效率。 此外，虽然排序确实改善了数据的局部性，但在这个特定情况下，性能提升的主要原因更可能是分支预测的准确性提高，而不是缓存行为的改善。 总的来说，处理已排序的数组之所以比处理未排序的数组更快，主要是因为分支预测的准确性得到了显著提高。