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

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

class Person {
private:
    int id;
    std::string name;

public:
    Person( int id, const char* name ) {
        this->id = id;
        this->name = name;
    }

    Person() {
        this->id = 0;
        this->name = "";
    }

    int get_id() { return id; };
    std::string get_name() { return name; };

    bool operator< ( Person &p2 ) {
        return this->name < p2.name;
    };

    Person &operator=( const Person &p ) {
        this->id = p.id;
        this->name = p.name;
        return *this;
    }

};

template<class T> class sort {
    T *buf;
    std::vector<T> *array;

public:
    Sort() {
    };

private:
    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    void merge( int index_b, int index_c, int index_e ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if ( index_b + 1 == index_e ) {
            if ( (*array)[index_e] < (*array)[index_b] ) {
                auto tmp = (*array)[index_e];
                (*array)[index_e] = (*array)[index_b];
                (*array)[index_b] = tmp;
            }
            return;
        }

        // index_1とindex_2を動かしながら，小さい方を順次index_bufへ書き込む
        int index_1 = index_b;
        int index_2 = index_c + 1;
        int index_buf = index_b;

        while ( true ) {
            if ( (*array)[index_1] < (*array)[index_2] ) {
                buf[index_buf++] = (*array)[index_1];
                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if ( index_1++ == index_c ) {
                    while ( index_2 <= index_e ) {
                        buf[index_buf++] = (*array)[index_2++];
                    }
                    break;
                }
            } else {
                buf[index_buf++] = (*array)[index_2];
                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if ( index_2++ == index_e ) {
                    while ( index_1 <= index_c ) {
                        buf[index_buf++] = (*array)[index_1++];
                }
                    break;
                }
            }
        }

        // バッファから元配列へコピー
        for ( int i = index_b; i <= index_e; i++ ) {
            (*array)[i] = buf[i];
        }

        return;
    };

    // 再帰的に呼び出す関数
    void merge_sort( int index_b, int index_e ) {
        int index_c = ( index_b + index_e ) / 2;

        // 左側をソート
        if ( index_b != index_c )
            merge_sort( index_b, index_c );

        // 右側をソート
        if ( (index_c + 1) != index_e )
            merge_sort( index_c + 1, index_e );

        // 左と右をマージ
        merge( index_b, index_c, index_e );

        return;
    };

public:
    // mainから呼ぶソート関数
    void merge_sort( std::vector<T> *vec ) {
        // ソート対象の配列
        this->array = vec;

        // マージ中のソート結果を一時的に記憶するバッファ
        this->buf = new T[ vec->size() ];

        // マージソート
        merge_sort( 0, vec->size() - 1 );

        delete [] buf;
    };

};

int main(int argc, char *argv[]) {
    // 時間測定のための変数
    struct timespec tp_start, tp_end;

    /******** 標準入力からデータを読み込み ********/
    std::vector<Person> vec_people;
    int id;
    std::string name;

    clock_gettime(CLOCK_REALTIME, &tp_start);

    while ( std::cin >> id && std::cin >> name ) {
        vec_people.push_back( Person( id, name.c_str() ) );
    }

    clock_gettime(CLOCK_REALTIME, &tp_end);
    std::cout << "reading : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    /******** 読み込んだデータをソート ********/
    Sort<Person> sort;

    clock_gettime(CLOCK_REALTIME, &tp_start);

    sort.merge_sort( &vec_people );

    clock_gettime(CLOCK_REALTIME, &tp_end);
    std::cout << "sorting : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    // ソート済み確認
    for ( int i = 1; i < vec_people.size(); i++ ) {
        if ( vec_people[i] < vec_people[i-1] ) {
            std::cerr << "ERROR" << std::endl;
        }
    }

    return 0;
}

Swift

import Foundation

class Person : Comparable{
    let id : Int
    let name : String

    init( id : Int, name : String ) {
        self.id = id;
        self.name = name;
    }

    init() {
        self.id = 0
        self.name = ""
    }

    func get_id() -> Int { return id }
    func get_name() -> String { return name }

};

func < ( left: Person, right: Person ) -> Bool {
    return left.get_name() < right.get_name()
}

func == ( left: Person, right: Person ) -> Bool {
    return left.get_name() == right.get_name()
}

class Sort<T:Comparable> {
    var buf : Array<T>
    var array : Array<T>

    init() {
        buf = [T]()
        array = [T]()
    }

    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    func merge( index_b: Int, index_c: Int, index_e: Int ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if index_b + 1 == index_e {
            if array[index_e] < array[index_b] {
                let tmp = array[index_e]
                array[index_e] = array[index_b]
                array[index_b] = tmp
            }
            return
        }

        // index_1とindex_2を動かしながら，小さい方を順次index_bufへ書き込む
        var index_1 = index_b
        var index_2 = index_c + 1
        var index_buf = index_b

        while true {
            if array[index_1] < array[index_2] {
                buf[index_buf] = array[index_1]
                index_buf += 1

                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if index_1 == index_c {
                    while index_2 <= index_e {
                        buf[index_buf] = array[index_2]
                        index_buf += 1
                        index_2 += 1
                    }
                    break
                }
                index_1 += 1
            } else {
                buf[index_buf] = array[index_2]
                index_buf += 1

                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if index_2 == index_e {
                    while index_1 <= index_c {
                        buf[index_buf] = array[index_1]
                        index_buf += 1
                        index_1 += 1
                    }
                    break
                }
                index_2 += 1
            }
        }

        // バッファから元配列へコピー
        for i in index_b ... index_e {
            array[i] = buf[i]
        }

        return
    }

    // 再帰的に呼び出す関数
    func merge_sort( index_b: Int, index_e: Int ) {
        let index_c = ( index_b + index_e ) / 2

        // 左側をソート
        if index_b != index_c {
            merge_sort( index_b:index_b, index_e:index_c )
        }

        // 右側をソート
        if (index_c + 1) != index_e {
            merge_sort( index_b:index_c + 1, index_e:index_e )
        }

        // 左と右をマージ
        merge( index_b:index_b, index_c:index_c, index_e:index_e )

        return
    }

    // mainから呼ぶソート関数
    func merge_sort( vec : inout [T] ) {
        // ソート対象の配列をメンバ変数にコピー
        array = vec

        // マージ中のソート結果を一時的に記憶するバッファ
        buf = vec

        // マージソート
        merge_sort( index_b:0, index_e:vec.count - 1 )

        // ソート済み配列をvecにコピー
        vec = array
    }

}

// 時間測定のための変数
var tp_start = timespec()
var tp_end = timespec()

/******** 標準入力からデータを読み込み ********/
var array_people = Array<Person>()
var id : Int
var name : String

clock_gettime(CLOCK_REALTIME, &tp_start)

extension String: Collection {}
while let input : String = readLine() {
    let values = input.split( separator: " " )
    array_people.append( Person( id: Int(values[0])!, name: values[1] ) )
}

clock_gettime(CLOCK_REALTIME, &tp_end)
print( "reading : \(Double(tp_end.tv_sec - tp_start.tv_sec) + Double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0)" )

/******** 読み込んだデータをソート ********/
var sort = Sort<Person>()

clock_gettime(CLOCK_REALTIME, &tp_start)

sort.merge_sort( vec : &array_people )

clock_gettime(CLOCK_REALTIME, &tp_end)
print( "sorting : \(Double(tp_end.tv_sec - tp_start.tv_sec) + Double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0)" )

// ソート済み確認
for i in 1 ..< array_people.count {
    if array_people[i] < array_people[i-1] {
        print( "ERROR" )
    }
}

結果

標準入力からの読み込みの部分とソーティングの部分のそれぞれの実行時間を計測しました。時間の計測には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++11/14の機能を使ってより効率的なコードを書くために良い書籍です。基本的な入門書ではなくC/C++をある程度理解していることが必須です。

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

Scott Meyers (著), 千住治郎 (翻訳)

amazon.co.jp