初心者への GNU perf のススメ
Lynx Optimized Pages!
51030 accesses since 2001/07/27.
5 accesses per day.
[ TOP ]
一部から完全ハッシュ関数を作るツール gperf の使い方を知りたい、というリクエストが あったので、軽く説明してみようと思います。 (深く突っ込めないという話も。知ってることしか説明できないよねー(汗;))
ちなみに gperf は cperf-2.1a.tar.gz, gperf-3.0.4.tar.gz, gperf-3.1.tar.gz というパッケージになってます。gperf-2.7 以降は C++ がないとコンパイルできません。
(2017/06/19現在) 3.1 には突然 size_t が出現する不具合があります。http://lists.gnu.org/archive/html/bug-gperf/2017-01/msg00004.html
オプション -I, --includes を指定、または 3.0.4 以前にダウングレードすることで回避可能です。
パッケージのコンパイルについては割愛します。
ハッシュが線形逐次検索に比べて速いことは周知です。完全ハッシュ関数は固定長のハッシュ表により ハッシュ値の計算コストを抑えてキーワードの探索を高速に行う関数です。普段使われる動的ハッシュに 対して静的ハッシュとも呼ばれます。
簡単な例を。入力した文字列が ID とマッチするかどうか調べるプログラムを作ってみましょう。
--- id.key --- AVG-FOE M.H Sato/2 Sharl UME20 anti-top nbkz oo -------------- ID 勝手に出してごめんなさい
このようなキーワードファイルを用意します。
先程のファイル id.key を入力ファイルとして
% gperf id.key
または
% gperf < id.key
とすると、標準出力に C のソースが出力されるので、リダイレクトして id.c とでもしておきます。
version 3.0 以降ではキャラクタセットが異なるとエラーを出すようになりました(id.c 参照)。
完全ハッシュ関数の関数名はデフォルトで in_word_set です。-N オプションで関数名を変更できます (-N name or --lookup-function-name=name)。プロトタイプ宣言は id.c を見てもらうとわかるように
const char *in_word_set(const char *str, unsigned int len);
です。version 2.1 では -a オプションにより len を int にすることができます。
実際の使用例は以下のようになります。
--- main.c ---
#include <stdio.h>
#include <string.h>
extern const char *in_word_set(char *, unsigned int);
void
main(int argc, char *argv[])
{
const char *p;
if (argc == 1)
return;
p = in_word_set(argv[1], strlen(argv[1]));
if (p == NULL)
printf("no match.\n");
else
printf("hit [%s]\n", p);
}
--------------
id.c とリンクしてください。
% cc main.c id.c % ./a.out aa no match. % ./a.out oo hit [oo] %
次の例を見てください。
--- asm.key --- add asl asr dec inc lsl lsr mov ret rol ror sub --------------- % gperf asm.key /* starting time is 14:59:48 */ Key link: "rol" = "lsr", with key set "lr". Some input keys have identical hash values, try different key positions or use option -D.
どうやら文字が重複している(アナグラムになっている)ので一意に決定できないようです。こういう場合は -D オプションを指定してください(と書いてある(汗;))。
% gperf -D asm.key
‘try different key positions’というのは…うまく説明できません。省略(汗;)。この場合は -k1,3,$ とか -k1,2,$ と指定すればいいんですけど…。この辺は試行錯誤してみてください。 すみません。(清く正しいシェルは $ をエスケープするのを忘れずに :-)
version 3.0 以降では -D をつけなくても自動的に計算してくれるようになりました。
とりあえずこれで gperf を使えるようになりました。(実用的かどうかは神のみぞ知る…)
ここからが普通の使い方です。
通常はキーワードとその属性(?)を構造体で格納して、キーワードの属性に対してアクションを行います。
gperf は文字列をキーワードとしてハッシュ表を作るので、かなり用途が限定されます。 逆引きできない、ということですね。
--- word.key ---
%{
/*
* a portion of GNU make keywords
*/
#include "word.h"
%}
struct OPE { char *name; int type; int args; };
%%
addprefix, F_ADDPREFIX, DYNAMIC
addsuffix, F_ADDSUFFIX, DYNAMIC
basename, F_BASENAME, MONAMIC
dir, F_DIR, MONAMIC
filter, F_FILTER, DYNAMIC
filter-out, F_FILTEROUT, DYNAMIC
findstring, F_FINDSTRING, DYNAMIC
firstword, F_FIRSTWORD, MONAMIC
foreach, F_FOREACH, TRINAMIC
join, F_JOIN, DYNAMIC
notdir, F_NOTDIR, MONAMIC
origin, F_ORIGIN, MONAMIC
patsubst, F_PATSUBST, TRINAMIC
shell, F_SHELL, MONAMIC
sort, F_SORT, MONAMIC
strip, F_STRIP, MONAMIC
subst, F_SUBST, TRINAMIC
suffix, F_SUFFIX, MONAMIC
wildcard, F_WILDCARD, MONAMIC
word, F_WORD, DYNAMIC
words, F_WORDS, MONAMIC
----------------
この例では word.h に define や enum などで定数を定義しておきます。この書式、yacc/bison の .y に似てますね。f?lex の .l にも似てるかも。
%{ と %} の間の行がソースに挿入されます。%} と %% の間の行が、構造体の宣言になります。%% 以降が 構造体の内容の羅列です。1 行に構造体 1 つぶんしか書いてはいけません。 キーワードは必ず先頭に書きます。それにあわせて構造体のメンバの型も決めてください。
ここで注意。デフォルトではキーワードに対するメンバ名が‘name’です。 メンバ名を変更したい、という時は -K で指定します(-K name or --slot-name=name)。
ex.)
struct MEMB { char *id; char *addr; char *tel; };
のとき gperf -K id ... となります。
キーワードから属性(この場合は構造体のメンバ)を得たいので、構造体へのポインタが返ってこないと 参照できませんね。
しかし、デフォルトではキーワードへのポインタを返すので、構造体へのポインタを返すように オプションで -p -t を指定します。 -pt と続けて書いてもかまいません。
% gperf -pt word.key > word.c
さて、word.c の中に構造体 OPE の定義が残っています。もし word.h の中で struct OPE を定義したり していると redefinition error が出ます。ヘッダを使い回す人は注意ですね。そういうときは -T を指定すると、構造体の宣言が出力されなくなります。
% gperf -ptT word.key > word.c
めでたく構造体へのポインタが返るようになりました(なりましたよね???)。この場合の in_word_set のプロトタイプ宣言は
struct OPE *in_word_set(const char *str, unsigned int len);
になります。あとは
struct OPE *p;
if ((p = in_word_set(key, strlen(key))) != NULL)
do_func(p->type, p->args);
などとして使いましょう。Rubyが予約語のハッシュをgperfで作っていますね。
構造体の初期化でコンパイラの警告が出る場合は version 3.0以降で -F ", 0, 0" と オプションで初期化するものを指定するか、構造体宣言の前か後ろに
%define initializer-suffix ,0,0
と書いてあげると埋めてくれます。自動的に構造体宣言の中を解析してくれるわけじゃないですけど。%define を 使うときに空白を入れるとダメな感じなので -F を使ってquoteしてあげるといい感じのソースになります。
3.5 The Copyright of the Output
gperfis under GPL, but that does not cause the output produced bygperfto be under GPL. The reason is that the output contains only small pieces of text that come directly fromgperf's source code – only about 7 lines long, too small for being significant –, and therefore the output is not a “work based ongperf” (in the sense of the GPL version 3).On the other hand, the output produced by
※強調部分は筆者によるものgperfcontains essentially all of the input file. Therefore the output is a “derivative work” of the input (in the sense of U.S. copyright law); and its copyright status depends on the copyright of the input. For most software licenses, the result is that the the output is under the same license, with the same copyright holder, as the input that was passed togperf.
長年議論されてきましたが、これでようやくの決着となりそうです。
駆け足で説明してきましたが、けっこうな量になっちゃいました。でも、これだけ覚えておけば一応使う ことはできます。わたしもこのくらいしかわかりませんけど大丈夫ですし(汗;)。
もっと突っ込んで知りたい方は gperf.texinfo や付属の gperf.html を参照してください(汗;)。
(2017/06/19) gperf-3.1.tar.gz が出ていたので更新。size_t が突然出てくる不具合も追記。
(2012/03/23, 2012/07/18) gperf が出力したソースコードの権利についての項を追加。公式マニュアルへのリンクを追加。
(2005/10/29) gperfの吐くソースにgccが文句を言うを受けて構造体の初期化を追加。
(2003/08/09) version 3.0.1 に対応した内容に改変。
(2001/08/02) サンプルで使ったソースを見られるようにした。若干改変。
(2001/08/01) 休んでいる間に gperf-2.7.2.tar.gz が出ていたので更新。
(1998/05/08) gperf-2.7.tar.gz が独立パッケージに。
(1997/10/06) gperf の在処を追加。
(1997/05/16) はるか昔に書いたドキュメントを HTML にしてみました。今でもここに書いたくらいの知識しか持って ないし、これ以上の使い方をしてないので、この説明が役にたつ人もいるんじゃないかなぁ。 ツッコミもお待ちしております。