システムアーキテクト通訳案内士のブログ

C++/STL 1GBのintのソートにかかる時間 2010

未踏の説明会の続きですが、説明会の中に技術的なセッションもありまして、グーグル株式会社のソフトウェアエンジニア　鵜飼さんの講演が面白かったのですが、その中で、『1GBのintのソートにかかる時間は、封筒の裏計算で、30秒』というのがありました。

パフォーマンスには一家言ある私ですが、さすがに1GBのintのソート時間にはピンと来ませんでした。
という訳で、ホントかどうかやってみました。

#include <vector>
#include <algorithm>
#include <iostream>
#include <time.h>

using namespace std;

int main(void)
{
    vector<int>        values;

    srand(time(0));
    // vectorに適当な値を入れる
    for ( int i = 0; i < 1024*1024*1024 / sizeof(int); i++ ) {
        values.push_back((int)(rand()*rand()-i));
    }

    // ソートする
    clock_t        t = clock();
    sort( values.begin(), values.end());
    cout << "Time(sort) is "
         << (double)(clock() - t) / CLOCKS_PER_SEC << "sec." << endl;

    return 0;
}

実行時間（Core i7-920 Windows7 コンパイルVC++2008 リリースモード 64ビットモード）は以下になります。上記のプログラムですが、32ビットモードでは動作しません。32ビットプロセスはリニアに1GBのメモリは確保できないです。

Time(sort) is 43.895sec.

なるほど、確かに30秒からそう離れていません。
ちなみに、この手の封筒の裏計算ですが、桁が違わなければOKと考えてよいでしょう。なので、細かい値の違いが問題になる場合は、実アプリでキチンとベンチマークをとるのがよいでしょう。
この手の結果の受け止め方ですが、おそらく一般の業務アプリを作成する人にとっては『理論的限界値』程度に思っていた方がよいでしょう。つまり

　1秒間に数百万個のint型のソートができる。数千万個になったら要注意。

と思っておけばよろしいかと思います。実際に私の経験でも行数が数百万件のソートをSQLで行うのはあまり問題になることはなかったです。（もちろんメモリが十分にあればの話ですが）。

実行時間の詳細ですが、説明では以下のとおりでした。
　・要素を比較する回数（ソートのオーダnlogn）から、
　　2^28 * log(2^28) → 2^28 * 28 → 2^28 * 2^5 → 2^33(2の33乗)回
　・比較に際してのL1キャッシュのアクセス時間 0.5ns / 回
　・比較に際してのブランチペナルティ 2.5ns / 回（2回に1回ペナルティがあると仮定する）

　実行時間 2^33 * (0.5 + 2.5)nsec = 25.76sec 約30秒

ただ、上記の計算ですが、ブランチペナルティが全体の速度を決定しているというのはいささか疑問があります。上記の場合、メモリのアクセス回数から計算した方が良いのでは？と思います。
つまり、
　・要素を比較する回数（ソートのオーダnlogn）から、
　　2^28 * log(2^28) → 2^28 * 28 → 2^28 * 2^5 → 2^33（2の33乗）回
　・ 比較に際してのメモリアクセス回数　2回（リード&ライト） 2*4バイト
　・キャッシュライン 32バイト

　・メインメモリへのアクセス回数　2^33 * 2 * 4 / 32 = 2^31 回
　・メインメモリアクセス性能　1回のアクセス 10nsec（DDR3のレイテンシーから）

　実行時間 2^31 * 10nsec = 21.47sec

うーん、数値的には似たり寄ったりであまり変わらないか・・・・

C++ オブジェクトを new/delete するコスト

少し間があきましたが、技術ネタで。
new/deleteは、C++はもとより、最近のプログラミング言語なら当たり前のようにやる（おっとdeleteはしないか）かと思いますが、そのコストについてはついつい忘れがちになります。

ADPは、C++で作成しているのですが、オブジェクトをリサイクルするように変更したところ、実行速度が倍ぐらいに速くなった。もともとは速くするために行った訳ではないのだが意外な副産物となった。

Visutal C++ではいつのころからか（遅くともVC++ 2003以降）、newすると最終的にはWindowsのAPIが呼び出される。パフォーマンスにシビアなシステムでは、ローカル変数の定義のようにお気楽に出来るものではないかもしれない。

といっても理屈だけではなんなので、具体的にどのくらいのコストがかかるかベンチマークしてみました。

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

class myobject {
    int    myvalue;
public:
    myobject() : myvalue(0){};
};

myobject    *myobjects[10*1000*1000];

int test(int v)
{
    return v * 1000;
}


int main(void)
{
    clock_t        t = clock();

    // new（1千万回）
    t = clock();
    for ( int i = 0; i < 10 * 1000 * 1000; i++ ) {
        myobjects[i] = new myobject();
    }
    cout << "Time(new) is "
         << (double)(clock() - t) / CLOCKS_PER_SEC << "sec." << endl;

    // delete（1千万回)
    t = clock();
    for ( int i = 0; i < 10 * 1000 * 1000; i++ ) {
        delete myobjects[i];
    }
    cout << "Time(delete) is "
         << (double)(clock() - t) / CLOCKS_PER_SEC << "sec." << endl;

    // 関数呼出し（1千万回)
    t = clock();
    for ( int i = 0; i < 10 * 1000 * 1000; i++ ) {
        test(i);
    }
    cout << "Time(function call) is "
         << (double)(clock() - t) / CLOCKS_PER_SEC << "sec." << endl;

    return 0;
}

以下、実行結果（Core i7-920 Windows7 コンパイルVC++2008 デバッグモード）

Time(new) is 2.065sec.
Time(delete) is 2.35sec.
Time(function call) is 0.26sec.

Windows環境でC++だと、おおむね1秒間に約数百万個のオブジェクトが作れるようです。また、関数呼び出しは数千万回できるようです。
上記の実行結果はデバッグ環境で行っていますので、リリースモードで実行するとこれから数倍速くなります。
この手の数字にピンとこない人の為に補足しますと、最近のコンピュータは1秒間に数十億個の命令が実行できます。単純に計算しますと、メモリの確保は約千個の命令を使っており、関数呼び出しは約百個の命令を使うということになります。

C++/STL 正規表現の置換－boost::Regex_replace

１年ぶりのC++/SLTネタです。

正規表現での置換ですが、ちょっとハマったのでメモ書きします。以下、srcstrで与えられたstringに対して,fstr(正規表現）の検索を行い、repstrで置換します。マッチする文字列全てを置換します。結果の文字列はdststrで返します。

void replace_regex_all(
    string &srcstr, const char *fstr, const char *repstr, string &dststr)
{
    string tmp;
    boost::regex fnd(fstr);
    ostringstream t(ios::out | ios::binary);
    ostream_iterator<char, char> oi(t);
    boost::regex_replace(
        oi,
        srcstr.begin(),
        srcstr.end(),
       fnd,
       repstr,
       boost::match_default | boost::format_all);
    dststr = t.str();
}

SQLの実行パフォーマンスについて 2010

＠IT エンジニアライフのコメンテータ（だった）生島さんのコラムhttp://el.jibun.atmarkit.co.jp/g1sys/2010/05/post-2d1b.htmlのコメント欄に参加しました。

生島さんのコラムですが、過去に度々炎上してきましたが、炎上するたびに、

『SQLはオブジェクト指向言語の数十倍の効率』

という、この手の話が出てきます。この手の呪文は他にも幾つかあるのですが、これを出せば議論が終結するというある種の必殺技みたいに使われます。
が、それどころか、毎回、毎回、明確な結論が出ずにさらにコメント欄が荒れます。
私としては、本来はどうでもよい話なのですが、いきがかり上、私も思わず、

「私は、過去にSQLが遅いのでSQLを崩して、C言語でJOINをやらせて高速化しました。OO言語ではないですが、今だったらC++を使うでしょう（なぜってハッシュクラス があるから）。」
と発言しました。恐らく、多くの方は、

『いやいや、いくらなんでも、それはウソでしょう。』
とか、
『売り言葉に買い言葉でしょうが、それは良くないでしょう。』
とか、
『幾らC++が好きって言ったって、原理的にDBMS内で処理が閉じるSQLの方が速いでしょう。』
とか思われたことでしょう。

私も、そういうツッコミが来ることは重々承知していたのですが、現実に私は10年以上前になりますが、上記のような最適化を行ったことがありました。
以来、別にわざわざSQLを崩してCでJOINなんて事はしませんでしたが、逆にその後、さまざまなプロジェクトを通して、DBMSの動作をみる限り上記の最終手段は、まだ有効だなというのも実感としてあったのですが、あまりの共感の得られ無さにものすごい孤独感に襲われ、また生島さんの煽りも受け、このあたりで白黒はっきり付けたいと思います。


では、どのように白黒つけるのかですが、やはりベンチマークテストを行ってみるしかないかと思います。

つまり、生島さんが件のコラムのコメント欄に書かれた

TABLE_A a
INNER JOIN TABLE_B b
　　　　a.KEY = b.KEY

をもとにしたSQLをC++で書き実際に実行させてその実行時間をみてみましょう。

■実験の環境

　＜追記＞この記事のコメント欄の指摘（サーバーとクライアントマシンが分かれていない）および環境が変わったので再現できない関係で、新しく環境を構築してテストをやり直しました。
　今回実験したテスト環境を示します。

■実験するSQLとプログラムの概要

以下のSQLを実行させ、カンマをセパレーターとして標準出力へ出力させます。
CSVファイルへの出力を想定したSQL、JOINの部分は生島さんがコメント欄で指摘したSQLそのものになっています。このSQLをもとにJOIN部分をC＋＋でやらせてみます。

SELECT Price.CODE, RDATE, OPEN, CLOSE, NAME
FROM Price INNER JOIN Company ON (Price.CODE = Company.CODE)

■実験１　素直にSQL側でJOINをさせたものを実行

　以下のコードのとおり、実験するSQLをそのまま実行してみました。

#include <iostream>
#include <time.h>
#include "../kz_odbc.h"

using namespace std;

int main(void)
{
    kz_odbc db("DSN=Trade",true);
    kz_stmt stmt(&db);

    time_t  t = time(NULL);

    // テーブルからデータの取得
    stmt, "SELECT Price.CODE, RDATE, OPEN, CLOSE, NAME "
          " FROM Price INNER JOIN Company ON (Price.CODE=Company.CODE)"
          , endsql;
    kz_string_array result = stmt.next();
    int             cnt = 0;
    while ( !result.empty() ) {
        cout << result[0] << "," << result[1] << ","
             << result[2] << ","  << result[3] << ","
             << result[4] << "\n";
        result = stmt.next();
        cnt++;
    }

    cerr << "Execute time is " << time(0) - t << "sec." << endl;
    cerr << "Record count is " << cnt << "." << endl;
    return 0;
}

コードですが、Wordpressに合わせて編集してますので、変なところで改行が入っていますが御勘弁を。
　若干ですが、コードの説明を、
　stmt, "SELECT ・・・・
　とか
　result.empty()
　stmt.next()
の部分が私が作成したライブラリになります。といってもODBC APIを呼び出しているだけになります。そう特異なものでもないかと思います。
　実行結果ですが、

Execute time is 131sec.
Record count is 4671568.　　

　となりました。プログラムは標準出力に出力していますが、実行に際しては標準出力をファイルにリダイレクトしています。その方が実行速度は速くなります。
　比較元のデータが無いので何とも言えませんが、1秒間に約3万5千件のデータがCSVファイルへ落とされているのでマシンスペックを考えますとまずまずでしょう。
ちなみに、実行ブランを確認しましたが、CompanyテーブルへのアクセスのTYPEはeq_refでユニークキーによるJOIN（最速のテーブルアクセス）が実行されていることを確認しました。

■実験２　C++側でネステッドループでJOINさせてみる

　ループループといっていたものですが、いわゆるネステッドスープのことだと推測します。

#include <iostream>
#include <time.h>
#include "../kz_odbc.h"

using namespace std;

int main(void)
{
    kz_odbc db("DSN=Trade",true);
    kz_stmt stmt(&db);
    time_t  t = time(NULL);

    // テーブルからデータの取得
    stmt, "SELECT CODE,RDATE,OPEN,CLOSE FROM Price", endsql;

    kz_string_array result = stmt.next();
    int                cnt = 0;
    while ( !result.empty() ) {
        // JOINの実行（ネステッドループ）
        kz_stmt    stmt2(&db);
        stmt2, "SELECT NAME FROM Company WHERE CODE = ? "
             ,  result[0].c_str(), endsql;
        kz_string_array result2 = stmt2.next();

        cout << result[0] << "," << result[1]  << ","
             << result[2] << ","  << result[3] << ","
             << result2[0] << "\n";
        result = stmt.next();
        cnt++;
    }

    cerr << "Execute time is " << time(0) - t << "sec." << endl;
    cerr << "Record count is " << cnt << "." << endl;
    return 0;
}

実行結果は以下のとおりです。

Execute time is 1714sec.
Record count is 4671568.

　これはものすごく遅いですね。生島さんが、
『SQLにすると数十倍速くなる』
といっていたのは、実験１のコードと実験２のコードを比べて言っていたと思われます。
では、これ以上に速くさせる方法はないのでしょうか？
生島さんの言うとおり、OO言語はSQLと比べて何十倍も遅いのでしょうか？

■実験３　C++側でハッシュJOINさせてみる

　件のコメント欄で生島さんが難しいとおっしゃっていた、ハッシュJOINですが、実は特段、難しいものではありません。
　以下のようにすっきりと実装できます。
　ちなみにコード中に出てきますmapというのはバイナリサーチを行います。なので、正確にはハッシュJOINではありません。
　C++でハッシュ検索を行うには、Boost等のライブラリを使う必要があります。
　つまり今回のコードはある意味、最適化の余地を残しているのですが、ここではテストの再現性（環境設定）の手間を考えてmapを使います。

#include <iostream>
#include <time.h>
#include "../kz_odbc.h"

using namespace std;

int main(void)
{
    kz_odbc db("DSN=Trade",true);
    kz_stmt stmt(&db);

    time_t  t = time(NULL);

    // マスターの取得・マップの作成
    map< string, string>    company;
    stmt, "SELECT CODE, NAME FROM Company  ",  endsql;
    kz_string_array result = stmt.next();
    while ( !result.empty() ) {
        company.insert( pair< string, string>( result[0], result[1]) );
        result = stmt.next();
    }

    // テーブルからデータの取得
    stmt, "SELECT CODE,RDATE,OPEN,CLOSE FROM Price ", endsql;
    result = stmt.next();
    int                cnt = 0;
    while ( !result.empty() ) {
        cout << result[0] << "," << result[1] << ","
             << result[2] << ","  << result[3] << ","
             << company[ result[0] ] << "\n";
        result = stmt.next();
        cnt++;
    }

    cerr << "Execute time is " << time(0) - t << "sec." << endl;
    cerr << "Record count is " << cnt << "." << endl;
    return 0;
}

　結果ですが、以下のとおり、実験１のコードよりも早くなっております。

Execute time is 108sec.
Record count is 4671568.

■結果

実行結果を再度以下に掲載します。
　

実験１（SQL)	131秒
実験２（C++側でネステッドループ）	1714秒
実験３（C++側でハッシュ）	108秒

　明確に結果が出ているかと思います。こんなに単純なテストの結果からでも
　「SQLをばらしてJOINをC++で行えば速くなる場合がある」
ということは理解していただけれるかと思います。
また、
『SQLはオブジェクト指向言語の数十倍の効率』
というのは、単純に
　「OO言語側の最適化が不十分である可能性がある」
ということも言えるでしょう。

ただ、実験３では、高々十数%しか速くなっていません。
ということであれば、通常はやはり実験１のようなコードの方がトータル（開発効率と実行効率を考えると）としては良いと思われる。実験３のような事実はあくまでも知識としてしておきたいところです。

追記、コメント欄の議論を踏まえて再度記事をアップしました。
追記、コメント欄の指摘（ローカルマシンで動かしている）を受けまして再度環境を作成して実験しました。
追記、まとめ記事を作成しました。

C++/STLで数値の3桁区切り

久しぶりのC++/STLネタです。今回は数値の3桁区切りをやってみました。
ネットを探すとCのサンプルはあるのですが、少々トリッキーなコーディングのものが多いので、C++でのベタな実装というとこで作ってみました。

/**********************************************************************
　数値の3桁区切り
 試したコンパイル環境
    VC++ .NET 2003 / WINDOWS XP Professional 64 bit edition.
    GCC C++ 3.3.6 / glibc 2.3.4 / Vine Linux 4.2
**********************************************************************/

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <sstream>

std::string formatNumber(int num)
{
    std::vector<int>    sepnum;
    int                 number = abs(num);
    int                 sgn = num >= 0 ? 1 : -1;

    while ( number / 1000 ) {
        sepnum.push_back(number % 1000);
        number /= 1000;
    }

    std::stringstream  ss;
    ss << number * sgn;
    for ( std::vector<int>::reverse_iterator i = sepnum.rbegin();
                                        i < sepnum.rend(); i++ ) {
        ss << "," << std::setfill('0') << std::setw(3) << *i;
    }
    return std::string(ss.str());
}

using namespace std;
int main(int argc, char* argv[])
{
    cout << formatNumber(0) << endl;
    cout << formatNumber(1) << endl;
    cout << formatNumber(12) << endl;
    cout << formatNumber(123) << endl;
    cout << formatNumber(1234) << endl;
    cout << formatNumber(12345) << endl;
    cout << formatNumber(123456) << endl;
    cout << formatNumber(1234567) << endl;
    cout << formatNumber(12345678) << endl;
    cout << formatNumber(123456789) << endl;
    cout << formatNumber(1234567890) << endl;
    cout << formatNumber(-1) << endl;
    cout << formatNumber(-12) << endl;
    cout << formatNumber(-123) << endl;
    cout << formatNumber(-1234) << endl;
    cout << formatNumber(-12345) << endl;
    cout << formatNumber(-123456) << endl;
    cout << formatNumber(-1234567) << endl;
    cout << formatNumber(-12345678) << endl;
    cout << formatNumber(-123456789) << endl;
    cout << formatNumber(-1234567890) << endl;

}