From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 60124 invoked by alias); 20 May 2019 05:39:50 -0000 Mailing-List: contact libstdc++-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libstdc++-owner@gcc.gnu.org Received: (qmail 60109 invoked by uid 89); 20 May 2019 05:39:50 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.7 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=remain, UD:deque.tcc, dequetcc, UD:tcc X-HELO: mail-wr1-f48.google.com Received: from mail-wr1-f48.google.com (HELO mail-wr1-f48.google.com) (209.85.221.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 20 May 2019 05:39:48 +0000 Received: by mail-wr1-f48.google.com with SMTP id g12so12720331wro.8; Sun, 19 May 2019 22:39:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=RjS/GiXCVnoG5wjc522be+dmaz1HynkhhPaKZy70YEw=; b=shqPUz8TFiaY0+rc3FoRhC8nzzp3hj1UiGr7vQJCvVoDa0ANwcvFB63C8lPYWf7zZE mbI/kLZHpm2dNUWyWgVbKKwQ4tFC+HUGZUUFFo9UY2Ib12aU1YJxv7o2Y8Uc7EK+qu1Q nhKanGfC3M846JOAbePr7vv9nOzr9h/vZrd57kgagYrBtNzCr1sRA87QIMpXkcJoG1IB 1MBklr07pf153u4yOv3I1CARSujShEPPRHFGF14xs3stlMtIsPho67CytTKUixAGzXJr 2JoZ1ZK8mp8Bw/vjQ19cashP7icOTml72YOBXSYA0S50+s6/BybSXzTUaFv02RIO57/W 3szw== Return-Path: Received: from [192.168.42.161] ([92.184.105.122]) by smtp.googlemail.com with ESMTPSA id a11sm16335757wrx.31.2019.05.19.22.39.44 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 19 May 2019 22:39:45 -0700 (PDT) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Deque rotate on current node Message-ID: <2a947ca5-56ea-cd46-f4bb-c094fa980745@gmail.com> Date: Mon, 20 May 2019 05:39:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------234C2386F1377C7888E29754" X-IsSubscribed: yes X-SW-Source: 2019-05/txt/msg00166.txt.bz2 This is a multi-part message in MIME format. --------------234C2386F1377C7888E29754 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 1169 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.     * 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 --------------234C2386F1377C7888E29754 Content-Type: text/x-patch; name="deque_rotate.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="deque_rotate.patch" Content-length: 1422 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()")); --------------234C2386F1377C7888E29754--