sysinstallに対するパッチ (2012/02/27)

あなたは 人目のお客様です．

FreeBSD の sysinstall に対するパッチです． 当然無保証．各自の責任で利用すること．

パッチの内容

sysinstall でパッケージインストールしようとすると， 「Located INDEX, now reading package data from it...」 というメッセージでやたら時間がかかる．(イライラしている人は多いはず…)

なんとなくINDEXファイルのダウンロードとデータベース構築に時間がかかっている のかなーこれってしかたがないのかなーと思っていたのだが，実はソート処理に時間が かかっており，数箇所修正することでデータベース構造を変更せずに処理時間を 改善できることが判明したのでパッチを作ってみた．結果として，パッケージ インストールの立ち上げにかかる時間を127秒から15秒に短縮できた．(測定結果は後述)

パッチではリストのエントリ移動をしているのが気になるが，近辺のコードを ざっくり見たところ(そして試してみたところ)修正に問題は無いと思う． のだが，もしもなにか問題あったらごめんなさい．

パッチの内容は以下．まず，INDEX展開の高速化の修正が３つ．

• (1) index_sort() に対するパッチ
  パッケージのソートにクイックソートを利用する．(強力！)
  ※ オリジナルはバブルソートになっていてとっても効率悪そう．
• (2) index_register() に対するパッチ
  パッケージリストの作成時のカテゴリ検索で，ヒットしたカテゴリをリストの 先頭に移動することでヒット率を上げる．
• (3) index_search(),index_recorddeps() に対するパッチ
  依存のチェック時のパッケージ検索で，ヒットしたパッケージをリストの 先頭に移動することでヒット率を上げる．

• (4) index_menu() に対するパッチ
  パッケージ名が長過ぎるためwwwのカテゴリの表示が崩れることの修正． (そして文字列オーバー時のメモリ破壊の可能性を防止)
• (5) index_extract() に対するパッチ
  突然落ちることがあったのだが core dump を見るとここで落ちていたよう なので対応．(どういう条件で落ちるのかは詳しく追っていない)
• (6) mediaSetFTP() に対するパッチ
  FTP先のURLを手打ちしたときに覚えておいてくれないことの対応． 毎回打つのがとても面倒だった．

パッチの当てかた

• index.c.patch.txt
• media.c.patch.txt

パッチは /usr/src/usr.sbin/sysinstall に以下の要領で当てる．

% su
# cd /usr/src/usr.sbin/sysinstall
# patch < /tmp/index.c.patch.txt
# patch < /tmp/media.c.patch.txt
# make
# ./sysinstall (動作確認)
# make install (動作確認できたらインストールする)

パッチ詳細 ((1),(2),(3)のパッチについて)

• (a) パッケージリストの作成 ← (2)のパッチで改善
• (b) パッケージの依存チェック ← (3)のパッチで改善
• (c) パッケージ名のソート ← (1)のパッチで改善

以下はパッチ適用前と後でのインデックス作成の処理速度の測定結果． ゼロ秒はほとんど一瞬，という意味．

修正内容	(a)+(b)	(c)
オリジナルの状態	40秒	87秒
(1)を適用	40秒	0秒
(1)+(2)を適用	20秒	0秒
(1)+(2)+(3)を適用	15秒	0秒

ほとんどの時間はソートで費されているがこれはバブルソートによるとっても 効率悪そうな処理(コメントにも「単純だけどゲロゲロ」とか書かれている)で あったため改善できる．

で，クイックソートで処理するようにしてみたら，ソートにほとんど時間が かからなくなった．つまり(c)の「87秒」が「ほぼ一瞬」になった． (クイックソートすげえ…)

ただしクイックソートはソート用のエントリテーブルをmalloc()で獲得する必要が あるためちょっと不満あり(組込みプログラマとしては，動的メモリ獲得を安易に 使うことに抵抗がある)．しかし以下の理由より問題ないだろうと判断し， メモリ獲得できたときはクイックソートを使うような処理を採用．

• 既存のバブルソート処理をなるべく崩さず高速化するような工夫を他にも いろいろ試してみたが大きな改善は無く，対してクイックソートの威力は絶大．
• sysinstall の中で malloc() しているような部分は他にも多数有り，malloc() することに問題はなさそう．ていうかsysinstallはわりとメモリ効率に無頓着な 感じのコードなので，あんま気を使わなくてよさそう． (スタックの使いかたとか派手だし)
• malloc()でメモリ獲得できなかった場合には既存のバブルソートを使うような ハイブリッド構成にすれば，メモリ獲得失敗の問題も無し．(既存に戻るだけ)

他にもwwwのカテゴリが崩れる問題とかは，このような明らかな問題がなぜ直らないのか 以前から不思議に思っていて，なにか歴史的な理由とかあるのかなーと思っていたの だが，今回sysinstallの中を軽く見てみたところ，とくに直さない理由があるとか ではなくて，sysinstall のコードはけっこうベタな感じで書かれていて，単なる人手 不足とかで誰も直してないだけという感じがしたのだけどどうなのだろう．

sysinstallはbsdinstallに置き換わっていくことになっているのであまり喜ぶ人は いないパッチかもしれないが，これって send-pr すべき？

• トップページに戻る