C++ STL のイテレーターでインクリメントは前置すべきか後置すべきか

結論

最適化が有効でシンプルな使い方である限りどっちでも良い

前置き

C++のSTLではvector, list, dequeなど様々なコンテナにおいてイテレーターが多用されています。このイテレーターを順にたどって行くときにインクリメントを前置したほうが早いという話を聞いたことがあったのですが、確かめたことが無かったので確かめてみました。

なぜ、インクリメントを前置した方が早いと言われているのか？

STLの実装を見てみましょう。以下のコードはGCC 6.1のイテレーターの実装で、include/gcc6/c++/bits/stl_iterator.hから持ってきました。

      move_iterator&
      operator++()
      {
        ++_M_current;
        return *this;
      }

      move_iterator
      operator++(int)
      {
        move_iterator __tmp = *this;
        ++_M_current;
        return __tmp;
      }

演算子オーバーロードしているうち、上が前置で下が後置です。前置では自分自身を一回インクリメントして自分自身を参照返しているのに対し、後置では一旦自分自身のコピーをとった上で自分をインクリメントしてコピーを値返ししています。このことからも後置するとコピーが発生するの対して前置ではコピーが発生しないので高速であることが推定できます。

しかし、この程度のコードで今どきのコンパイラが最適化を行わないとは思えなかったので検証を行いました。

GCC 6.1での測定

テストは OS X 10.11 で MacPorts を使ってインストールした GCC 6.1 で行いました。検証コードは以下の通りです。CPU時間を測定しています。200000000個の要素が入ったvectorを10回読み出して、その時間を計測することを10回行いました。

# include <iostream>
# include <ctime>
# include <vector>

const int COUNT = 10;
const int REPEAT = 10;
const int NUM = 200000000;

class StopWatch {
private:
    clock_t _start;
    clock_t _stop;
public:
    StopWatch() : _start(0), _stop(0) {}
    void start() { _start = std::clock();}
    void stop() { _stop = std::clock(); }
    double seconds() const {return ((double)_stop - _start)/CLOCKS_PER_SEC;}
    void show() const { std::cout << seconds() << "s"; }
};

std::ostream &operator << (std::ostream &s, const StopWatch &st)
{
    return s << st.seconds();
}

int main()
{
    std::vector<int> vec;
    for (int i = 0; i < NUM; i++) {
        vec.push_back(i);
    }

    for (int i = 0; i < COUNT; i++) {
        StopWatch st;
        int sum;
        
        // ++iterator
        sum = 0;
        st.start();
        for (int j = 0; j < REPEAT; j++) {
            for (auto it = vec.begin(); it != vec.end(); ++it) {
                sum += *it;
            }
        }
        st.stop();
        std::cout << sum << " ++iterator: " << st << std::endl;

        // ++iterator
        sum = 0;
        st.start();
        for (int j = 0; j < REPEAT; j++) {
            for (auto it = vec.begin(); it != vec.end(); it++) {
                sum += *it;
            }
        }
        st.stop();
        std::cout << sum << " iterator++: " << st << std::endl;

        // iterator+=1
        sum = 0;
        st.start();
        for (int j = 0; j < REPEAT; j++) {
            for (auto it = vec.begin(); it != vec.end(); it+=1) {
                sum += *it;
            }
        }
        st.stop();
        std::cout << sum << " iterator+=: " << st << std::endl;
    }
    
    return 0;
}

最適化は-O0と-Osで試しました。

計測結果

最適化	インクリメント	平均時間(s)	標準偏差
0	++it	41.933200	1.64191688
0	it++	52.896340	2.29125478
0	it+=1	42.772790	0.42448212
s	++it	1.594248	0.03496150
s	it++	1.585829	0.01765536
s	it+=1	1.578326	0.02466453

最適化なし (-O0)

最適化あり (-Os)

考察

結果を見る限り最適化なしの場合には前置インクリメント、+=によるインクリメント、後置インクリメントの順で高速であることが検定するまでもなく分かります。しかし、最適化ありでは誤差程度の差しかないことが分かります。このように最適化が有効であればどれを使っても変わらないことが検証できました。

コンパイル結果を見てみる

最適化ありの場合のコンパイル結果を確認してみました。コンパイラはGCC 6.1でclock関数の呼び出しの間を抜きだしています。

	movq	24(%rsp), %rsi
	movl	$10, %edx
	movq	32(%rsp), %rcx
	movq	%rax, 8(%rsp)
L40:
	movq	%rsi, %rax
L39:
	cmpq	%rax, %rcx
	je	L38
	addl	(%rax), %r12d
	addq	$4, %rax
	jmp	L39
L38:
	decl	%edx
	jne	L40

	movq	24(%rsp), %rcx
	movl	$10, %edx
	xorl	%r13d, %r13d
	movq	32(%rsp), %rsi
	movq	%rax, 8(%rsp)
L43:
	movq	%rcx, %rax
L42:
	cmpq	%rax, %rsi
	je	L41
	addl	(%rax), %r13d
	addq	$4, %rax
	jmp	L42
L41:
	decl	%edx
	jne	L43

	movq	24(%rsp), %rcx
	movl	$10, %edx
	xorl	%r13d, %r13d
	movq	32(%rsp), %rsi
	movq	%rax, 8(%rsp)
L46:
	movq	%rcx, %rax
L45:
	cmpq	%rsi, %rax
	je	L44
	addl	(%rax), %r13d
	addq	$4, %rax
	jmp	L45
L44:
	decl	%edx
	jne	L46

この結果をみると使っているレジスタが一部違う程度で、ループの中は全く同じ命令が並んでいます。このことからも最適化が有効であれば全く同じようにコンパイルされるようです。

インクリメントした値を直接使う場合には結果が変わるかもしれませんが、今回のようなシンプルな場合ではパフォーマンスに差がないことが検証できました。

おまけ

Rのコード

library(ggplot2)
library(dplyr)

dat0 <- data.frame(sec=c(41.6628, 52.8142, 42.8535, 41.631, 52.8388, 42.865, 40.0388, 50.7011, 43.8264, 45.4467, 59.1299, 42.7976, 44.3081, 52.2687, 42.5564, 41.0486, 52.0807, 42.6148, 41.1657, 52.2148, 42.407, 41.0746, 51.5172, 42.4055, 41.4501, 52.8702, 42.9702, 41.5056, 52.5278, 42.4315), optimize='0', type=c('++it', 'it++', 'it+=1'))

dats <- data.frame(sec=c(1.63602, 1.59056, 1.57367, 1.56267, 1.58933, 1.58923, 1.61306, 1.56378, 1.57109, 1.55267, 1.57868, 1.55573, 1.56605, 1.57564, 1.60277, 1.55993, 1.57779, 1.57435, 1.64596, 1.61542, 1.52979, 1.61858, 1.58537, 1.60794, 1.61541, 1.61472, 1.60782, 1.57213, 1.567, 1.57087), optimize='s', type=c('++it', 'it++', 'it+=1'))

dat.all <- rbind(dat0, dats)

png(width = 800, height = 800, res=200)
g <- ggplot(dat0, aes(y=sec, x=type, fill=type))
g <- g + geom_boxplot()
print(g)

g <- ggplot(dats, aes(y=sec, x=type, fill=type))
g <- g + geom_boxplot()
print(g)

g <- ggplot(dats, aes(x=sec, fill=type))
g <- g + geom_density(alpha=0.5)
print(g)

dev.off()

t.test(subset(dats, type=='++it')$sec, subset(dats, type=='it++')$sec)
t.test(subset(dats, type=='++it')$sec, subset(dats, type=='it+=1')$sec)
t.test(subset(dats, type=='it++')$sec, subset(dats, type=='it++')$sec)

dat.all %>% dplyr::group_by(optimize, type) %>% dplyr::summarize(sec.mean=mean(sec), sec.sd=sd(sec))