rotate algorithm seems inefficient for bidirectional iterators

rotate algorithm seems inefficient for bidirectional iterators

[Sidney Marshall]

I was looking at the implementation of the rotate(first, middle, 
last) algorithm and found what I think is an inefficiency. The number 
of swaps for forward iterators and random access iterators is 
generally the same but for bidirectional iterators is sometimes much 
greater. For the case where the two halves are equal it uses twice as 
many swaps. Running the code:

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <cstdlib>
#include <algorithm>

using namespace std;

static long int c;

class swapable {
   swapable() { // needed to count all swaps - maybe to make this a non pod
   }
};

void swap(swapable &a, swapable &b) {
   c++;
}

template<class T>
void doit(T container) {
   auto b = container.begin();
   auto e = container.end();
   c = 0;
   for(auto m = b; m != e; ++m) {
     rotate(b, m, e);
   }
   cout << "c: " << c << endl;
}

int main(int argc, char *argv[]) {
   int n = atoi(argv[1]);
   cout << "n: " << n << endl;
   doit(forward_list<swapable>(n));
   doit(list<swapable>(n));
   doit(vector<swapable>(n));
}

I can count the number of swaps. It is always true that the 
bidirectional iterator does equal or more swaps than the forward 
iterator. Looking at the code verifies this observation. Why is the 
bidirectional code used at all?

If this is an inappropriate message, please let me know. If you would 
like me to examine other algorithms also let me know.

--Sidney Marshall 

Re: rotate algorithm seems inefficient for bidirectional iterators

[Jonathan Wakely]

On 24/08/20 18:35 -0400, Sidney Marshall wrote:
>I was looking at the implementation of the rotate(first, middle, last) 
>algorithm and found what I think is an inefficiency. The number of 
>swaps for forward iterators and random access iterators is generally 
>the same but for bidirectional iterators is sometimes much greater. 
>For the case where the two halves are equal it uses twice as many 
>swaps. Running the code:
>
>#include <iostream>
>#include <vector>
>#include <list>
>#include <forward_list>
>#include <cstdlib>
>#include <algorithm>
>
>using namespace std;
>
>static long int c;
>
>class swapable {
>  swapable() { // needed to count all swaps - maybe to make this a non pod
>  }
>};
>
>void swap(swapable &a, swapable &b) {
>  c++;
>}
>
>template<class T>
>void doit(T container) {
>  auto b = container.begin();
>  auto e = container.end();
>  c = 0;
>  for(auto m = b; m != e; ++m) {
>    rotate(b, m, e);
>  }
>  cout << "c: " << c << endl;
>}
>
>int main(int argc, char *argv[]) {
>  int n = atoi(argv[1]);
>  cout << "n: " << n << endl;
>  doit(forward_list<swapable>(n));
>  doit(list<swapable>(n));
>  doit(vector<swapable>(n));
>}
>
>I can count the number of swaps. It is always true that the 
>bidirectional iterator does equal or more swaps than the forward 
>iterator. Looking at the code verifies this observation. Why is the 
>bidirectional code used at all?

The three separate implementations originate with the STL, see
footnote [2] at
https://web.archive.org/web/20170518213244/http://www.sgi.com/tech/stl/rotate.html#2

The BidirectionIterator one is the three-reverses algorithm, which
Stepanov describes in http://stepanovpapers.com/notes.pdf?page=154

The overall performance of the algorithm is not just a consequence of
how many swaps it does. There are other factors, such as how well the
code can be vectorized and how cache friendly it is.

But the BidirectionIterator version does seem to be consistently
slower than the ForwardIterator one in the tests I just tried.