しゃある通信

#17-01 [hack]gperfによるCompiler::Lexer,mrubyのfootprint最小化実験

gperfで完全ハッシュ関数を作成してキーワードのマッチを高速に行う試みはrubyなどで行われている手法だけど、 そこで生成される関数とかハッシュテーブルのサイズをgperfに与えるオプションを変えることで小さくできると 嬉しいことがあるんじゃないか? というのを、ふと思いついたのでやってみてる途中経過。

コードはhttps://github.com/sharl/gperf-minに。

ターゲットはLinux x86_64で対象はCompiler::Lexerで。

ハッシュ関数はinline化されてしまってよくわからないので、生成されるシンボルテーブルから関連するサイズを求めてみるようにした。

以下は途中経過なのでまだまだ変わるかも? (4/21に終わってました)

Compiler::Lexer キーワード 408 個
$ sort -k2 gperf-min-p5-Compiler-Lexer-linux.log | head
in_word_set 00e0 asso_values 0200 wordlist 06f78 lookup 0000 total  29272 filesize 2207840 [-i1 -j1 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 075b8 lookup 0000 total  30872 filesize 2213560 [-i0 -j1 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 07cf8 lookup 0000 total  32728 filesize 2215392 [-i2 -j1 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 09998 lookup 0000 total  40056 filesize 2226840 [-i2 -j3 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 09e58 lookup 0000 total  41272 filesize 2228032 [-i0 -j3 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 0a038 lookup 0000 total  41752 filesize 2228512 [-i1 -j3 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 0bf78 lookup 0000 total  49752 filesize 2240632 [-i2 -j5 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 0c878 lookup 0000 total  52056 filesize 2247008 [-i0 -j5 -k1,2,4,5,$]
in_word_set 00e0 asso_values 0200 wordlist 0c878 lookup 0000 total  52056 filesize 2247008 [original]
in_word_set 00e0 asso_values 0200 wordlist 0e1f8 lookup 0000 total  58584 filesize 2257656 [-i1 -j5 -k1,2,4,5,$]
src/compiler/util/Compiler_reserved_keyword.cppをコンパイルしてできるblib/arch/auto/Compiler/Lexer/Lexer.sonmしてサイズを出してる。 コードサイズは変わってないけど、lookupが減ってトータル38kBytesくらい減ってますな。

in_word_setが文字列から構造体のポインタを返すハッシュ関数のサイズ。totalin_word_set+asso_values+wordlist+lookupの合計。filesizeLexer.soのサイズ。オリジナルソースから生成されるサイズよりも 少し減ってるのがわかるはず。アラインメントがあるから多少の誤差はあるけども。

次はOS X Mavericks, Command Line Tools for Xcode5.1.1のLLVM環境でmrubyを。

mruby キーワード 40 個
$ sort -k2 gperf-min-mruby-osx.log | head
parser_yylex 66e0 asso_values 0100 wordlist 03b50 lookup 0000 total  41776 filesize 1073700 [-i0 -j1 -k1,2,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03b98 lookup 0000 total  41848 filesize 1073668 [-i0 -j1 -k1,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03bb0 lookup 0000 total  41872 filesize 1073828 [-i1 -j1 -k1,2,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03bf8 lookup 0000 total  41944 filesize 1073796 [-i1 -j1 -k1,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03bf8 lookup 0000 total  41944 filesize 1073796 [original]
parser_yylex 66e0 asso_values 0100 wordlist 03c58 lookup 0000 total  42040 filesize 1073924 [-i2 -j1 -k1,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03c58 lookup 0000 total  42040 filesize 1074052 [-i1 -j3 -k1,2,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03c88 lookup 0000 total  42088 filesize 1074116 [-i2 -j1 -k1,2,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03cd0 lookup 0000 total  42160 filesize 1074084 [-i0 -j3 -k1,3,$]
parser_yylex 66e0 asso_values 0100 wordlist 03cd0 lookup 0000 total  42160 filesize 1074212 [-i0 -j3 -k1,2,3,$]
src/lex.defをincludeしてるparse.yから生成されるy.tab.cをコンパイルしてできるbuild/host/src/y.tab.o。キーワード少ないからあんまり変わんないね。

などなど、実験してたりするのでした。CPUパワー足りねえ(笑)

小さくするんじゃなくて速度を求めるなら--switchとか--readonly-tablesとかするといいんじゃないかな。



マクロミルへ登録

© 2014 Kazuya 'Sharl' Masuda
(C)Willoo Entertainment Inc. (C)Konami Digital Entertainment 株式会社ウィローエンターテイメント及び株式会社コナミデジタルエンタテインメントの著作権を侵害する行為は禁止されています。 0.044278 cached