With a vector a reverse iterator is derived from the normal iterator
and accesses with an offset of -1. With today's CPUs this isn't slower.
I wondered if the performance is still the same with ordered maps or
sets, where this would mean a real penalty since offsetting is done
twice, once for the access and once for iteration to the next element.
So I wrote a small benchmark for that:

#include <iostream>
#include <set>
#include <chrono>
#include <atomic>

using namespace std;
using namespace chrono;

atomic_int aSum;

int main()
{ set<int> st;
for( int i = 0; i != 100; ++i )
st.emplace( i );
auto timeLoop = []( char const *what, auto fn )
{
auto start = high_resolution_clock::now();
int sum = 0;
for( size_t i = 1'000'000; i; --i )
fn( sum );
cout << what << duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / 100e6 << endl;
::aSum.store( sum, memory_order_relaxed );
};
timeLoop( "forward: ",
[&]( int &sum )
{
for( auto it = st.begin(); it != st.end(); ++it )
sum += *it;
} );
timeLoop( "reverse: ",
[&]( int &sum )
{
for( auto it = st.rbegin(); it != st.rend(); ++it )
sum += *it;
} );
timeLoop( "manual reverse: ",
[&]( int &sum )
{
for( auto it = st.end(); it != st.begin(); )
sum += *--it;
} );
}

This is the result with MSVC++ 18 on a 5.7GHz Zen4-CPU.

forward: 1.70247
reverse: 2.05701
manual reverse: 1.77813

The first result is from the bidirectional iterator, the second from the
reverse-iterator and the third from a bidirectional iterator iterating
reverse.
So iterate reverse only if necessary.

On 5/4/2024 5:16 AM, Bonita Montero wrote:
> With a vector a reverse iterator is derived from the normal iterator
> and accesses with an offset of -1. With today's CPUs this isn't slower.
> I wondered if the performance is still the same with ordered maps or
> sets, where this would mean a real penalty since offsetting is done
> twice, once for the access and once for iteration to the next element.
> So I wrote a small benchmark for that:
[...]

Cache lines like to be read, going forward, perhaps a prefetch is in
order... ;^)

Am 04.05.2024 um 21:56 schrieb Chris M. Thomasson:
> On 5/4/2024 5:16 AM, Bonita Montero wrote:
>> With a vector a reverse iterator is derived from the normal iterator
>> and accesses with an offset of -1. With today's CPUs this isn't slower.
>> I wondered if the performance is still the same with ordered maps or
>> sets, where this would mean a real penalty since offsetting is done
>> twice, once for the access and once for iteration to the next element.
>> So I wrote a small benchmark for that:
> [...]
>
> Cache lines like to be read, going forward, perhaps a prefetch is in
> order... ;^)
>

Theres's no specific phyisal access order with a set or map.

On 5/4/2024 1:19 PM, Bonita Montero wrote:
> Am 04.05.2024 um 21:56 schrieb Chris M. Thomasson:
>> On 5/4/2024 5:16 AM, Bonita Montero wrote:
>>> With a vector a reverse iterator is derived from the normal iterator
>>> and accesses with an offset of -1. With today's CPUs this isn't slower.
>>> I wondered if the performance is still the same with ordered maps or
>>> sets, where this would mean a real penalty since offsetting is done
>>> twice, once for the access and once for iteration to the next element.
>>> So I wrote a small benchmark for that:
>> [...]
>>
>> Cache lines like to be read, going forward, perhaps a prefetch is in
>> order... ;^)
>>
>
> Theres's no specific phyisal access order with a set or map.
>

It depends on the implementation. Is this a generic set or map, or a
very highly specialized one that only works well with certain inputs...

Am 04.05.2024 um 22:32 schrieb Chris M. Thomasson:

> It depends on the implementation. ...

There's nothing to prefetch in a tree.

On 5/4/2024 8:31 PM, Bonita Montero wrote:
> Am 04.05.2024 um 22:32 schrieb Chris M. Thomasson:
>
>> It depends on the implementation. ...
>
> There's nothing to prefetch in a tree.
>
>

Nevermind.