From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 91532 invoked by alias); 28 Aug 2017 19:13:01 -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 91505 invoked by uid 89); 28 Aug 2017 19:13:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.5 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,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy=7046 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-wm0-f53.google.com Received: from mail-wm0-f53.google.com (HELO mail-wm0-f53.google.com) (74.125.82.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 28 Aug 2017 19:12:50 +0000 Received: by mail-wm0-f53.google.com with SMTP id t201so9350721wmt.1; Mon, 28 Aug 2017 12:12:49 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:subject:to:message-id:date:user-agent :mime-version:content-language; bh=Gqo1RyC3Qu6CAXbzlv+qlOtH58PJps/W8ZkVFy0Lx90=; b=pl8YfJPW1XQfcc/RqQjUNxuElo/+E5TeK+jVvVjqxtEKHIHkW8AjF4o7hMsno819UT svrsG2q+R9rLQGLvvqimUtVd8LAQjsgfftMSxj6qJYBvVVBUFrQEjWLW3enVc8lSEhbk uu6Aphj2zRZJ+pB/u1hMb+rIueZNsImWU97//j5ATdT4JchK+9L2xEPiqMGXyZtvN4rw LRI92pHMzsSCy+3zpkLANPY9sYE4G2lzRBoQRR4uvlj4uulChkxpgdQqUZkw9MxyAX1q +wJ3Yn+ZQQABFLtl3EzPyRIZH3gIY0MqLX5uLy4FicwfWM/fCMlUcaHTVt5Vev/SKafR RFQQ== X-Gm-Message-State: AHYfb5iK3iQVmzta3nqGo2zb/b9LEnMiwUoE1wNyDt5o8PYqJhR3lC9W pB+YZi7HSt1qV4a0 X-Received: by 10.28.191.22 with SMTP id p22mr909333wmf.48.1503947567694; Mon, 28 Aug 2017 12:12:47 -0700 (PDT) Received: from [192.168.0.23] (arf62-1-82-237-250-248.fbx.proxad.net. [82.237.250.248]) by smtp.googlemail.com with ESMTPSA id o98sm1353821wrb.30.2017.08.28.12.12.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 28 Aug 2017 12:12:47 -0700 (PDT) From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: Rb_tree constructor optimization To: "libstdc++@gcc.gnu.org" , gcc-patches Message-ID: <4026eacd-cb49-e756-c855-627cd5a40206@gmail.com> Date: Mon, 28 Aug 2017 19:13:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------DF6AF348BEA0B09A0D35618E" X-IsSubscribed: yes X-SW-Source: 2017-08/txt/msg00042.txt.bz2 This is a multi-part message in MIME format. --------------DF6AF348BEA0B09A0D35618E Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 459 Hi Here is the always equal allocator optimization for associative containers. Tested under Linux x86_64. * include/bits/stl_tree.h (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New. (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New. (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): Likewise. (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters. Ok to apply ? François --------------DF6AF348BEA0B09A0D35618E Content-Type: text/x-patch; name="rb_tree.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="rb_tree.patch" Content-length: 1945 diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index c2417f1..f7d34e3 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #else _Rb_tree_impl(_Rb_tree_impl&&) = default; + _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) noexcept + : _Node_allocator(std::move(__a)), + _Base_key_compare(std::move(__x)), + _Rb_tree_header(std::move(__x)) + { } + _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) : _Node_allocator(std::move(__a)), _Base_key_compare(__comp) { } @@ -947,7 +953,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _Rb_tree(std::move(__x), _Node_allocator(__a)) { } - _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a); + private: + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::true_type) noexcept + : _M_impl(std::move(__x._M_impl), std::move(__a)) + { } + + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type); + + public: + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) + : _Rb_tree(std::move(__x), std::move(__a), + typename _Alloc_traits::is_always_equal{}) + { } #endif ~_Rb_tree() _GLIBCXX_NOEXCEPT @@ -1591,12 +1608,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: - _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) + _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type __eq) : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) { - using __eq = typename _Alloc_traits::is_always_equal; if (__x._M_root() != nullptr) - _M_move_data(__x, __eq()); + _M_move_data(__x, __eq); } template