C++とSwiftの速度比較 〜ソートアルゴリズム編〜

前回の記事（C++とJavaとSwiftの速度比較 〜配列編〜）ではC++とJavaとSwiftでの配列アクセス速度の違いを見てみました。今回は少し複雑な動作させてみようということで、C++とSwiftでソートアルゴリズムの実行速度を比較してみます。

(2017.09.02 追記)
Javaも含めて比較してみました：C++とJava（とSwift）の速度比較 〜ソートアルゴリズム編〜

概要

C++とSwiftの速度比較ということで、以前は配列の読み書きを行うプログラムで比較を行いました。今回は単純な配列アクセスだけではなく、比較や関数呼び出しなども含めた総合的なプログラムの実効速度を比較したいと考え、配列のソートを行うプログラムで速度の比較実験を行いました。

おおまかには

• 標準入力からテキストデータを読み込み、オブジェクトを生成し、順次配列の後ろへ追加
• オブジェクトのメンバを基準に配列の中身をソート

という処理を行います。

ソーティングにはマージソートを用います。関数呼び出しを増やしたかったのと、実装の手間削減のため、再帰関数による実装としました。

ソートの対象はPersonクラスのオブジェクトで、id（整数型）とname（文字列型）というメンバ変数を持っており、nameを基準として昇順にソートを行います。データは全部で50万件あり、nameは3〜10文字のランダムなアルファベットです。

C++では速度向上のためにオブジェクトへのポインタの配列をソートする方が一般的かと思いますが、Swiftでポインタの配列のようなことをするのが面倒だったため、どちらもオブジェクトの配列を用いることで統一しています。

実験環境

以下、今回の実験環境です。全て同じハードウェア上で動かしています（前回とは別のハードウェアです）。

OS

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.3 LTS"

C++

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/5/lto-wrapper
Target: x86_64-linux-gnu
（中略）
Thread model: posix
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4) 

コンパイルオプション

$ g++ -O2 -std=gnu++11

Swift

$ swift --version
Swift version 3.1.1 (swift-3.1.1-RELEASE)
Target: x86_64-unknown-linux-gnu

コンパイルオプション

$ swiftc -O

および

$ swiftc -Ounchecked

ソースコード

以下ちょっと長いですが、実験に用いたソースコードです。

C++

Swift

結果

標準入力からの読み込みの部分とソーティングの部分のそれぞれの実行時間を計測しました。時間の計測にはC言語のライブラリからclock_gettime関数を用い、CPU時間ではなく実際に経過した時間を測定しました。以下の時間は5回実行したときの平均を表しています。

言語	読み込み（秒）	ソート（秒）
C++	0.433	0.492
Swift (-Ounchecked)	1.346	6.393
Swift (-O)	2.284	7.628

以下の表は各行の結果が各列の結果からみてどれだけ実行時間がかかったかを示しています。

• 読み込み

	C++	Swift (-Ounchecked)	Swift (-O)
C++	-	32.15%	18.95%
Swift (-Ounchecked)	311.08%	-	58.94%
Swift (-O)	527.80%	169.67%	-

• ソート

	C++	Swift (-Ounchecked)	Swift (-O)
C++	-	7.69%	6.45%
Swift (-Ounchecked)	1300.34%	-	83.81%
Swift (-O)	1551.49%	119.31%	-

読み込み（オブジェクトの生成、配列への追加を含む）はSwiftでuncheckedの最適化をしてもC++の約2倍かかり、uncheckedを外すとさらに2倍かかっています。

ソートはSwiftに関してはuncheckedの有無でそれほど速度は変わっていませんが、C++との比較では読み込み以上に差が広がっており、uncheckedをつけてもC++の約13倍、Swiftから見るとC++は7.69%の時間で完了しています。

参考までに、今回用いた自作のソート関数と、C++のSTLのsort関数およびSwiftのArrayのメンバ関数であるsort関数を比較した結果も載せておきます。

言語	自作ソート関数（秒）	組み込みソート関数（秒）
C++	0.492	0.289
Swift (-Ounchecked)	6.393	3.148
Swift (-O)	7.628	3.147

もちろん組み込み関数の方が今回用いたプログラムよりも速いのですが、速度の傾向としては同じようなものとなりました。また面白いのが、Swiftでは最適化オプションでuncheckedを付けても付けなくても速度は全く変わりませんでした。内部では元々実行時チェックを行わない処理で書かれているのでしょうね。

おわりに

ソートアルゴリズムの観点では単純な配列アクセス以上にC++とSwiftの速度差が出ました。逆に何がボトルネックになっているのか？がわかりづらいですが，これもひとつの参考になればと思います。

ここが差が出る原因じゃないか？とか、この比べ方はフェアじゃない！など、なにか指摘があればコメントいただけると幸いです。

(2017.09.02 追記)
Javaも含めて比較してみました：C++とJava（とSwift）の速度比較 〜ソートアルゴリズム編〜

---

独習C++ 第4版

Effective Modern C++ ―C++11/14プログラムを進化させる42項目