2014-05-02

Linux Torvalds、最近のCPUのPage Faultのコストにご不満の様子

Linus Torvalds - Google+ - One of the things I end up doing is do a lot of performance…

Linus Torvaldsが、最近のIntelのCPUは、通常以外の処理のコスト、つまりPage faultのコストが上がっているので、問題であるとしている。

俺はよくカーネルコードのパフォーマンスプロファイリングをやる。特に、VMとかファイルシステム周りに対してだ。

俺がよくやるのは、「うまくいってるとき」に対する計測だ。つまり、だいたいほぼ完璧にキャッシュされてる状況だな。というのも、俺はもちろんIOのことは気にかけているが、俺の個人的なワークロードはたいてい、うまくキャッシュされてるからだ。たとえば、俺にとってよくあるロードは、pullした後のフルカーネルビルドだ。これにどのくらいの時間がかかるかが問題になる。というのも、俺はまず取り込んだものが、基本的なテストをパスするのを確認した後でなければ、次のpullをしたくないからだ。

さて、カーネルビルドシステムは、実際の所、けっこう賢い。ほとんどのドライバーやアーキテクチャーのpullでは、コアヘッダーを書き換えないので、「全カーネルを再コンパイル」というのは、それほど大規模なビルドではない。大方は、「オッケー、依存してるヘッダーとファイルは変更されてないな。何もする必要がねーぜ」というチェックだけだ。

だが、これを何千ものヘッダーファイルと、何万ものCファイルで行うわけで、けっこう時間がかかる。フルビルドカーネル("allmodconfig"なので、まあ大体フルビルド)で、「終わったぜ。pullは何もコンパイルする必要のある変更をしてなかったぜ」と言うだけでも、俺の普通のデスクトップでは、30秒はかかる。

まあ、30秒のallmodconfigは、それほどってわけでもない。だが、次のpullを始めるまでの待ち時間としては長すぎるし、コーヒーでも1杯といくには短すぎる。

要するに、うざいということだ。

そこで、俺はこのクソをぶっ殺すためにプロファイルしたが、半分ぐらいは、"make"が遅かった。これは、実際には、珍しいことに、カーネル由来のロードである。なぜならば、makeは大量のpathname lookupをしていて、けっこうな量の短命なプロセス(短いシェルスクリプトとか、"make"がfork/exitするとか)もやっているからだ。

従来、この手の問題の原因は、VFS pathname lookupで、もちろんいまだに大きな問題ではあるのだが、最近はそれだけの問題ではなくなっている。

最も大きいコストは何か? CPUによるPage fault handlingさ。

この「CPUによる」という部分に注目してもらいたい。カーネルVMはよくやってるのだ。問題はPage faultのコストそのものと、(小規模だが)、page faultから戻る"iret"のコストだ。

この問題を特定するために、ちょっとしたテストプログラムを書いたが、その結果が興味深い。俺のHaswell CPUでは、page fault一回のコストは、約715サイクルだ。"iret"で戻るのは330サイクルだ。そのため、page faultとreturnは、約1050サイクルだ。このコストは多少の誤差があるかもしれないが、近い値だ。他のテストでは、1150サイクルあたりに計測された。だが、これにもっとノイズが大きいので、1050は最小コストとしてはありえるだろう。

なんでこれが興味深いかって? カーネルソフトウェアが、ページを見つけてページテーブルに設定するためのコストは、はるかに小さいからさ。最悪の状況で(固定のzero-pageをマップしたばかりという、あからさまに作り上げた状況だが)、この1050サイクルは、全CPU時間の実に80.7%を占めるのだ。これは、カーネルもユーザースペースもpageをfaultさせるのにほとんど何もしていないという極端な例だが、俺の実際のカーネルビルドでは、全CPU時間の5%を占める。

古い32bitのCore DUoでは、俺のテストプログラムは、page faultオーバーヘッドは、80%ではなく、「たった」の58%だと計測している。これは、page faultが遅くなっているからだ(Core Duoのコストは、「たった」の700 + 240サイクルだ)

この問題の理由の一つとしては、Haswellは通常のコードでは改良されている(ので、faultオーバーヘッドが相対的に意識されやすい)が、コストが明後日の方向に向かっているのは、なんだかなぁ。

Intelエンジニアと話つけて、これを改良できるかやってみるか。

G+やHacker Newsのコメント欄では、ユーザースペースのビルドシステムの問題が指摘されている。

そもそもいまだに旧態依然のMakeを使っているのが問題なのだ。ビルドシステムに大量の小さなシェルスクリプトや、fork/exitのようなものが発生するから遅いのだ。例えばChromiumを見よ。規模はLinuxカーネルと同程度だが、まともなビルドシステムを使っているため、何もしないビルドは、数秒で終わるぞ。

といった意見だ。これに対しLinus Torvaldsは、

いや、そりゃ確かに、makeはブタでやりすぎだが、GNU makeの拡張機能や複雑な変数やらその他のよくわからんシェルエスケープやら何やらを駆使したところで、状況は改善しない。

だから、いわゆるmakefileコンパイラーが、この状況を最適化できるのは確かだ。だが、make代替品は自分でいくつも試してみた。imake, cmake, qmake, こいつらは問題の一部は解決しているが、やはり特有のクソさがある。

makeが超効率的になるのはありがたいが、俺としては、makeが必要とする部分のカーネルを最適化をしたいし、CPUに手間取ってもらいたくない。

というのも、まあ考えてみろ。たといカーネルビルドひとつ、超効率的になったとしてもだ、現実はそうじゃない。言っておくが、カーネルビルドでやっている「大量の小さなシェルスクリプトとか何とか」というのは、よそでもやっている現実のワークロードだ。page faultを最適化するのは、他のワークロードのためにも役立つのだ。

この話は、Old New Thingの記事を思い出した。

The hunt for a faster syscall trap - The Old New Thing - Site Home - MSDN Blogs

syscallトラップのパフォーマンスは興味深いものだ。

15年前[訳注:この記事が書かれたのは2004年なので、1989年頃]、IntelとMicrosoftと会議があった(残念ながら、私はこの会議に参加していなかったので、この話は伝聞なのだが)

Microsoftというのは、Intelの最大の顧客のひとつなので、Intelの代表はよくMicrosoftを訪問して、最新のプロセッサーを紹介したり、カーネル開発部に新しいプロセッサーの機能をサポートするようロビーしたり、どのような機能を追加すれば、もっとも役立つかという知見を吸い上げたりしていた。

この会議で、Intelの代表がたずねた。「でさ、たったひとつだけ、速くして欲しいところがあるとすれば、どこ?」

躊躇なく、カーネルの開発主任が答えた。「無効命令のfaultingの高速化」

Intel社員は笑い転げた。「いやぁ、Microsoftのエンジニアは愉快でいらっしゃる」というわけで、会議は冗談で締めくくられた。

研究所に戻った後、IntelのエンジニアがWindowsカーネルのプロファイルをしたところ、驚くなかれ、彼らはWindowsがかなりの時間を、無効命令例外をさばくためにつかっていることを発見したのである。何だと! ひょっとして、Microsoftのエンジニアは冗談を言ったのではなかったのか?

冗談じゃない。

この当時の80386チップで、V86モードからカーネルモードに移行する最速の方法は、無効命令を実行することだったのだ! そのため、Windows/386は、無効命令をsyscall trapに使っていたのであった。

この話の教訓? よくわからない。たぶん、何か物を作ったならば、それが作成者の意図しない方法で使われるだろうということか。

立っている者は親でも使えとは、それこれこれを謂か。

3 comments:

Anonymous said...

s/Linux Torvalds/Linus Torvalds/

Anonymous said...

時代は移り行きますが、最適な手法も移り変わるべきです。
互換性を売りにしている以上何通りかのシナリオは想定しているはずですが、それでも世の中無情ですね。

NyaRuRu said...

> 例えばChromiumを見よ。規模はLinuxカーネルと同程度だが、
> まともなビルドシステムを使っているため、
> 何もしないビルドは、数秒で終わるぞ。

ちなみに Hacker News のこのコメントを書いているのは Ninja の作者の Evan Martin 本人だったり.
https://news.ycombinator.com/item?id=7680494

Ninja そのものについて Evan Martin が書いた文章としてはこれがおすすめです.
http://aosabook.org/en/posa/ninja.html

最近社内 G+ 経由で知った話としては,こんな話もあるそうです.
http://www.spottradingllc.com/gyp-ninja-3/
とある trading firm が autotools ベースのビルドシステムから gyp+ninja に移行してビルド時間を半分にしたんだとか.