C++11 forループの速度比較と、コンパイラのループ展開

C++ コンパイラ

C++11 forループの速度比較と、コンパイラのループ展開についてテストをしたときの結果です。構造体のメンバを、5で割った余りごとに分けて、頻度を数えるようなソースコードで実験しました（ソースコードは最後にあります）。プロセッサは、Intel(R) Core(TM) i7-3632QM CPU @ 2.20GHzですが、実行結果は、コンパイラ・CPU・メモリ・キャッシュで大きく異ってくると思うので、ざっくりとだけ参考にしてもらえればと思います。

1. ループの方法ごとの速度の比較

Visual Studio 2012は、Release、その他は初期設定のままでコンパイルしました。
g++ 4.8.2は、--std=c++0x -O2 -W -Wall -Wno-sign-compareでコンパイルしました。

方法 Visual Studio 2012（秒） g++ 4.8.2（秒）
(1) 通常のforループ 2.995 3.562
(2) 通常のforループとconst参照 3.035 3.579
(3) c++11のrange-based forループ 3.604 3.502
(4) for_eachとc++11のラムダ式 3.619 3.462
(5) for_eachと関数オブジェクト 3.604 3.477
  • Visual Studio 2012で(1)(2)が速いのは、ループ展開が行われているからです。g++ 4.8.2は、(1)から(5)までおおよそ同じ時間です。デフォルトのオプションでは、ループ展開しないようです。
  • (4)と(5)は、http://msdn.microsoft.com/ja-jp/library/dd293608.aspx にあるように、C++11のラムダ式は関数オブジェクトを使用したものと同じになります。実際に、Visual Studio 2012でコンパイルすると、DebugでもReleaseでも(4)と(5)は、全く同じアセンブリになりました。

2. コンパイラのループ展開の仕方

（同じコードを使いましたが、ちょっと前に違う状態で実験したので、当時の簡易的な実験の結果として見てもらえれば）

ループ展開とは、コンパイラの高速化の手法です。

for (int i = 0; i < 10000; ++i)
{
	frequency[positions[i].x%SZ(frequency)]++;
}

上のようなコードを、下のようなコードに置き換えて、ループ回数を減らします。（動作はかわりません）

for (int i = 0; i < 10000/5; ++i)
{
	frequency[positions[i*5].x%SZ(frequency)]++;
	frequency[positions[i*5+1].x%SZ(frequency)]++;
	frequency[positions[i*5+2].x%SZ(frequency)]++;
	frequency[positions[i*5+3].x%SZ(frequency)]++;
	frequency[positions[i*5+4].x%SZ(frequency)]++;
}

メリット・デメリットについて、詳細はこちらのリンクを参考にしてみてください→ http://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%97%E5%B1%95%E9%96%8B

Visual Studio 2012
  • Nを定数にした場合、6以下の約数で最も大きい個数に展開するようです。Nが素数のときや、2でしか割り切れないときは遅くなりました。
N ループ展開の個数 実行時間（秒）
9996 4 2.839
9997 1 3.213
9998 2 3.136
9999 3 2.854
10000 5 2.871
10001 1 3.276
10002 6 2.855
10003 1 3.214
  • Nを変数にした場合（標準入力でNに値を渡した場合）は、ループ展開はされませんでした。
g++ 4.8.2
  • Nを定数にした場合、コンパイルオプションに-funroll-loopsを追加すると、ループ展開されます。12個までループされる展開を確認できましたが、8個や12個まで展開されたときは、かえって遅くなりました。
  • Nを変数にした場合（標準入力でNに値を渡した場合）は、 -funroll-all-loopsを追加すると、ループ展開されます。この場合、8個にループ展開されましたが、Nが8で割り切れないことを考えて、ループを途中で抜けるジャンプ命令が入ってしまうため、かえって遅くなってしまいます。


ソースコードです。

#include <vector>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;
#define SZ(a) ((int)a.size()) 

#include <sys/time.h>
unsigned long long getTime() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	unsigned long long  result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
	return result;
}

struct POS
{
	int x;
	int y;
};


class FunctorClass
{
public:
	explicit FunctorClass(vector <int>& frequency) 
		: m_frequency(frequency)
	{
	}

	void operator()(const POS& pos) const
	{
		m_frequency[pos.x%SZ(m_frequency)]++;
	}

private:
	FunctorClass& operator=(const FunctorClass&);
	vector <int>& m_frequency;
};



int main()
{
	int N = 10000;
	vector <POS> positions(N);
	for (int i = 0; i < N; ++i)
	{
		positions[i].x = rand();
		positions[i].y = rand();
	}

	const int DIVIDE = 5;
	vector <int> frequency(DIVIDE);

	const ll start = getTime();

	for(int k = 0; k < 100000; ++k)
	{
#if 1
		// (1) 通常のforループ
		for (int i = 0; i < N; ++i)
		{
			frequency[positions[i].x%SZ(frequency)]++;
		}
#elif 0
		// (2) 通常のforループとconst参照
		for (int i = 0; i < N; ++i)
		{
			const POS& p = positions[i];
			frequency[p.x%SZ(frequency)]++;
		}
#elif 0
		// (3) c++11のrange-based forループ
		for (const POS& p : positions)
		{
			frequency[p.x%SZ(frequency)]++;
		}
#elif 0
		// (4) for_eachとc++11のラムダ式
		for_each(positions.begin(),positions.end(), [&frequency] (const POS& pos) {
			frequency[pos.x%SZ(frequency)]++;
		});
#else
		// (5) for_eachと関数オブジェクト
		for_each(positions.begin(),positions.end(), FunctorClass(frequency));
#endif
	}

	cout << " Time=" << getTime()-start << endl;

	for (int i = 0; i < SZ(frequency); ++i)
	{
		cout << " frequency[" << i << "]=" << frequency[i] << endl;
	}

	return 0;
}