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(); } -- 2.25.1.377.g2d2118b814