std::vector 与 C++ 中的 [] 比较慢 - 为什么？

Question

我对 C++ 有点生疏了——20 年前就用过它。我试图理解为什么 std::vector 在以下代码中比本机数组慢得多。谁能给我解释一下？我更喜欢使用标准库，但不会以这种性能损失为代价：

矢量：

const int grid_e_rows = 50;
const int grid_e_cols = 50;

int H(std::vector<std::vector<int>> &sigma) {
    int h = 0;
    for (int r = 0; r < grid_e_rows; ++r) {
        int r2 = (r + 1) % grid_e_rows;
        for (int c = 0; c < grid_e_cols; ++c) {
            int c2 = (c + 1) % grid_e_cols;

            h += 1 * sigma[r][c] * sigma[r][c2] + 1 * sigma[r][c] * sigma[r2][c];
        }
    }

    return -h;
}


int main() {
    auto start = std::chrono::steady_clock::now();

    std::vector<std::vector<int>> sigma_a(grid_e_rows, std::vector<int>(grid_e_cols));
    for (int i=0;i<600000;i++)
        H(sigma_a);
    auto end = std::chrono::steady_clock::now();
    std::cout << "Calculation completed in " << std::chrono::duration_cast<std::chrono::seconds>(end - start).count()
              << " seconds";

 return 0;
}

输出为：

Calculation completed in 23 seconds

数组：

const int grid_e_rows = 50;
const int grid_e_cols = 50;
typedef int (*Sigma)[grid_e_rows][grid_e_cols];

int H(Sigma sigma) {
    int h = 0;
    for (int r = 0; r < grid_e_rows; ++r) {
        int r2 = (r + 1) % grid_e_rows;
        for (int c = 0; c < grid_e_cols; ++c) {
            int c2 = (c + 1) % grid_e_cols;

            h += 1 * (*sigma)[r][c] * (*sigma)[r][c2] + 1 * (*sigma)[r][c] * (*sigma)[r2][c];
        }
    }

    return -h;
}

int main() {
    auto start = std::chrono::steady_clock::now();

    int sigma_a[grid_e_rows][grid_e_cols];
    for (int i=0;i<600000;i++)
        H(&sigma_a);
    auto end = std::chrono::steady_clock::now();
    std::cout << "Calculation completed in " << std::chrono::duration_cast<std::chrono::seconds>(end - start).count()
              << " seconds";

 return 0;
}

输出为：

Calculation completed in 6 seconds

如有任何帮助，我们将不胜感激。

Answer 1

首先，您要为初始化计时。对于数组情况，有 none（数组完全未初始化）。在矢量情况下，矢量被初始化为零，然后复制到每一行。

但主要原因是缓存位置。数组的情况是 50*50 整数的单个块，它们在内存中都是连续的，它们可以很容易地放入 L1D 缓存中。在 vector 的情况下，每一行都是动态分配的，这意味着它们的地址几乎肯定不是连续的，而是遍布整个程序的地址 space。访问一个不会将相邻行拉入缓存。

此外，由于行相对较小，缓存 space 被浪费在相邻的不相关数据上，这意味着即使您已经触及所有内容以将其拉入内存，它也可能不再适合 L1。最后，访问模式的线性度要低得多，它可能超出了硬件预取器的预测能力。

Answer 2

您没有使用优化进行编译。

比较：

为了让您初步了解优化器可能为您做些什么，请考虑针对 vector 的 vector 情况对 H() 函数进行以下修改。

int H(std::vector<std::vector<int>> &arg) {
    int h = 0;
    auto sigma = arg.data();
    for (int r = 0; r < grid_e_rows; ++r) {
        int r2 = (r + 1) % grid_e_rows;
        auto sr = sigma[r].data();
        auto sr2 = sigma[r2].data();
        for (int c = 0; c < grid_e_cols; ++c) {
            int c2 = (c + 1) % grid_e_cols;
            h += 1 * sr[c] * sr[c2] + 1 * sr[c] * sr2[c];
        }
    }

    return -h;
}

您会发现，如果不进行优化，此版本将运行更接近您的阵列版本的性能。

std::vector 与 C++ 中的 [] 比较慢 - 为什么？

Slow std::vector vs [] in C++ - Why?

c++

arrays

performance

stdvector