How to eliminate intermediate container for parallel std::transform_reduce()?

user_14559358 0
Viewed 116

Frequently, I have to find Sum( f(i), 1, N ) or Product( f(i), 1, N ), where f(i) is computationally CPU-intensive, while integral i is from sequential range but huge.

Using C++20 compiler I can write function:

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;
                 });  

}

But that will be RAM constrained.

How I can completely eliminate intermediate memory operations with input vector in run-time using only C++20 STL (i.e. no vendor specific or 3rd party libraries) and yet have efficient parallel execution?

c++20 concurrency multithreading stl c++
2 Answers

Disclaimer: I have no prior experience in implementing iterators or in C++20

This seems to work for me with gcc 10.1 and -std=c++2a. I put this together in very short time without putting much thought into it, so the implementation can certainly be improved, if only by templatizing it. If operator<=> is exchanged for the old two-way comparison operators, this should also run with C++17, but I haven't tested it. If you find any errors or easily correctable design flaws, you are welcome to comment them below, such that this answer can be improved.

#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;
}

EDIT: I worked over the class to make it usable with C++17 as well. Now it also explicitly typedefs the std::random_access_iterator_tag. I still don't get any parallel computing with that execution policy, neither with the iterator nor with the vector, so I don't know if there is anything about the class itself inhibiting parallel execution.

user_101074540

After some massaging and experiments I am confirming that bidirectional iterator, based on sample from Paul above, had worked:

class counting_iterator {
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = std::ptrdiff_t;
private:
    value_type val_;
public:
    counting_iterator() : val_(0) {}
    explicit counting_iterator(value_type init) : val_(init) {}

    value_type operator*() noexcept { return val_; }
    const value_type& operator*() const noexcept { return val_; }

    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; }

    value_type operator[](difference_type index) noexcept { return val_ + index; }

    counting_iterator& operator+=(difference_type offset) noexcept { val_ += offset; return *this; }
    counting_iterator& operator-=(difference_type offset) noexcept { val_ -= offset; return *this; }

    counting_iterator operator+(difference_type offset) const noexcept { return counting_iterator{ *this } += offset; };
    /*counting_iterator& operator+(difference_type offset) noexcept { return operator+=(offset); }*/

    counting_iterator operator-(difference_type offset) const noexcept { return counting_iterator{ *this } -= offset; };

    /*counting_iterator& operator-(difference_type offset) noexcept { return operator-=(offset); }*/

    difference_type operator-(counting_iterator const& other) noexcept { return val_ - other.val_; }

    bool operator<(counting_iterator const& b) const noexcept { return val_ < b.val_; }
    bool operator==(counting_iterator const& b) const noexcept { return val_ == b.val_; }
    bool operator!=(counting_iterator const& b) const noexcept { return !operator==(b); }

    std::strong_ordering operator<=>(counting_iterator const& b) const noexcept { return val_ <=> b.val_; }
};

I could not make it work though in parallel std::transform_reduce with iterator_category = std::random_access_iterator_tag, and that I believe is the reason for the performance drop.

UPD: In the code above commented lines made MS compiler choosing them instead of copy version alternative and that made a havoc during parallel execution if iterator was marked as random_access_category_tag.

user_145593580
Related