From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x343.google.com (mail-wm1-x343.google.com [IPv6:2a00:1450:4864:20::343]) by sourceware.org (Postfix) with ESMTPS id C14503858D37; Tue, 30 Jun 2020 20:33:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org C14503858D37 Received: by mail-wm1-x343.google.com with SMTP id q15so20045452wmj.2; Tue, 30 Jun 2020 13:33:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:from:to:cc:references:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=IJ2/7eOW1bcj3F48QfNhLuSgkKPdL2oin2EWlRHF8fg=; b=Uuv+eFwaD72unZ8/VdwyDqIFEIYVDNVsHs4kIvOPrwaPqgA2qU5d9FN1iD4sJiCEJA Pp7yrSDd941s0d/845OOjaBbw41loHzKZEs3KcferX3hTxqokjIccZx6rsWzPWNB4sdu jaM50BoKaNPbHIRm13C4LdgWA4MVu8hE96tm9XCdZ+m3Q/Y28jbiFqtKlRkDTREGmGJ3 FNRS//YrufdFMBdZqiFMz5BpodPfacDZJ/Nz1q+NB+h+QRb+8kohQH9wMytNrmn2f6Be TflZ/PgHdWerLxkIPYhVlRhOFmPZLDYKCLPBkkWmFKHB0j9pDajVytzfAD9Z6cP5AxJJ wyYw== X-Gm-Message-State: AOAM532urgbOGai+hkHZL3+Yx759RrEBb5U6hy0AjvhOST8mK187Dxr7 iFU0kLDAGZvX4z41Xz+Z+f9SoS6xclY= X-Google-Smtp-Source: ABdhPJzsXNkw1XB+UpXQZFXS9zHJ0MVBV7hjWdzAJsQNyGBGjErOReDLA7R7MvABstbYudH9nvAq5Q== X-Received: by 2002:a1c:f00a:: with SMTP id a10mr24006815wmb.61.1593549230088; Tue, 30 Jun 2020 13:33:50 -0700 (PDT) Received: from ?IPv6:2a01:e0a:1dc:b1c0:60f2:d84b:335b:f016? ([2a01:e0a:1dc:b1c0:60f2:d84b:335b:f016]) by smtp.googlemail.com with ESMTPSA id d81sm31419828wmc.0.2020.06.30.13.33.48 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 30 Jun 2020 13:33:48 -0700 (PDT) Subject: Re: Deque rotate on current node From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: Jonathan Wakely Cc: "libstdc++@gcc.gnu.org" , gcc-patches References: <2a947ca5-56ea-cd46-f4bb-c094fa980745@gmail.com> <20200117100152.GV60955@redhat.com> <4e1d5fbf-9c10-8cfa-f71f-66d8936a6ef5@gmail.com> Message-ID: <72fc2aae-1c9b-f862-7370-3d94c87fa0e1@gmail.com> Date: Tue, 30 Jun 2020 22:33:47 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.8.0 MIME-Version: 1.0 In-Reply-To: <4e1d5fbf-9c10-8cfa-f71f-66d8936a6ef5@gmail.com> Content-Type: multipart/mixed; boundary="------------4C3C1E5B7BD30BFFBD824654" Content-Language: fr X-Spam-Status: No, score=-8.7 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 30 Jun 2020 20:33:54 -0000 This is a multi-part message in MIME format. --------------4C3C1E5B7BD30BFFBD824654 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Hi Any feedback regarding this patch ? François On 17/01/20 6:27 pm, François Dumont wrote: > On 1/17/20 11:01 AM, Jonathan Wakely wrote: >> On 20/05/19 07:39 +0200, François Dumont wrote: >>> Hi >>> >>>   std::deque is supposed to be like a double-queue that you can >>> attack from front and back. But currrently its implementation makes >>> it behave differently when starting from a fresh deque. If push_back >>> then all goes well, it is copy/move to the current internal 'node'. >>> If push_front then a new 'node' is created and on next pop_back the >>> initial node will be deallocated without having ever be used. >>> >>>   This patch changes this behavior. As long as deque is empty we can >>> play with its state to make it push_back- or push_front-ready. It >>> will also benefit to the usage of deque in the std::stack. >>> >>>   More generally it could really improve scenario in which deque is >>> used as queue of elements exchanged between different threads. As >>> you need to make sure that consumers are faster than producers then >>> your deque should remain empty most of the time and so this proposed >>> patch should avoid nodes to be allocated/deallocated all the time. >> >> This benefits the case where you always push at the same end. But with >> your patch if I do push_front then push_back, >> we still allocate a second node even though the first one is nearly >> empty. >> >> Would it be better to point into the middle of the node, not right at >> the end or right at the beginning? > > That's purely empirical but I tend to think that when you need > push_back only you go with std::vector or std::deque, when you need > push_front only you go with std::deque and when you need both you go > with std::list. At least std::stack and std::queue are following this > axiom per default. > > The tradeoff you are describing is not worst than current situation > where you will eventually deallocate a node that you haven't used at all. > > Are you proposing to just init in the middle or also to always reset > when empty in the middle ? If we also reset in the middle those doing > always push_back or push_front will live with half a node unreachable. > > We could just init in the middle however. It would be a different > patch as this one is focus on just recycling the last empty node. > > I consider adding a flag keeping the info that the deque is > push_back|push_front|both-oriented updated based on its usage but I > doubt it would worth it. Moreover it would introduce an abi breakage. > >> >>>     * include/bits/deque.tcc (deque<>::_M_push_back_aux): >>>     Rotate on current node if deque is empty. >>>     (deue<>::_M_push_front_aux): Likewise. >>> >>> Tested under Linux x86_64, ok to commit ? >>> >>> François >>> >> >>> diff --git a/libstdc++-v3/include/bits/deque.tcc >>> b/libstdc++-v3/include/bits/deque.tcc >>> index 2053afe1d69..245e3e712d8 100644 >>> --- a/libstdc++-v3/include/bits/deque.tcc >>> +++ b/libstdc++-v3/include/bits/deque.tcc >>> @@ -507,6 +507,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER >>>       _M_push_back_aux(const value_type& __t) >>> #endif >>>       { >>> +    if (empty()) >>> +      { >>> +        // Move iterators to point to the current node begin. >>> +        this->_M_impl._M_start._M_cur = >>> this->_M_impl._M_start._M_first; >>> +        this->_M_impl._M_finish._M_cur = >>> this->_M_impl._M_finish._M_first; >>> +#if __cplusplus >= 201103L >>> +        emplace_back(std::forward<_Args>(__args)...); >>> +#else >>> +        push_back(__t); >>> +#endif >>> +        return; >>> +      } >>> + >>>     if (size() == max_size()) >>>       __throw_length_error( >>>           __N("cannot create std::deque larger than max_size()")); >>> @@ -546,6 +559,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER >>>       _M_push_front_aux(const value_type& __t) >>> #endif >>>       { >>> +    if (empty()) >>> +      { >>> +        // Move iterators to point to the current node end. >>> +        this->_M_impl._M_finish._M_cur = >>> this->_M_impl._M_finish._M_last - 1; >>> +        this->_M_impl._M_start._M_cur = >>> this->_M_impl._M_start._M_last - 1; >>> +#if __cplusplus >= 201103L >>> +        emplace_front(std::forward<_Args>(__args)...); >>> +#else >>> +        push_front(__t); >>> +#endif >>> +        return; >>> +      } >>> + >>>     if (size() == max_size()) >>>       __throw_length_error( >>>           __N("cannot create std::deque larger than max_size()")); >> > --------------4C3C1E5B7BD30BFFBD824654 Content-Type: text/x-patch; charset=UTF-8; name="deque_reuse_node.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="deque_reuse_node.patch" diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 7d1ec86456a..e0fb7f07bc4 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -486,6 +486,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_push_back_aux(const value_type& __t) #endif { + if (empty()) + { + // Move iterators to point to the current node begin. + this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; + this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; +#if __cplusplus >= 201103L + emplace_back(std::forward<_Args>(__args)...); +#else + push_back(__t); +#endif + return; + } + if (size() == max_size()) __throw_length_error( __N("cannot create std::deque larger than max_size()")); @@ -525,6 +538,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_push_front_aux(const value_type& __t) #endif { + if (empty()) + { + // Move iterators to point to the current node end. + this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; + this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; +#if __cplusplus >= 201103L + emplace_front(std::forward<_Args>(__args)...); +#else + push_front(__t); +#endif + return; + } + if (size() == max_size()) __throw_length_error( __N("cannot create std::deque larger than max_size()")); --------------4C3C1E5B7BD30BFFBD824654--