New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

The chunk_size_iterator violates multipass guarantee. #2866

Closed
taeguk opened this Issue Aug 28, 2017 · 1 comment

Comments

Projects
None yet
2 participants
@taeguk
Member

taeguk commented Aug 28, 2017

template <typename Iterator>
struct chunk_size_iterator
: public hpx::util::iterator_facade<
chunk_size_iterator<Iterator>,
hpx::util::tuple<Iterator, std::size_t> const,
std::forward_iterator_tag>
{
private:
typedef hpx::util::iterator_facade<
chunk_size_iterator<Iterator>,
hpx::util::tuple<Iterator, std::size_t> const,
std::forward_iterator_tag
> base_type;
public:
HPX_HOST_DEVICE
chunk_size_iterator(Iterator it, std::size_t chunk_size,
std::size_t count = 0)
: data_(it, (std::min)(chunk_size, count))
, chunk_size_(chunk_size)
, count_(count)
{}
private:
HPX_HOST_DEVICE
Iterator& iterator() { return hpx::util::get<0>(data_); }
HPX_HOST_DEVICE
Iterator iterator() const { return hpx::util::get<0>(data_); }
HPX_HOST_DEVICE
std::size_t& chunk() { return hpx::util::get<1>(data_); }
HPX_HOST_DEVICE
std::size_t chunk() const { return hpx::util::get<1>(data_); }
protected:
friend class hpx::util::iterator_core_access;
HPX_HOST_DEVICE bool equal(chunk_size_iterator const& other) const
{
return iterator() == other.iterator() &&
count_ == other.count_ &&
chunk_size_ == other.chunk_size_;
}
HPX_HOST_DEVICE typename base_type::reference dereference() const
{
return data_;
}
HPX_HOST_DEVICE void increment()
{
// prepare next value
count_ -= chunk();
iterator() = parallel::v1::detail::next(iterator(), chunk());
chunk() = (std::min)(chunk_size_, count_);
}
private:
hpx::util::tuple<Iterator, std::size_t> data_;
std::size_t chunk_size_;
std::size_t count_;
};

The chunk_size_iterator has forward iterator tag. But, it violates multipass guarantee.

// The 'iter' is chunk_size_iterator.
auto const& elem = *iter++;
...(usage of elem)...

Above code has a bug because the data which elem referenced is changed when iter is incremented.
Really, I encounted that bug, I consumed my much time for finding bug and fixing it.

http://en.cppreference.com/w/cpp/concept/ForwardIterator
As you can see from the link above, forward iterator tag must satisfy multipass guarantee.
But, the chunk_size_iterator isn't.
So, I think that the chunk_size_iterator should be classified to input iterator tag.

taeguk added a commit to taeguk/hpx that referenced this issue Aug 28, 2017

@hkaiser hkaiser added this to the 1.1.0 milestone Aug 28, 2017

@hkaiser

This comment has been minimized.

Show comment
Hide comment
@hkaiser

hkaiser Aug 28, 2017

Member

Excellent catch! please prepare a PR for this.

Member

hkaiser commented Aug 28, 2017

Excellent catch! please prepare a PR for this.

@hkaiser hkaiser closed this in #2932 Oct 12, 2017

hkaiser added a commit that referenced this issue Oct 12, 2017

Merge pull request #2932 from taeguk/tg_fix_2866
Classify chunk_size_iterator to input iterator tag. (Fix #2866)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment