関数は全て関数オブジェクトで実装するべき？

Question

以下のコードは、アッカーマン関数を用いてそれぞれの関数の実行速度を調べるものです。
時間を変えて何度か実行した結果が下の画像になります。単位はミリ秒です。

すると、関数オブジェクト(コールバック)が関数よりも速いという結果が出ました。
関数オブジェクトのほうが速いというのであれば、実装する全ての関数を関数オブジェクトとして実装したほうが良いのでしょうか？

また関数の戻り値を型推論にして何度か実行してみたところ、実行時間が若干増えてしまいました。（何度やっても平均時間が型推論でないときを下回ることはなかった）
型推論はコンパイル時で完結するものだと思っているのですが、それは間違いなのでしょうか？それともただ単に実行タイミングが悪かったのでしょうか？
ついでに教えていただけたら幸いです。

#include <iostream>
#include <chrono>
using namespace std;

// アッカーマン関数
int acker(int x, int y) {
	if (x == 0) return y + 1;
	if (y == 0) return acker(x - 1, 1);
	return acker(x - 1, acker(x, y - 1));
}

// アッカーマン関数オブジェクト
struct ackerman {
	/*int operator()(int x, int y) {
		if (x == 0) return y + 1;
		if (y == 0) return ackerman()(x - 1, 1);
		return ackerman()(x - 1, ackerman()(x, y - 1));
	}*/

	// callback
	int operator()(ackerman& ack, int x, int y) {
		if (x == 0) return y + 1;
		if (y == 0) return ack(ack, x - 1, 1);
		return ack(ack, x - 1, ack(ack, x, y - 1));
	}
};

int main()
{
	constexpr int N = 10;
	constexpr int TIMES = 10;
	constexpr int TIMES_TIMES = 10;
	double ave = 0;
	double aveave = 0;
	ackerman ack;
	int a[N];

	for (int l = 0; l < TIMES_TIMES; l++) {
		for (int k = 0; k < TIMES; k++) {
			auto start = chrono::system_clock::now();

			for (int i = 0; i < N; i++) {
				//a[i] = acker(3, i);
				//a[i] = ack(3, i);
				//a[i] = ack(ack, 3, i);
			}

			auto end = chrono::system_clock::now();
			double time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

			//cout << time << "[ms]" << endl;
			ave += time;
		}
		cout << "ave=" << (ave / N) << "[ms]" << endl;
		aveave += ave;
		ave = 0;
	}
	cout << "aveave=" << (aveave / TIMES_TIMES * TIMES) << "[ms]" << endl;

	return 0;
}

Answer 1

現代のコンパイラは複雑です。 様々な要素の組み合わせによって上手く最適化可能なパターンになることもならないこともあります。 どのようにコンパイルされるか事前に予想するのはよほどそのコンパイラに通じた達人でもなければ出来ないものと思ってください。 そして最適化技術は激しく変遷しているので同じコンパイラでもほんの少しバージョンが変われば結果が違うということはあります。

また、個別の部分でわずかに速かったとしても全体としては観測不能なほどの差だったり逆効果だったりするのはよくあることです。 わずかな速度のために奇妙な設計をしてしまうと後に全体を見通して最適化しようとしても手を出しづらくなってしまいます。 「早すぎる最適化は諸悪の根源」というのはプログラミング業界ではよく知られている格言です。

まずは綺麗に設計して、速度が足りないようならどこが遅いのか測定して改良するという手順が望ましいですし、仮に関数オブジェクトが速いのだとしても「それは速い必要あるの？ (そのために回りくどいデザインにしてでも？)」ということも配慮すべきです。

Comments

[asobinin]

シンプルな質問かと思いましたが、その解答は一筋縄ではいかないようですね。
メタプログラミングもそうですが、あまり速度に拘りすぎるのもよくないということですね。
C++ではそれらの行為が全て許されてしまうので、速度と見た目の折り合いは非常に難しいです。

Answer 2

こんにちは。

まず、関数と関数オブジェクト（非コールバック）の差が激しいことが非常に気になります。
同じ処理を事実上同じコードで処理しているので結果がこんなに差がでることが不思議です。

ちょっとやってみたのですが、最適化ON/OFFで結果が変わります。
そして、最適化ONの場合、関数バージョンは実行時間が0mSecになります。ほぼ全てインライン展開されてしまう場合があるということのようです。（xをコンパイル時定数であたえていますし）
インライン展開を無限に行うことはできないので「どこまで」展開するかコンパイラがよしなに決めていると思いますが、その相違がありそうです。最適化OFFでも最適化を全くしないわけではないですから、似たような振る舞いはありえます。
（実際にどうなっているのか把握するためにはy_waiwaiさんも言っているようにアセンブラ・コードを見るのが確実です。アセンブラの勉強から始める場合はかなりたいへんですが、長いプログラマー人生の中で１度はやってみてもよいと思います。）

もし、実使用時の高速化を目的に速度比較されているのでしたら、コンパイラの実力がでない最適化OFFではなく、実力が発揮される最適化ONで比較することをお勧めします。

Answer 3

この質問の回答ではないですが、

そういうことを調べるのなら、まずはアセンブルリストを出してどういう命令コードが生成されるのかを調べましょう。
それぞれの場合で、なにか変わることをリストアップしていけばとりあえずその傾向が出てくると思います。

で、これだけで済めばいいのですが、イマドキのCPUではキャッシュメモリというのが搭載されてます。また、命令の実行に際してはパイプライン処理というのがなされます。
そのどれもが実行時間というのに深く関わるものなので、そこらへんが実際にはどう動くのかの理屈をすべて理解していかないと、なにが早くてなにが遅いということを判断するのはなかなか難しいと思います。

がんばってください。

Comments

[asobinin]

根本的な原因を特定するにはやはり、アセンブラや機械語など低レベルな部分を調べないといけないのですね・・・
がんばります