2014年6月21日土曜日

C++11 スマートポインタの使い方・用途・サンプル

C++はガーベジコレクションがないので、動的にallocateしたオブジェクトは明示的にdeallocateしなければなりません。これを怠るとメモリリークなどもの問題が出てくるわけです。また逆に、オブジェクトを破棄したポインタを使いつづけるとnullポインタ、或いはダングリングポインタとしてエラーの原因になります。

C++において生来的ともいえるこれらの問題を解決しようというのがスマートポインタの機能です。簡単に言うと、ポインタのスコープに合わせてオブジェクトが勝手にdeallocate(deconstruct)されます。これによってオブジェクトとポインタの寿命が一致するのでメモリリーク、ダングリングポインタが防げます。

スマートポインタには何種類かあり、それぞれ異なる仕様・用途があります。以下、unique_ptr, shared_ptr, weak_ptr, auto_ptr(C++11以前)の説明をします。


1. unique_ptr

一番使われるのはunique_ptrでしょう。以上に述べたスマートポインタの特徴に加え、名の通り「指しているオブジェクトに対する唯一のポインタ」であることを保証します(低レベルで色々やれば崩せますが)。即ち、unique_ptrは他のスマートポインタからオブジェクトをコピーしたりアサインしたりすることが出来ません。

オブジェクトを他のポインタに割り当てたい場合はstd::moveを使う必要があります。これを使うと元のポインタはnullポインタになるので、やはり一つのポインタしかそれを指すことが出来ません。

以下のコードのように、いちいちdeleteなどしなくても使うことができます。


void unique_ptr_test() {
    cout << "----- unique_ptr test -----" << endl;
    std::unique_ptr<int> first(new int(1));
    std::unique_ptr<int> second(new int(2));

    // 関連して、nullptrも新しく加わった。0, NULLと区別される。
    std::unique_ptr<int> nullpo(nullptr);

    cout << "*first = " << *first << endl;
    cout << "*second = " << *second << endl;

//    std::unique_ptr<int> second = first; ERROR: コピーは出来ない。
//    second = first; ERROR: アサインも出来ない。

    // moveを用いることでオブジェクトをsecondに移すことが出来る。
    // そのとき、firstはnullptrになるので注意。
    // つまり、unique_ptrを参照できるポインタは常に一つである。(定義より)
    second = std::move(first);
    cout << endl << "second = std::move(first);" << endl << endl;
    cout << "*fisrt = " << (first? "not null" : "null") << endl;
    cout << "*second = " << *second << endl << endl;

    cout << "nullpo is " << (nullpo? "not null" : "null") << endl;

    // unique_ptrはスコープの外に出るときにdeconstructorを呼ぶ。
    {
        std::unique_ptr<Foo> locale(new Foo());
    }
}


2. shared_ptr

unique_ptrの使いやすさの一つに「オブジェクトを指す唯一のポインタ」であることがあるでしょうが、逆にそうでない方が使いやすい場合もあるでしょう。複数のスマートポインタで同じオブジェクトを指したい時に使われるのがshared_ptrです。

shared_ptrはunique_ptrと異なり、コピー・アサインをすることができます。また、オブジェクトを指している複数のshared_ptrのうちの一つだけを初期化したい場合にreset()を呼ぶことで、そのオブジェクトを破棄せずに(それによって他のポインタがnullポインタにならずに)そのポインタだけをnullポインタにすることができます。

また、共有されているオブジェクトはshared_ptrの全てがスコープから外れた時に破棄されます。



void shared_ptr_test() {
    cout << "----- shared_ptr test -----" << endl;
    std::shared_ptr<Foo> first(new Foo());
    std::shared_ptr<Foo> copy = first;

    // copyがまだあるのでresetでもオブジェクトは持続される。
    // しかしfirstはnullポインタになる。
    first.reset();
    cout << "first = " << (first? "not null" : "null") << endl;
    cout << "copy = " << (first? "not null" : "null") << endl;

    // copyもreset()が呼ばれるとdestructor
    copy.reset();
}


3. weak_ptr

 weak_ptrはshared_ptrをサポートするスマートポインタです。
weak_ptrはshared_ptrが指しているオブジェクトを同様に指すことが出来ます。しかし、先ほどshared_ptrの指すオブジェクトは、「shared_ptrの全てがスコープから外れたら破棄される」とありましたが、つまりweak_ptrが指していても、shared_ptrが全てなくなれば破棄される、ということです。

ではweak_ptrは何に使われるのかというと、 shared_ptrを用いてオブジェクトを破棄して新しいオブジェクトをconstructしたり、という流れの中で使われます。つまり、weak_ptrでshared_ptrのオブジェクトを参照しておき、それからshared_ptrで新しいオブジェクトをallocateすると、weak_ptrはNullを指すことになります。使ってみるとこれが便利な場合が結構あります。



void weak_ptr_test() {
    cout << "----- weak_ptr test -----" << endl;


    // 通常のポインタはDangling pointerとなるリスクがある。
    // 例えばここでrefはdangling pointerである。
    int* ptr = new int(10);
    int* ref = ptr;
    delete ptr;

    // それに対して、
    // weak_ptrは対象のオブジェクトがdeallocateされたかをexpired(), lock()で確認することが出来る。

    std::shared_ptr<int> sptr;
    // takes ownership of pointer
    sptr.reset(new int(10));

    // weak1は*sptrを参照はするが、保持はしない。
    std::weak_ptr<int> weak1 = sptr;

    // 前のオブジェクトを破棄し、新しいオブジェクトを作る。
    // ここでweak1がshared_ptrなら一緒に5を指すことになるが、ここではweak_ptrなので参照オブジェクトがなくなる。
    sptr.reset(new int(5));

    // 5を指すweak_ptr
    std::weak_ptr<int> weak2 = sptr;


    // weak1の指していたオブジェクトがdeallocateされたかはlock()で確認することが出来る。
    if ( auto tmp = weak1.lock() ) {
        std::cout << "weak1.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak1 is expired\n";
    }

    if ( auto tmp = weak2.lock() ) {
        std::cout << "weak2.lock() = " << *tmp << '\n';
    } else {
        std::cout << "weak2 is expired\n";
    }

}


4. auto_ptr (C++11以前)

 auto_ptrはレガシーです。簡単に言うならunique_ptrの下位互換です。C++11以前からあるので(これを発展させたものが今まで説明してきたスマートポインタら)、C++11を使いたくない事情がある場合に代用として使えます。基本的に使い方はunique_ptrと同じです。ただ隠蔽構造がやや不完全で、例えば以下のコードだとy = xでunique_ptrのy = std::move(x)に当たり、ここでxはnullポインタになるので、なかなか注意が必要な構造をしています。



void auto_ptr_test() {
    cout << "----- auto_ptr test -----" << endl;
    auto_ptr<int> x(new int(5));
    auto_ptr<int> y;

    y = x;

    cout << "x is " << (x.get() ? "not null" : "null") << endl; // Print NULL
    cout << "y is " << (y.get() ? "not null" : "null") << endl; // Print non-NULL address i
}


スマートポインタは通常のポインタと比べてそんなに遅くないそうです(アセンブリにして追加一行程度とのこと)。特にパフォーマンスが求められていない部分のコードは手軽く使っていけるようです。

2014年6月10日火曜日

Zobrist Hashing

Zobrist Hashingは将棋やチェスなどで用いられる、状態をハッシュ値に落とし込む方法です。

というのも将棋やチェスのような状態のハッシュ値を計算する場合、n進数や辞書順によるハッシュ関数では状態空間に対してハッシュ値を不偏的に散らすことはなかなか難しいです。そこでZobrist Hashingは乱数とXORを使って不偏性を作り出します。


WikipediaのZobrist Hashingの擬似コードを引用します。


   constant indices
       white_pawn := 1
       white_rook := 2
       # etc.
       black_king := 12
   
   function init_zobrist():
       # fill a table of random numbers/bitstrings
       table := a 2-d array of size 64×12
       for i from 1 to 64:  # loop over the board, represented as a linear array
           for j from 1 to 12:      # loop over the pieces
               table[i][j] = random_bitstring()
   
   function hash(board):
       h := 0
       for i from 1 to 64:      # loop over the board positions
           if board[i] != empty:
               j := the piece at board[i], as listed in the constant indices, above
               h := h XOR table[i][j]
       return h
(Wikipediaより: http://en.wikipedia.org/wiki/Zobrist_hashing)


・init_zobrist
まず下準備として、予めパズルの各マスに対してランダムビットstringを定義する。
例えば将棋なら、
7六に歩がある状態を 0100 0111 のように定義する。
7七に角がある状態を 1001 1100...
のように全てのマスの、全てのありうる状態に対するキーの値をテーブルに保存する。(以後テーブル値とする。)


・hash(board)
全てのマスの状態に対して定義されたテーブル値をビット毎のXORでかけていく。


さて、このZobrist Hashingの特徴を見ていきましょう。

まず、Zobrist HashingはPerfect Hashingである保証は全くありません。盤が違う状態でも同じハッシュ値になり得ます。簡単な例だと
0000 XOR 0011 = 0011
0100 XOR 0111 = 0011
ですので。

・そこから一歩進んで、このハッシュ関数は同じフレームワークの中でビット長を変えることでハッシュの重複度を変化させることが出来ます。つまり、ビットを長くするほど違う盤の状態が同じハッシュ値を持つ割合(確率)を小さくさせることが出来ます。これは当然計算速度とメモリ量のトレードオフになります。

・n進数や辞書順によるハッシュ関数と比較して、盤の状態に対して偏りのないハッシュ値が得られることが多い。Bitwise XORなのでハッシュ値のビットストリングの各桁は、全てのマスの状態の関数なので、全てのマスのテーブル値を参照した結果の値といえる。ただしここで注意しなければならないのは、必ず偏りがないハッシュになるとは限らないということです。それは状態空間の性質にもよりますし、乱数の揺れにも依存します。



天才的な発想ですよね。どの位実用されているのかはよく知らないのですが、こういうアイディアの出せる人間になりたいものですね。




C++で簡単なサンプルを実装をしたものが以下のコードです。





/*
 * zobrist.cc
 *
 * Short sample to test Zobrist hashing.
 * Zobrist hashing is a hash function construction for abstract board games.
 *
 *
 *  Created on: Jun 10, 2014
 *      Author: Yuu Jinnai
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INDICES 16
#define SIZE 32

void initZobrist(int* table);
void initRandomBoard(int* board);
int hash(int* board);

int* table;

int main() {

 srand(time(NULL));
 table = new int[SIZE*INDICES];
 initZobrist(table);

 int* board = new int[SIZE];
 for (int i = 0; i < 10; ++i) {
  initRandomBoard(board);
  printf("hash(board) = %d\n\n", hash(board));
 }

}

void initZobrist(int* table) {
 for (int i = 0; i < SIZE; ++i) {
  for (int j = 0; j < INDICES; ++j) {
   table[i+SIZE*j] = rand();
   printf("table[%d][%d] = %d\n", i, j, table[i+SIZE*j]);
  }
 }
}

void initRandomBoard(int* board) {
 for (int i = 0; i < SIZE; ++i) {
   board[i] = rand() % INDICES;
   printf("%d ", board[i]);
 }
 printf("\n");
}

int hash(int* board) {
 int h = 0;
 for (int i = 0; i < SIZE; ++i) {
  h = (h ^ table[i+SIZE*board[i]]);
 }
 return h;
}


2014年5月29日木曜日

コンピュータサイエンス

コンピュータサイエンスというのは色々なパラダイムが共存しているように思えます。

論理学や離散数学の延長といえるものもありますし、UIなど認知に伸びていく分野も多いですし、そもそもサイエンスといいつつ工学的な応用が非常に大きな部分を占めているように思えます。そうするとコンピュータサイエンスというくくりは大きすぎるのかもしれませんね。

それでも、ゴールは多岐に渡っても学ぶべきスキルというのはある程度収束するものだと思います。つまり共有できるツールや枠組みというのはあるのでしょう。やはり基礎から学ぶというのは定石の一つだと思います。イメージとしてはピラミッド型に伸びている科学技術の要の部分から学ぶということです。

さて、では基礎を学ぼうとしたときに、じゃあ基礎って何なんでしょうか。思うに本屋に並ぶ本はアプリケーションレベルのものばかりで、むしろ末端を深く解説するものが置かれている印象です。だからといってアプリケーションを作りたい人が記号論理学とかを学ぶにはモチベーションがないとやってけないように思えます。


ということでまずはコンピュータサイエンスを俯瞰するという作業がまず必要になるでしょう。どういう分野があって、どういう内容をやっていて、それらはどう関連しているのか。

お勧めの教科書はこちら。



一冊でだいたいの俯瞰が出来るようになります
Cやjavaなどの高レベル言語が物理レベルまでどう翻訳されていくか、コンピュータが下部構造をいかに隠蔽してあるか、丹念に説明されています。


あとはADUniがおすすめです。
これは元々、他分野のバックグラウンドを持つ学生に一年間で情報科学を一通り教えるというコンセプトで生まれたプログラムです。各分野を体系立って学ぶことが出来ます。前述の教科書を見て面白いと思う分野があればこっちでもっと深く学ぶというのが良い方法だと思います。



2014年5月24日土曜日

プロファイラを使ってみよう

プロファイラって使ってますか?

なんか思ったよりもっさり動いているなぁという時に思いつくがままに改良してみて、あまり上手くいかないというのは、改良している部分がプログラムのボトルネックではないからです。

しかしプログラムの中のどの部分が時間を食っているのかは分かりづらいこともあります。

そこで便利なのがプロファイラ。
プロファイラは実行されたプログラムの関数ごとの計算時間、呼び出し回数などなとを計測するかなり便利な代物です。

ここでは例としてgnuのg++プロファイラ、gprofの使い方を説明します。
使い方の手順としては、


1. -pgオプションをつけてコンパイルする。 
g++ -pg main.cc

2. 実行する。 
./a.out

3. gprofを実行する。
gprof a.out


とするだけでプログラムの各関数の消費時間が空間的に理解できるように表示されます。

gprof出力の全文を載せるとちょっと詳細過ぎるのでここでは一番に見るべき情報に絞ります。

Flat profile: 各関数で結局どのくらい時間がかかったのか。
Call graph: 各関数がどのように他の関数から呼ばれたか。


Flat profile:

Each sample counts as 0.01 seconds.
%        cumulative self           self    total
time  seconds       seconds calls  s/call  s/call  name
67.15 30.77         30.77     2    15.39  23.14    f2
33.82 46.27         15.50     1    15.50  15.50    f1
0.07   46.30         0.03                          main

Call graph (explanation follows)

granularity: each sample hit covers 2 byte(s) for 0.02% of 46.30 seconds

index   %time        self  children  called  name

[1]     100.0        0.03   46.27             main [1]
                     30.77  15.50     2/2      f2 [2]
-----------------------------------------------------
                     30.77  15.50     2/2      main [1]
[2]     99.9         30.77  15.50     2      f2 [2]
                     15.50   0.00     1/1      f11 [3]
----------------------------------------------------
                     15.50   0.00     1/1      f2 [2]
[3]        33.5      15.50 0.00       1      f1 [3]
-----------------------------------------------
この辺りを見ればどの関数を手直しすべきか分かると思います。
プロファイラはユニットテストみたいに使うと便利なんじゃないかと思います。
つまり、


1. コードを改善する。

2. 実行してプロファイラにかける。

3. プロフィールを分析し、次に改善すべき関数を決める。


のイテレーションを行えば効率良く質の高いコードがかけます。

とにかくはしから改善していけばいいじゃないか、という考えもありますが、アムダールの法則をみるに、ボトルネックとなっている関数から改善するという考えの方がプログラマ的なんじゃないかなと思います。

複数人の開発なら端から改善していく、TOYOTA生産方式というのは有用でしょうが、一人の開発の場合資源の投下場所は考慮すべきでしょう。

2014年5月21日水曜日

データ構造とアルゴリズム

データ構造とアルゴリズムの本は五万とありますね。アプリケーションレベルに近いほど多様性を増していくというのは書籍の数にも表れますね。

しかし考えてみると、データ構造やアルゴリズムというのは離散数学なので、例えばマージソートの説明の仕方にそんな五万通りもあるようには思えません。

逆に、アルゴリズムを学ぶメリットというのはアルゴリズムが汎用的であり、一度根幹を学べば同じフレームワークを似た問題で何度も使えるというところにあると思います。

つまるところ、汎用的で再利用可能であることが特にアルゴリズムを学ぶべき理由であると思います。そうすると、javaアルゴリズムだとかC++アルゴリズム事典だとかいう本はややアドホックにすぎるように思えます。

でもこういうアドホックな本が出回るのは自然なことで、アルゴリズムが抽象的すぎて学習しずらいということは大いにあるでしょう。目的からの距離が遠いですから。

データ構造とアルゴリズムで一番評判の高い本はIntroduction to Algorithmsでしょう。


しかしこの鈍器に等しい厚さの数学書を一人で全て理解しきることが出来る人はそんなにいないでしょう。

そこで、なんとも素晴らしいことに、MITOPENCOURSEWAREでこの本の講義が開かれております。

Introduction to Algorithms MIT OPEN COURSEWARE



You TubeのVideo Lectureに比べて充実しているのは、Video Lectureだけでなく講義ノート、宿題や試験とその解答まで公開されていることです。MITの学生と殆ど変わらない学習環境になるんじゃないでしょうか。


もっと薄い和書だとデータ構造とアルゴリズム(杉原厚吉)とかがコンパクトにまとまっています。しかし薄いということは内容が凝縮されていることであって必ずしも簡単だとは限らないと思います。いずれにせよ上の洋書があまりにもきついという人はこちらから初めてもよいように思います。



2014年5月18日日曜日

コンピュータアーキテクチャ

今や大学の授業はタダで受けられる世界です。

テキストファイルのチュートリアルはいくらでもあるし、動画ならCoursera, iTunes, Youtubeで見られる。具体的に知りたいことがあるならgoogle検索で調べればいいし、見つからなければStack Overflowに聞けばいい。

ただ、こうなってくるとどう手をつけていいか分からなくなってきますよね。情報がありすぎると今度は適切なMiningをする必要が出てきます。

ということでData Miningの話も面白いと思うのですが、今日はComputer Architectureを学ぶための1セットをまとめてみました。

・Computer Architecture - Carnegie Mellon

カーネギーメロンのコンピュータの授業です。
これを見れば少なくともアプリケーションレベルのプログラマは困ることはないんじゃないかと思います。35回×1.5時間なのでかなりしっかり学ぶことが出来ます。そんなに時間をかけられないという人でも最初の2、3回だけでも見るべきだと思います。コンピュータアーキテクチャの概念とか目的といったものが非常に明瞭に分かります。Trade-offや隠蔽のヒエラルキーなどの本質的な考え方というのは本では学びにくいことなので。

Computer Architecture Video Lecture


・Computer Organization and Design (Patterson & Hennessy)

世界的に有名でコンピュータアーキテクチャの金字塔といえる教科書です。

しかし、この本、声を大にして言わなければならないのは、日本語訳があまりにもひどすぎる!和訳版は残念ながら学術書ではない。(こんな価値の高い教科書がこんな訳で出てしまう限り日本のIT技術がアメリカに追いつくことはないだろう・・・)

ので原著を強くお勧めします。アセンブラ、ISA、 プロセッサまわりの説明が充実し手織り、今後必ず必要になるであろう並列プログラミングを真に実現するのに非常に役に立つ教科書だと思います。

また、上のCarnegie Mellonの講義でも教科書的に使われていますので、この本を読みつつ講義を見れば、理解がいっそう深まるかと思います。


しかしこの本の翻訳の問題はもっと根が深いでしょうね。
IT関連で何か検索すると英語でした方が100倍位情報があるというのは非常に大きな問題でしょう。もう日本語で科学やビジネスは出来ないということなのでしょうか。

・CPUの創りかた

なんとも人を選ぶ表紙で、キャッチーなだけの中身のない本かと思ってしまいますが、とても面白い本です。かなり本格的な理論を学びつつ、手を動かして4BitCPUを作ることが出来ます。

4bitCPUなのでもちろん実用性はないのですが、ゲートや回路レベルからCPUレベルまでの階層がどうなっているのかを理解するのに非常に役立ちます。

この本を学べば結構本格的な電子工作も出来るようになると思います。というかこの類の本でこんなにAmazonのレビューが高いというのも驚きです。


ということでコンピュータアーキテクチャのまとめでした。

この流れでコンピュータサイエンスを俯瞰していこうかなって考えています。

2014年5月11日日曜日

Mutex Profiler Mutrace

プロファイラはコードのパフォーマンスをあげるのにとても役立ちます。コードのどこに時間がかかっているのかが非常に明瞭にわかるからです。

並列計算のパフォーマンスも一般的なプロファイラでかなり分かることがたくさんありますが、同期処理などのオーバーヘッドを見出すのは結構難しいです。
また、ロックをもっと細かくするにせよatom型を使うにせよ、そのような同期処理を改善するのは結構手間がかかるしどちらが速いか見積りずらいことは多々あります。

そういうときに便利なのがmutrace、Mutex Profilerです。

実行ファイルと一緒に使い、mutexのロック回数、ロックの推移回数、合計待ち時間、ロックの種類などを列挙してくれます。ので改善すべきロックが一目瞭然で分かります。

$ mutrace gedit

とシンプルなコマンドで使えます。出力はこんな感じ。
mutrace: 10 most contended mutexes:

 Mutex #   Locked  Changed    Cont. tot.Time[ms] avg.Time[ms] max.Time[ms]       Type
      35   368268      407      275      120,822        0,000        0,894     normal
       5   234645      100       21       86,855        0,000        0,494     normal
      26   177324       47        4       98,610        0,001        0,150     normal
(公式ページより引用)

こんな感じで出たら、35番のロックは改善した方がいいかな?って絞ることが出来るという訳です。
便利。
・参照リンク
公式ページ
mutraceのGitレポジトリ