为何使用std::view与PSTL的C++实现运行速度更慢？

我最近刚接触PSTL并开展相关实验，无法理解以下两段C++代码为何性能差异如此显著。

代码对比 #

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（PSTL并行实现） #

#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++ (Debian 10.2.1-6) 10.2.1 20210110

Ofast优化下的运行时间 #

➜  ~ 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

疑问与观察 #

我原本预期使用std::execution::par的并行版本会更快，但结果完全相反。查看汇编后发现，b.cpp中的std::max_element似乎被优化掉了，但程序运行速度依然远慢于串行版本。

请问：

• 这种性能差异的核心原因是什么？
• 如何在保留PSTL并行策略的前提下优化这段代码？

内容的提问来源于stack exchange，提问作者ketsi