Deque fiil/copy/move/copy_backward/move_backward/equal overloads

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Deque fiil/copy/move/copy_backward/move_backward/equal overloads

François Dumont-2
I wanted to implement Debug overloads for those already existing
overloads but then realized that those algos could be generalized. This
way we will benefit from the memmove replacement when operating with C
array or std::array or std::vector iterators.

I might do the same for lexicographical_compare one day.

The ChangeLog below is quite huge so I attached it. I wonder if I could
use deque::iterator and deque::const_iterator in place of the
_Deque_iterator<> to reduce it ?

Tested under Linux x86_64 normal and debug modes, ok to commit ?

François


ChangeLog.entry (20K) Download Attachment
deque_algos.patch (139K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Deque fiil/copy/move/copy_backward/move_backward/equal overloads

Morwenn Edrahir
That's actually a solution to bug 90409, thanks for it :)

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90409

Morwenn

________________________________
De : [hidden email] <[hidden email]> de la part de François Dumont <[hidden email]>
Envoyé : mercredi 19 juin 2019 19:32
À : [hidden email]; gcc-patches
Objet : Deque fiil/copy/move/copy_backward/move_backward/equal overloads

I wanted to implement Debug overloads for those already existing
overloads but then realized that those algos could be generalized. This
way we will benefit from the memmove replacement when operating with C
array or std::array or std::vector iterators.

I might do the same for lexicographical_compare one day.

The ChangeLog below is quite huge so I attached it. I wonder if I could
use deque::iterator and deque::const_iterator in place of the
_Deque_iterator<> to reduce it ?

Tested under Linux x86_64 normal and debug modes, ok to commit ?

François

Reply | Threaded
Open this post in threaded view
|

Re: Deque fiil/copy/move/copy_backward/move_backward/equal overloads

François Dumont-2
In reply to this post by François Dumont-2
Ping ?

On 6/19/19 7:32 PM, François Dumont wrote:

> I wanted to implement Debug overloads for those already existing
> overloads but then realized that those algos could be generalized.
> This way we will benefit from the memmove replacement when operating
> with C array or std::array or std::vector iterators.
>
> I might do the same for lexicographical_compare one day.
>
> The ChangeLog below is quite huge so I attached it. I wonder if I
> could use deque::iterator and deque::const_iterator in place of the
> _Deque_iterator<> to reduce it ?
>
> Tested under Linux x86_64 normal and debug modes, ok to commit ?
>
> François
>

Reply | Threaded
Open this post in threaded view
|

Re: PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads

Daniel Krügler-3
In reply to this post by François Dumont-2
Am Do., 1. Aug. 2019 um 11:57 Uhr schrieb Jonathan Wakely <[hidden email]>:
>
> More comments inline below ...
[..]

>
> >François
> >
> >On 6/19/19 7:32 PM, François Dumont wrote:
> >>I wanted to implement Debug overloads for those already existing
> >>overloads but then realized that those algos could be generalized.
> >>This way we will benefit from the memmove replacement when operating
> >>with C array or std::array or std::vector iterators.
> >>
> >>I might do the same for lexicographical_compare one day.
> >>
> >>The ChangeLog below is quite huge so I attached it. I wonder if I
> >>could use deque::iterator and deque::const_iterator in place of the
> >>_Deque_iterator<> to reduce it ?
> >>
> >>Tested under Linux x86_64 normal and debug modes, ok to commit ?
> >>
> >>François
> >>
> >
>
> >diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
> >index 3f77b4f079c..9db869fb666 100644
> >--- a/libstdc++-v3/include/bits/deque.tcc
> >+++ b/libstdc++-v3/include/bits/deque.tcc
> >@@ -967,155 +967,507 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> >       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
> >     }
> >
[..]

>
> And anyway, isn't _Deque_iterator<T, T&, T*>::_Self just the same type as
> _Deque_iterator<T, T&, T*> ? It should be something like:
>
>       typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
>
> >+  template<typename _II, typename _Tp>
> >+    typename enable_if<
> >+      is_same<typename std::iterator_traits<_II>::iterator_category,
> >+            std::random_access_iterator_tag>::value,
>
> Use is_base_of<random_access_iterator_tag, ...::iterator_category> so
> it works for types derived from random_access_iterator_tag too.

Interesting. Traditional type tag dispatching approaches (as function
parameters) do have more in a manner that would be equivalent to an
implicit conversion (Being used as "by-value-parameters"), so I'm
wondering whether this should not instead refer to is_convertible? I
also found examples where this trait is currently used in <stl_algo.h>
such as

      static_assert(
      __or_<is_convertible<__pop_cat, forward_iterator_tag>,
        is_convertible<__samp_cat, random_access_iterator_tag>>::value,
      "output range must use a RandomAccessIterator when input range"
      " does not meet the ForwardIterator requirements");

Should possibly this trait be preferred?

- Daniel
Reply | Threaded
Open this post in threaded view
|

Re: PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads

François Dumont-2
On 8/1/19 2:53 PM, Jonathan Wakely wrote:

> On 01/08/19 13:52 +0100, Jonathan Wakely wrote:
>> On 01/08/19 13:31 +0200, Daniel Krügler wrote:
>>> Am Do., 1. Aug. 2019 um 13:01 Uhr schrieb Jonathan Wakely
>>> <[hidden email]>:
>>>>
>>>> On 01/08/19 12:36 +0200, Daniel Krügler wrote:
>>>>> Am Do., 1. Aug. 2019 um 11:57 Uhr schrieb Jonathan Wakely
>>>>> <[hidden email]>:
>>>>>>
>>>>>> More comments inline below ...
>>>>> [..]
>>>>>>
>>>>>> >François
>>>>>> >
>>>>>> >On 6/19/19 7:32 PM, François Dumont wrote:
>>>>>> >>I wanted to implement Debug overloads for those already existing
>>>>>> >>overloads but then realized that those algos could be generalized.
>>>>>> >>This way we will benefit from the memmove replacement when
>>>>>> operating
>>>>>> >>with C array or std::array or std::vector iterators.
>>>>>> >>
>>>>>> >>I might do the same for lexicographical_compare one day.
>>>>>> >>
>>>>>> >>The ChangeLog below is quite huge so I attached it. I wonder if I
>>>>>> >>could use deque::iterator and deque::const_iterator in place of
>>>>>> the
>>>>>> >>_Deque_iterator<> to reduce it ?
>>>>>> >>
>>>>>> >>Tested under Linux x86_64 normal and debug modes, ok to commit ?
>>>>>> >>
>>>>>> >>François
>>>>>> >>
>>>>>> >
>>>>>>
>>>>>> >diff --git a/libstdc++-v3/include/bits/deque.tcc
>>>>>> b/libstdc++-v3/include/bits/deque.tcc
>>>>>> >index 3f77b4f079c..9db869fb666 100644
>>>>>> >--- a/libstdc++-v3/include/bits/deque.tcc
>>>>>> >+++ b/libstdc++-v3/include/bits/deque.tcc
>>>>>> >@@ -967,155 +967,507 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>>>> > this->_M_impl._M_finish._M_set_node(__new_nstart +
>>>>>> __old_num_nodes - 1);
>>>>>> >     }
>>>>>> >
>>>>> [..]
>>>>>>
>>>>>> And anyway, isn't _Deque_iterator<T, T&, T*>::_Self just the same
>>>>>> type as
>>>>>> _Deque_iterator<T, T&, T*> ? It should be something like:
>>>>>>
>>>>>>       typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&,
>>>>>> _Tp*> _Iter;
>>>>>>
>>>>>> >+  template<typename _II, typename _Tp>
>>>>>> >+    typename enable_if<
>>>>>> >+      is_same<typename
>>>>>> std::iterator_traits<_II>::iterator_category,
>>>>>> >+ std::random_access_iterator_tag>::value,
>>>>>>
>>>>>> Use is_base_of<random_access_iterator_tag,
>>>>>> ...::iterator_category> so
>>>>>> it works for types derived from random_access_iterator_tag too.
>>>>>
>>>>> Interesting. Traditional type tag dispatching approaches (as function
>>>>> parameters) do have more in a manner that would be equivalent to an
>>>>> implicit conversion (Being used as "by-value-parameters"), so I'm
>>>>> wondering whether this should not instead refer to is_convertible? I
>>>>> also found examples where this trait is currently used in
>>>>> <stl_algo.h>
>>>>> such as
>>>>>
>>>>>      static_assert(
>>>>>      __or_<is_convertible<__pop_cat, forward_iterator_tag>,
>>>>>        is_convertible<__samp_cat,
>>>>> random_access_iterator_tag>>::value,
>>>>>      "output range must use a RandomAccessIterator when input range"
>>>>>      " does not meet the ForwardIterator requirements");
>>>>>
>>>>> Should possibly this trait be preferred?
>>>>
>>>> Hmm, I don't know why I did it that way in sample.
>>>>
>>>> The standard requires derivation in a couple of places today, see
>>>> [reverse.iterator] bullet 2.1 and [move.iterator] bullet 1.1 which use
>>>> DerivedFrom<random_access_iterator_tag> to check whether the base
>>>> iterator is random access or not.
>>>
>>> If you want to mimic DerivedFrom you also need to include
>>> is_convertible in some way, because is_base_of does not care about
>>> access.
>>
>> Ah yes, that's probably why I used is_convertible :-)
>>
>>> Maybe introduce __is_derived_from?
>>
>> Whatever we do, we should make it work for C++98 too, as that's needed
>> for François's patch. I wonder if it's good enough to just check if
>> iterator_traits<I>::iterator_category* converts to
>> random_access_iterator_tag*.
>>
>> So rather than a generic is_derived_from, just a check for
>> is_random_access, as that's all we need here.
>
> I already added a C++11-and-later version of that to <numeric>, but
> forgot to check that the base is public and unambiguous:
>
>  template<typename _It, typename _Traits = iterator_traits<_It>,
>           typename _Cat = typename _Traits::iterator_category>
>    using __is_random_access_iter
>      = is_base_of<random_access_iterator_tag, _Cat>;
>
I use it in this new patch making it compatible for C++98.

I haven't added the is_convertible. It seems strange to use
random_access_iterator_tag to hide it but if you think otherwise I can
try to add it.

Performance enhancements are very good.

Before:

copy_deque_iterators.cc      deque 2 deque                 735r 733u   
0s         0mem    0pf
copy_deque_iterators.cc      deque 2 vector               3420r 3419u   
0s         0mem    0pf
copy_deque_iterators.cc      vector 2 deque               3197r 3196u   
0s         0mem    0pf
copy_deque_iterators.cc      int deque 2 char vector      3341r 3336u   
0s         0mem    0pf
copy_deque_iterators.cc      char vector 2 int deque      3136r 3134u   
1s         0mem    0pf
copy_deque_iterators.cc      deque 2 list                 9941r 9940u   
0s         0mem    0pf
copy_deque_iterators.cc      list 2 deque                 2273r 2274u   
0s         0mem    0pf

After:

copy_deque_iterators.cc      deque 2 deque                 554r 553u   
0s         0mem    0pf
copy_deque_iterators.cc      deque 2 vector                316r 316u   
0s         0mem    0pf
copy_deque_iterators.cc      vector 2 deque                524r 523u   
0s         0mem    0pf
copy_deque_iterators.cc      int deque 2 char vector      1882r 1879u   
0s         0mem    0pf
copy_deque_iterators.cc      char vector 2 int deque      2199r 2192u   
2s         0mem    0pf
copy_deque_iterators.cc      deque 2 list                 7630r 7625u   
1s         0mem    0pf
copy_deque_iterators.cc      list 2 deque                 2254r 2254u   
0s         0mem    0pf

Even deque 2 deque is enhanced which I don't explain. The good point is
that even if it eventually do not use memcpy it is still a good
enhancement. It behaves like a loop unrolling optimization I think. And
moreover the deque iterator arithmetic is more complicated than the
pointer one.

Note that 'list 2 deque' perf are identical which is normal as in this
case the copy overload is disabled. I hesitated but prefer to keep it,
let me know if I better remove it.

For std::equal the result are also very good:

Before:

equal_deque_iterators.cc     deque vs deque               6275r 6274u   
0s         0mem    0pf
equal_deque_iterators.cc     deque vs vector              4277r 4277u   
0s         0mem    0pf
equal_deque_iterators.cc     vector vs deque              2280r 2280u   
0s         0mem    0pf
equal_deque_iterators.cc     int deque vs char vector     4263r 4263u   
0s         0mem    0pf
equal_deque_iterators.cc     char vector vs int deque     2390r 2390u   
0s         0mem    0pf

After:

equal_deque_iterators.cc     deque vs deque                555r 554u   
0s         0mem    0pf
equal_deque_iterators.cc     deque vs vector               201r 201u   
0s         0mem    0pf
equal_deque_iterators.cc     vector vs deque               360r 360u   
0s         0mem    0pf
equal_deque_iterators.cc     int deque vs char vector     1197r 1196u   
0s         0mem    0pf
equal_deque_iterators.cc     char vector vs int deque     1311r 1310u   
0s         0mem    0pf

testsuite_file/25_algorithms tested under Linux x86_64.

Ok to commit after I run all the other tests ?

François


deque_algos.patch (149K) Download Attachment