競プロ勢のためのデバッグテクニック
Facebook Hacker Cup Round1の問題をオーバーフローと配列外参照で2問落としてしまい、反省を込めてデバッグテクニックを調べました。
競技勢がやらかすケアレスミスなバグの多くはこの2つだと思うので、この2つのみについて述べていきます。また、僕は普段の実装にMacを使っているので、gccのフリをしたMac仕様Clang（クソ）についても言及します。
オーバーフロー
これは-ftrapvオプションを付けてコンパイルしたファイルを実行すればオーバーフローした瞬間に検知（abort）する事が出来ます。
しかし、どこで死ぬのかがわからずこのままでは使い勝手が悪いので、-g（デバッグ）オプションも付けてコンパイルした後に、gdbで実行すると良いです。
#include <iostream> using namespace std; int main(){ int x = 10000000; int y = 10000000; cout << x * y << endl; }
$ clang++ -ftrapv -g overflow.cpp $ gdb -q ./a.out Reading symbols from ./a.out...done. (gdb) r Starting program: /tmp/a.out Program received signal SIGILL, Illegal instruction. 0x00000000004008cf in main () at overflow.cpp:8 8 cout << x * y << endl;
これはUbuntuでビルドした最新のClang++、Mac版Clang++でも動きます。 Ubuntuにもとから入っていたg++では__GI_raiseでSIGQUITを送出して終了した点で終了しました。（これはよく考えたらg++ではなくてgdbがデフォルトでユーザーのプログラムの中まで戻ってくるかどうかというだけかもしれない？あと、No such file or directory.と出ているのがややこしいですが、これは多分gdbのエラーメッセージ。）
$ g++ -ftrapv -g overflow.cpp $ gdb -q ./a.out Reading symbols from ./a.out...done. (gdb) r Starting program: /tmp/a.out Program received signal SIGABRT, Aborted. 0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54 54 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
一応、backtraceをすればどこで死んだかは分かります。
(gdb) bt #0 0x00007ffff74ab418 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54 #1 0x00007ffff74ad01a in __GI_abort () at abort.c:89 #2 0x00007ffff7842522 in __mulvsi3 () from /lib/x86_64-linux-gnu/libgcc_s.so.1 #3 0x00000000004008b7 in main () at overflow.cpp:8 (gdb) frame 3 #3 0x00000000004008b7 in main () at memory.cpp:8 8 cout << a * b << endl;
Ubuntuにはgdbがデフォルトで入っているので、ICPCでも使えますね。
配列外参照
これはg++とMac版Clang++で対応が若干変わります。
g++
g++の場合、最初に#define _GLIBCXX_DEBUGを書くことで検出出来ます。
最初に書かないと動かないので注意してください。
これは、vectorファイルの中に
#ifdef _GLIBCXX_DEBUG # include <debug/vector> #endif
というコードがあるためです。つまり、include前であれば良いですが、誤りを避けるために最初に書いておくことをおすすめします。
#define _GLIBCXX_DEBUG #include <vector> using namespace std; int main(){ vector<int> a(10); for(int i=0; i<100; i++) a[i] = 1; return 0; }
例によってgdbを使います。
$ g++ -g memory.cpp
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) r
Starting program: /tmp/a.out
/usr/include/c++/5/debug/vector:409:error: attempt to subscript container
with out-of-bounds index 10, but container only holds 10 elements.
Objects involved in the operation:
sequence "this" @ 0x0x7fffffffdd00 {
type = NSt7__debug6vectorIiSaIiEEE;
}
Program received signal SIGABRT, Aborted.
0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
54 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0 0x00007ffff74ab428 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:54
#1 0x00007ffff74ad02a in __GI_abort () at abort.c:89
#2 0x00007ffff7b0af95 in __gnu_debug::_Error_formatter::_M_error() const () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3 0x000000000040110c in std::__debug::vector<int, std::allocator<int> >::operator[] (this=0x7fffffffdd00, __n=10) at /usr/include/c++/5/debug/vector:409
#4 0x0000000000400ba8 in main () at memory.cpp:8
(gdb)
Mac版Clang++
Mac版Clangの場合、_GLIBCXX_DEBUGの代わりに_LIBCPP_DEBUGを用います。
_LIBCPP_DEBUGの設定した値によってデバッグレベルが変わるらしく、0か1をdefineすれば良いのですが、何故か1を指定するとバグりました。
#define _LIBCPP_DEBUG 0 #include <vector> using namespace std; int main(){ vector<int> a(10); for(int i=0; i<100; i++) a[i] = 1; return 0; }
$ g++ memory.cpp $ ./a.out vector[] index out of bouns Abort trap: 6
ここまではICPCで使うことも想定して電子的な準備に該当しない領域でどこまで出来るのか考えました
valgrindを使う方法
Facebook Hacker CupやGoogle Code Jam、または一般のプログラミングに関してはこれが一番やりやすいかもしれません。 -gオプションを付けてコンパイルした後
valgrind ./a.out
とするだけで詳細な結果が出てきます。
$ g++ -g -O0 test.cpp $ valgrind ./a.out ==1120== Memcheck, a memory error detector ==1120== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al. ==1120== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info ==1120== Command: ./a.out ==1120== ==1120== Invalid write of size 4 ==1120== at 0x10000156D: main (test.cpp:7) ==1120== Address 0x100a8e068 is 0 bytes after a block of size 40 alloc'd ==1120== at 0x10000A681: malloc (in /usr/local/Cellar/valgrind/3.12.0/lib/valgrind/vgpreload_memcheck-amd64-darwin.so) ==1120== by 0x10004F7DD: operator new(unsigned long) (in /usr/lib/libc++.1.dylib) ==1120== by 0x10000179E: std::__1::vector<int, std::__1::allocator<int> >::allocate(unsigned long) (new:156) ==1120== by 0x1000016B1: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1070) ==1120== by 0x1000015CC: std::__1::vector<int, std::__1::allocator<int> >::vector(unsigned long) (vector:1073) ==1120== by 0x10000152E: main (test.cpp:5) ==1120== ==1120== ==1120== HEAP SUMMARY: ==1120== in use at exit: 22,153 bytes in 191 blocks ==1120== total heap usage: 258 allocs, 67 frees, 27,993 bytes allocated ==1120== ==1120== LEAK SUMMARY: ==1120== definitely lost: 0 bytes in 0 blocks ==1120== indirectly lost: 0 bytes in 0 blocks ==1120== possibly lost: 0 bytes in 0 blocks ==1120== still reachable: 0 bytes in 0 blocks ==1120== suppressed: 22,153 bytes in 191 blocks ==1120== ==1120== For counts of detected and suppressed errors, rerun with: -v ==1120== ERROR SUMMARY: 90 errors from 1 contexts (suppressed: 0 from 0)
追記
オーバーフロー時の挙動がMacとUbuntuで異なっていたのはどうやらftrapvの実装の違いのせいのようです
@aki33524 clangはftrapvの実装にundefinedなオペコードぶち込んで対応してるらしい https://t.co/3Yq4hde8JU
— るくす (@RKX1209) 2017年1月16日
" -ftrapv flag will cause clang to intenionally insert ud2"
tf-idfを使ったDbpediaの型推定
卒論が上手く行かないので逃避していたらまぁまぁ良さそうなので公開しておく。
前提
DbpediaとはWikipediaを元に半自動で変換したLODである。
各リソース（記事）にはclass（人とか政治家とか虫とか）が定義されたりされなかったりする。
全リソースの3割ほどにclassが定義されておらず、これを推定する需要がある。
この前のISWCのデモセッションでDbpediaの型（class）推定をしようとしている研究があったのが心に残っていた（全然手法違うけど）。
卒論でデータを眺めていたらふとtf-idfで上手く行くように見えたので試してみた。
というかこれをもっと筋良くした研究が既にあると思うけどパッと出てこなかった。Dbpediaの自動変換の過程で似たようなことをやっている気がする。詳しい人教えてください。
アイデア
基本的なアイデアとしては
「A is writer of B」
という関係があれば、Aはおそらく作家だろうしBはおそらく本だろうという推定が出来るというところ。
つまり、リソース（Wikipediaの記事1つに該当）間のプロパティ（Wikipedia間のリンクに相当、ただのリンクではなく種類がある）
を特徴量として扱う。
tf-idfについては無限に資料があるので詳しく語らないが
「リソースを文書とする」
「（方向、プロパティ）の組を語彙とする」
というアイデアをtf-idfに適用した。
また、2つの文書間の類似度はcos類似度によって表される。
そこで、あるリソースAと他の任意のリソースBのcos類似度を計算して、Bにclassが定義されていれば類似度をclassの推定値として重畳する。
この時、足し合わせたあとにそもそもそのclassを持つリソースがいくつあるかで除したり、推移的なtype定義を用いたりするとよい。
最終的に、最も推定値の大きなclassが推定結果である。
所感
簡単な割に結構上手く行ってくれる。
例えばバラク・オバマにはclassが定義されていない。これを推定するときちんとpolitician - Wikidataと出てきた。
ただ、当然だがプロパティ関係が殆ど存在していないようなリソースは推定を誤る。恐竜が「虫」に推定されたりしていた。
他には、1735年などの年度シリーズが殆ど「場所」として推定されていた。
これは日本語版Dbpediaのデータが悪いようで、birthPlaceとして人との間に関係が定義されていた（birthTime？的なものにしてくれ……）。
これを発展させるとすればプロパティの種類だけではなく、その先に存在しているリソースのclassなども推定すべきだろう。
「A is writer of <instance of Movie>」であれば、Aは作家は作家でも監督？とかそういった推定が出来るかもしれない。
結局これは辺に種類が付いた有向グラフのクラスタリング問題に帰着できそうで、何か機械学習で上手く出来たりするのかなぁというところ。
コードはこれです。
GitHub - aki33524/typeprediction
