在 C++ 中优化 2D 向量和数组

Question

我正在努力优化 C++ 中大型二维连续数组的访问性能，我希望在其中执行结构化访问。然而，关于实际解决这个问题的最有效方法，StackOverflow（以及网络上的其他地方）似乎有很多混杂的信息。

我使用以下代码来测试四种不同解决方案的运行时。在 clang 版本 14.0.3 上通过

g++ -std=c++20 -O3 vectortest.cpp -o vectortest

进行编译。

#include <vector>
#include <chrono>
#include <iostream>

using namespace std::chrono;

#define ARRAYSIZE 25000

template <typename T>
class vector2d {
    public:
        size_t size_x, size_y;
        std::vector<T> mvec;

    public:
        vector2d(
            size_t a_size_x,
            size_t a_size_y
        ) :
            size_x(a_size_x),
            size_y(a_size_y)
        {
            mvec.resize(size_x * size_y);
        }

    public:
        T & operator()(size_t i, size_t j) {
            return mvec[i * size_x + j];
        }
};

template <typename T>
class array2d {
    public:
        size_t size_x, size_y;
        T * mvec;

    public:
        array2d(
            size_t a_size_x,
            size_t a_size_y
        ) :
            size_x(a_size_x),
            size_y(a_size_y)
        {
            mvec = new T[size_x * size_y];
        }

        ~array2d() {
            delete[] mvec;
        }

    public:
        T & operator()(size_t i, size_t j) {
            return mvec[i * size_x + j];
        }
};

double vectorvector() {
    std::vector< std::vector<double> > x(ARRAYSIZE, std::vector<double>(ARRAYSIZE));

    for (size_t i = 0; i < ARRAYSIZE; i++) {
        for (size_t j = 0; j < ARRAYSIZE; j++) {
            x[i][j] = static_cast<double>(i) * static_cast<double>(j);
        }
    }

    return x[ARRAYSIZE/2][ARRAYSIZE/2];
}

double vector_contiguous() {
    std::vector<double> x(ARRAYSIZE*ARRAYSIZE);

    for (size_t i = 0; i < ARRAYSIZE; i++) {
        for (size_t j = 0; j < ARRAYSIZE; j++) {
            x[i * ARRAYSIZE + j] = static_cast<double>(i) * static_cast<double>(j);
        }
    }

    return x[(ARRAYSIZE/2)*ARRAYSIZE + (ARRAYSIZE/2)];
}

double vector2d_class() {
    vector2d<double> x(ARRAYSIZE, ARRAYSIZE);

    for (size_t i = 0; i < ARRAYSIZE; i++) {
        for (size_t j = 0; j < ARRAYSIZE; j++) {
            x(i,j) = static_cast<double>(i) * static_cast<double>(j);
        }
    }

    return x(ARRAYSIZE/2,ARRAYSIZE/2);
}

double array2d_class() {
    array2d<double> x(ARRAYSIZE, ARRAYSIZE);

    for (size_t i = 0; i < ARRAYSIZE; i++) {
        for (size_t j = 0; j < ARRAYSIZE; j++) {
            x(i,j) = static_cast<double>(i) * static_cast<double>(j);
        }
    }

    return x(ARRAYSIZE/2,ARRAYSIZE/2);
}

int main() {

    std::chrono::time_point<std::chrono::high_resolution_clock> start, stop;
    microseconds duration;

    start = high_resolution_clock::now();
    std::cout << vectorvector() << std::endl;
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);
 
    std::cout << "vectorvector: " << duration.count() << " microseconds" << std::endl;

    start = high_resolution_clock::now();
    std::cout << vector_contiguous() << std::endl;
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);

    std::cout << "vector_contiguous: " << duration.count() << " microseconds" << std::endl;

    start = high_resolution_clock::now();
    std::cout << vector2d_class() << std::endl;
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);

    std::cout << "vector2d_class: " << duration.count() << " microseconds" << std::endl;

    start = high_resolution_clock::now();
    std::cout << array2d_class() << std::endl;
    stop = high_resolution_clock::now();
    duration = duration_cast<microseconds>(stop - start);

    std::cout << "array2d_class: " << duration.count() << " microseconds" << std::endl;

}

结果时间如下：

vectorvector: 3291998 microseconds
vector_contiguous: 2238134 microseconds
vector2d_class: 2221989 microseconds
array2d_class: 1544225 microseconds

向量向量解决方案在网上很常见，我在 StackOverflow 上看到了一些说法，即使用现代编译器，它可能与连续的一维数组具有相同的性能。然而，情况似乎并非如此，向量向量比连续向量解慢 45%。

但也许最令我惊讶的是，array2d 选项比使用向量的类似解决方案快 45% 左右，即使使用 -O3 也是如此。在 C++ 中的向量和数组之后，我还尝试了 -finline-functions 并发现了大致相似的性能。

无论如何，我的问题是：这些结果符合预期吗？这个实验有什么明显的缺陷吗？是否应该寻求替代解决方案？为什么STL没有多维向量类型？

Answer 1

正如其他人在评论中所解释的那样，一维数组/内存现在比向量>快得多，有时甚至快几个数量级。事实上，我很惊讶它只比连续向量慢 45%。我假设，由于您在函数中初始化了容器，因此它已经在缓存中拥有大部分数据，因此比预期更快。如果您实际上想要对容器在使用时直接初始化的情况进行基准测试，这可能没问题，但对于稍后访问它们的许多情况，最好将这些操作分开，并确保缓存在运行实际循环之间失效。

但也许最让我惊讶的是 array2d 选项是围绕 即使使用 -O3，也比使用向量的类似解决方案快 45%。 在 C++ 中的向量和数组之后我也尝试过 -finline-functions 并发现大致相似的性能。

这很肯定是因为 vector<> 在调整大小时初始化了它的内容，如评论中所述 - 尽管这部分也适用于 1d 向量，并且在调用采用大小值的构造函数时也是如此。 在某些情况下，编译器可能能够对此进行优化，但我认为您的情况太复杂，无法理解您正在有效地覆盖整个数组（或者它还有其他原因仍然决定初始化它）。查看 godbolt 中 clang (-O3) 的程序集：

movabs r14, 5000000000
mov rdi, r14
call operator new(unsigned long)@PLT
mov rbx, rax
xor r15d, r15d
mov rdi, rax
xor esi, esi
mov rdx, r14
call memset@PLT

这是矢量连续情况下需要做的第一件事。这意味着在整个循环之前，调用“memset”将整个数组初始化为 0，所有 5000000000 个元素。这解释了您自己分配的数组之间的差异。

在我看来，这是向量的一个相当严重的限制——至少你没有办法阻止它。 std::string 最近添加了 resize_and_overwrite （https://en.cppreference.com/w/cpp/string/basic_string/resize_and_overwrite），恕我直言，它的语法有点笨拙，但实现了这一点：您保存了所有0 的开销 - 初始化字符串，适用于您知道无论如何都会覆盖它的情况。这为我处理文件加载代码的代码提供了一些真正的加速，该代码暂时使用 std::string 作为缓冲区。

顺便说一句，我个人已经使用我自己的“向量”实现相当长一段时间了。我采用了更直接的方法并添加了 ctor 重载，这允许内存未初始化：

sys::Vector<double> vectorContinous(VECTOR_SIZE * VECTOR_SIZE, sys::UninitializedHint); // behaves like "new double[]" for allocating the memory, without initialization

当然，这只会编译不重要的类型。但是，当使用与您建议的类似的向量时，这也被证明可以带来一些显着的加速。 std::string 采用 resize_and_overwrite 方法是有原因的，论文中对此进行了解释；所以我不一定说向量必须采用我的建议。但对于 std::vector 来说类似的东西恕我直言会很有用。