2009年3月10日火曜日

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

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

#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;
}


結果は

v.size() = 100000
0.077 sec...
0.063 sec...
2.49995e+011
1.139 sec...
2.49995e+011
0.717 sec...

で、ローテーションしてからリニアにアクセスした方が速い。さすがに100000だと、条件分岐予測もあるし、ローテーションしない方が速いだろうと予想していたが、見事に裏切られた。ま、環境やテクノロジが変われば結果も変わりそうだけど、シンプル・イズ・ベストで良いって事だと思った。

0 件のコメント: