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

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

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

パッチの内容

sysinstall からのパッケージインストールで,インデックス作成にやたら時間が かかることの修正とその他のいくつかの修正.

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

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

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

パッチの内容は以下.まず,INDEX展開の高速化の修正が3つ.

さらに,ついでにその他の不満点を直してみた.

パッチの当てかた

まず,以下をダウンロード. パッチは FreeBSD-8.2 用.ちなみに sysinstall のソースは FreeBSD-8.1, FreeBSD-9.0 でもほとんど変化無く,同じ手順でパッチ当てできた.

パッチは /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)のパッチについて)

sysinstallでのパッケージインストールのインデックス作成処理は,以下の3つの 処理が順に行われている. オリジナルの状態で測定した所,(a)+(b)の処理に約40秒,(c)の処理に約87秒, 全体で約127秒かかっていた.つまりほとんどはソート処理.

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

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

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

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

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

さらにリスト作成時のカテゴリ検索と,依存リストの作成時のパッケージ検索で, 検索にヒットしたエントリをリスト先頭に移動して次にヒットしやすくなるように したら,こっちもあるていど改善された.

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

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


メールは kozos(アットマーク)kozos.jp まで