dtl-1.09

http://code.google.com/p/dtl-cpp/

dtl-1.09をリリースしました。今回の主な変更点は以下になります。

• specifyConflictionが正常に動作しないケースへの対応およびテストの追加
• Diff3クラスのtemplateパラメータにカスタムコンパレータを指定できるように変更
• uniPatchが正常に動作しないケースへの対応およびテストの追加
• サンプルプログラム用のデバックオプションを用意
• テストプログラムの分割

dtlのテストプログラム

近頃、dtlのテストプログラムのコンパイルが規模の割に時間がかかっているのが気になっていました。メインの開発環境として使っているCore 2 Duoのマシンや最近自作したCore i5のマシンだと10〜11秒ぐらい、手元のMacBookだと35秒かかっていました。(-Wall -O2でコンパイル)

いくらコンパイル時間の長いC++とはいえ、千行そこいらのプログラムでこれは遅すぎだろうと思い、改善することにしました。

dtlのテストプログラムではgoogletestを使っているのですが、調べてみるとどうもgoogletestが提供しているASSERT_EQやEXPECT_EQのマクロが増える度にコンパイルにかかる時間が増大しているようでした。

おそらくこれらのマクロがtemplateを使っているためだと思いますが、まだ詳しく追い切れていません。*1

今回よりも前のバージョンのdtlのテストプログラムではASSERT_EQやEXPECT_EQのマクロが500個以上あり、最終的にテストプログラムを工夫してこれらのマクロを減らすことにしました。

そもそも千行そこいらでなんでそんなにASSERT_EQやEXPECT_EQがあるんだ？と言われそうなので先に理由を言っておくと、例えばdtlのテストプログラムには以下のようなものがあります。

TEST_F (Strdifftest, diff_test0) {
    // edit distance
    EXPECT_EQ(2,          diff_cases[0].editdis);

    // LCS
    EXPECT_EQ("ab",       diff_cases[0].lcs_s);

    // SES
    ASSERT_EQ('a',        diff_cases[0].ses_seq[0].first);
    ASSERT_EQ('b',        diff_cases[0].ses_seq[1].first);
    ASSERT_EQ('c',        diff_cases[0].ses_seq[2].first);
    ASSERT_EQ('d',        diff_cases[0].ses_seq[3].first);
    ASSERT_EQ(SES_COMMON, diff_cases[0].ses_seq[0].second.type);
    ASSERT_EQ(SES_COMMON, diff_cases[0].ses_seq[1].second.type);
    ASSERT_EQ(SES_DELETE, diff_cases[0].ses_seq[2].second.type);
    ASSERT_EQ(SES_ADD,    diff_cases[0].ses_seq[3].second.type);
 
    // Unified Format difference
    ASSERT_EQ(1,          diff_cases[0].hunk_v[0].a);
    ASSERT_EQ(3,          diff_cases[0].hunk_v[0].b);
    ASSERT_EQ(1,          diff_cases[0].hunk_v[0].c);
    ASSERT_EQ(3,          diff_cases[0].hunk_v[0].d);
    ASSERT_EQ('a',        diff_cases[0].hunk_v[0].common[0][0].first);
    ASSERT_EQ('b',        diff_cases[0].hunk_v[0].common[0][1].first);
    ASSERT_EQ('c',        diff_cases[0].hunk_v[0].change[0].first);
    ASSERT_EQ('d',        diff_cases[0].hunk_v[0].change[1].first);
    ASSERT_EQ(SES_COMMON, diff_cases[0].hunk_v[0].common[0][0].second.type);
    ASSERT_EQ(SES_COMMON, diff_cases[0].hunk_v[0].common[0][1].second.type);
    ASSERT_EQ(SES_DELETE, diff_cases[0].hunk_v[0].change[0].second.type);
    ASSERT_EQ(SES_ADD,    diff_cases[0].hunk_v[0].change[1].second.type);
    ASSERT_TRUE(diff_cases[0].hunk_v[0].common[1].empty());
}

これはdtlのDiffクラスを使って計算された文字列「abc」と「abd」の編集距離、LCS、SES、Unified Formatの差分が正しいかどうかをチェックしています。

プログラムを見ればわかるようにSESとUnified Formatの差分が正しいかどうか検証するのに大量のASSERT_EQを使用しています。ASSERT_EQやEXPECT_EQが500個以上もあったのは、こんな感じのテストがいくつもあるためです。*2

入力するのが非常に面倒くさそうに見えますが、キーマクロを使ってほぼ自動化できるのでそれほど苦ではありませんでした。
SESやUnified Formatの差分は出力すると以下のようになります。

SES

 a
 b
-c
+d

Unified Formatの差分

@@ -1,3 +1,3 @@
 a
 b
-c
+d

さきほどのASSERT_EQで検証していたのはこれらのための構造体やクラスのメンバの値です。出力だけを見ると簡単ですが、一個一個の値を真面目に比較してると結構な量になります。一文字違うだけでこれなので、編集距離が長くなってくるとなかなか馬鹿になりません。しかし、よくよく考えてみるとdtlにはSESやUnified Formatの差分を任意の出力ストリームに渡す機能があるのでした。例えばこんな具合に。

    using namespace dtl;   
    using namespace std;   
                           
    ofstream ofs_ses;      
    ofstream ofs_uni;      
    Diff< char, string > diff("abc", "abd");
                           
    diff.compose();        
    diff.composeUnifiedHunks();
                           
    // SESをses_abc_and_abdファイルに出力
    ofs_ses.open("ses_abc_and_abd");
    diff.printSES(ofs_ses);
    ofs_ses.close();       
                           
    // Unified Formatの差分をunihunks_abc_adn_abdファイルに出力
    ofs_uni.open("unihunks_abc_and_abd");
    diff.printUnifiedFormat(ofs_uni);
    ofs_uni.close();

なので、事前にSESやUnified Formatの差分を外部ファイル化しておき、テストプログラムでこれらの機能を使って作成したファイルと事前に作成した外部ファイルの(行単位の)編集距離が0かどうか確認することによってテストすることができます。すると各SESやUnified Formatの差分が期待通りに作成されているかどうか検証するにはASSERT_EQ文一つで済むことになります。

最新版のdtlではさきほどのテストプログラムは以下のようになっています。

TEST_F (Strdifftest, diff_test0) {
    // edit distance
    EXPECT_EQ(2,    diff_cases[0].editdis);
 
    // LCS
    EXPECT_EQ("ab", diff_cases[0].lcs_s);
 
    // SES
    ASSERT_EQ(0,    diff_cases[0].editdis_ses);
 
    // Unified Format difference
    ASSERT_EQ(0,    diff_cases[0].editdis_uni);
}

とてもすっきりしました。この変更により必要なASSERTとEXPECTのマクロが150個ぐらいまで減り、環境にも依りますがコンパイルにかかる時間が10〜20%ほど改善できました。同じ頃にヘッダファイルのみで構成されていたテストプログラムの拡張子を.cppに変更して分割コンパイルするようにした分、全体のコンパイルは多少遅くなりましたが、逆に一つのテストプログラムを修正しただけで全体をコンパイルするようなことはなくなったので、開発の効率は若干上がったと思います。

また、dtlはすべてヘッダファイルで構成されるライブラリであり、しかも名前の通りテンプレートをバリバリ使っているので、これもコンパイル時間を増大させる一因になっています。ただ、これはdtlの方針上なかなか難しい問題なので、しばらくはこのままで行くつもりです。

*1:文字列の比較にtemplateが(少なくともASSERT_EQよりは)必要なさそうなASSERT_STREQ等を使って計測してみましたが、ほとんど改善せず。

*2:そもそも無駄なテストもいくつかありそうですが、それについての改善はまだ今度