[C++ PATCH] Speed up inplace_merge algorithm & fix inefficient logic(PR c++/83938)

[Jason Merrill]

This is a libstdc++ bug and patch, not the C++ front end.  So I'm
adding the libstdc++ list to CC.

On Fri, Jan 19, 2018 at 3:02 AM, chang jc <r97922153@gmail.com> wrote:
> Current std::inplace_merge() suffers from performance issue by inefficient
> logic under limited memory,
>
> It leads to performance downgrade.
>
> Please help to review it.
>
> Index: include/bits/stl_algo.h
> ===================================================================
> --- include/bits/stl_algo.h     (revision 256871)
> +++ include/bits/stl_algo.h     (working copy)
> @@ -2437,7 +2437,7 @@
>           _BidirectionalIterator __second_cut = __middle;
>           _Distance __len11 = 0;
>           _Distance __len22 = 0;
> -         if (__len1 > __len2)
> +         if (__len1 < __len2)
>             {
>               __len11 = __len1 / 2;
>               std::advance(__first_cut, __len11);
> @@ -2539,9 +2539,15 @@
>        const _DistanceType __len1 = std::distance(__first, __middle);
>        const _DistanceType __len2 = std::distance(__middle, __last);
>
> +
>        typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
> -      _TmpBuf __buf(__first, __last);
> -
> +      _BidirectionalIterator __start, __end;
> +      if (__len1 < __len2) {
> +       __start = __first; __end = __middle;
> +      } else {
> +       __start = __middle; __end = __last;
> +      }
> +      _TmpBuf __buf(__start, ___end);
>        if (__buf.begin() == 0)
>         std::__merge_without_buffer
>           (__first, __middle, __last, __len1, __len2, __comp);
> Index: include/bits/stl_tempbuf.h
> ===================================================================
> --- include/bits/stl_tempbuf.h  (revision 256871)
> +++ include/bits/stl_tempbuf.h  (working copy)
> @@ -95,7 +95,7 @@
>                                                         std::nothrow));
>           if (__tmp != 0)
>             return std::pair<_Tp*, ptrdiff_t>(__tmp, __len);
> -         __len /= 2;
> +         __len = (__len + 1) / 2;
>         }
>        return std::pair<_Tp*, ptrdiff_t>(static_cast<_Tp*>(0), 0);
>      }
>
>
>
>
> Thanks