diff mbox series

Avoids std::distance calls

Message ID 8c9ec4bd-c2d2-a81b-52ee-7141465e32df@gmail.com
State New
Headers show
Series Avoids std::distance calls | expand

Commit Message

François Dumont June 4, 2018, 8:13 p.m. UTC 
Hi

I'd like to propose this patch to avoid std::distance calls. In a number 
of situation in algos we already have the size of the buffer we need so 
we shouldn't have to compute it again.

I don't think there is any abi concern for this inline constructor, 
isn't there ?

     * include/bits/stl_tempbuf.h
     (_Temporary_buffer(_FwdIte, _FwdIte)): Delete, replaced by...
     (_Temporary_buffer(_FwdIte, size_type)): ...this, new.
     * include/ext/memory (temporary_buffer<>(_FwdIte, _FwdIte)): Adapt.
     * include/bits/stl_algo.h (__stable_partition): Adapt.
     (__inplace_merge): Adapt.
     (__stable_sort): Adapt.

Tested under Linux x86_64 normal mode.

Ok to commit ?

François

Comments

Jonathan Wakely June 4, 2018, 9:09 p.m. UTC | #1 
On 04/06/18 22:13 +0200, François Dumont wrote:
>Hi
>
>I'd like to propose this patch to avoid std::distance calls. In a 
>number of situation in algos we already have the size of the buffer we 
>need so we shouldn't have to compute it again.

Just one place, in __inplace_merge, no?

>I don't think there is any abi concern for this inline constructor, 
>isn't there ?

No concerns, users can't explicitly instantiate that type, and it will
be inlined or generate an instantiation everywhere it's used.

>    * include/bits/stl_tempbuf.h
>    (_Temporary_buffer(_FwdIte, _FwdIte)): Delete, replaced by...
>    (_Temporary_buffer(_FwdIte, size_type)): ...this, new.
>    * include/ext/memory (temporary_buffer<>(_FwdIte, _FwdIte)): Adapt.
>    * include/bits/stl_algo.h (__stable_partition): Adapt.
>    (__inplace_merge): Adapt.
>    (__stable_sort): Adapt.
>
>Tested under Linux x86_64 normal mode.
>
>Ok to commit ?

OK, thanks.
François Dumont June 5, 2018, 5:49 a.m. UTC | #2 
On 04/06/2018 23:09, Jonathan Wakely wrote:
> On 04/06/18 22:13 +0200, François Dumont wrote:
>> Hi
>>
>> I'd like to propose this patch to avoid std::distance calls. In a 
>> number of situation in algos we already have the size of the buffer 
>> we need so we shouldn't have to compute it again.
>
> Just one place, in __inplace_merge, no?

For the moment yes but I'll submit another patch soon.

Now committed.
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 914a6b6..d8488a7 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1615,7 +1615,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename iterator_traits<_ForwardIterator>::difference_type
 	_DistanceType;
 
-      _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
+      _Temporary_buffer<_ForwardIterator, _ValueType>
+	__buf(__first, std::distance(__first, __last));
       return
 	std::__stable_partition_adaptive(__first, __last, __pred,
 					 _DistanceType(__buf.requested_size()),
@@ -2534,7 +2535,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _DistanceType __len2 = std::distance(__middle, __last);
 
       typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
-      _TmpBuf __buf(__first, __last);
+      _TmpBuf __buf(__first, __len1 + __len2);
 
       if (__buf.begin() == 0)
 	std::__merge_without_buffer
@@ -4992,7 +4993,7 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	_DistanceType;
 
       typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
-      _TmpBuf __buf(__first, __last);
+      _TmpBuf __buf(__first, std::distance(__first, __last));
 
       if (__buf.begin() == 0)
 	std::__inplace_stable_sort(__first, __last, __comp);
diff --git a/libstdc++-v3/include/bits/stl_tempbuf.h b/libstdc++-v3/include/bits/stl_tempbuf.h
index 56c4ac5..159ee27 100644
--- a/libstdc++-v3/include/bits/stl_tempbuf.h
+++ b/libstdc++-v3/include/bits/stl_tempbuf.h
@@ -158,9 +158,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       /**
        * Constructs a temporary buffer of a size somewhere between
-       * zero and the size of the given range.
+       * zero and the given length.
        */
-      _Temporary_buffer(_ForwardIterator __first, _ForwardIterator __last);
+      _Temporary_buffer(_ForwardIterator __seed, size_type __original_len);
 
       ~_Temporary_buffer()
       {
@@ -241,9 +241,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _ForwardIterator, typename _Tp>
     _Temporary_buffer<_ForwardIterator, _Tp>::
-    _Temporary_buffer(_ForwardIterator __first, _ForwardIterator __last)
-    : _M_original_len(std::distance(__first, __last)),
-      _M_len(0), _M_buffer(0)
+    _Temporary_buffer(_ForwardIterator __seed, size_type __original_len)
+    : _M_original_len(__original_len), _M_len(0), _M_buffer(0)
     {
       __try
 	{
@@ -253,7 +252,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_len = __p.second;
 	  if (_M_buffer)
 	    std::__uninitialized_construct_buf(_M_buffer, _M_buffer + _M_len,
-					       __first);
+					       __seed);
 	}
       __catch(...)
 	{
@@ -268,4 +267,3 @@  _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
 #endif /* _STL_TEMPBUF_H */
-
diff --git a/libstdc++-v3/include/ext/memory b/libstdc++-v3/include/ext/memory
index c5d526e..fcc4948 100644
--- a/libstdc++-v3/include/ext/memory
+++ b/libstdc++-v3/include/ext/memory
@@ -184,7 +184,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       /// Requests storage large enough to hold a copy of [first,last).
       temporary_buffer(_ForwardIterator __first, _ForwardIterator __last)
-      : _Temporary_buffer<_ForwardIterator, _Tp>(__first, __last) { }
+      : _Temporary_buffer<_ForwardIterator, _Tp>(__first,
+						 std::distance(__first, __last))
+      { }
       
       /// Destroys objects and frees storage.
       ~temporary_buffer() { }