From a15350157862db3631772b4ae69a9c9e3b0fab6e Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Tue, 11 Feb 2020 17:14:22 -0500 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 usable. In the general case we represent the cached result of begin() as a bare iterator. This takes advantage of the fact that value-initialized forward iterators can be compared to 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/ChangeLog | 28 ++++ 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 ++++++++ 6 files changed, 336 insertions(+), 15 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 9fe2fd2caa8..89e1f5bf952 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,31 @@ +2020-02-28 Patrick Palka + + * 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. + 2020-02-28 Jonathan Wakely * testsuite/27_io/filesystem/operations/last_write_time.cc: Fixes for diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 38d497ec88e..2f773130979 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1334,6 +1334,83 @@ namespace views } } // namespace __detail + namespace __detail + { + template + 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 + 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 + 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> _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> 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 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 +struct test_wrapper : forward_iterator_wrapper +{ + static inline int increment_count = 0; + + using forward_iterator_wrapper::forward_iterator_wrapper; + + test_wrapper() : forward_iterator_wrapper() + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + forward_iterator_wrapper::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + forward_iterator_wrapper::operator--(); + return *this; + } +}; + +void +test07() +{ + int x[] = {1,2,3,4,5}; + test_range 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::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); } +// The following tests that drop_while_view::begin caches its result. + +template typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template typename wrapper> +void +test03() +{ + auto v + = test_view{} | 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(); + test03(); } - 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 typename wrapper> +struct test_view : ranges::view_base +{ + bool begin_already_called = false; + static inline int x[] = {1,2,3,4,5}; + test_range rx{x}; + + auto + begin() + { + if (begin_already_called) + x[0] = 10; + begin_already_called = true; + return rx.begin(); + } + + auto + end() + { return rx.end(); } +}; + +template typename wrapper> +void +test05() +{ + auto v = test_view{} | 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(); + test05(); } 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 +struct test_wrapper : bidirectional_iterator_wrapper +{ + static inline int increment_count = 0; + + using bidirectional_iterator_wrapper::bidirectional_iterator_wrapper; + + test_wrapper() : bidirectional_iterator_wrapper() + { } + + test_wrapper + operator++(int) + { + auto tmp = *this; + ++*this; + return tmp; + } + + test_wrapper& + operator++() + { + ++increment_count; + bidirectional_iterator_wrapper::operator++(); + return *this; + } + + test_wrapper + operator--(int) + { + auto tmp = *this; + --*this; + return tmp; + } + + test_wrapper& + operator--() + { + bidirectional_iterator_wrapper::operator--(); + return *this; + } +}; + +void +test05() +{ + int x[] = {1,2,3,4,5}; + test_range 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::increment_count == 5 ); +} + int main() { @@ -83,4 +138,5 @@ main() test02(); test03(); test04(); + test05(); } -- 2.30.2