std::vector 与 C++ 中的 [] 比较慢 - 为什么?
Slow std::vector vs [] in C++ - Why?
我对 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
如有任何帮助,我们将不胜感激。
首先,您要为初始化计时。对于数组情况,有 none(数组完全未初始化)。在矢量情况下,矢量被初始化为零,然后复制到每一行。
但主要原因是缓存位置。数组的情况是 50*50
整数的单个块,它们在内存中都是连续的,它们可以很容易地放入 L1D 缓存中。在 vector 的情况下,每一行都是动态分配的,这意味着它们的地址几乎肯定不是连续的,而是遍布整个程序的地址 space。访问一个不会将相邻行拉入缓存。
此外,由于行相对较小,缓存 space 被浪费在相邻的不相关数据上,这意味着即使您已经触及所有内容以将其拉入内存,它也可能不再适合 L1。最后,访问模式的线性度要低得多,它可能超出了硬件预取器的预测能力。
您没有使用优化进行编译。
比较:
为了让您初步了解优化器可能为您做些什么,请考虑针对 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;
}
您会发现,如果不进行优化,此版本将 运行 更接近您的阵列版本的性能。
我对 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
如有任何帮助,我们将不胜感激。
首先,您要为初始化计时。对于数组情况,有 none(数组完全未初始化)。在矢量情况下,矢量被初始化为零,然后复制到每一行。
但主要原因是缓存位置。数组的情况是 50*50
整数的单个块,它们在内存中都是连续的,它们可以很容易地放入 L1D 缓存中。在 vector 的情况下,每一行都是动态分配的,这意味着它们的地址几乎肯定不是连续的,而是遍布整个程序的地址 space。访问一个不会将相邻行拉入缓存。
此外,由于行相对较小,缓存 space 被浪费在相邻的不相关数据上,这意味着即使您已经触及所有内容以将其拉入内存,它也可能不再适合 L1。最后,访问模式的线性度要低得多,它可能超出了硬件预取器的预测能力。
您没有使用优化进行编译。
比较:
为了让您初步了解优化器可能为您做些什么,请考虑针对 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;
}
您会发现,如果不进行优化,此版本将 运行 更接近您的阵列版本的性能。