c++ - 为什么 size_t 和 unsigned int 比 int 慢？

Question

我正在使用下面的简单交换排序算法在 Windows 的 Visual Studio 项目中试验不同的整数类型。处理器是英特尔。代码在版本 x64 中编译。优化设置是“最大化速度 (/O2)”。编译设置对应的命令行为

/permissive- /GS /GL /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /sdl /Fd"x64\Release\vc141.pdb" /Zc:inline /fp:precise /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /errorReport:prompt /WX- /Zc:forScope /Gd /Oi /MD /Fa"x64\Release\" /EHsc /nologo /Fo"x64\Release\" /Fp"x64\Release\SpeedTestForIntegerTypes.pch" /diagnostics:classic 

代码本身:

#include <ctime>
#include <vector>
#include <iostream>

void sort(int N, int A[], int WorkArray[]) // exchange sort
{
    int i, j, index, val_min;
    for (j = 0; j < N; j++)
    {
        val_min = 500000;
        for (i = j; i < N; i++)
        {
            if (A[i] < val_min)
            {
                val_min = A[i];
                index = i;
            }
        }
        WorkArray[j] = A[j];
        A[j] = val_min;
        A[index] = WorkArray[j];
    }
}

int main()
{
    std::vector<int> A(400000), WorkArray(400000);
    for(size_t k = 0; k < 400000; k++)
        A[k] = 400000 - (k+1);

    clock_t begin = clock();

    sort(400000, &A[0], &WorkArray[0]);

    clock_t end = clock();
    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Sort time: " << sortTime << std::endl;
    return 0;
}

WorkArray 只需要在排序前保存 vector 。关键是，这个排序花了我 22.3 秒才完成。有趣的是，如果我将数组 A、WorkArray 的类型 int 更改为 size_t(均在 std::vector 和函数 sort 的参数列表)，以及 val_min，时间增加到 67.4!这慢了三倍!新代码如下:

#include <ctime>
#include <vector>
#include <iostream>

void sort(int N, size_t A[], size_t WorkArray[]) // exchange sort
{
    int i, j, index;
    size_t val_min;
    for (j = 0; j < N; j++)
    {
        val_min = 500000U;
        for (i = j; i < N; i++)
        {
            if (A[i] < val_min)
            {
                val_min = A[i];
                index = i;
            }
        }
        WorkArray[j] = A[j];
        A[j] = val_min;
        A[index] = WorkArray[j];
    }
}

int main()
{
    std::vector<size_t> A(400000), WorkArray(400000);
    for(size_t k = 0; k < 400000; k++)
        A[k] = 400000 - (k+1);

    clock_t begin = clock();

    sort(400000, &A[0], &WorkArray[0]);

    clock_t end = clock();
    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Sort time: " << sortTime << std::endl;
    return 0;
}

请注意，我仍然为函数局部变量 i、j、index、 保留类型 int >N，因此仅有的两个算术运算 i++ 和 j++ 在两种情况下执行的时间应该相同。因此，这种放缓与其他原因有关。它与内存对齐问题或寄存器大小或其他问题有关吗？

但是最离谱的部分是当我将int 更改为unsigned int 时。 unsigned int 和 int 都占用相同数量的字节，即 4(sizeof 表明了这一点)。但是 unsigned int 的运行时间是 65.8 秒!虽然第一个结果有点可以接受，但第二个结果让我完全困惑!为什么运行这样一个甚至不涉及符号检查的简单算法所花费的时间会有如此显着的差异？

感谢所有解决这两个问题的人。我可以从哪里开始阅读有关这些硬件级优化特性的更多信息？我不关心排序算法本身，它只是为了说明问题。

更新:我再次强调，我在所有三种情况下都使用整数作为数组索引。

Answer 1

检查所有 3 种变体(int、unsigned、size_t)的生成程序集，最大的区别在于 int 情况下 sort 函数中的循环被展开并使用 SSE 指令(一次处理 8 个整数)，而在其他 2 种情况下它两者都不做。有趣的是，sort 函数在 int 情况下被调用，而在其他两个情况下它被内联到 main 中(可能是由于增加了由于循环展开而导致的函数大小)。

我正在使用 cl/nologo/W4/MD/EHsc/Zi/Ox 从命令行进行编译，使用 dumpbin 进行反汇编，使用工具集 Microsoft (R) C/C++ 优化编译器版本 19.12.25830.2 for x64。

int 的执行时间约为 30 秒，其他两个的执行时间为 100 秒。