为什么使用 `std::view` 和 PSTL 实现速度较慢？

Question

我最近刚刚了解 PSTL，正在尝试它。我不明白为什么以下代码的行为如此不同。代码如下：

---

// a.cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <ranges>
#include <vector>

const long n = 1000;
long dp[n][n];

int main() {
  // init
  for (long i = 0; i < n; i++) {
    dp[i][0] = dp[0][i] = 1;
  }
  // dp, dp[i][j] = max((dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000, k < j)
  for (long i = 1; i < n; i++) {
    for (long j = 1; j < n; j++) {
      dp[i][j] = -1;
      for (long k = 0; k < j; k++) {
        dp[i][j] = std::max(dp[i][j], (dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000);
      }
    }
  }
  printf("res = %ld\n", dp[n - 1][n - 1]);
}

// b.cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <ranges>
#include <vector>
#include <execution>

const long n = 1000;
long dp[n][n];

int main() {
  // init
  for (long i = 0; i < n; i++) {
    dp[i][0] = dp[0][i] = 1;
  }
  // dp, dp[i][j] = max((dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000, k < j)
  for (long i = 1; i < n; i++) {
    for (long j = 1; j < n; j++) {
      auto view = std::views::iota(0, j)
        | std::views::transform([&i](long k) { 
            return (dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000;
          })
        | std::views::common;
      auto it = std::max_element(std::execution::par, view.begin(), view.end());
      dp[i][j] = *it;
    }
  }
  printf("res = %ld\n", dp[n - 1][n - 1]);
}

---

然后我编译并运行它们：

➜  ~ g++ -std=c++2a -Ofast -march=native a.cpp -o a
➜  ~ g++ -std=c++2a -Ofast -march=native b.cpp -o b
➜  ~ time ./a
res = 998
./a  0.79s user 0.01s system 99% cpu 0.804 total
➜  ~ time ./b
res = 998
./b  3.22s user 0.00s system 99% cpu 3.221 total

更令人惊讶的是，

-O2

比

-O3

更快：

➜  ~ g++ -Wall -std=c++2a -O2 -march=native b.cpp -o b -ltbb && time ./b
res = 998
./b  1.13s user 0.00s system 99% cpu 1.134 total
➜  ~ g++ -Wall -std=c++2a -O3 -march=native b.cpp -o b -ltbb && time ./b
res = 998
./b  3.18s user 0.00s system 99% cpu 3.180 total

编译器版本（我知道它很旧）：

➜  ~ g++ --version                                 
g++ (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

我绝对没想到时间会有如此巨大的不同，但以“相反的方式”，因为

b.cpp

使用并行策略

std::execution::par

。我还查看了汇编代码，似乎

b.cpp

甚至不再调用

std::max_element

（参见here），所以我想这意味着它已经被优化了。那怎么还慢？

有人可以提供关于我做错了什么的见解，以及我应该如何以仍然使用并行 STL 的方式“修复”它吗？

谢谢！

Answer 1

我得到了一个令人满意的答案，可能会帮助将来发现这个问题的人。

首先，我没有使用

-ltbb

。需要启用并行化。

此外，计时显示“99% cpu”，这表明没有任何并行化。事实上，查看 godbolt 反编译输出，我们看到所有函数都是内联的，这与我的观察相符（“我还查看了汇编代码，似乎

b.cpp

甚至不再调用

std::max_element

”） 。然而，这并不意味着它比

a.cpp

更优化。

最后，更好的解决方案是并行化 j 循环。请注意，对于固定的

i

，

j

循环可以并行运行，而无需写入数据竞争（当然它们可以同时从 dp[i - 1][*] 读取）。

我没有直接在

dp[i][j]

调用中与

std::max

进行比较和写入（这需要对其进行读取和写入），而是使用可能存储为寄存器或其他内容的局部变量。

在评论中讨论 STL 可能很慢之后，我也改回使用

omp.h

。平心而论，这也符合我平时的观察。甚至

std::deque

都比我自己写的糟糕的慢。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <omp.h>

// compile with -fopenmp

const long r = 50;
const long n = 5000;
long dp[r][n];

int main() {
  // init
  for (long i = 0; i < n; i++) {
    dp[0][i] = 1;
  }
  // dp, dp[i][j] = max((dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000, k < j)
  for (long i = 1; i < r; i++) {
    dp[i][0] = 1;
    #pragma omp parallel for
    for (long j = 1; j < n; j++) {
      long max = -1;
      for (long k = 0; k < j; k++) {
        max = std::max(max, (dp[i - 1][k] + dp[i - 1][n - 1 - k]) % 1000);
      }
      dp[i][j] = max;
    }
  }
  printf("res = %ld\n", dp[r - 1][n - 1]);
}

时间：

➜  ~ g++ -Wall -std=c++2a -O2 -march=native b.cpp -o b -fopenmp && time ./b
res = 998
./b  2.56s user 0.01s system 910% cpu 0.283 total

如您所见，CPU 使用率为 887%。对于

n = 20000

只需要 3 秒。