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

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

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

using namespace std;

int main(void)
{
    vector        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

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

少し間があきましたが、技術ネタで。
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秒間に数十億個の命令が実行できます。単純に計算しますと、メモリの確保は約千個の命令を使っており、関数呼び出しは約百個の命令を使うということになります。