This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Hi

    It sounds like a very sensitive change to make but nothing worth figures. Do you have any bench showing the importance of the gain ?

    At least the memory usage optimization is obvious.

On 19/01/2018 10:43, chang jc 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);
Note another optimization, we could introduce a _Temporary_buffer<> constructor in order to write:
_TmpBuf __buf(std::min(__len1, __len2), __first);

So that std::distance do not need to be called again.
        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

Thanks for the report.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]