logo标签列表

使用二维数组还是一维数组，哪个更快？

c++optimization
4
我一直在网上（和stackoverflow）搜索关于一维数组（或向量）是否比它们的二维对应物更快的意见。总的结论似乎是一维数组最快。然而，我写了一个简短的测试程序来自己验证，结果表明二维数组最好。有人能找到我的测试中的错误，或者至少解释为什么我得到这个结果吗？
我用它来存储矩阵，因此需要同时使用行和列索引1维数组。
#include <iostream>
#include <chrono>
#include <vector>

uint64_t timestamp()
{
    namespace sc = std::chrono;
    static auto start = sc::high_resolution_clock::now();
    return sc::duration_cast<sc::duration<uint64_t, std::micro>>(sc::high_resolution_clock::now() - start).count();
}

int main(int argc, char** argv)
{
    if (argc < 3)
        return 0;
    size_t size = atoi(argv[1]);
    size_t repeat = atoi(argv[2]);

    int** d2 = (int**)malloc(size*sizeof(int*));
    for (size_t i = 0; i < size; ++i)
        d2[i] = (int*)malloc(size*sizeof(int));

    int* d1 = (int*)malloc(size*size*sizeof(int));

    std::vector<std::vector<int> > d2v(size);
    for (auto& i : d2v)
        i.resize(size);

    std::vector<int> d1v(size*size);

    uint64_t start, end;
    timestamp();

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d2[r][c] = 0;
                else
                    d2[r][c] = d2[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D array\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d2[r][c] = 0;
                else
                    d2[r][c] = d2[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D array C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d1[r + c*size] = 0;
                else
                    d1[r + c*size] = d1[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D array\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d1[r + c*size] = 0;
                else
                    d1[r + c*size] = d1[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D array C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d2v[r][c] = 0;
                else
                    d2v[r][c] = d2v[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D vector\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d2v[r][c] = 0;
                else
                    d2v[r][c] = d2v[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D vector C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d1v[r + c*size] = 0;
                else
                    d1v[r + c*size] = d1v[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D vector\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d1v[r + c*size] = 0;
                else
                    d1v[r + c*size] = d1v[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D vector C\t" << size << "\t" << end - start << std::endl;

    return 0;
}

我得到了以下输出：
user@user-debian64:~/matrix$ ./build/test/index_test 1000 100
2D array    1000    79593
2D array C  1000    326695
1D array    1000    440695
1D array C  1000    262251
2D vector   1000    73648
2D vector C 1000    418287
1D vector   1000    371433
1D vector C 1000    269355
user@user-debian64:~/matrix$ ./build/test/index_test 10000 1
2D array    10000   149748
2D array C  10000   3507346
1D array    10000   2754570
1D array C  10000   257997
2D vector   10000   92041
2D vector C 10000   3791745
1D vector   10000   3384403
1D vector C 10000   266811
关键词：本地性，缓存。 - Seyf
是的，但这似乎是人们说一维最快的原因。 - Jonas
哦，刚刚检查了代码。你在迭代一维数组时做错了很多。请看我几分钟后的答案。 - Seyf
1
这是在Intel Core i7上使用Intel、Clang和GCC编译器，在Arch Linux 64位系统上的结果：http://pastebin.com/MfsQzf5N。 - rubenvb
@Jonas：对于“2D数组”情况，添加这两个选项可以使性能提高约14％，而对于其他测试来说则更少或可以忽略不计。 -O3并不总是更快，它会添加一些像-fast-math这样的东西，可能是不需要的。不要只使用-O3。你也可以选择优化大小，然后进行优化。-O2应该是一个合理的默认值。如果需要了解，请进行测量。 - rubenvb
显示剩余5条评论
2个回答
2
问题的根源在于两种方案之间的存储顺序不同。
你的二维结构以行为主进行存储。通过先解引用行，您可以到达一个单一的缓冲区，该缓冲区可以直接按列索引。相邻的列位于相邻的内存位置。
你的一维结构以列为主进行存储。相邻的列在内存中相隔“size”个元素。
尝试迭代两种顺序几乎涵盖了所有影响。但剩下的是数据依赖性。通过引用“D（r-1，c）”，在行优先和列优先之间访问模式完全不同。
确实，将一维索引更改为“d1 [r * size + c]”和“d1 [(r-1) * size + c]”会产生以下时间：
2D array    1000    78099
2D array C  1000    878527
1D array    1000    19661
1D array C  1000    729280
2D vector   1000    61641
2D vector C 1000    741249
1D vector   1000    18348
1D vector C 1000    726231

所以，我们仍需要解释一下。我选择使用“循环依赖”这个术语。当你按列主序遍历列主序的一维数组（好主意），每个元素都依赖于前一个迭代中计算出的元素。这意味着循环不能完全流水线化，因为结果必须完全计算并写回缓存，然后才能再次读取以计算下一个元素。在行主序中，依赖关系现在是一个很久以前计算出的元素，这意味着循环可以展开和流水线化。
编译时使用了优化标志吗？当我使用“-O3”时，1D和2D向量的速度几乎与1D数组相同。 - Jonas
1
是的，这些时间是使用GCC 4.8和-O3选项得出的。在不同的优化设置下，至少存在50%的差异，除非我使用-O3并禁用向量化。在这种情况下，一维数组仅比二维数组略快。因此，自动向量化也影响了这些时间。 - Peter
2
你在遍历一维数组的方式是错误的。在一维数组中不需要嵌套循环。这不仅是不必要的，而且会增加计算索引的额外工作量。取而代之的是，
for (size_t c = 0; c < size; ++c)
{
    for (size_t r = 0; r < size; ++r)
    {
        if (r == 0)
            d1[r + c*size] = 0;
        else
            d1[r + c*size] = d1[r-1 + c*size] + 1;
    }
}

你应该编写

for (size_t r = 0; r < size*size; ++r)
{
    if (r == 0)
        d1[r] = 0;
    else
        d1[r] = d1[r-1] + 1;
}

并且它会很好。

我的使用案例是矩阵存储，因此我使用行和列来填充矩阵，其中整数介于 0 和 size-1 之间。因此，我需要能够通过行和列进行索引。 - Jonas
2
这会产生不同的结果。 - Peter
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接