FreeBSD、SYSINITのバブルソートをマージソートに変更

• FreeBSDでは起動時に、時間の 7% を SYSINIT のバブルソートに費やしているとの報告があった
• これは 1996 年に作られたコードで、当時はソート対象の SYSINIT が約 30 個程度だったが、現在は 1000 個以上になり時間がかかるようになっていた
• 最近のコミットで SYSINIT 配列を SLIST に変更し、マージソートが可能になったほか、新しい SYSINIT の追加も高速化された
  • マージソートは最大で約 100 倍高速
• Firecracker では、全体の起動時間 28ms のうち 2ms を節約できるようになった

[rousseau]

ある程度の規模以下のデータセットについては、小さくて理解しやすいコードを使うのが有効だったのでしょう。
そうした判断の結果として残っている遅いアルゴリズムの用例は、今でもまだ多いのでしょうね。
（偏見ですが）こういうことにいちいち文句をつける人がいるとしたら、役には立たないのに不平ばかり多い人なんだろう、という気が強くします。

[xguru]

FreeBSDは起動時にSYSINITをバブルソートするのに7%の時間を使っている

[GN⁺]

Hacker Newsのコメント

• FreeBSDはSYSINITでbubblesortをmergesortに置き換え、起動時間を大幅に改善しました。
• bubblesortの使用はミスではなく、その非効率さが特定のユースケースで顕在化するまで、長年にわたって十分に機能していました。
• これは、AWS Lambdaのように頻繁に起動するケースで必要とされた最適化でした。
• FreeBSDカーネルは、Firecracker上で起動する際、SYSINITでbubblesortを実行するのに7%の時間を費やしていました。
• mergesortへの変更により、コードは正味5行減少し、起動時間は「100倍高速」になりました。
• 当初bubblesortを使うと決めた判断は、タスク数のような要因に影響されていた可能性があります。
• mergesortへの変更は、小さな改善が全体の性能に重要な差をもたらしうることを示す一例です。
• bubblesortの既知の非効率性や直感的でない点を考えると、初期採用に疑問を呈するユーザーもいます。
• この変更は、FreeBSDの起動時間やSYSINITにおけるbubblesortの使用について、関連する議論を呼び起こしました。