public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: Tamar Christina <tnfchris@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc(refs/vendors/ARM/heads/arm-struct-reorg-wip)] libstdc++: Memoize {drop, drop_while, filter, reverse}_view::begin Date: Fri, 17 Jul 2020 13:16:41 +0000 (GMT) [thread overview] Message-ID: <20200717131641.7A15C385DC39@sourceware.org> (raw) https://gcc.gnu.org/g:a15350157862db3631772b4ae69a9c9e3b0fab6e commit a15350157862db3631772b4ae69a9c9e3b0fab6e Author: Patrick Palka <ppalka@redhat.com> Date: Tue Feb 11 17:14:22 2020 -0500 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. Diff: --- libstdc++-v3/ChangeLog | 28 +++++ libstdc++-v3/include/std/ranges | 136 ++++++++++++++++++--- libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 57 +++++++++ .../testsuite/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 <ppalka@redhat.com> + + * 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 <jwakely@redhat.com> * 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<range _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(); }
reply other threads:[~2020-07-17 13:16 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20200717131641.7A15C385DC39@sourceware.org \ --to=tnfchris@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).