[PATCH] Improve _Safe_iterator _M_distance_to

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

[PATCH] Improve _Safe_iterator _M_distance_to

François Dumont-2
     Here is the patch to improve _Safe_iterator<>::_M_get_distance_to
implementation.

I introduced a new _Distance_precision  __sp_sign_max_size for occasions
where we can't find out the exact size of a range but still get the max
size of it. Thanks to this the performance tests are much better when
dealing with list iterators:

Normal mode:

copy_backward_deque_iterators.cc    deque 2 list 5616r 5616u   
0s         0mem    0pf
copy_backward_deque_iterators.cc    list 2 deque 1586r 1586u   
0s         0mem    0pf
copy_deque_iterators.cc      deque 2 list                 5495r 5495u   
0s         0mem    0pf
copy_deque_iterators.cc      list 2 deque                 2400r 2400u   
0s         0mem    0pf

Debug mode:

copy_backward_deque_iterators.cc    deque 2 list 5789r 5785u   
1s         0mem    0pf
copy_backward_deque_iterators.cc    list 2 deque 1656r 1655u   
0s         0mem    0pf
copy_deque_iterators.cc      deque 2 list                 5792r 5793u   
0s         0mem    0pf
copy_deque_iterators.cc      list 2 deque                 2636r 2636u   
0s         0mem    0pf

Tested under Linux x86_64.

I'll commit once other patches are in.


     * include/debug/forward_list
(_Sequence_traits<__debug::forward_list<>>::_S_size): Returns __dp_sign
     distance when not empty.
     * include/debug/list
     (_Sequence_traits<__debug::list<>>::_S_size): Likewise.
     * include/debug/helper_functions.h (__dp_sign_max_size): New
     _Distance_precision enum entry.
     * include/debug/safe_iterator.h
     (__copy_move_a(_II, _II, const _Safe_iterator<>&)): Check for output
     iterator _M_can_advance as soon as input range distance precision is
     strictly higher than __dp_size.
     (__copy_move_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
     const _Safe_iterator<>&)): Likewise.
     (__copy_move_backward_a(_II, _II, const _Safe_iterator<>&)): Likewise.
     (__copy_move_backward_a(const _Safe_iterator<>&,
     const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
     (__equal_aux(_II, _II, const _Safe_iterator<>&)): Likewise.
     (__equal_aux(const _Safe_iterator<>&,
     const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.

François


distance_to.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Improve _Safe_iterator _M_distance_to

Jonathan Wakely-3
On 16/09/19 22:31 +0200, François Dumont wrote:

>    Here is the patch to improve _Safe_iterator<>::_M_get_distance_to
>implementation.
>
>I introduced a new _Distance_precision  __sp_sign_max_size for
>occasions where we can't find out the exact size of a range but still
>get the max size of it. Thanks to this the performance tests are much
>better when dealing with list iterators:
>
>Normal mode:
>
>copy_backward_deque_iterators.cc    deque 2 list 5616r 5616u   
>0s         0mem    0pf
>copy_backward_deque_iterators.cc    list 2 deque 1586r 1586u   
>0s         0mem    0pf
>copy_deque_iterators.cc      deque 2 list                 5495r
>5495u    0s         0mem    0pf
>copy_deque_iterators.cc      list 2 deque                 2400r
>2400u    0s         0mem    0pf
>
>Debug mode:
>
>copy_backward_deque_iterators.cc    deque 2 list 5789r 5785u   
>1s         0mem    0pf
>copy_backward_deque_iterators.cc    list 2 deque 1656r 1655u   
>0s         0mem    0pf
>copy_deque_iterators.cc      deque 2 list                 5792r
>5793u    0s         0mem    0pf
>copy_deque_iterators.cc      list 2 deque                 2636r
>2636u    0s         0mem    0pf
>
>Tested under Linux x86_64.
>
>I'll commit once other patches are in.
>
>
>    * include/debug/forward_list
>(_Sequence_traits<__debug::forward_list<>>::_S_size): Returns __dp_sign
>    distance when not empty.
>    * include/debug/list
>    (_Sequence_traits<__debug::list<>>::_S_size): Likewise.
>    * include/debug/helper_functions.h (__dp_sign_max_size): New
>    _Distance_precision enum entry.
>    * include/debug/safe_iterator.h
>    (__copy_move_a(_II, _II, const _Safe_iterator<>&)): Check for output
>    iterator _M_can_advance as soon as input range distance precision is
>    strictly higher than __dp_size.
>    (__copy_move_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
>    const _Safe_iterator<>&)): Likewise.
>    (__copy_move_backward_a(_II, _II, const _Safe_iterator<>&)): Likewise.
>    (__copy_move_backward_a(const _Safe_iterator<>&,
>    const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
>    (__equal_aux(_II, _II, const _Safe_iterator<>&)): Likewise.
>    (__equal_aux(const _Safe_iterator<>&,
>    const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.

The patch looks OK, but the safe_iterator.tcc changes are not listed
in the changelog, and those are the most complex part of the patch.

Please add a changelog entry for the _M_get_distance_to changes. OK
for trunk after that, thanks.


Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Improve _Safe_iterator _M_distance_to

François Dumont-2
I eventually committed the attach patch.

The usage of __dp_sign_max_size will come later.

François

On 9/27/19 1:45 PM, Jonathan Wakely wrote:

> On 16/09/19 22:31 +0200, François Dumont wrote:
>>     Here is the patch to improve _Safe_iterator<>::_M_get_distance_to
>> implementation.
>>
>> I introduced a new _Distance_precision  __sp_sign_max_size for
>> occasions where we can't find out the exact size of a range but still
>> get the max size of it. Thanks to this the performance tests are much
>> better when dealing with list iterators:
>>
>> Normal mode:
>>
>> copy_backward_deque_iterators.cc    deque 2 list 5616r 5616u
>> 0s         0mem    0pf
>> copy_backward_deque_iterators.cc    list 2 deque 1586r 1586u
>> 0s         0mem    0pf
>> copy_deque_iterators.cc      deque 2 list                 5495r
>> 5495u    0s         0mem    0pf
>> copy_deque_iterators.cc      list 2 deque                 2400r
>> 2400u    0s         0mem    0pf
>>
>> Debug mode:
>>
>> copy_backward_deque_iterators.cc    deque 2 list 5789r 5785u
>> 1s         0mem    0pf
>> copy_backward_deque_iterators.cc    list 2 deque 1656r 1655u
>> 0s         0mem    0pf
>> copy_deque_iterators.cc      deque 2 list                 5792r
>> 5793u    0s         0mem    0pf
>> copy_deque_iterators.cc      list 2 deque                 2636r
>> 2636u    0s         0mem    0pf
>>
>> Tested under Linux x86_64.
>>
>> I'll commit once other patches are in.
>>
>>
>>     * include/debug/forward_list
>> (_Sequence_traits<__debug::forward_list<>>::_S_size): Returns __dp_sign
>>     distance when not empty.
>>     * include/debug/list
>>     (_Sequence_traits<__debug::list<>>::_S_size): Likewise.
>>     * include/debug/helper_functions.h (__dp_sign_max_size): New
>>     _Distance_precision enum entry.
>>     * include/debug/safe_iterator.h
>>     (__copy_move_a(_II, _II, const _Safe_iterator<>&)): Check for output
>>     iterator _M_can_advance as soon as input range distance precision is
>>     strictly higher than __dp_size.
>>     (__copy_move_a(const _Safe_iterator<>&, const _Safe_iterator<>&,
>>     const _Safe_iterator<>&)): Likewise.
>>     (__copy_move_backward_a(_II, _II, const _Safe_iterator<>&)):
>> Likewise.
>>     (__copy_move_backward_a(const _Safe_iterator<>&,
>>     const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
>>     (__equal_aux(_II, _II, const _Safe_iterator<>&)): Likewise.
>>     (__equal_aux(const _Safe_iterator<>&,
>>     const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
>
> The patch looks OK, but the safe_iterator.tcc changes are not listed
> in the changelog, and those are the most complex part of the patch.
>
> Please add a changelog entry for the _M_get_distance_to changes. OK
> for trunk after that, thanks.
>
>
>


distance_to.patch (5K) Download Attachment