logo标签列表

为什么 size_t 和 unsigned int 比 int 慢？

c++performanceintsize-t
6

我在Windows Visual Studio项目中，使用下面的简单交换排序算法尝试了不同类型的整数。 处理器是Intel。 代码已使用“最大化速度（/ O2）”进行了Release x64编译。 对应于编译设置的命令行如下：

/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;
}
< p > WorkArray 只需要在排序前保存向量。 重点是，这个排序花费了我 22.3 秒才完成。有趣的是，如果我将数组 A、WorkArray（都在 std::vector 中和函数 sort 的参数列表中）以及 val_min 的类型从 int 改为 size_t，那么时间会增加到 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时。无符号整数和整数占用相同的字节数，即4个（sizeof显示）。但unsigned int的运行时间为65.8秒！虽然第一个结果还可以接受，但第二个结果完全使我困惑！为什么运行这样一个甚至没有涉及符号检查的简单算法所需的时间差异如此显着？
感谢所有回答这两个问题的人。我在哪里可以开始阅读有关这些硬件级别优化特性的更多信息？我不关心排序算法本身，它只是用于说明问题。
更新：再次强调，我在所有三种情况下都使用int作为数组索引。
3
当您更改类型时，您是在所有位置更改还是仅在主要位置更改？您能否发布两个表现不同的代码版本来回答我的问题？当你改变类型时，你是在所有地方改变还是只在主函数中改变？你能否发布两个行为不同的代码版本来回答我的问题？ - Benjamin Barrois
4
你的优化设置是什么？通常情况下，基准测试应该只应用于已发布、非调试版本的构建。 - Thomas Matthews
1
无法在Coliru上重现GCC错误。同时，有一个警告：main.cpp:23:16: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized] A[index] = WorkArray[j]; 不幸的是，我目前没有MSVC来测试它。 - Mysticial
1
在我的机器上测试了代码。int用了42秒，unsigned int用了41秒。当你测试这两种情况时，你的机器是否空闲？（我对size_t不感兴趣，因为它对我来说是一种“显而易见的两倍数据”东西。） - zzxyz
1
@zzxyz 在VS中反汇编看起来很可怕，我担心这可能会引起不必要的混乱。最好让读者在他们的VS上本地生成它。一些读者成功复现了所描述的行为。 - MajinSaha
显示剩余21条评论
2个回答
10
检查生成的汇编代码（对于所有3个变量：int、unsigned和size_t），最大的区别在于，在int情况下，sort函数中的循环展开并使用SSE指令（一次处理8个整数），而在其他2种情况下则没有。有趣的是，在int情况下调用了sort函数，而在另外两个情况下将其内联到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秒的执行时间。
谢谢！你有没有想过为什么它不会展开unsigned int，考虑到它与int大小相同？ - MajinSaha
1
这就是闭源编译器的悲哀之处，除非你自己编写并违反雇主的保密协议，否则没有其他人知道编译器在进行特定优化时为什么会做出某些操作。 - David C. Rankin
1
可能是由于有一个SSE指令（pcmpgtd）用于进行带符号比较，但没有用于无符号比较的指令。 - 1201ProgramAlarm
@1201ProgramAlarm - 有趣。我的代码从未生成过这个指令或类似的指令，尽管它使用了其他AVX/SSE指令。 - zzxyz
@1201ProgramAlarm - 在VS 2015和2017中，汇编有相当大的不同（2015年为25秒，而2017年为40秒）。 - zzxyz
6

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

个人而言，我不喜欢隐式转换。

为了解决这种问题，将警告级别提高到最大，并解决所有警告，然后转换为通用代码。这将帮助您识别问题。

此代码的结果出现在各种组合中。

你是如何成功将三种情况的运行时间缩短到0.67秒的？！非常感谢你的出色回答，我会慢慢消化它。 - MajinSaha
哦，我明白了。抱歉，我没有注意到。 - MajinSaha
1
回复：“我不喜欢隐式转换”--这是不存在的。强制转换是你在源代码中编写的内容，告诉编译器进行转换。也就是说，它总是显式的。转换可以是隐式的。 - Pete Becker
所以在你的情况下，我现在有大约67秒来完成这三个任务。尽管你设法使所有三种情况的运行时间相等，但这并不能解释为什么我仅使用裸的int时需要22秒。请注意，我在所有情况下都使用int作为数组索引。 - MajinSaha
@Minos，我测试了你的示例，它似乎表现得与OP一样（也就是说：似乎没有什么被修复）：size_t测试用例需要97.936秒，int测试用例需要27.149秒，而unsigned int则需要94.835秒。在你问之前：是的，我正在使用启用了全程序优化的x64 Release模式进行构建。 - Algirdas Preidžius
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接