1. informationsea

    Posted

    informationsea
Changes in title
+C++ STL のイテレーターでインクリメントは前置すべきか後置すべきか
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,238 @@
+
+## 結論
+
+最適化が有効でシンプルな使い方である限りどっちでも良い
+
+## 前置き
+
+C++のSTLではvector, list, dequeなど様々なコンテナにおいてイテレーターが多用されています。このイテレーターを順にたどって行くときにインクリメントを前置したほうが早いという話を聞いたことがあったのですが、確かめたことが無かったので確かめてみました。
+
+## なぜ、インクリメントを前置した方が早いと言われているのか?
+
+STLの実装を見てみましょう。以下のコードはGCC 6.1のイテレーターの実装で、`include/gcc6/c++/bits/stl_iterator.h`から持ってきました。
+
+```c++
+ 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回行いました。
+
+```c++
+#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`)
+![Rplot001.png](https://qiita-image-store.s3.amazonaws.com/0/56302/2375bb82-cf56-a5ee-7efa-7eae0e093674.png "Rplot001.png")
+
+
+### 最適化あり (`-Os`)
+![Rplot002.png](https://qiita-image-store.s3.amazonaws.com/0/56302/ef708d5f-4b26-f0ee-f160-05138b6ec67b.png "Rplot002.png")
+
+### 考察
+
+結果を見る限り最適化なしの場合には前置インクリメント、`+=`によるインクリメント、後置インクリメントの順で高速であることが検定するまでもなく分かります。しかし、最適化ありでは誤差程度の差しかないことが分かります。このように最適化が有効であればどれを使っても変わらないことが検証できました。
+
+## コンパイル結果を見てみる
+
+最適化ありの場合のコンパイル結果を確認してみました。コンパイラはGCC 6.1でclock関数の呼び出しの間を抜きだしています。
+
+```objdump
+ 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
+```
+
+```objdump
+ 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
+```
+
+```objdump
+ 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のコード
+
+```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))
+
+```