为什么size_t和unsigned int比int慢？

Question

我正在使用下面的简单交换排序算法在Windows中的Visual Studio项目中尝试不同的整数类型.处理器是英特尔.代码是在Release 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只需要排序前保存的载体.关键是,这次排序花了我22.3秒才完成.有趣的是,如果我改变类型int到size_t数组A,WorkArray(无论是在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;
}

请注意,我仍然保持类型int的函数的局部变量i,j,index,N,和使是仅有的两个算术运算i++和j++应采取相同的时间量在两种情况下进行.因此,这种放缓与其他原因有关.它与内存对齐问题或寄存器大小或其他内容有关吗？

不过,最离谱的部分是当我改变int到unsigned int.既unsigned int与int占据相同数目是4个字节的(sizeof表明).但是运行时间unsigned int是65.8秒!虽然第一个结果有点可以接受,但第二个结果让我很困惑!为什么运行这样一个甚至不涉及符号检查的简单算法所需的时间差别如此之大？

感谢所有人都解决了这两个问题.我在哪里可以开始阅读有关这些硬件级优化特性的更多信息？我不关心排序算法本身,它仅用于说明问题.

更新:再一次,我强调在所有三种情况下我都使用int作为数组索引.

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++ Optimizing Compiler Version 19.12.25830.2 for x64.

我的执行时间大约为30秒,int其他两个执行时间为100秒.

Answer 2

我在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;
}

就个人而言,我不喜欢隐式演员.要解决此类问题,请将警告级别提高到最大值,并解决所有警告,然后转换为通用代码.这有助于您确定问题所在.

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

• signed vs unsigned: 在C中,为什么"signed int"比"unsigned int"更快？

• 类型大小(int32 vs int64)

• 数组索引汇编代码

• vc ++优化:/ O2(最大优化(偏好速度))

  • 这使(int/int)快速.