| Message ID | 20200212044301.3565762-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin | expand |
On Tue, 11 Feb 2020, Patrick Palka wrote: > This patch adds memoization for these four views so that their begin() has the > required constant time amortized complexity. > > In the general case we use std::optional to cache the result. When the > underlying range is a random_access_range then we store the cache as an offset > from the beginning of the range, which should be more compact. And when the > underlying iterator is not copyable, then we completely disable the cache. > > Using std::optional in the cache is not ideal though because it means that the > cache can't be utilized during constexpr evaluation. If instead of > std::optional we store a separate flag to denote an empty cache then we'll be > able to use the cache during constexpr evaluation at the cost of a extra byte or > so. I am not sure which design to settle on. Here's v2 of this patch which uses the new helper __detail::__maybe_empty_t and provides a more descriptive commit message. It also refines the constraints on the partial specializations of _CachedPosition. -- >8 -- Subject: [PATCH] libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin This patch adds memoization for these four views so that their begin() has the required amortized constant time complexity. In the general case we use an std::optional<iterator_t<_Range>> to cache the iterator to the first element of the view. But when the underlying range models random_access_range and when sizeof(range_difference_t<_Range>) is no larger than sizeof(iterator_t<_Range>), then we instead cache the offset to the first element. Otherwise, when the underlying range does not model forward_range, then we completely disable the cache. Additionally, in drop_view and reverse_view, we disable the cache when the underlying range models random_access_range, because in these cases recomputing begin() takes O(1) time anyway. Using std::optional to cache the iterator in the general case is not ideal though because it means that the cache can't be utilized during constexpr evaluation. If instead of std::optional we store an (iterator, bool) pair where the bool denotes whether the cache is empty, then we'll be able to use the cache during constexpr evaluation at the cost of a extra byte or so in the size of the corresponding view structure. I'm not sure which trade-off to choose. libstdc++-v3/ChangeLog: * include/std/ranges (__detail::_CachedPosition): New struct. (views::filter_view::_S_needs_cached_begin): New member variable. (views::filter_view::_M_cached_begin): New member variable. (views::filter_view::begin): Use _M_cached_begin to cache its result. (views::drop_view::_S_needs_cached_begin): New static member variable. (views::drop_view::_M_cached_begin): New member variable. (views::drop_view::begin): Use _M_cached_begin to cache its result when _S_needs_cached_begin. (views::drop_while_view::_M_cached_begin): New member variable. (views::drop_while_view::begin): Use _M_cached_begin to cache its result. (views::reverse_view::_S_needs_cached_begin): New static member variable. (views::reverse_view::_M_cached_begin): New member variable. (views::reverse_view::begin): Use _M_cached_begin to cache its result when _S_needs_cached_begin. * testsuite/std/ranges/adaptors/drop.cc: Augment test to check that drop_view::begin caches its result. * testsuite/std/ranges/adaptors/drop_while.cc: Augment test to check that drop_while_view::begin caches its result. * testsuite/std/ranges/adaptors/filter.cc: Augment test to check that filter_view::begin caches its result. * testsuite/std/ranges/adaptors/reverse.cc: Augment test to check that reverse_view::begin caches its result. --- libstdc++-v3/include/std/ranges | 136 ++++++++++++++++-- .../testsuite/std/ranges/adaptors/drop.cc | 57 ++++++++ .../std/ranges/adaptors/drop_while.cc | 38 ++++- .../testsuite/std/ranges/adaptors/filter.cc | 36 +++++ .../testsuite/std/ranges/adaptors/reverse.cc | 56 ++++++++ 5 files changed, 308 insertions(+), 15 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 440487b15cb..e7927fb0436 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1335,6 +1335,85 @@ namespace views } } // namespace __detail + namespace __detail + { + template<range _Range> + struct _CachedPosition + { + private: + std::optional<iterator_t<_Range>> _M_iter; + + public: + constexpr bool + _M_has_value() const + { return _M_iter.has_value(); } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(_M_has_value()); + return *_M_iter; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + if constexpr (copyable<iterator_t<_Range>>) + if (!is_constant_evaluated()) + _M_iter.emplace(__it); + } + }; + + template<random_access_range _Range> + requires (sizeof(range_difference_t<_Range>) + <= sizeof(iterator_t<_Range>)) + struct _CachedPosition<_Range> + { + private: + range_difference_t<_Range> _M_offset = -1; + + public: + constexpr bool + _M_has_value() const + { return _M_offset >= 0; } + + constexpr iterator_t<_Range> + _M_get(_Range& __r) const + { + __glibcxx_assert(_M_has_value()); + return ranges::begin(__r) + _M_offset; + } + + constexpr void + _M_set(_Range& __r, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + _M_offset = __it - ranges::begin(__r); + } + }; + + template<range _Range> + requires (!forward_range<_Range>) + struct _CachedPosition<_Range> + { + constexpr bool + _M_has_value() const + { return false; } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(false); + return {}; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>&) const + { } + }; + } // namespace __detail + template<input_range _Vp, indirect_unary_predicate<iterator_t<_Vp>> _Pred> requires view<_Vp> && is_object_v<_Pred> @@ -1492,6 +1571,7 @@ namespace views _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: filter_view() = default; @@ -1516,11 +1596,15 @@ namespace views constexpr _Iterator begin() { - // XXX: we need to cache the result here as per [range.filter.view] + if (_M_cached_begin._M_has_value()) + return {*this, _M_cached_begin._M_get(_M_base)}; + __glibcxx_assert(_M_pred.has_value()); - return {*this, __detail::find_if(ranges::begin(_M_base), - ranges::end(_M_base), - std::ref(*_M_pred))}; + auto __it = __detail::find_if(ranges::begin(_M_base), + ranges::end(_M_base), + std::ref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return {*this, std::move(__it)}; } constexpr auto @@ -2121,6 +2205,10 @@ namespace views _Vp _M_base = _Vp(); range_difference_t<_Vp> _M_count = 0; + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + __maybe_empty_t<_S_needs_cached_begin, __detail::_CachedPosition<_Vp>>; + public: drop_view() = default; @@ -2141,9 +2229,15 @@ namespace views begin() requires (!(__detail::__simple_view<_Vp> && random_access_range<_Vp>)) { - // XXX: we need to cache the result here as per [range.drop.view] - return ranges::next(ranges::begin(_M_base), _M_count, - ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = ranges::next(ranges::begin(_M_base), + _M_count, ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -2199,6 +2293,7 @@ namespace views private: _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: drop_while_view() = default; @@ -2223,10 +2318,14 @@ namespace views constexpr auto begin() { - // XXX: we need to cache the result here as per [range.drop.while.view] - return __detail::find_if_not(ranges::begin(_M_base), - ranges::end(_M_base), - std::cref(*_M_pred)); + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = __detail::find_if_not(ranges::begin(_M_base), + ranges::end(_M_base), + std::cref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -3072,6 +3171,10 @@ namespace views private: _Vp _M_base = _Vp(); + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + __maybe_empty_t<_S_needs_cached_begin, __detail::_CachedPosition<_Vp>>; + public: reverse_view() = default; @@ -3091,9 +3194,14 @@ namespace views constexpr reverse_iterator<iterator_t<_Vp>> begin() { - // XXX: we need to cache the result here as per [range.reverse.view] - return make_reverse_iterator(ranges::next(ranges::begin(_M_base), - ranges::end(_M_base))); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return make_reverse_iterator(_M_cached_begin._M_get(_M_base)); + + auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return make_reverse_iterator(std::move(__it)); } constexpr auto diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc index 93fbafcf5a3..2db275fb28b 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -24,6 +24,7 @@ #include <testsuite_iterators.h> using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; using __gnu_test::bidirectional_iterator_wrapper; namespace ranges = std::ranges; @@ -95,6 +96,61 @@ test06() VERIFY( ranges::empty(x | views::drop(10)) ); } +// The following tests that drop_view::begin caches its result. + +template<typename T> +struct test_wrapper : forward_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using forward_iterator_wrapper<T>::forward_iterator_wrapper; + + test_wrapper() : forward_iterator_wrapper<T>(nullptr, nullptr) + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + forward_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + forward_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test07() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::drop(3); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( test_wrapper<int>::increment_count == 7 ); +} + int main() { @@ -104,4 +160,5 @@ main() test04(); test05(); test06(); + test07(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc index be47551563d..4d8bb109fae 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -54,10 +56,44 @@ test02() static_assert(ranges::bidirectional_range<R>); } +// The following tests that drop_while_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test03() +{ + auto v + = test_view<wrapper>{} | views::drop_while([] (int i) { return i<3; }); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); +} + int main() { test01(); test02(); + test03<forward_iterator_wrapper>(); + test03<random_access_iterator_wrapper>(); } - diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc index 4e41232cd5c..58d898fb207 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -89,6 +91,38 @@ test04() (int[]){0}) ); } +// The following tests that filter_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test05() +{ + auto v = test_view<wrapper>{} | views::filter([] (int i) { return i%2 == 0; }); + VERIFY( ranges::equal(v, (int[]){2,4}) ); + VERIFY( ranges::equal(v, (int[]){2,4}) ); +} + int main() { @@ -96,4 +130,6 @@ main() test02(); test03(); test04(); + test05<forward_iterator_wrapper>(); + test05<random_access_iterator_wrapper>(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc index 0c6aceabbed..db85c57dd43 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc @@ -76,6 +76,61 @@ test04() (int[]){5,4,3,2,1}) ); } +// The following tests that reverse_view::begin caches its result. + +template<typename T> +struct test_wrapper : bidirectional_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using bidirectional_iterator_wrapper<T>::bidirectional_iterator_wrapper; + + test_wrapper() : bidirectional_iterator_wrapper<T>(nullptr, nullptr) + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + bidirectional_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + bidirectional_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test05() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::reverse; + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( test_wrapper<int>::increment_count == 5 ); +} + int main() { @@ -83,4 +138,5 @@ main() test02(); test03(); test04(); + test05(); }
On Wed, 26 Feb 2020, Patrick Palka wrote: > On Tue, 11 Feb 2020, Patrick Palka wrote: > > > This patch adds memoization for these four views so that their begin() has the > > required constant time amortized complexity. > > > > In the general case we use std::optional to cache the result. When the > > underlying range is a random_access_range then we store the cache as an offset > > from the beginning of the range, which should be more compact. And when the > > underlying iterator is not copyable, then we completely disable the cache. > > > > Using std::optional in the cache is not ideal though because it means that the > > cache can't be utilized during constexpr evaluation. If instead of > > std::optional we store a separate flag to denote an empty cache then we'll be > > able to use the cache during constexpr evaluation at the cost of a extra byte or > > so. I am not sure which design to settle on. > > Here's v2 of this patch which uses the new helper > __detail::__maybe_empty_t and provides a more descriptive commit > message. It also refines the constraints on the partial specializations > of _CachedPosition. > > -- >8 -- > Here's v3 of this patch which takes advantage of the fact that value-initialized forward iterators can be compared to. This means we can cache the bare iterator instead of having to use std::optional or needing an external flag denoting the empty state of the cache, which is both optimal space-wise and constexpr safe! -- >8 -- Subject: [PATCH] libstdc++: Memoize {drop,drop_while,filter,reverse}_view::begin This patch adds memoization to these four views so that their begin() has the required amortized constant time complexity. The cache is enabled only for forward_ranges and above because we need the underlying iterator to be copyable and multi-pass in order for the cache to be useful. In the general case we store the cached result of begin() as a bare iterator by taking advantage of the fact that value-initialized forward iterators can be compared with as per N3644, so we can use a value-initialized iterator to denote the "empty" state of the cache. As a special case, when the underlying range models random_access_range and when it's profitable size-wise, then we cache the offset of the iterator from the beginning of the range instead of caching the iterator itself. Additionally, in drop_view and reverse_view we disable the cache when the underlying range models random_access_range, because in these cases recomputing begin() takes O(1) time anyway. libstdc++-v3/ChangeLog: * include/std/ranges (__detail::_CachedPosition): New struct. (views::filter_view::_S_needs_cached_begin): New member variable. (views::filter_view::_M_cached_begin): New member variable. (views::filter_view::begin): Use _M_cached_begin to cache its result. (views::drop_view::_S_needs_cached_begin): New static member variable. (views::drop_view::_M_cached_begin): New member variable. (views::drop_view::begin): Use _M_cached_begin to cache its result when _S_needs_cached_begin. (views::drop_while_view::_M_cached_begin): New member variable. (views::drop_while_view::begin): Use _M_cached_begin to cache its result. (views::reverse_view::_S_needs_cached_begin): New static member variable. (views::reverse_view::_M_cached_begin): New member variable. (views::reverse_view::begin): Use _M_cached_begin to cache its result when _S_needs_cached_begin. * testsuite/std/ranges/adaptors/drop.cc: Augment test to check that drop_view::begin caches its result. * testsuite/std/ranges/adaptors/drop_while.cc: Augment test to check that drop_while_view::begin caches its result. * testsuite/std/ranges/adaptors/filter.cc: Augment test to check that filter_view::begin caches its result. * testsuite/std/ranges/adaptors/reverse.cc: Augment test to check that reverse_view::begin caches its result. --- libstdc++-v3/include/std/ranges | 136 ++++++++++++++++-- .../testsuite/std/ranges/adaptors/drop.cc | 57 ++++++++ .../std/ranges/adaptors/drop_while.cc | 38 ++++- .../testsuite/std/ranges/adaptors/filter.cc | 36 +++++ .../testsuite/std/ranges/adaptors/reverse.cc | 56 ++++++++ 5 files changed, 308 insertions(+), 15 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 38d497ec88e..22a494ae495 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1334,6 +1334,83 @@ namespace views } } // namespace __detail + namespace __detail + { + template<typename _Range> + struct _CachedPosition + { + constexpr bool + _M_has_value() const + { return false; } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(false); + return {}; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>&) const + { } + }; + + template<forward_range _Range> + struct _CachedPosition<_Range> + { + private: + iterator_t<_Range> _M_iter{}; + + public: + constexpr bool + _M_has_value() const + { return _M_iter != iterator_t<_Range>{}; } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(_M_has_value()); + return _M_iter; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + _M_iter = __it; + } + }; + + template<random_access_range _Range> + requires (sizeof(range_difference_t<_Range>) + <= sizeof(iterator_t<_Range>)) + struct _CachedPosition<_Range> + { + private: + range_difference_t<_Range> _M_offset = -1; + + public: + constexpr bool + _M_has_value() const + { return _M_offset >= 0; } + + constexpr iterator_t<_Range> + _M_get(_Range& __r) const + { + __glibcxx_assert(_M_has_value()); + return ranges::begin(__r) + _M_offset; + } + + constexpr void + _M_set(_Range& __r, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + _M_offset = __it - ranges::begin(__r); + } + }; + + } // namespace __detail + template<input_range _Vp, indirect_unary_predicate<iterator_t<_Vp>> _Pred> requires view<_Vp> && is_object_v<_Pred> @@ -1491,6 +1568,7 @@ namespace views _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: filter_view() = default; @@ -1515,11 +1593,15 @@ namespace views constexpr _Iterator begin() { - // XXX: we need to cache the result here as per [range.filter.view] + if (_M_cached_begin._M_has_value()) + return {*this, _M_cached_begin._M_get(_M_base)}; + __glibcxx_assert(_M_pred.has_value()); - return {*this, __detail::find_if(ranges::begin(_M_base), - ranges::end(_M_base), - std::ref(*_M_pred))}; + auto __it = __detail::find_if(ranges::begin(_M_base), + ranges::end(_M_base), + std::ref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return {*this, std::move(__it)}; } constexpr auto @@ -2127,6 +2209,11 @@ namespace views _Vp _M_base = _Vp(); range_difference_t<_Vp> _M_count = 0; + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + __detail::__maybe_empty_t<_S_needs_cached_begin, + __detail::_CachedPosition<_Vp>> _M_cached_begin; + public: drop_view() = default; @@ -2147,9 +2234,15 @@ namespace views begin() requires (!(__detail::__simple_view<_Vp> && random_access_range<_Vp>)) { - // XXX: we need to cache the result here as per [range.drop.view] - return ranges::next(ranges::begin(_M_base), _M_count, - ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = ranges::next(ranges::begin(_M_base), + _M_count, ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -2205,6 +2298,7 @@ namespace views private: _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: drop_while_view() = default; @@ -2229,10 +2323,14 @@ namespace views constexpr auto begin() { - // XXX: we need to cache the result here as per [range.drop.while.view] - return __detail::find_if_not(ranges::begin(_M_base), - ranges::end(_M_base), - std::cref(*_M_pred)); + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = __detail::find_if_not(ranges::begin(_M_base), + ranges::end(_M_base), + std::cref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -3079,6 +3177,11 @@ namespace views private: _Vp _M_base = _Vp(); + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + __detail::__maybe_empty_t<_S_needs_cached_begin, + __detail::_CachedPosition<_Vp>> _M_cached_begin; + public: reverse_view() = default; @@ -3098,9 +3201,14 @@ namespace views constexpr reverse_iterator<iterator_t<_Vp>> begin() { - // XXX: we need to cache the result here as per [range.reverse.view] - return make_reverse_iterator(ranges::next(ranges::begin(_M_base), - ranges::end(_M_base))); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return make_reverse_iterator(_M_cached_begin._M_get(_M_base)); + + auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return make_reverse_iterator(std::move(__it)); } constexpr auto diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc index 93fbafcf5a3..3c82caea772 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -24,6 +24,7 @@ #include <testsuite_iterators.h> using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; using __gnu_test::bidirectional_iterator_wrapper; namespace ranges = std::ranges; @@ -95,6 +96,61 @@ test06() VERIFY( ranges::empty(x | views::drop(10)) ); } +// The following tests that drop_view::begin caches its result. + +template<typename T> +struct test_wrapper : forward_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using forward_iterator_wrapper<T>::forward_iterator_wrapper; + + test_wrapper() : forward_iterator_wrapper<T>() + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + forward_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + forward_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test07() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::drop(3); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( test_wrapper<int>::increment_count == 7 ); +} + int main() { @@ -104,4 +160,5 @@ main() test04(); test05(); test06(); + test07(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc index be47551563d..4d8bb109fae 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -54,10 +56,44 @@ test02() static_assert(ranges::bidirectional_range<R>); } +// The following tests that drop_while_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test03() +{ + auto v + = test_view<wrapper>{} | views::drop_while([] (int i) { return i<3; }); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); +} + int main() { test01(); test02(); + test03<forward_iterator_wrapper>(); + test03<random_access_iterator_wrapper>(); } - diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc index 4e41232cd5c..58d898fb207 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -89,6 +91,38 @@ test04() (int[]){0}) ); } +// The following tests that filter_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test05() +{ + auto v = test_view<wrapper>{} | views::filter([] (int i) { return i%2 == 0; }); + VERIFY( ranges::equal(v, (int[]){2,4}) ); + VERIFY( ranges::equal(v, (int[]){2,4}) ); +} + int main() { @@ -96,4 +130,6 @@ main() test02(); test03(); test04(); + test05<forward_iterator_wrapper>(); + test05<random_access_iterator_wrapper>(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc index 0c6aceabbed..ceaaf3e9e00 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc @@ -76,6 +76,61 @@ test04() (int[]){5,4,3,2,1}) ); } +// The following tests that reverse_view::begin caches its result. + +template<typename T> +struct test_wrapper : bidirectional_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using bidirectional_iterator_wrapper<T>::bidirectional_iterator_wrapper; + + test_wrapper() : bidirectional_iterator_wrapper<T>() + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + bidirectional_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + bidirectional_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test05() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::reverse; + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( test_wrapper<int>::increment_count == 5 ); +} + int main() { @@ -83,4 +138,5 @@ main() test02(); test03(); test04(); + test05(); }
On 27/02/20 14:26 -0500, Patrick Palka wrote: >On Wed, 26 Feb 2020, Patrick Palka wrote: > >> On Tue, 11 Feb 2020, Patrick Palka wrote: >> >> > This patch adds memoization for these four views so that their begin() has the >> > required constant time amortized complexity. >> > >> > In the general case we use std::optional to cache the result. When the >> > underlying range is a random_access_range then we store the cache as an offset >> > from the beginning of the range, which should be more compact. And when the >> > underlying iterator is not copyable, then we completely disable the cache. >> > >> > Using std::optional in the cache is not ideal though because it means that the >> > cache can't be utilized during constexpr evaluation. If instead of >> > std::optional we store a separate flag to denote an empty cache then we'll be >> > able to use the cache during constexpr evaluation at the cost of a extra byte or >> > so. I am not sure which design to settle on. >> >> Here's v2 of this patch which uses the new helper >> __detail::__maybe_empty_t and provides a more descriptive commit >> message. It also refines the constraints on the partial specializations >> of _CachedPosition. >> >> -- >8 -- >> > >Here's v3 of this patch which takes advantage of the fact that >value-initialized forward iterators can be compared to. This means we >can cache the bare iterator instead of having to use std::optional or >needing an external flag denoting the empty state of the cache, which is >both optimal space-wise and constexpr safe! Nice. OK for master, thanks.
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index ef613175b7c..485a073ad3a 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1302,6 +1302,83 @@ namespace views } } // namespace __detail + namespace __detail + { + template<range _Range> + struct _CachedPosition + { + private: + std::optional<iterator_t<_Range>> _M_iter; + + public: + constexpr bool + _M_has_value() const + { return _M_iter.has_value(); } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(_M_has_value()); + return *_M_iter; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + if constexpr (copyable<iterator_t<_Range>>) + if (!is_constant_evaluated()) + _M_iter.emplace(__it); + } + }; + + template<random_access_range _Range> + struct _CachedPosition<_Range> + { + private: + range_difference_t<_Range> _M_offset = -1; + + public: + constexpr bool + _M_has_value() const + { return _M_offset >= 0; } + + constexpr iterator_t<_Range> + _M_get(_Range& __r) const + { + __glibcxx_assert(_M_has_value()); + return ranges::begin(__r) + _M_offset; + } + + constexpr void + _M_set(_Range& __r, const iterator_t<_Range>& __it) + { + __glibcxx_assert(!_M_has_value()); + _M_offset = __it - ranges::begin(__r); + } + }; + + template<range _Range> + requires (!copyable<iterator_t<_Range>>) + struct _CachedPosition<_Range> + { + constexpr bool + _M_has_value() const + { return false; } + + constexpr iterator_t<_Range> + _M_get(const _Range&) const + { + __glibcxx_assert(false); + return {}; + } + + constexpr void + _M_set(const _Range&, const iterator_t<_Range>&) const + { } + }; + } // namespace __detail + template<input_range _Vp, indirect_unary_predicate<iterator_t<_Vp>> _Pred> requires view<_Vp> && is_object_v<_Pred> @@ -1457,6 +1534,7 @@ namespace views _Vp _M_base = _Vp(); __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: filter_view() = default; @@ -1488,11 +1566,15 @@ namespace views constexpr _Iterator begin() { - // XXX: we need to cache the result here as per [range.filter.view] + if (_M_cached_begin._M_has_value()) + return {*this, _M_cached_begin._M_get(_M_base)}; + __glibcxx_assert(_M_pred.has_value()); - return {*this, __detail::find_if(ranges::begin(_M_base), - ranges::end(_M_base), - std::ref(*_M_pred))}; + auto __it = __detail::find_if(ranges::begin(_M_base), + ranges::end(_M_base), + std::ref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return {*this, std::move(__it)}; } constexpr auto @@ -2104,6 +2186,12 @@ namespace views _Vp _M_base; range_difference_t<_Vp> _M_count; + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + conditional_t<_S_needs_cached_begin, + __detail::_CachedPosition<_Vp>, + __detail::_Empty> _M_cached_begin; + public: drop_view() = default; @@ -2124,9 +2212,15 @@ namespace views begin() requires (!(__detail::__simple_view<_Vp> && random_access_range<_Vp>)) { - // XXX: we need to cache the result here as per [range.drop.view] - return ranges::next(ranges::begin(_M_base), _M_count, - ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = ranges::next(ranges::begin(_M_base), + _M_count, ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -2182,6 +2276,7 @@ namespace views private: _Vp _M_base; __detail::__box<_Pred> _M_pred; + [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; public: drop_while_view() = default; @@ -2206,10 +2301,14 @@ namespace views constexpr auto begin() { - // XXX: we need to cache the result here as per [range.drop.while.view] - return __detail::find_if_not(ranges::begin(_M_base), - ranges::end(_M_base), - std::cref(*_M_pred)); + if (_M_cached_begin._M_has_value()) + return _M_cached_begin._M_get(_M_base); + + auto __it = __detail::find_if_not(ranges::begin(_M_base), + ranges::end(_M_base), + std::cref(*_M_pred)); + _M_cached_begin._M_set(_M_base, __it); + return __it; } constexpr auto @@ -3071,6 +3170,12 @@ namespace views private: _Vp _M_base = _Vp(); + static constexpr bool _S_needs_cached_begin = !random_access_range<_Vp>; + [[no_unique_address]] + conditional_t<_S_needs_cached_begin, + __detail::_CachedPosition<_Vp>, + __detail::_Empty> _M_cached_begin; + public: reverse_view() = default; @@ -3099,9 +3204,14 @@ namespace views constexpr reverse_iterator<iterator_t<_Vp>> begin() { - // XXX: we need to cache the result here as per [range.reverse.view] - return make_reverse_iterator(ranges::next(ranges::begin(_M_base), - ranges::end(_M_base))); + if constexpr (_S_needs_cached_begin) + if (_M_cached_begin._M_has_value()) + return make_reverse_iterator(_M_cached_begin._M_get(_M_base)); + + auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base)); + if constexpr (_S_needs_cached_begin) + _M_cached_begin._M_set(_M_base, __it); + return make_reverse_iterator(std::move(__it)); } constexpr auto diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc index 93fbafcf5a3..2db275fb28b 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc @@ -24,6 +24,7 @@ #include <testsuite_iterators.h> using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; using __gnu_test::bidirectional_iterator_wrapper; namespace ranges = std::ranges; @@ -95,6 +96,61 @@ test06() VERIFY( ranges::empty(x | views::drop(10)) ); } +// The following tests that drop_view::begin caches its result. + +template<typename T> +struct test_wrapper : forward_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using forward_iterator_wrapper<T>::forward_iterator_wrapper; + + test_wrapper() : forward_iterator_wrapper<T>(nullptr, nullptr) + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + forward_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + forward_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test07() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::drop(3); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( ranges::equal(v, (int[]){4,5}) ); + VERIFY( test_wrapper<int>::increment_count == 7 ); +} + int main() { @@ -104,4 +160,5 @@ main() test04(); test05(); test06(); + test07(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc index be47551563d..4d8bb109fae 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop_while.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -54,10 +56,44 @@ test02() static_assert(ranges::bidirectional_range<R>); } +// The following tests that drop_while_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test03() +{ + auto v + = test_view<wrapper>{} | views::drop_while([] (int i) { return i<3; }); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); + VERIFY( ranges::equal(v, (int[]){3,4,5}) ); +} + int main() { test01(); test02(); + test03<forward_iterator_wrapper>(); + test03<random_access_iterator_wrapper>(); } - diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc index 83d52967a0f..834d10f7f91 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/filter.cc @@ -25,6 +25,8 @@ using __gnu_test::test_range; using __gnu_test::bidirectional_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; namespace ranges = std::ranges; namespace views = std::ranges::views; @@ -87,6 +89,38 @@ test04() (int[]){0}) ); } +// The following tests that filter_view::begin caches its result. + +template<template<typename> typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range<int, wrapper> rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template<template<typename> typename wrapper> +void +test05() +{ + auto v = test_view<wrapper>{} | views::filter([] (int i) { return i%2 == 0; }); + VERIFY( ranges::equal(v, (int[]){2,4}) ); + VERIFY( ranges::equal(v, (int[]){2,4}) ); +} + int main() { @@ -94,4 +128,6 @@ main() test02(); test03(); test04(); + test05<forward_iterator_wrapper>(); + test05<random_access_iterator_wrapper>(); } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc index 0c6aceabbed..db85c57dd43 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/reverse.cc @@ -76,6 +76,61 @@ test04() (int[]){5,4,3,2,1}) ); } +// The following tests that reverse_view::begin caches its result. + +template<typename T> +struct test_wrapper : bidirectional_iterator_wrapper<T> +{ + static inline int increment_count = 0; + + using bidirectional_iterator_wrapper<T>::bidirectional_iterator_wrapper; + + test_wrapper() : bidirectional_iterator_wrapper<T>(nullptr, nullptr) + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + bidirectional_iterator_wrapper<T>::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + bidirectional_iterator_wrapper<T>::operator--(); + return *this; + } +}; + +void +test05() +{ + int x[] = {1,2,3,4,5}; + test_range<int, test_wrapper> rx(x); + auto v = rx | views::reverse; + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( ranges::equal(v, (int[]){5,4,3,2,1}) ); + VERIFY( test_wrapper<int>::increment_count == 5 ); +} + int main() { @@ -83,4 +138,5 @@ main() test02(); test03(); test04(); + test05(); }