すごくいまさらなんですが.
もう1年以上も前になるかな,GoogleのC++のスタイルガイドというのが公開されて,なかなか読む暇が無くてずっとあとで読む上体だったんだけど,昨日ちらっと読んでみたらなかなかおもしろくて寝不足なのです.

いくつか個人的におもしろかったところをピックアップするというか,忘れないためにメモっておこうと思う.

ちなみに参照したサイトは以下です.
Google C++スタイルガイド 日本語訳

インライン関数

インライン関数を定義するのは関数が小さいときのみ(10行以下)にする。

個人的にはinline関数はほとんど使わないから,このキモチがよくわからないんだよなあ.inlineにしなくてもコンパイラが結構最適化してくれることが多くて,経験上ほとんどスピードが変わらないということが多い.inlineがどういうときにもっとも有効なの
かって,まだ僕には結論を言うほどC++に詳しくないのだけれども,この件に関しては賛否両論ありそうだよなあ.僕は依然inlineは相当最適化しなけばならない時以外考えません.

コンストラクタでやるべきこと

コンストラクタでやることは簡単な初期化だけにする。もし簡単でなければ、できる限り Init() メソッドを使うこと。

定義:  コンストラクタ本体で初期化をすることができる。

賛成: 入力に好都合。クラスが初期化されているかどうかを気にする必要がなくなる。

反対: コンストラクタで初期化をするのには、いくつか問題がある。

    * 例外以外にコンストラクタがエラーになったことを知る簡単な方法がない(外を使うことは禁止されている)。
    * もし処理に失敗すると、初期化が完了していないオブジェクトが得られてしまう。このオブジェクトは不定状態になるおそれがある。
    * もしコンストラクタで仮想関数を呼び出していると、この呼び出しはサブクラス実装に対してディスパッチされない。 たとえ今のところはサブクラス化されていなくても、後になってサブクラス化したときにこの問題が入り込んでしまい、大きな問題になるおそれがある。
    * 誰かがクラス型のグローバル変数を作ってしまうと(これはルールに反しているが、それでも作ってしまった場合)、コンストラクタのコードは main() 関数よりも前に呼び出されることになる。おそらくこれは、コンストラクタのコードにとっては想定外
のことだろう。 例えば gflags はまだ初期化されていない。

結論: オブジェクトの初期化が簡単なものでなければ、明示的な Init() メソッドを用意したり、オブジェクトの初期化が成功したかどうかを示すフラグをメンバに追加するなどを検討すること。 

これはいつも悩むところ.反対派の意見にも出ているのだけれど,コンストラクタではboolを返すことができない.だから,ちょっとでも込み入ったことをするとエラーが発生する可能性があって,かつそれを検知することができない.これは正直C++のいけてないところだと思っている.僕は,結論に書いてあるように,基本的にはエラーハンドラをコンストラクタにも持たせるようにしている.複雑ならばInit()関数に任せるというのも同意だし,そうしている.基本的にはコンストラクタでやらせるのは変数の初期化のみ
ですね.

明示的なコンストラクタ
▽ 引数が1つのコンストラクタには、C++の explicit キーワードを付ける。

れは単純にやってなかったらこれからはやるようにしよう...

宣言の順序
▽ クラスにおける宣言は、次に指定した順序にする。public: は private: の前に置く、メソッドはデータメンバ(変数)の前に置くなど。
link

クラスの定義は public: セクションから始めて、protected: セクション、private: セクションという順にするべきだ。セクションが空であれば省略する。

各セクション内では通常、次の順序で宣言するべきだ。

    * typedef と enum
    * 定数
    * コンストラクタ
    * デストラクタ
    * メソッド。スタティックメソッドも含む
    * データメンバ。スタティックデータメンバも含む

気をつけないといけないのだけど,いつも手を抜いて一貫性がとれていなかった.特にこれ,という決まりはないのだけど,この際この順番で統一させるようにしようと思う.

例外
▽ C++の例外を使わない。

同意.例外だとエラーがトレースできない場合はある.独自にエラーハンドラを書いたほうが確実だと思う.

Boost
▽ Boostライブラリ群のうち許可されているライブラリだけを使う。

同意.確かにBoostは便利だし,すごく使いたくなるんだけど,移植性を考えると使わないほうが良いと思っている.個人的には公開したプログラムではBoostを使ったものは無い.ただし,googleでは以下のライブラリは許可しているらしい.要調査.

    *    Compressed Pair(boost/compressed_pair.hpp)
    * Pointer Container(boost/ptr_container)ただしシリアライゼーションを除く。
    * Array(boost/array.hpp)
    * Boost Graph Library(BGL)(boost/graph)ただしシリアライゼーションを除く。
    * Property Map(boost/property_map.hpp)
    * Iterator の一部。次のイテレータの定義に対応するもの。 boost/iterator/iterator_adaptor.hpp、 boost/iterator/iterator_facade.hpp、 boost/function_output_iterator.hpp
私たちはこの他のBoost機能をリストに追加することを積極的に検討している。そのため、このルールは将来緩和されるかもしれない。 
型名
▽ 型名は大文字で始めて、単語の頭文字を大文字にする。アンダースコアは使わない。MyExcitingClass、MyExcitingEnumなどとする。
link

あらゆる型、— クラス、構造体、typedef、enum — の名前には同じ命名規約を使う。型名は大文字で始めて、単語の先頭を大文字にするべきだ。アンダースコアは使わない。例: 

大文字で初めてキャメルケースでということですね.同意.

変数名
▽ 変数名はすべて小文字にして、単語と単語の間にはアンダースコアを入れる。クラスメンバ変数はアンダースコアで終わるようにする。例えば、my_exciting_local_variable、my_exciting_member_variable_。
link

よく使う変数名

例:

string table_name;  // OK - アンダースコアを使っている。
string tablename;   // OK - すべて小文字だ。

string tableName;   // よくない - 大文字小文字が混ざっている。

僕は変数名もキャメルケースで書いてたんだけど,確かに見分けをつけるにはアンダースコアにしたほうがいいかも.今後取り入れよう.

定数名
▽ kで始まり、大文字小文字で続ける。kDaysInAWeek
link

コンパイル時定数は、それがローカルであろうとグローバルであろうと、クラスの一部としてであろうと、どう宣言されていても、他の変数とは全然違う命名規約に従うこと。k の後に単語の先頭を大文字にして続けること。

const int kDaysInAWeek = 7;

C風に全部大文字のほうがわかりやすい気がする.目立つし.

うーん,なかなかおもしろい.結構自分は一過性を持って書いていると思っていても実は一貫性が取れていない部分が結構多い.オープンソースで開発する場合は他人に読んでもらうことが多いから一貫性に関しては特に気をはらわなければならないし,はらって
いるつもりなのだけれども.


ここ何回かgperfのメモを取ってきて,かつここには書かなかったけど個人的にサンプルプログラムを作って改めて思ったんだけど,gperfってルックアップがめちゃくちゃ高速なわけですね.完全ハッシュなので当然っちゃー当然なのですが.早くてお手軽っての
がgperfの良いところなわけですが.さてさて,早いのわかったけど,どれぐらい早いの?ってのは何かの指標がなければわかりませんね.そこで,今のところ最強に早いといわれているTokyo Cabinetのhash DBMとのスピードの比較をしてみようという,結構無意
味なベンチテストをやってみた.

データの準備

やったことは単純で,ランダムにkey, valueのセットを作成し,それぞれ10セット,100セット,1000セット,10000セット,100000セット,のDBの作成時間と,ルックアップの時間を比較してみた.ちなみにkeyは[A-Za-z1-9]の文字列からランダムに選択した32
文字で構成され,valueは[1-9]の数字からランダムに選択した5桁の数値となります.

データの具体例

ls8NRbatYxDtR7xFYI33gR6Xd7UISN5E,64424
9sNbbs8fSvLC4XKGOyIVkE2pG3qDdoXN,81452
kC7gEuCC9YjEXclUjNHSqZYMSoRxCcIv,92562
85cH1CKlczbmXukZAk7EDbVyHee12mRl,27441
mBCqaxbg4xnT6qi67BxoosYnvefcPmAC,84235
IQ88EVLy5lOswuClaZsN6N8En6AK6BOi,38926
FinG7fDmDoEuLCeotyHcsAr5vF9Puz28,33697
bfMhSn3ee8tdB7PD348aCgDCceTv4p5N,84162
8DkGQWkpVUh7MvyVrULQfj49aLbOAYr9,29667
EoaxVsQIZbD9CXlumXeCGH4S5HVNQ7Ex,61271

上記のようなデータ(10set, 100set, 1000set, 10000set, 100000set)をそれぞgperfを使って完全ハッシュ関数のコードと,Tokyo Cabinetのhash DBMを作成した.

作成の時間比較

#of keys gperf TC hash DBM
10 0.002sec 0.035sec
100 0.009sec 0.036sec
1000 0.435sec 0.04sec
10000 1m26.67sec 0.082sec
100000 NaN 0.0496sec
  • gperfでのkeyの数100000万個の場合は75分以上たっても終わらなかったためあきらめました.今度終わったらまた書きます.

keyの数が増えると圧倒的にTCの方が早いですね.まあ,完全ハッシュ関数だから時間がかかるのは当然か...しかし,TCのDBMの作成は超はええなああ...keyの数が莫大になるとちょっとgperfは使い物にならないかもしれないなあ.

ルックアップスピードの比較

ルックアップスピードの比較は,DBに入ってるkeyをすべてイテレーションをして個々のkeyのvalueを引くという処理をそれぞれ1万回やりました.具体的にはkeyの数が10個の場合のテストは「イテレーションで10個のkeyを引く * 10000回」なので100000回のルッ
クアップをすることになります.

# of keys gperf TC hash DBM
10 0.012sec 0.035sec
100 0.097sec 0.330sec
1000 1.057sec 3.317sec
10000 11.526sec 33.531sec

綺麗にgperfのほうが約3倍早いですね.

まとめ

  • gperfはkeyの数が膨大になるとコード生成がものすごく時間がかかる,TCはコンスタントに早い
  • gperfはルックアップがtc hash DBMより約3倍早い

しかし,gperfはデータの更新をするたびにまたコードを生成しなおさなければなりません.TCはデータの追加も削除も高速にできます.
つまりユースケースによってどちらがいいかを選択すれば良いわけですね.前にも書いたのだけどgperfはデータの更新が無くて,ルックアップの数が莫大な数のユースケース,keyの数は1万以下ぐらいで適切かもしれません.TCのようなDBMはその逆で,データの
更新が頻繁にある場合で,かつkeyの数が莫大な場合に適切だと思います.

ちょっと長くなったけど,すごい自己満足なエントリーとなってしまった.しかも走り書きなので超まとまり悪くなったなあ.

一応将来の自分のために今回使ったプログラムの一部をメモっておく.

  • createData.pl (ランダムなデータの作成)
use strict;
use warnings;
use String::Random;

for(my $i = 0; $i < 100000; $i++){     my $rand_key = String::Random->new->randregex('[A-Za-z1-9]{32}');
    my $rand_val = String::Random->new->randregex('[1-9]{5}');
    print "$rand_key,$rand_val\n";
}
  • inputTc.pl (ランダムデータをTCにぶち込む)
use strict;
use warnings;
use TokyoCabinet;

my $save_path = shift @ARGV;

my $hdb = TokyoCabinet::HDB->new();
$hdb->tune(200000);
$hdb->open($save_path, $hdb->OWRITER|$hdb->OCREAT|$hdb->OTRUNC);

while(my $line = <>){
    chomp $line;
    my ($key, $val) = split ",", $line;
    $hdb->put($key, $val);
}
$hdb->close();
  • gperf (完全ハッシュ関数を生成するときのコマンド)
gperf -CtGD -Z TrainHash -L C++ dataFile
  • lookup.cpp (TCとgperfのルックアップをしたプログラム)
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include "perfect_hash.hpp"

int main(int argc, char** argv)
{
  std::string fileName = argv[0];
  std::string listFile = argv[1];
  std::string tcPath = argv[2];
  std::string mode = argv[3];
  std::vector keys;

  /* create key list*/
  std::ifstream ifs(listFile.c_str());
  std::string line;
  while(std::getline(ifs, line)){
    keys.push_back(line);
  }

  /* create gperf instance */
  TrainHash train;

  /* create tokyocabinet instance */
  TCHDB* hdb = tchdbnew();
  tchdbopen(hdb, tcPath.c_str(), HDBOREADER);

  for(unsigned int j = 0; j < 10000; j++){
    for(unsigned int i = 0; i < keys.size(); i++){
      if(mode == "gperf"){
        const struct Train* rv = train.in_word_set(keys[i].c_str(), std::strlen(keys[i].c_str()));
        //std::cout << keys[i].c_str() << "\t" << rv->val << std::endl;                                                                                                             
        if(!rv){
          std::cerr << "error: gperf not found key" << std::endl;
          exit(1);
        }
      } else if(mode == "tc"){
        char* val = tchdbget2(hdb, keys[i].c_str());
        //std::cout << keys[i].c_str() << "\t" << val << std::endl;                                                                                                                 
        if(!val){
          std::cerr << "error: tc not found key" << std::endl;
          exit(1);
        }
        std::free(val);
      }
    }
  }
  tchdbclose(hdb);
  tchdbdel(hdb);
  return 0;
}


超個人的なエントリで恐縮です。
先日完全ハッシュ関数に関して調査していたのですが、

perfect hash function(完全ハッシュ関数)の概要|http://blog.broomie.net/index.cgi?id=7

そこで、GNU gperfというアプリケーションが完全ハッシュ関数の生成器として存在するって話を少ししだけれども、かくいう僕もgperfを使わせていただいておるのですが、実際にどんなアプリケーションやユースケースで使われているのかなあ、と興味を持った
ので軽い気持ちで調べてみた。

gperfの本家のマニュアルを調べてみると確かに、それらしいことが書いてある。

gperf currently generates the reserved keyword recognizer for lexical analyzers in several production and research compilers and language processing tools, including GNU C, GNU C++, GNU Java, GNU Pascal, GNU Modula 3, and GNU indent. Complete C++ source code for gperf is available from http://ftp.gnu.org/pub/gnu/gperf/. A paper describing gperf’s design and implementation in greater detail is available in the Second USENIX C++ Conference proceedings or from http://www.cs.wustl.edu/~schmidt/resume.html.

http://www.gnu.org/software/gperf/manual/gperf.html|http://www.gnu.org/software/gperf/manual/gperf.html

gperfは(GNU C, GNU C++, GNU Java, GNU Pascal, GNU Modula 3, GNU indent.)などの様々なプログラミング言語のコンパイラで予約語の認識部分の処理を担っている.

って書いてありますね。予約語のチェックはルックアップ数が多いから、gperfで高速化しているんですね。上のリストには書いてないけれども、Rubyのソースを眺めてみたら、実際にRubyも予約語のチェックはgperfでやっているんですね。Rubyをソースで落とす
とパッケージの中にlex.cというのがあって、それはgperfで出力されたソースになっていました。参考になるので今後じっくり読んでみよう。

lex.cに先頭に以下のようにコメントしてあります。

/* C code produced by gperf version 3.0.3 */
/* Command-line: gperf -C -p -j1 -i 1 -g -o -t -N rb_reserved_word -k'1,3,$' keywords  */

google code searchでgperfというキーワードで検索してみたら、4000件もヒットしたし結構色んなところで使われているんですね。ばばーっと使われている部分を見てたんだけどやっぱり、予約語のチェックみたいに、シンタックスのチェックとかで使われているみたいです。高速で簡単に使えるんだからgperfってもっと色んなところで使われてもいいような気がするんだけどなあ。。。まあ更新ができないっていうのがネックなんだけどね。


perfect hash function(完全ハッシュ関数)に関する調査。

perfect hash functionとは

wikipediaにはperfect hash functionは以下のようにまとまっている。

ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。このような関数を使えば、1つのハッシュテーブルで目的のエントリを直接探すことができ、それ以外の探索の手間が生じない。
完全ハッシュ関数は、入力される範囲が予め分かっていて変化しない場合のみ成立する。例えば英語の月の名前を0から11の整数にマッピングするとか、ある辞書に掲載されている単語にハッシュ値を割り当てるといった場合である。入力の集合を与えられると、それに対応した完全ハッシュ関数を実行する最適化されたサブルーチンを出力する生成器がいくつか存在する(例えば、GNU gperf)。

wikipedi:ハッシュ関数より引用

つまりハッシュ関数で、keyが絶対に衝突せずに必ず個々のkeyのハッシュ値が必ず一意に定まるのがperfect hashingです。特徴としては、衝突がないため検索が極めて高速であること。昨今のオープンソースのソフトウェアではGNU gperfというperfect hashingのハッシュ関数を生成してくれるソフトが多く用いられている。さくっと使ってみたい場合はgperfを試してみるのが良いでしょう。gperfは複数のkey, valueのデータセットを探索できるハッシュ関数を生成してくれて、CやC++で用いることができる便利なユーティリティです。

perfect hashingはどのようなケースで有効か

Using a perfect hash function is best in situations where there is a large set, S, which is not updated frequently, and many lookups into it. Efficient solutions to performing updates are known as dynamic perfect hashing, but these methods are relatively complicated to implement. A simple alternative to perfect hashing, which also allows dynamic updates, is cuckoo hashing.

wikipedia:perfect hash function より引用

上記の引用した内容のようにperfect hashingは以下のようなケースで有効です。

  • 更新が無い莫大なkey、valueのデータセット
  • かつkeyの探索(lookup)が高頻度の場合

ダイナミックに更新が必要な場合は、dynamic perfect hashingというアルゴリズムがあるが複雑らしいです。また、シンプルであるがダイナミックに更新できるもにcuckoo hashingというのがあるらしい。ちょっとこれは興味があるから別の機会に調査してみよう。

関連事項

perfect hasingと似たアルゴリズムでminimal perfect hash function(最小完全ハッシュ関数)がある。

n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数(通常 0 から n-1)の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しい。

wikipedi:ハッシュ関数より引用

最小完全ハッシュ関数は、perfect hashingでかつ、ハッシュテーブルとてもコンパクトになる。詳しい調査は別のエントリーでしようと思う。最小完全ハッシュ関数は多くの実装あり、具体的にはなどがある。