java - .Net core vs c++ performance - 为什么处理一个排序数组比处理一个未排序数组快?

Java vs C# performance / java / c++ / performance / optimization / branch-prediction

这里有一段C++代码,显示了一些非常奇特的行为。由于一些奇怪的原因,对数据进行排序,奇迹般地使代码速度快了近六倍。

#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 << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

最初,我认为这可能只是一种语言或编译器的异常,所以我尝试了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);
    }
}

Aplet123



Answer #1

通过使用决策位的0/1值作为进入数组的索引,我们可以做出无论数据是否排序都同样快速的代码。我们的代码总是会添加一个值,但是当决定位为0时,我们会把值添加到我们不关心的地方。下面是代码。

// 测试
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    //主循环
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];
// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}
if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个图书馆会做这样的事情。

i = (x < node->value);
node = node->link[i];