10月24日、Phoronixが「Linux's Early Boot-Time Physical Memory Allocator Sees Big Speed-Up: ~268s To ~50ms」と題した記事を公開した。この記事では、Linuxカーネルの起動初期に使われる物理メモリアロケータ「memblock」の処理が、線形探索から二分探索への変更によって劇的に高速化されたことについて詳しく紹介されている。以下に、その内容を紹介する。

268秒が50ミリ秒に——たった1つのアルゴリズム変更で

Linux 7.4カーネルに向けて、mm/memblock.c に対する改善パッチが取り込まれた。変更の核心は単純だ。線形探索（O(N²)）から二分探索（O(N log N)）への切り替えである。

memblock はLinuxカーネルの起動初期段階で使われる物理メモリアロケータだ。通常のページアロケータが立ち上がる前のごく短い期間だけ使われるため、これまで最適化の優先度は高くなかった。しかし今回、Googleのエンジニア Tarun Sahu が memblock_add_range() および memblock_isolate_range() 関数内で、候補領域の探索に線形探索が使われていることを発見した。

パッチのコメントには次のように記されている。

"Using binary search reduces the worst-case complexity to O(N log N) (and O(N) for sequential appends), cutting KHO memory retrieval time from ~268s to ~50ms."

最悪ケースで268秒かかっていた処理が、50ミリ秒まで短縮された。削減率にして実に99.98%超である。

なぜ今まで問題にならなかったのか

memblock は起動時の限られた時間にしか使われない。通常の起動シーケンスでは管理するメモリ領域の数が少ないため、線形探索でも事実上問題は生じなかった。

問題が表面化したのは、**Kernel Handover（KHO）** という機能との組み合わせによるものだ。KHOは、カーネルの再起動をまたいでメモリ状態を引き継ぐ仕組みで、Live Update Orchestrator などが活用している。KHOを使うと、大量の不連続なfolio（メモリの管理単位）が生じ、memblock が管理する領域が爆発的に増える。その結果、線形探索のコストが現実的な問題として顕在化した。

Phoronixはこの点について「線形探索がこれほど長く残っていたのは驚きだ」と述べつつ、「とはいえ、影響は起動初期のメモリアロケータに限られる」と補足している。

ベンチマーク結果

Linux 7.4 memblockプルリクエストとして正式送付

この最適化は、2026年10月24日に送出された memblockプルリクエスト の一部としてLinux 7.4に向けて提案された。元パッチ は2026年9月にTarun Sahuによって投稿されている。

「なぜ今まで誰も気づかなかったのか」という疑問は自然だが、裏を返せば、KHOのような新しいユースケースがカーネルの古いコードの盲点を露わにした好例だ。低レイヤーのコードベースであっても、使われ方が変わればボトルネックも変わる。

詳細はLinux's Early Boot-Time Physical Memory Allocator Sees Big Speed-Up: ~268s To ~50msを参照していただきたい。