c++ - 如何消除并行 std::transform_reduce() 的中间容器？

Question

经常，我必须找到 Sum( f(i), 1, N ) 或 Product( f(i), 1, N )，其中 f(i) 是计算密集型的，而积分 i 来自序列范围但很大。

使用 C++20 编译器我可以编写函数:

uint64_t solution(uint64_t N)
{
    std::vector<uint64_t> v(N);
    std::iota(v.begin(), v.end(), 1ULL);

    return std::transform_reduce(
                std::execution::par, 
                v.cbegin(), v.cend(), 
                0ull, 
                std::plus<>(), 
                []f(const uint64_t& i)->uint64_t {
                   uint64_t result(0);
                   // expensive computation of result=f(i) goes here
                   // ...
                   return result;
                 });  

}

但这会受到 RAM 的限制。

如何仅使用 C++20 STL(即没有供应商特定库或第 3 方库)在运行时完全消除使用输入 vector 的中间内存操作，同时实现高效的并行执行？

Answer 1

免责声明:我之前没有实现迭代器或使用 C++20 的经验

这似乎适用于 gcc 10.1 和 -std=c++2a .我在很短的时间内就把它放在一起，没有考虑太多，所以如果只是通过模板化的话，实现肯定可以得到改进。如果operator<=>换成了旧的双向比较运算符，这应该也可以用 C++17 运行，但我还没有测试过。如果您发现任何错误或易于纠正的设计缺陷，欢迎您在下方发表评论，以便改进此答案。

#include <cstddef>

#if __cplusplus > 201703L
#include <compare>
#endif

#include <execution>
#include <iostream>
#include <iterator>
#include <numeric>

class counting_iterator {
public:
  typedef std::ptrdiff_t difference_type;
  typedef std::ptrdiff_t value_type;
  typedef void pointer;
  typedef void reference;
  typedef std::random_access_iterator_tag iterator_category;

private:
  value_type val_{0};

public:
  counting_iterator() = default;
  explicit counting_iterator(value_type init) noexcept : val_{init} {}
  value_type operator*() const noexcept { return val_; }
  value_type operator[](difference_type index) const noexcept {
    return val_ + index;
  }
  counting_iterator &operator++() noexcept {
    ++val_;
    return *this;
  }
  counting_iterator operator++(int) noexcept {
    counting_iterator res{*this};
    ++(*this);
    return res;
  }
  counting_iterator &operator--() noexcept {
    --val_;
    return *this;
  }
  counting_iterator operator--(int) noexcept {
    counting_iterator res{*this};
    --(*this);
    return res;
  }
  friend counting_iterator operator+(counting_iterator const &it,
                                     difference_type const &offset) noexcept;
  friend counting_iterator operator+(difference_type const &offset,
                                     counting_iterator const &it) noexcept;
  friend counting_iterator operator-(counting_iterator const &it,
                                     difference_type const &offset) noexcept;
  friend difference_type operator-(counting_iterator const &a,
                                   counting_iterator const &b) noexcept;
  counting_iterator &operator+=(difference_type offset) noexcept {
    val_ += offset;
    return *this;
  }
  counting_iterator &operator-=(difference_type offset) noexcept {
    val_ -= offset;
    return *this;
  }
  friend bool operator==(counting_iterator const &a,
                         counting_iterator const &b) noexcept;
#if __cplusplus > 201703L
  friend std::strong_ordering operator<=>(counting_iterator const &a,
                                          counting_iterator const &b);
#else
  friend bool operator!=(counting_iterator const &a,
                         counting_iterator const &b) noexcept;
  friend bool operator<=(counting_iterator const &a,
                         counting_iterator const &b) noexcept;
  friend bool operator>=(counting_iterator const &a,
                         counting_iterator const &b) noexcept;
  friend bool operator<(counting_iterator const &a,
                        counting_iterator const &b) noexcept;
  friend bool operator>(counting_iterator const &a,
                        counting_iterator const &b) noexcept;
#endif
};

counting_iterator
operator+(counting_iterator const &it,
          counting_iterator::difference_type const &offset) noexcept {
  return counting_iterator{it.val_ + offset};
}
counting_iterator operator+(counting_iterator::difference_type const &offset,
                            counting_iterator const &it) noexcept {
  return counting_iterator{it.val_ + offset};
}
counting_iterator
operator-(counting_iterator const &it,
          counting_iterator::difference_type const &offset) noexcept {
  return counting_iterator{it.val_ - offset};
}
counting_iterator::difference_type
operator-(counting_iterator const &a, counting_iterator const &b) noexcept {
  return a.val_ - b.val_;
}
bool operator==(counting_iterator const &a,
                counting_iterator const &b) noexcept {
  return a.val_ == b.val_;
}
#if __cplusplus > 201703L
std::strong_ordering operator<=>(counting_iterator const &a,
                                 counting_iterator const &b) {
  return a.val_ <=> b.val_;
}
#else
bool operator!=(counting_iterator const &a,
                counting_iterator const &b) noexcept {
  return a.val_ != b.val_;
}
bool operator<=(counting_iterator const &a,
                counting_iterator const &b) noexcept {
  return a.val_ <= b.val_;
}
bool operator>=(counting_iterator const &a,
                counting_iterator const &b) noexcept {
  return a.val_ >= b.val_;
}
bool operator<(counting_iterator const &a,
               counting_iterator const &b) noexcept {
  return a.val_ < b.val_;
}
bool operator>(counting_iterator const &a,
               counting_iterator const &b) noexcept {
  return a.val_ > b.val_;
}
#endif

int main() {
    auto res = std::transform_reduce(
                std::execution::par, 
                counting_iterator(0), counting_iterator(10), 
                0L, 
                std::plus<>(), 
                [](const std::ptrdiff_t& i) { return i * i; });

    std::cout << res << std::endl;
}

编辑:我研究了该类，使其也可用于 C++17。现在它还显式定义了 std::random_access_iterator_tag .我仍然没有使用该执行策略进行任何并行计算，无论是迭代器还是 vector ，所以我不知道类本身是否有任何东西会抑制并行执行。