From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com [IPv6:2a00:1450:4864:20::529]) by sourceware.org (Postfix) with ESMTPS id A9B92383B40F; Thu, 27 May 2021 05:04:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org A9B92383B40F Received: by mail-ed1-x529.google.com with SMTP id s6so4161514edu.10; Wed, 26 May 2021 22:04:29 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=2enBeqWe469tB4hugZNEQENVR7lqrEqZnxXzkcqCoWg=; b=gs70kZRYkS5Bf070rPvJbWMLdcTLGI3o11UVCuvzKsr2ksJh4Z4e0GQDZ6hu9i/dG+ ndj7N2LZjQMs9d2vckLok8C7WgOECFzNbNDBleZnuqfBRcEYtRVo0sS4cEckDm1LxRV7 8cFmMCCsbDYgxI//ar5xHBDBzzWimx3r65YEqHKKfvxa+o5cCxqVNveoYq4EY8/jwLDs 9xApRcWvxcxUt4A7lGLuxM2cfnRZrp5Oey+0GPxoTzC+u0FniQWyT2yLFAnSXF3RMOB1 /DQqZT5X8q22TsOooirpmx+leictThnVqczrFf4qPnp0QJRGPOI0gFHLudN0m0t4rYJL ltNA== X-Gm-Message-State: AOAM530zbtYLD2Dr9Wf7wiUB0ydRa6EfEwmtofFdFa4StvQaYYG26Xl+ mWwMBz4qqWuBgWYYYYBKJOialzKX/jI= X-Google-Smtp-Source: ABdhPJz3K/DyAYa5xk3nr4LkHcwrY2sT6xC16JLXGqptpnMusePd5NdqPK9IvM6hdOVxRnR0PyOcPg== X-Received: by 2002:aa7:ca0d:: with SMTP id y13mr2091373eds.307.1622091868501; Wed, 26 May 2021 22:04:28 -0700 (PDT) Received: from [10.25.4.78] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id ck28sm425435edb.63.2021.05.26.22.04.26 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 May 2021 22:04:27 -0700 (PDT) To: "libstdc++@gcc.gnu.org" Cc: gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH] Simplify branching in algos Message-ID: <3efeb7a1-ac7f-17e7-6fd0-62b363be34d0@gmail.com> Date: Thu, 27 May 2021 07:04:25 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------CAA1B1BA9ABC6E08C72E7D68" Content-Language: fr X-Spam-Status: No, score=-9.8 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_BARRACUDACENTRAL, 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: Thu, 27 May 2021 05:04:31 -0000 This is a multi-part message in MIME format. --------------CAA1B1BA9ABC6E08C72E7D68 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Following latest fixes in std::inplace_merge and std::stable_sort you propose Jonathan to enhance branching in the first. Here is a proposal based on yours to do so in both algos.     libstdc++: Enhance branching in std::inplace_merge and std::stable_sort     libstdc++-v3/ChangeLog:             * include/bits/stl_algo.h             (__merge_adaptive): Adapt to merge only when buffer is large enough..             (__merge_adaptive_resize): New, adapt merge when buffer is too small.             (__inplace_merge): Adapt, use latter.             (__stable_sort_adaptive): Adapt to sort only when buffer is large enough.             (__stable_sort_adaptive_resize): New, adapt sort when buffer is too small.             (__stable_sort): Adapt, use latter. Tested under Linux x64. Ok to commit ? François --------------CAA1B1BA9ABC6E08C72E7D68 Content-Type: text/x-patch; charset=UTF-8; name="algo.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="algo.patch" diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index a18bb000d0c..02ae40c1fb4 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -2401,28 +2401,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } /// This is a helper function for the merge routines. - template void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, - _Pointer __buffer, _Distance __buffer_size, - _Compare __comp) + _Pointer __buffer, _Compare __comp) { - if (__len1 <= __len2 && __len1 <= __buffer_size) + if (__len1 <= __len2) { _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, __first, __comp); } - else if (__len2 <= __buffer_size) + else { _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); std::__move_merge_adaptive_backward(__first, __middle, __buffer, __buffer_end, __last, __comp); } + } + + template + void + __merge_adaptive_resize(_BidirectionalIterator __first, + _BidirectionalIterator __middle, + _BidirectionalIterator __last, + _Distance __len1, _Distance __len2, + _Pointer __buffer, _Distance __buffer_size, + _Compare __comp) + { + if (__len1 <= __buffer_size || __len2 <= __buffer_size) + std::__merge_adaptive(__first, __middle, __last, + __len1, __len2, __buffer, __comp); else { _BidirectionalIterator __first_cut = __first; @@ -2450,14 +2464,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _BidirectionalIterator __new_middle = std::__rotate_adaptive(__first_cut, __middle, __second_cut, - __len1 - __len11, __len22, __buffer, - __buffer_size); - std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, - __len22, __buffer, __buffer_size, __comp); - std::__merge_adaptive(__new_middle, __second_cut, __last, - __len1 - __len11, - __len2 - __len22, __buffer, - __buffer_size, __comp); + __len1 - __len11, __len22, + __buffer, __buffer_size); + std::__merge_adaptive_resize(__first, __first_cut, __new_middle, + __len11, __len22, + __buffer, __buffer_size, __comp); + std::__merge_adaptive_resize(__new_middle, __second_cut, __last, + __len1 - __len11, __len2 - __len22, + __buffer, __buffer_size, __comp); } } @@ -2535,11 +2549,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // [first,middle) and [middle,last). _TmpBuf __buf(__first, std::min(__len1, __len2)); - if (__buf.begin() == 0) + if (__builtin_expect(__buf.size() == __buf.requested_size(), true)) + std::__merge_adaptive + (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp); + else if (__builtin_expect(__buf.begin() == 0, false)) std::__merge_without_buffer (__first, __middle, __last, __len1, __len2, __comp); else - std::__merge_adaptive + std::__merge_adaptive_resize (__first, __middle, __last, __len1, __len2, __buf.begin(), _DistanceType(__buf.size()), __comp); } @@ -2720,34 +2737,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } - template + template void __stable_sort_adaptive(_RandomAccessIterator __first, + _RandomAccessIterator __middle, _RandomAccessIterator __last, - _Pointer __buffer, _Distance __buffer_size, - _Compare __comp) + _Pointer __buffer, _Compare __comp) + { + std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); + std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); + + std::__merge_adaptive(__first, __middle, __last, + __middle - __first, __last - __middle, + __buffer, __comp); + } + + template + void + __stable_sort_adaptive_resize(_RandomAccessIterator __first, + _RandomAccessIterator __last, + _Pointer __buffer, _Distance __buffer_size, + _Compare __comp) { const _Distance __len = (__last - __first + 1) / 2; const _RandomAccessIterator __middle = __first + __len; if (__len > __buffer_size) { - std::__stable_sort_adaptive(__first, __middle, __buffer, - __buffer_size, __comp); - std::__stable_sort_adaptive(__middle, __last, __buffer, - __buffer_size, __comp); + std::__stable_sort_adaptive_resize(__first, __middle, __buffer, + __buffer_size, __comp); + std::__stable_sort_adaptive_resize(__middle, __last, __buffer, + __buffer_size, __comp); + std::__merge_adaptive_resize(__first, __middle, __last, + _Distance(__middle - __first), + _Distance(__last - __middle), + __buffer, __buffer_size, + __comp); } else - { - std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); - std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); - } - - std::__merge_adaptive(__first, __middle, __last, - _Distance(__middle - __first), - _Distance(__last - __middle), - __buffer, __buffer_size, - __comp); + __stable_sort_adaptive(__first, __middle, __last, __buffer, __comp); } /// This is a helper function for the stable sorting routines. @@ -5017,11 +5045,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO // so the buffer only needs to fit half the range at once. _TmpBuf __buf(__first, (__last - __first + 1) / 2); - if (__buf.begin() == 0) + if (__builtin_expect(__buf.requested_size() == __buf.size(), true)) + std::__stable_sort_adaptive(__first, __first + __buf.size(), __last, + __buf.begin(), __comp); + else if (__builtin_expect(__buf.begin() == 0, false)) std::__inplace_stable_sort(__first, __last, __comp); else - std::__stable_sort_adaptive(__first, __last, __buf.begin(), - _DistanceType(__buf.size()), __comp); + std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(), + _DistanceType(__buf.size()), __comp); } /** --------------CAA1B1BA9ABC6E08C72E7D68--