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))