为什么 size_t 和 unsigned int 比 int 慢？

Question

我在 Windows 的 Visual Studio 项目中使用下面的简单交换排序算法试验不同的整数类型。处理器是英特尔。代码在版本 x64 中编译。优化设置为 "Maximize Speed (/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只需要在排序前保存向量。关键是，这个排序花了我 22.3 秒才完成。有趣的是，如果我将数组 A、WorkArray 的类型 int 更改为 size_t（在 std::vector 和函数 [= 的参数列表中） 20=])，以及 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、N 保留类型 int，因此仅有的两个算术i++ 和 j++ 的操作在这两种情况下应该花费相同的时间来执行。因此，这种放缓与其他原因有关。它与内存对齐问题或寄存器大小或其他问题有关吗？

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

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

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

Answer 1

我在 VS2017 中试过这段代码。复制成功

我修改了代码如下，这样时间就差不多了

原因似乎是数组索引的隐式转换。

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

using namespace std;

// exchange sort
template<typename elem_t, typename index_t>
void sort(index_t size, elem_t* a, elem_t* b)
{
    index_t index = 0, i, j;
    elem_t min;

    for (j = 0; j < size; j++)
    {
        min = 500000;
        for (i = j; i < size; i++)
        {
            if (a[i] < min)
            {
                min = a[i];
                index = i;
            }
        }
        b[j] = a[j];
        a[j] = min;
        a[index] = b[j];
    }
}

template<typename elem_t, typename index_t, index_t size>
void test() {
    //vector<elem_t> a(size);
    //vector<elem_t> b(size);

    elem_t a[size];
    elem_t b[size];

    for (index_t k = 0; k < size; k++)
        a[k] = (elem_t)(size - (k + 1));

    clock_t begin = clock();
    sort(size, &a[0], &b[0]);
    clock_t end = clock();

    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    cout << "Sort time: " << sortTime << endl;
}

int main()
{
    const int size = 40000;

    cout << "<size_t, int>" << endl;
    test<size_t, int, size>();
    cout << endl;

    cout << "<size_t, size_t>" << endl;
    test<size_t, size_t, size>();
    cout << endl;

    cout << "<int, int>" << endl;
    test<int, int, size>();
    cout << endl;

    cout << "<int, size_t>" << endl;
    test<int, size_t, size>();
    cout << endl;

    cout << "<uint, int>" << endl;
    test<unsigned int, int, size>();
    cout << endl;

    cout << "<uint, size_t>" << endl;
    test<unsigned int, size_t, size>();
    cout << endl;

    cout << "<uint, uint>" << endl;
    test<unsigned int, unsigned int, size>();
    cout << endl;
}

就我个人而言，我不喜欢隐式转换。为了解决此类问题，将警告级别提高到最大，并解决所有警告，然后转换为通用代码。这将帮助您确定问题。

此代码的结果显示为各种组合的结果。

有符号与无符号： In C, why is "signed int" faster than "unsigned int"?
类型大小（int32 与 int64）
数组索引汇编代码
vc++优化：/O2（最大优化（优先速度））
- 这使 (int / int) 变快了。

Answer 2

检查所有 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++ Optimizing Compiler Version 19.12.25830.2 for x64。

int 的执行时间约为 30 秒，另外两个的执行时间为 100 秒。

为什么 size_t 和 unsigned int 比 int 慢？

Why are size_t and unsigned int slower than int?

c++

int

performance

size-t