2003-07-10
■ 非デジタル
たまにはパソコンの電源を入れない一日もいいなあ。
■ HiNote Ultra 2 へ Linux をインストール
これ↓
にインストールを試みる。
うまくいったら今月の SICP 読書会から使おう。
……FDD からブートできない。FDD が死んでる模様。 しかたないので HDD に直接入れることにする。
2.5" HDD → 3.5" 変換アダプタでメインマシンにつなぎ、 現在の環境から直接ファイルをコピーしてしまおう。 HDD の構成はこうなる。
IDE0 master (/dev/hda): main HDD 1 slave (/dev/hdb): main HDD 2 IDE1 master (/dev/hdc): HiNote の HDD slave (/dev/hdd): CD-ROM Drive
まず cp -a でまるごと移し、目で見ていらないものをバサバサと消す。 chroot してみるとちゃんとシェルは動いた。
が、lilo できないことに気付く。/dev/hda からロードするという設定で /dev/hdd の MBR に書き込みたいのだが、そういうオプションはなさそうだ。 多少近いのが lilo -r rootdir だが、これでは書き込むデバイスが変わらない。 また、boot = /dev/hdd にしてしまうと 本番環境で /dev/hdd を探しにいってしまうことになる。
そこで lilo のソースコードを見てみることにした。 うまくするとちょっと書き換えるだけで出力先を変えられるかもしれない。 まずコンパイルに as86, ld86 (bin86 package), nasm などが必要だったのでこれを入れる。
……
飽きた (おい)。
やっぱり物理的につなぎなおすほうが早いな。 メインマシンの IDE ケーブルをつなぎかえて
IDE0 master: HiNote の HDD slave: CD-ROM Drive IDE1 master: main HDD 1 slave: main HDD 2
とする。この状態で Plamo の CD-ROM からブートし、lilo だけやる。 と思ったら、Plamo の ramdisk 環境には lilo が入ってなかった。 うわあ。
が、本番環境に lilo もコピーしていたので、 /dev/hda をマウントしてそこから取ることができた。 (追記：改めて考えると、パッケージのどれかに入ってたんだろうな)
よしっ、HiNote につなぎ直してブート！ LILO Loading Linux.........................
勝手にリブート。
うわっ。 しくじってる、しくじってるよ……。
ああっ、そうか！ メインマシンのカーネルって P6 に最適化されてるんだった！ 原因は十中八九これだな。 （HiNoteUltraIIはPentium150MHzです）
うーむ、メインマシンでコンパイルしなおすか、 それともおとなしく Plamo の CD-ROM から入れるか。 どっちが面倒かなあ。環境を作り直す手間を考えると、 カーネルだけ作りなおすほうがいいか？
つづく
■ 総当たり検索 (1)
ソースツリーからシンボルとか文字列を探すことはよくある。 真面目にやるなら global とか使えばいいのだけど、 面倒なときは全部 grep てのも楽でよいもんだ。
が、一つ問題がある。 Ruby くらいなら zsh 使って grep '^rb_define_method' **/*.[ch] とでもすればいいが、Linux とか glibc だとソースツリーがでかすぎて、 引数の数の限界を越えてしまう。かと言って for 文使って
for f (**/*.[chS]) { grep 'sys_ioctl' $f }
とすると、
~/s/src/linux-2.4.20 % time zsh t > /dev/null zsh t > /dev/null 36.48s user 9.31s system 100% cpu 45.781 total
こんなに遅くなってしまう。プロセス起こしすぎですな。
そこでこんな Ruby スクリプトを書いてみた。
#!/usr/bin/ruby
#
# search.rb
#
require 'find'
require 'getopts'
def usage( status )
(status == 0 ? $stdout : $stderr).print(<<EOS)
Usage: #{File.basename($0)} [-f function] [-c function] [-m macro] [-g pattern]
-f func search definition of function FUNC.
-c func search function call of FUNC.
-m macro search definition of macro MACRO.
-d sym search definition of function or macro, SYM.
-g pattern search PATTERN.
EOS
end
def main
getopts(nil, 'c:' , 'd:', 'f:', 'g:', 'm:', 'help') or usage(1)
usage(0) if $OPT_help
case
when $OPT_c then find_pattern(/\b#{$OPT_c}\(/)
when $OPT_f then find_pattern(/(?:^|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_m then find_pattern(/^\#\s*define\s+#{$OPT_m}[\(\s]/)
when $OPT_d then find_pattern(/^\#\s*define\s+#{$OPT_m}[\(\s]|(?:\A|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_g then find_pattern Regexp.compile($OPT_g)
end
end
def find_pattern( re )
Find.find('.') do |path|
next unless /\.[chsS]/ === path
File.open(path) {|f|
f.each do |line|
if re === line
puts path.sub(%r<\A\./>, '') + ":#{f.lineno}"
puts ' ' + line.strip
break
end
end
}
end
end
main
ようするに単なる力任せ検索。 最近のマシンにかかるとこんなおバカなプログラムでも結構速くて、 Linux 2.4.20 のソースツリー (170MB) 全体でも
~/s/src/linux-2.4.20 % time ruby search.rb -f 'sys_ioctl' > /dev/null 9.04s user 0.33s system 98% cpu 9.485 total
こんなに速い。びっくりだ。
■ 総当たり検索 (2) キャッシュ
だけど、やっぱりもうちょっと速いと嬉しいな。 検索サーバをたててファイルを常に全部オンメモリにしておいたら 速くなるんじゃないかと思いついたので、次にこれを実装してみた。
まずサーバ。
#!/usr/bin/ruby
#
# searchserver.rb
#
require 'socket'
require 'find'
DEFAULT_PORT = 6668
def main
daemon {
cache = read_cache('.')
$stderr.puts 'ready' if $DEBUG
server = TCPServer.open(DEFAULT_PORT)
while true
sock = server.accept
len = sock.gets.to_i
re = Marshal.load(sock.read(len))
search cache, re, sock
sock.puts '.'
sock.close
end
}
end
def read_cache( dir )
cache = {}
Find.find(dir) do |path|
next unless /\.[chsS]/ === path
#cache[path.sub(%r<\A#{Regexp.escape(dir)}/>, '')] = File.readlines(path)
cache[path.sub(%r<\A#{Regexp.escape(dir)}/>, '')] = File.read(path)
end
cache
end
def search( cache, re, sock )
cache.each do |path, lines|
#lines.each_with_index do |line, lineno|
if re === lines
#sock.puts path + ":#{lineno}"
#sock.puts ' ' + line.strip
sock.puts path
#break
end
#end
end
end
def daemon
return yield if $DEBUG
fork {
Process.setsid
fork {
Dir.chdir '/'
$stdin.close
$stdout.close
$stderr.close
return yield
}
exit!
}
exit!
end
main
次にクライアント。
#!/usr/bin/ruby
#
# searchclient.rb
#
require 'socket'
require 'getopts'
DEFAULT_PORT = 6668
def usage( status )
(status == 0 ? $stdout : $stderr).print(<<EOS)
Usage: #{File.basename($0)} [-f function] [-c function] [-m macro] [-g pattern]
-f func search definition of function FUNC.
-c func search function call of FUNC.
-m macro search definition of macro MACRO.
-d sym search definition of function or macro, SYM.
-g pattern search PATTERN.
EOS
end
def main
getopts(nil, 'c:' , 'd:', 'f:', 'g:', 'm:', 'help') or usage(1)
usage(0) if $OPT_help
case
when $OPT_c then find_pattern(/\b#{$OPT_c}\(/)
when $OPT_f then find_pattern(/(?:\A|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_m then find_pattern(/\A\#\s*define\s+#{$OPT_m}[\(\s]/)
when $OPT_d then find_pattern(/\A\#\s*define\s+#{$OPT_m}[\(\s]|(?:\A|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_g then find_pattern Regexp.compile($OPT_g)
end
end
def find_pattern( re )
sock = TCPSocket.open('localhost', DEFAULT_PORT)
data = Marshal.dump(re)
sock.puts data.length
sock.print data
sock.flush
while (line = sock.gets) != ".\n"
print line
end
sock.close
end
main
で、以下が Linux 2.4.20 のソースツリーでの実験結果。
~/s/src/linux-2.4.20 % time ruby search.rb -f 'sys_ioctl' > /dev/null 9.04s user 0.33s system 98% cpu 9.485 total ~/s/src/linux-2.4.20 % time ruby searchclient.rb -f 'sys_ioctl' > /dev/null 0.00s user 0.00s system 0% cpu 10.468 total
なんと、遅くなってしまった。 原因はなんだろう。
まず、オンメモリにするという点に元々あまり意味がなかった。 なぜなら Linux のソースツリー全体よりも物理メモリのほうが圧倒的に大きいので、 一度読んだらその後は全て OS にキャッシュされていると考えられるからである。 従ってコストの最も大きいディスク I/O が速度に影響しない。
そうなると検索サーバが有利なのは
- I/O のコスト (カーネルへの切り替え) が減る
- ファイルツリーのトラバースのコストがなくなる
- 文字列など、大量のオブジェクトの生成コストが減る
という程度に限られる。 検索対象データが多くなればこの程度のコストは無いに等しくなってしまうだろう。 前者二点は力任せ検索のベンチマークが 0.33s system となっていることから裏付けられる。 おそらく検索プロセスの実行時間のほとんどは正規表現マッチに使われているんだろう。
しかし、毎回ファイルから読むほうが速いのはどうしてだろう。 ここまでの考察では「少ししか速くならない」ことは説明できても 「遅くなる」説明にはなっていない。
これには、プロセスサイズが関係しているのではないかと予想する。 力任せ検索プロセスの RSS は一貫して約 2.4 MB 程度であった。 ハードウェアのキャッシュは L1 8KB, L2 512KB なので、 このプロセスサイズなら大部分がキャッシュに乗ってしまうはずだ。 一方、検索サーバプロセスの RSS は 800 MB 程度であり、 しかも検索のときはその全体をなめることになる。 つまり非常にキャッシュが効きにくくなる。 これによって速度差が出たのではないだろうか。
※ 全然関係ないけど、x86 システムの L2 って意外に小さいのな。 Alpha は 96 年のマシンでも 8MB 積んでるのに。
■ 総当たり検索 (3) アルゴリズムの変更
もう一つ別の方法を考えた。 いままでは file.each を使って行ごとにマッチしていたが、 まずファイル全体を読みこんで正規表現マッチを試し、 マッチするファイルに対してだけ各行に対してマッチを行ってみる。 つまりこう。
#!/usr/bin/ruby
#
# search2.rb
#
require 'find'
require 'getopts'
def usage( status )
(status == 0 ? $stdout : $stderr).print(<<EOS)
Usage: #{File.basename($0)} [-f function] [-c function] [-m macro] [-g pattern]
-f func search definition of function FUNC.
-c func search function call of FUNC.
-m macro search definition of macro MACRO.
-d sym search definition of function or macro, SYM.
-g pattern search PATTERN.
EOS
end
def main
getopts(nil, 'c:' , 'd:', 'f:', 'g:', 'm:', 'help') or usage(1)
usage(0) if $OPT_help
case
when $OPT_c then find_pattern(/\b#{$OPT_c}\(/)
when $OPT_f then find_pattern(/(?:^|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_m then find_pattern(/^\#\s*define\s+#{$OPT_m}[\(\s]/)
when $OPT_d then find_pattern(/^\#\s*define\s+#{$OPT_m}[\(\s]|(?:\A|[^=\s] )#{$OPT_f}\(\w/)
when $OPT_g then find_pattern Regexp.compile($OPT_g)
end
end
def find_pattern( re )
Find.find('.') do |path|
next unless /\.[chsS]/ === path
lines = File.read(path) ####
if re === lines #### 問題はこの 3 行
lines.each_with_index do |line, idx| ####
if re === line
puts path.sub(%r<\A\./>, '') + ":#{idx + 1}"
puts ' ' + line.strip
break
end
end
end
end
end
main
そうしたら、
~/s/src/linux-2.4.20 % time ruby search_eachline.rb -f 'sys_ioctl' > /dev/null 8.96s user 0.33s system 99% cpu 9.336 total ~/s/src/linux-2.4.20 % time ruby search_read.rb -f 'sys_ioctl' > /dev/null 0.57s user 0.35s system 102% cpu 0.896 total
いきなり 10 倍速になった。なぜっ！？ これは File#each が遅いのか、 はたまた正規表現マッチ開始時のオーバーヘッドが大きいのだろうか。 もうちょっと考察の余地がありそうだ。
■ 総当たり検索 (4) 負荷の検証
なるほど。 中田さんの仰るように、each が原因というのもありそうです。 検証しました。
# each で読み込むだけ (正規表現マッチはやらない) ~/s/src/linux-2.4.20 % time ruby loadonly_eachline.rb ruby loadonly_eachline.rb -f sys_ioctl 6.52s user 0.37s system 100% cpu 6.884 total # read で読み込むだけ (正規表現マッチはやらない) ~/s/src/linux-2.4.20 % time ruby loadonly_read.rb ruby loadonly_read.rb -f sys_ioctl 0.44s user 0.28s system 104% cpu 0.692 total
おおっ！ 犯人は each_line だったか！ 文字列オブジェクトが増えるのが遅いのかなあ。もしかしてほとんど GC？ そうか、検索サーバも GC 頻発で遅くなってる可能性があるな。 GC 止めてみよ。 Linux のツリーで GC 止めたらシェルに殺されたので glibc でやってみた。
# each で検索 ~/s/src/glibc-2.2.5 % time ruby search_eachline.rb -f sys_ioctl 2.10s user 0.19s system 101% cpu 2.261 total # read で検索して each ~/s/src/glibc-2.2.5 % time ruby search_read.rb -f sys_ioctl 0.27s user 0.20s system 105% cpu 0.445 total # 全部読み込んでおく (GC.enable) ~/s/src/glibc-2.2.5 % time ruby search_client.rb -f sys_ioctl 0.01s user 0.00s system 0% cpu 1.734 total # 全部読み込んでおく (GC.disable) ~/s/src/glibc-2.2.5 % time ruby search_client.rb -f sys_ioctl 0.01s user 0.00s system 0% cpu 1.716 total
あんまり変わらない。 単にこの検索のときにたまたま GC が起こってないだけかもしれないな。 それに glibc だとプロセスサイズが 200MB くらいしかないからさっきと条件が違いすぎる。
まとめると、each で大量に文字列オブジェクトを生成するのが遅い、 ということなのかな。キャッシュ云々はあんま関係なさげ。
■
なかだ [File#eachは、改行を探して各行ごとにStringを生成するあたりが大きいのかも。
File.readは、通常ファイルなら一回で読んじゃいますし。
# でもふつー、 grep -r のような。]
■
あおき [-r 知りませんでした…。
あ、GNU grep のオプションなんですね。
それはちょっと…]
■ woods [じゃfind . -name '*.c' | xargs grep 'hoge' /dev/null では？]
■
あおき [xargs って複数回に分けたりもするんですか！
それも知らなかった…(恥)。勉強になります。]
■ たむら [どうせ editor で開くんだから ctags -R *.[ch]]
■
旧世代 [find . -name '*.c' -exec grep 'hoge' {} \ -print;
しか知りませんでした。勉強になりました。]
■ なかだ [それは当然、fixしろってことでは。]
■ あおき [やっぱ直さなきゃだめですか…]