From patchwork Wed Feb 12 04:43:01 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1236620 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-519379-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=s/Ksr/35; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=P6KtUZCp; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 48HRqB4X43z9sPJ for ; Wed, 12 Feb 2020 15:43:32 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=pWVfYeIuy/CBpLQ4 R58gZ7pdS/PvNBQXFDWUnqpAL5Px233e41Kfvt4EBRX1Y8hPVcblsKqkANk/bC93 oq4PZLxpkJdEOOcbARaVyAIZgpxID3uzSuZFL+C/B9qRsbjtrbhQ3IYERxwpuwaW NO0GHl5kqlcLZ34bmADenjg3pOA= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=qMuom9694xegBEjv75lrKn iDFBs=; b=s/Ksr/358XcL5mjwzkTd3P33pdOER3RfVqkP/3w7HhXq8hjUQsdh8/ eYTkTKhj+mSUeioMOfBukYoRC4mCOBk+kXiIyENJClqWBMdbiz3zHFWtWvzSUReC CRGBpTVzxW7flyTxEvXYsXREIbkbVu/g1Eflh1DsqrWVEpR2dKpcE= Received: (qmail 71397 invoked by alias); 12 Feb 2020 04:43:14 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 71299 invoked by uid 89); 12 Feb 2020 04:43:13 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.1 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=unavailable version=3.3.1 spammy= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-2.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 12 Feb 2020 04:43:11 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1581482589; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=uWY7BANn/0F4H5SgFagJ9KJOVHDZtFwzebY2OaKb7GE=; b=P6KtUZCp83+kBgvghX1dNEK8mn82LRRJ2TRTOpoVfoFha/8o1CPOYBMpnqE1VBLIkcKsWb XHwDz5kvtNLKvREik4GXpq4ZkgTq1XKkEotZ6WiQjUzqUCnqKZQrpvABUVJ0qcbSL3StsG L3JAaY8YWpa6e2cgCm1XtvnEDiOOrIc= Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-283-vE-1y322P0KPYvcs3jresQ-1; Tue, 11 Feb 2020 23:43:05 -0500 Received: by mail-qt1-f198.google.com with SMTP id e37so497074qtk.7 for ; Tue, 11 Feb 2020 20:43:05 -0800 (PST) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id p19sm3198925qkm.69.2020.02.11.20.43.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 11 Feb 2020 20:43:03 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, jwakely@redhat.com, Patrick Palka Subject: [PATCH] libstdc++: Memoize {drop, drop_while, filter, reverse}_view::begin Date: Tue, 11 Feb 2020 23:43:01 -0500 Message-Id: <20200212044301.3565762-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-IsSubscribed: yes 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. libstdc++-v3/ChangeLog: * include/std/ranges (__detail::_CachedPosition): New. (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 | 138 ++++++++++++++++-- .../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, 310 insertions(+), 15 deletions(-) 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 + struct _CachedPosition + { + private: + std::optional> _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>) + if (!is_constant_evaluated()) + _M_iter.emplace(__it); + } + }; + + template + 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 + requires (!copyable>) + 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> _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> 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 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(nullptr, nullptr) + { } + + 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 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 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() { @@ -94,4 +128,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..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 +struct test_wrapper : bidirectional_iterator_wrapper +{ + static inline int increment_count = 0; + + using bidirectional_iterator_wrapper::bidirectional_iterator_wrapper; + + test_wrapper() : bidirectional_iterator_wrapper(nullptr, nullptr) + { } + + 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(); }