From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by sourceware.org (Postfix) with ESMTPS id E3B893858D3C; Sun, 21 Nov 2021 20:34:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E3B893858D3C Received: by mail-wr1-x42b.google.com with SMTP id n29so28748907wra.11; Sun, 21 Nov 2021 12:34:55 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=10OsgCutulXu+u7aHyye4N3AdWfcw7JUisXenZUuxXc=; b=hG/NNekyG75FNa1+pVSJaJXNbTp5Qcyz4dbZaNlH+0OvG2flROVYEqB+A5uleNBPWj GmzIJy1g60mb6LNbU3gqOZbFGTdB78IyVwxlRpEKiLvYBcFqPyWLRcqIWQ1n8f/shdVG G36fBlP/fH1ATaW3Q5FquaWCNNj44N4zdjnreNSGTHFO3f0JW3UjO5XX7s2+WH24Pdqh 7dVyrwyeLJNGEymnNGSg4hHSX7wJW6QuAHuxQciwRUkqniR57sBwp/cDJIePgtwnV7F7 xieL6PHpuhr9tcLh+Z7AYi9/JOSk7k7Fh7+cN5GJGKsWednvxhKxAWWyMgOox4dbSvWx dKQw== X-Gm-Message-State: AOAM530wTTcgig896MDb94XYxSg+ooLN51rmS0yvYbub3gSqp7wJFi3U ihY193mKswbyFWtalr2Trrl/uNkxNq0= X-Google-Smtp-Source: ABdhPJzh3M2BUq8gumxRG5ywSCZwl1sPn+2PBuhn+Q8tn8rRw2UejG7R6yg1IvzYFhITVohs9AJvjA== X-Received: by 2002:adf:fb09:: with SMTP id c9mr29305624wrr.223.1637526894553; Sun, 21 Nov 2021 12:34:54 -0800 (PST) Received: from ?IPv6:2a01:e0a:1dc:b1c0:f94b:4072:21c:961f? ([2a01:e0a:1dc:b1c0:f94b:4072:21c:961f]) by smtp.googlemail.com with ESMTPSA id 8sm18555110wmg.24.2021.11.21.12.34.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 21 Nov 2021 12:34:53 -0800 (PST) Subject: Re: [PATCH] Simplify branching in algos To: Jonathan Wakely , "libstdc++@gcc.gnu.org" References: <3efeb7a1-ac7f-17e7-6fd0-62b363be34d0@gmail.com> Cc: gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Message-ID: <618ea432-517e-28d2-2ce4-f93c3e166c0e@gmail.com> Date: Sun, 21 Nov 2021 21:34:52 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/mixed; boundary="------------205145F4E452ECF6F31E3203" Content-Language: fr X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Sun, 21 Nov 2021 20:34:58 -0000 This is a multi-part message in MIME format. --------------205145F4E452ECF6F31E3203 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit A recent thread on this mailing list made me remember that this proposal is still open. I've updated it just to add a missing std qualification. François On 08/06/21 5:21 pm, Jonathan Wakely wrote: > I haven't forgotten this one, I just need to double-check that we > don't create another problem like std::rotate in 9.1 > > I'll try to finish the review tomorrow. > > J. > > > On 27/05/21 07:04 +0200, François Dumont via Libstdc++ wrote: >> 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 >> > >> 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> template>        typename _Pointer, typename _Compare> >>     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> +       typename _Pointer, typename _Compare> >> +    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> -       typename _Distance, typename _Compare> >> +  template> typename _Compare> >>     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> +       typename _Distance, typename _Compare> >> +    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); >>     } >> >>   /** > --------------205145F4E452ECF6F31E3203 Content-Type: text/x-patch; charset=UTF-8; name="stable_sort.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="stable_sort.patch" diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index bc611a95ef4..2ebc3b12713 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -2384,28 +2384,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; @@ -2433,14 +2447,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); } } @@ -2518,11 +2532,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); } @@ -2703,34 +2720,46 @@ _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); + std::__stable_sort_adaptive(__first, __middle, __last, + __buffer, __comp); } /// This is a helper function for the stable sorting routines. @@ -4995,11 +5024,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); } /** --------------205145F4E452ECF6F31E3203--