メモリ転送と条件分岐予測

　配列を循環とみなして処理する場合に、メモリ転送によるローテーションを行ってから、リニアにアクセスするのと、ローテーションしないでアクセスするのと、どちらが速いのか気になって、テストしてみた。思いっきり環境依存なので、あまり幸がなさそうなテストではある。

#include <vector>
#include <iostream>
#include <algorithm>
#include <boost/timer.hpp>

template <class ITER>
class circulator {
private:
   ITER first_;
   ITER last_;
public:
   circulator( ITER first, ITER last ) : first_(first), last_(last) {}
   ITER increment( ITER i ) const { return ((i+1)==last_) ? first_ : i+1; }
   ITER decrement( ITER i ) const { return (i==first) ? last_-1 : i-1; }
};

template <class ITER>
class linearator {
private:
   ITER first_;
   ITER last_;
public:
   linearator( ITER first, ITER last ) : first_(first), last_(last) {}
   ITER increment( ITER i ) const { return i+1; }
   ITER decrement( ITER i ) const { return i-1; }
};

template <class ITER, class INCREMENTOR>
double rounded_access_test(
   INCREMENTOR incr,
   ITER s,
   int length
) {
   double sum = double();
   for( int i = 0; i < length; ++i, s = incr.increment(s) ) {
     sum += static_cast<double>(*s);
   }
   return sum;
}


int main() {
   std::vector<int> v;
   v.resize( 100000 );
   std::cout << "v.size() = " << v.size() << std::endl;
   for( int i = 0; i < 100000; ++i ) {
     v[i] = i % 50000;
   }
   std::random_shuffle( v.begin(), v.end() );
   boost::timer t;
   for( int i = 0; i < 100; ++i ) {
     std::rotate( v.begin(), v.begin() + i, v.end() );
   }
   std::cout << t.elapsed() << " sec..." << std::endl;
   t.restart();
   for( int i = 0; i < 100; ++i ) {
     std::reverse( v.begin(), v.end() );
   }
   std::cout << t.elapsed() << " sec..." << std::endl;
   t.restart();
   circulator<std::vector<
  int>::iterator> circ( v.begin(), v.end() );
   double sum = double();
   for( int i = 0; i < 100; ++i ) {
     sum += rounded_access_test( circ, v.begin() + 50000, 100000 );
   }
   std::cout << sum << std::endl;
   std::cout << t.elapsed() << " sec..." << std::endl;
   t.restart();
   linearator<std::vector<int>::iterator> linr( v.begin(), v.end() );
   sum = double();
   for( int i = 0; i < 100; ++i ) {
     std::rotate( v.begin(), v.begin() + 50000, v.end() );
     sum += rounded_access_test( linr, v.begin(), 100000 );
   }
   std::cout << sum << std::endl;
   std::cout << t.elapsed() << " sec..." << std::endl;
}