青木日記

■ 非デジタル

たまにはパソコンの電源を入れない一日もいいなあ。

■ 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 で大量に文字列オブジェクトを生成するのが遅い、 ということなのかな。キャッシュ云々はあんま関係なさげ。