2017年のruby-mswin事情

WindowsRubyを使うのは難しいようで簡単なようで難しいことです。

ただインストールするだけならばインストーラがあるので簡単です。公式サイトのダウンロードページから探しましょう。

……ここでいきなり迷うであろうのが、"mswin"と"mingw"という語です。Unix系のOSではABIは通常一環境に一つです。しかし、Windowsではたくさんあります。64bit版Windowsでは32bitのバイナリも動かすことが出来るのと、最近までVisual Studioはバージョンアップの度にABIを変更していたため、2017年現在では以下のようなABIが存在します。

  • i386-mswin32
  • i386-mswin32_70
  • i386-mswin32_71
  • i386-mswin32_80
  • i386-mswin32_90
  • i386-mswin32_100
  • i386-mswin32_110
  • i386-mswin32_120
  • i386-mswin32_140
  • x64-mswin64_80
  • x64-mswin64_90
  • x64-mswin64_100
  • x64-mswin64_110
  • x64_mswin64_120
  • x64-mswin64_140
  • i386-mingw32
  • x64-mingw32

あとcygwinとかinterix、WSLですか。さて、挙げたうちの上の15個、mswinとあるのがVisual C++版で、下の2個がmingw版 (gcc版) です。i386-mswin32とi386-mingw32だけ互換性があることを除けば、あとはABI互換性がありません。一応付け加えると、ついに近年Microsoftも心を入れ替えたらしく 1、Visual C++ 2015と2017はABI互換性があり、ともに末尾140のものを使います。よかったですね。

さて、どの版を使うのが安心かですが、WindowsRubyを使う際の難しさはたいていが拡張ライブラリ絡みであることはそろそろ知られていると思います。つまり使いたいgemがバイナリgemで提供されているものを選ぶべきですね。たとえばNokogiriを見てみましょう。i386-mingw32版とx64-mingw32版が提供されていることがわかります。

mingw版とバイナリgem

他にもmingw版のバイナリgemが提供されているgemはmsgpackやffiなどいくつかあります。これはrake-compiler-dockを使うとdockerを使ってクロスコンパイルをしてくれる便利ツールがあるからです、みなさんもC拡張gemを作る場合は導入をぜひご検討ください。

mswin版を選ぶと言うこと

という世界の現実に抗いたい、そういう人もいると思います。Visual C++が好き、そういう人もいるでしょう。現代ではMicrosoftVisual StudioIDEを含む全てではなく、コンパイラだけを配布してくれるようになったので、VCのインストールも随分楽になりました。まだVisual C++ 2015または2017が入っていない人はBuild Tools for Visual Studio 2017をダウンロードして実行、個別のダウンロードで以下にチェックを入れてインストールします。

  • Windows ユニバーサル CRT
  • デスクトップ C++ x86 および x64 用 Windows 10 SDK (10.0.15063.0)
  • スタティック分析ツール
  • VC++ 2017 v141 ツールセット (x86,x64)
  • Visual C++ Buid Tools のコア機能

あとはスタートメニューからx64 Native Tools Command Prompt for VS 2017を選べばビルド環境が立ち上がります。

なお、blogによると自動インストールも可能なようですが、その際の最適なオプションの探求は読者の宿題とします。

Rubyの依存ツール

リリース版のtarballからビルドする場合はともかく、リポジトリからRubyをビルドするには色々なものが必要です。以前git for Windows SDKを用いると楽って話を書きましたが、現在ではRubyInstaller2でもいいかもしれませんね。pacmanからx64-mingw64版のautoconf, bison,rubyなどを入れて(例えばmsys版だとパス変換があるのでうまくいかない)、インストール先をcmd.exe側のPATHに足せば良いです。ここでの注意点はこれでインストール出来るのは実行ファイルだけなこと。ライブラリは前述の通りABIが異なるためMSYSではインストール出来ません。

Rubyの依存ライブラリ

依存ライブラリは従来は一つ一つ自分で調達する必要がありました。(たいへんだった)けれども最近vcpkgというMS謹製パッケージマネージャが登場しました。これを使うとopensslやzlib、libxml、libxsltなどを簡単にインストールすることが出来ます。

vcpkgのリポジトリをcloneしてcdし、

bootstrap-vcpkg.bat
.\vcpkg --triplet x64-windows install libxml2 libxslt openssl

あとはPATHに/vcpkg/installed/x64-windowsをいれ、win32\configure.bat --with-opt-dir=/vcpkg/installed/x64-windowsなどでRubyのビルドが出来るはずです。

また、gem install nokogiri -- --use-system-libraries --with-xml2-dir=/vcpkg/installed/x64-windows --with-xslt-dir=/vcpkg/installed/x64-windows --with-exslt=/vcpkg/installed/x64-windowsなどと指定すればnokogiriだってビルド出来ます。

Nokogiriが入れられたと言うことはつまり、最新のRailsが動くということですね。ぱちぱちぱち

残る問題

上記以外でよく必要とされる拡張ライブラリというと、readlineとtherubyracerあたりでしょうか。therubyracerはまぁexecjsとnode.exe使って回避すれば良いとして、readlineはどうすればいいんでしょうね。rb-readlineは日本語対応してなかった気がするし。Clang/C2でビルドって出来るんでしょうか。readlineは今でも勇者の登場を待っています。

Go言語感想文

最近、敵情視察を兼ねた仕事ととしてGoでアプリケーションを書いていた。このアプリケーションがどんなものかはそのうちid:tagomorisさんがどこかで話すと思うけれど、このコンポーネントOSS化される予定はいまのところないので、そこで得た知見をここにまとめておくことにする。

GoroutineとChannel

さて、GoといえばGoroutineとChannelですね。

Goroutineはようするにスレッドなんですが、文法と実装の支援でより気軽に使えるのが他の言語との違いでしょうか。なので、Goroutineをどれだけほいほい使うべきかというコスト感覚を身につけることがとても大事な気がします。Rubyなどとは気持ちを切り替えていく必要があるでしょう。ぼくはまだ切り替えきれていません。

もう一つがChannelですね。これは端的にはメッセージキューです。 Goは前述の通り同時に動くマルチスレッド (Simultaneous Multithreading; SMT) を気軽に扱えるわけですが、七つの人類悪の一つであるマルチスレッドに丸腰で立ち向かっても無残な死が見えています。 そのための道具の一つがキューで、適切にロックを用いて作られた通信路を経由してデータをコピーすることで、わかりやすくかつ比較的効率よくスレッドをまたいでデータをやりとりすることができるわけです。(ちなみにRubyにもThread::Queueってのがあったりしますが、CRubyだとGVLがあるのでわざわざ使うことは少ないかも)

とは言ってもそれなりにコストかかるんでしょう?って人はchansendの実装を眺めるとチャンネルごとのロックを取ってmemcpyしてるだけってわかるので、頑張って並列ハッシュとか使わなくていいんだって気分になれます。送受信にかかる時間は10~100ナノ秒くらいかな? とすると、話はいかに書きたいアプリケーションをGoroutineに分割し、間をChannelでつなぐかという話になります。そして、様々なデータは基本的にそれぞれのGoroutine内に閉じ込め、他のGoroutineはChannel経由でアクセスする。

この構図、どこかで見たことがありますね?そうマイクロサービスの話と同じです。 Goでアプリケーション書くのは、このようなマイクロサービス的なコンポーネント分割というマクロな楽しみと、Cのコードを触っている時のような細かなデータの取り回しというミクロな楽しみが隣り合わせにあって、独特の感覚を覚えます。

テストについて

Goの標準パッケージにはtestingってのがあります。このパッケージの思想はGo の Test に対する考え方などで解説されています。「まぁ、一理はあるけど……」という感想の方が多いのではないでしょうか。「いやダメでしょきつすぎ」って反射的に反応したくなりますが、敬意を表して実際にtestingでやってみました。

いや、ダメでしょこれ。結局テストのメッセージなんて”A is expected but B”が9割で、これのメッセージをいちいち考えるとか決断力の無駄遣いですよ。日本人が英語でメッセージを綴るリソースが有限だという悲しい現実を考慮していない。ぼくは5個くらいassertionを書いたところで嫌になってあとはひたすら”A is expected but B”をコピペしまくりました。

まぁでも、それで致命的につらいかというと真面目にやるのを放棄してコピペすれば良いし、Goのfmt.Printfは%vと%#vが便利なので、なんとかなりはします。assert_equalの類以外に、タイムアウトをつけてチャンネルを読んだりするassertionメソッドが欲しくなって作りたくなるかもしれませんが、そういうときはruntime.Callerで呼び出し元の行数が取れるので、うまいことやるとよいです。 まとめると、正直testingはダメだと思うけど、とはいえなんとかはなるのでtestingで依存先を減らすのはありかも。

その他

  • log.Fatalは使わない
    • カバレッジ上げづらくなる
    • fatalに追い込まれるようなエラーはもっと上流で捌くべきなんだと思う
  • テストでlogが邪魔なときはlog.SetOutput(ioutil.Discard)で黙らせる
    • 並列実行でうまくいかないのでloggerを持たせて個別にやった方がたぶんよい
  • 困ったときはgoto ← おまえほんとうにそれでいいのか
  • switchべんり ← おまえほんとうにそれでいいのか
    • selectやswitchの中でbreakすると外側のforまで届かないのでbreak <label>すればよいけど、結局goto使う
  • Printf(“%#v”, v)べんり
  • error伝播させたいときは、pkg/errorsのcause使う
  • とすると、エラー用構造体は作りまくった方がよい ← 本当に?
  • sync/atomicとかあるけど、new(expvar.Int)とかでmutex付き変数が簡単に作れる、便利
  • Goはnull安全ではない←構造体のポインタを扱い始めると気になってくる

まとめ

えーっと、この記事の趣旨は「Goは21世紀のRubyistが触っておくべき言語なのか?」でしたっけ。Elixirとかをやっていないのなら、Guildの予習として一度Goで何か作ってみるとよいと思いました。作ると言ってもこういう悪い例じゃなくてchannelを使ったアプリを作ってみると、従来のスレッドがうぇいうぇい暴れながら大事な共有リソースをロックで守るみたいなのとは違う設計が体に染みいります。みなさんもGoをいじってRuby 3.0を準備万端で迎えられるようにしましょう!

Re: Re: Go言語感想文

mattnさんのRe: Go言語感想文について。

テストについて

アサーションをコピーしなければならない理由は一つのテストケースの中で異なるテストが混在しているか、単に同様のテストがコピーして作られているのが原因ではないでしょうか。

あー、ちょっと言葉が悪かったかな。わたしはおそらくmattnさんより10倍くらいDRYに関して短気で、mattnさんの挙げた例で言えば、以下の3行ですら許せないのです。

        if !test.err && err != nil {
            t.Fatalf("should not be error for %v but:", test.input, err)
        }
        if test.err && err == nil {
            t.Fatalf("should be error for %v but not:", test.input)
        }
        if got != test.want {
            t.Fatalf("want %q, but %q:", test.want, got)
        }

あとは、Table Driven Testsって基本的には関数的というか入力と出力が対応するものでは便利なんだけど、REST APIを叩くコードのリトライ部分のテストとか、状態を持って他のコンポーネントとchannelで通信しながらループするコンポーネントのテストにはいまいち。

その他

Golang に限らずですが、最近の言語では Labeled Break という物があります。

あ、ゴメン「selectやswitchの中でbreakすると外側のforまで届かないのでbreak <label>すればよいけど、結局goto使う」の<label>がタグ扱いになって消えてた……。それはそれとして、上述のリトライみたいなケースだと結局goto使いました。

null安全について

これは世間一般での意味での「null安全」です。ポインタではなく直接構造体を扱えばうまいこと行くかなーと思いきや、なんやかんやでポインタ使う羽目になったりして悲しい。

RubyのTypo Checkerについての考察

RubyKaigi 2014の基調講演でまつもとさんが静的型の野望を明かしてから2年半が経った。 その間の進捗は芳しいものとは言えないけれど、それでもまじめな研究として例えば多相型、推論、Ruby が行われている。普通の人は私のこの記事を読むよりもこちらを読んだ方がよいと思う。 じゃあなぜこの記事を書いたかというと、それでも一部の人には得るところがあると思っているからである。この記事の読者の中にはRubyKaigi 2014中に書かれたakrさんの日記で「非常に簡単化した静的解析」の話を読んだ人もいるのではないかと思う。この話をそのまま発展させた場合にどういう迷路に迷い込むのかという点についていくつかの知見を得たものの、これまでそれを書いていなかったのでちゃんと書くことにしたのだ。

さて、nurse/static-check.rbである。 これは大きく分けて3つの部分からなっている。定義されているメソッドのリストを得る部分、呼ばれているメソッドのリストを得る部分、あるメソッドから呼ばれているメソッドをよりfalse positiveを減らしつつ得る部分だ。

定義されているメソッドのリストを得る部分はより漏れがないようにしている。具体的には特異メソッドも取れるようになったのだが、デメリットとして全てのオブジェクトに特異クラスを作ってしまう。(最近のRubyではいわゆる即値にあたるオブジェクトでは特異クラスがつくれなくなっているので、それ以外)これを避けるにはRuby側に新たな機能が必要なんだけど、これ、ぼくいがいにだれかほしい?

2つ目の呼ばれているメソッドのリストを得る部分はakrさんのものから本質的な違いは無い。RubyVM::InstructionSequence.disasm(meth)の戻り値はStringだが、RubyVM::InstructionSequence.of(meth).to_a[13]の戻り値はオブジェクトなのでより構造的に扱えるというくらいだ。

このスクリプトで本質的なのは3つ目のfalse positiveを減らす部分だ。false positive、つまり存在しないものとして扱われて欲しいのに、メソッドを呼び出しているとされてしまう例は例えばGem.load_yamlにある以下のようなコードだ。

        if defined?(YAML::ENGINE) && YAML::ENGINE.yamler != "psych"
          YAML::ENGINE.yamler = "psych"
        end

これらのYAML::ENGINE、YAML::ENGINE.yamler、YAML::ENGINE.yamler=はRuby 1.9でのSyckからPsychへのYAMLライブラリ移行に際して存在した移行用の定数とメソッドで、2.2以降ではもはや存在しない。こういうコードをそのまま読んでしまうと、typo checkに引っかかってしまう。これを避けるため、静的実行のように、スタックを管理しながら絶対に実行されない部分を除外しようとしている。

まぁここまで書くと、もっと効率的に数学的に解析出来ないものかと思い始めるわけですね。わたしはSSA形式に変換した方がいいんじゃないかなと思いました。で、中断して今に至るわけです。ですから、RubyバイトコードSSA形式に変換して変数への代入をうまく処理しながらデッドコードを削除してtypo checkをしたりするのは読者の宿題とします。

macOS上のAPFSはUnicode Normalizationを行うのか?

iOS 10.3がリリースされましたが、APFSへの移行が含まれていて話題です。特に文字コード界隈ではHFS+で搭載されていた暗黙のUnicode Normalizationがなくなっている点が指摘されています1

ではmacOSではどうなのでしょうか。SierraならばすでにAPFSを扱うことが出来るので試してみましょう。

% hdiutil create -fs APFS -size 1GB foo.sparseimage
WARNING: You are using a pre-release version of the Apple File System called
APFS which is meant for evaluation and development purposes only.  Files
stored on this volume may not be accessible in future releases of OS X.

You should back up all of your data before using APFS and regularly back up
data while using APFS, including before upgrading to future releases of OS X.

Continue? [y/N] y
created: /Users/naruse/foo.sparseimage
% hdiutil mount /Users/naruse/foo.sparseimage
/dev/disk2              GUID_partition_scheme
/dev/disk2s1            Apple_APFS
/dev/disk2s1s1          41504653-0000-11AA-AA11-0030654 /Volumes/untitled
% touch ガ.test
% cp ガ.test /Volumes/untitled
% ls -1|grep .test|od -tx1
0000000    e3  82  ab  e3  82  99  2e  74  65  73  74  0a
0000014
%  ls -1 /Volumes/untitled|grep .test|od -tx1
0000000    e3  82  ac  2e  74  65  73  74  0a
0000011

カレントディレクトリ (HFS+) では e3 82 ab e3 82 99 と2コードポイントにNFD2されていましたが、APFSでは e3 82 ac と1コードポイントになっていますね。

というわけで、macOS上のAPFSもUnicode Normalizationを行わないという結論でした。AppleもやっとファイルシステムのレイヤーでNormalizationを行うのが愚かな行いだと気付いたようでなによりです。(Foundation APIが正規化を行い続けていることがわかったので、この発言は撤回します。)


  1. http://mjtsai.com/blog/2017/03/24/apfss-bag-of-bytes-filenames/ など

  2. 正確にはNFDとは多少違うのだが

そして最近の分岐予測について2

先日の日記で最近のIntel CPUでは間接分岐の分岐予測がほとんどミスしなくなっているという話を紹介しましたが、Branch Prediction and the Performance of Interpreters - Don't Trust Folkloreという論文にまさに同じことが書かれているのを見つけました。ていうか、この論文わたし見た形跡がある……。

去年にこの論文を見かけたときは「Direct threaded codeとかオワコン」って話までしか見てなかったんですが、今改めて見ると分岐予測が世代ごとに進化していてすごいって話に加えて、ITTAGEという分岐予測手法を使うと同じくらい当たるって書いてありますね。

ITTAGEはTAGE (TAgged GEometric length predictor)の間接分岐版で、TAGEは原論文がA case for (partially) tagged Geometric History Length Branch Predictionにあります。また、Why TAGE is the bestという解説がありました。

なお、少なくともSandy Bridge世代では最適化マニュアルに"This unit predicts the target address not only based on the EIP of the branch but also based on the execution path through which execution reached this EIP. "とあり、これはTAGEの動きと異なるように見えます。Haswellでは再設計と共にこの記述は消え、"Next generation branch prediction"に変わりましたが、Intelからの発表は"Improved performance and saves wasted work"にとどまっています。Agner氏のまとめでは"These observations may indicate that there are two branch prediction methods: a fast method tied to the µop cache and the instruction cache, and a slower method using a branch target buffer."とあるので、TAGEとはまた違う手法なのかもしれません。

魔法が現実なのはわかったが、ブラックボックスなのは相変わらずなのであった。

それだけだとアレなので、optcarrotでのperf statの結果を載せておきます。optcarrotとは何かという話はRuby で高速なプログラムを書くを。なお、mameさんのマシンはBroadwellだと聞きました。

Sandy Bridge

$ perf stat ./miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 13.28153785633246
checksum: 59662

 Performance counter stats for './miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

      17860.390687 task-clock (msec)         #    0.998 CPUs utilized
               214 context-switches          #    0.012 K/sec
                 0 cpu-migrations            #    0.000 K/sec
            15,470 page-faults               #    0.866 K/sec
    40,509,030,133 cycles                    #    2.268 GHz                     [83.34%]
    18,724,702,913 stalled-cycles-frontend   #   46.22% frontend cycles idle    [83.33%]
    11,614,302,978 stalled-cycles-backend    #   28.67% backend  cycles idle    [66.67%]
    52,111,018,708 instructions              #    1.29  insns per cycle
                                             #    0.36  stalled cycles per insn [83.34%]
     9,668,028,188 branches                  #  541.311 M/sec                   [83.32%]
       505,219,551 branch-misses             #    5.23% of all branches         [83.33%]

      17.897844545 seconds time elapsed

$ perf stat ./miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 13.027601466360375
checksum: 59662

 Performance counter stats for './miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

      14796.375448 task-clock (msec)         #    0.998 CPUs utilized
               185 context-switches          #    0.013 K/sec
                 0 cpu-migrations            #    0.000 K/sec
            14,404 page-faults               #    0.973 K/sec
    33,417,895,565 cycles                    #    2.259 GHz                     [83.29%]
    11,061,511,903 stalled-cycles-frontend   #   33.10% frontend cycles idle    [83.34%]
     7,225,689,220 stalled-cycles-backend    #   21.62% backend  cycles idle    [66.70%]
    51,166,479,085 instructions              #    1.53  insns per cycle
                                             #    0.22  stalled cycles per insn [83.38%]
     9,698,878,651 branches                  #  655.490 M/sec                   [83.35%]
       507,996,700 branch-misses             #    5.24% of all branches         [83.34%]

      14.820478694 seconds time elapsed

Ivy Bridge

%  perf stat ./miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 17.73951805406009
checksum: 59662

 Performance counter stats for './miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

      11017.367463      task-clock (msec)         #    0.997 CPUs utilized
               273      context-switches          #    0.025 K/sec
                 3      cpu-migrations            #    0.000 K/sec
             14877      page-faults               #    0.001 M/sec
       31898032583      cycles                    #    2.895 GHz
        9862135088      stalled-cycles-frontend   #   30.92% frontend cycles idle
   <not supported>      stalled-cycles-backend
       52153024400      instructions              #    1.63  insns per cycle
                                                  #    0.19  stalled cycles per insn
        9663177149      branches                  #  877.086 M/sec
         492985311      branch-misses             #    5.10% of all branches

      11.046473500 seconds time elapsed

# 1472224481 0:14:41 naruse@tk2-243-31075:~
%  perf stat ./miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 16.002392702765267
checksum: 59662

 Performance counter stats for './miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

      11865.744103      task-clock (msec)         #    0.999 CPUs utilized
                41      context-switches          #    0.003 K/sec
                 1      cpu-migrations            #    0.000 K/sec
             14884      page-faults               #    0.001 M/sec
       34584790642      cycles                    #    2.915 GHz
       11820020205      stalled-cycles-frontend   #   34.18% frontend cycles idle
   <not supported>      stalled-cycles-backend
       51054848410      instructions              #    1.48  insns per cycle
                                                  #    0.23  stalled cycles per insn
        9677225367      branches                  #  815.560 M/sec
         567975115      branch-misses             #    5.87% of all branches

      11.871797668 seconds time elapsed

Haswell

%  perf stat ./miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 28.363176942909437
checksum: 59662

 Performance counter stats for './miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

       7021.035983      task-clock:u (msec)       #    0.999 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
             14846      page-faults:u             #    0.002 M/sec
       18991845254      cycles:u                  #    2.705 GHz
       52072400309      instructions:u            #    2.74  insn per cycle
        9648278758      branches:u                # 1374.196 M/sec
          61237531      branch-misses:u           #    0.63% of all branches

       7.026493931 seconds time elapsed

%  perf stat ./miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 27.269785989915373
checksum: 59662

 Performance counter stats for './miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

       7214.329827      task-clock:u (msec)       #    0.999 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
             14849      page-faults:u             #    0.002 M/sec
       19775865899      cycles:u                  #    2.741 GHz
       50975216372      instructions:u            #    2.58  insn per cycle
        9662536352      branches:u                # 1339.353 M/sec
          67884021      branch-misses:u           #    0.70% of all branches

       7.218712639 seconds time elapsed

Skylake

%  perf stat ./miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 45.18173733234584
checksum: 59662

 Performance counter stats for './miniruby-gcc48 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

       4496.992449      task-clock (msec)         #    1.000 CPUs utilized
                 6      context-switches          #    0.001 K/sec
                 1      cpu-migrations            #    0.000 K/sec
             14857      page-faults               #    0.003 M/sec
       17488535114      cycles                    #    3.889 GHz
       52123910662      instructions              #    2.98  insn per cycle
        9657149412      branches                  # 2147.468 M/sec
          54148235      branch-misses             #    0.56% of all branches

       4.498014828 seconds time elapsed

%  perf stat ./miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes
ruby 2.4.0dev (2016-08-26 trunk 56013) [x86_64-linux]
fps: 42.543931298125635
checksum: 59662

 Performance counter stats for './miniruby-gcc611 -v -Ioptcarrot/lib -r./optcarrot/tools/shim optcarrot/bin/optcarrot --benchmark optcarrot/examples/Lan_Master.nes':

       4662.130752      task-clock (msec)         #    1.000 CPUs utilized
                 4      context-switches          #    0.001 K/sec
                 1      cpu-migrations            #    0.000 K/sec
             13765      page-faults               #    0.003 M/sec
       18093681660      cycles                    #    3.881 GHz
       51137911290      instructions              #    2.83  insn per cycle
        9698686892      branches                  # 2080.312 M/sec
          74335218      branch-misses             #    0.77% of all branches

       4.662798673 seconds time elapsed

ムーアの法則の終わり、そして最近の分岐予測について

ムーアの法則の終わり、そして最近の分岐予測について

僕らx86の大地の上に生きるものは、この10年Intelが告げるTick-Tockの鐘の音にあわせてムーアの法則の恩恵を享受してきた。*1 *2 しかし、Kaby Lakeの14nmプロセス採用つまり、2年おきのプロセスルール刷新を諦めたことを持って、ムーアの法則は終焉を迎えたとされる。が、この認識は本当に正しいのだろうか。

ムーアの1965年の論文では、後のムーアの法則を”The complexity for minimum component costs has increased at a rate of roughly a factor of two per year"と表現している。人々はこの”complexity"は単位面積あたりのトランジスタ数のことだとこの50年間理解してきた。もっと言えばこの10年はプロセス・ルールのことだったかもしれない。だが、CPUがその内に集積してきたものはトランジスタだけだったのだろうか。

前述の論文のタイトルは"Cramming more components onto integrated circuits”という。Intelは様々なものをCPUという集積回路に詰め込んできた。しかし、このタイトルとムーアの法則の記述をあわせれば、真にCPUが集積したものが何かは明らかだろう。それは「複雑さ」だ。多数のSIMD命令も、AVXの奇怪なVEXエンコーディングも、すべてこの世界の複雑さを小さな魔法の石に封じ込めた結果なのだ。

分岐予測の進化

さて、高度なCPUにはブラックボックスが多数含まれますが、分岐予測はその中の最たるものの一つでしょう。CPUの最適化情報豊富なIntel® 64 and IA-32 Architectures Optimization Reference Manualを見ても毎度"Improved branch predictor."としか書かれていません。

とはいえ、手元にCPUはあるわけで、実際に動かしてその実力を測ることは出来るので測ってみましょう。

計測に使ったのはSpeed of various interpreter dispatch techniques V2のthreading.tar.gzの./directです。現代においてこれが適切なベンチマークだとは思わないのですが、間接分岐については多少参考にはなるんじゃないかな……。

SandyBridge

naruse@chkbuild008:~/threading$ grep -m1 'model name' /proc/cpuinfo
model name  : Intel(R) Xeon(R) CPU E5-2630L 0 @ 2.00GHz

naruse@chkbuild008:~/threading$ perf stat ./direct-gcc48

 Performance counter stats for './direct':

        277.440861 task-clock (msec)         #    0.998 CPUs utilized
                 5 context-switches          #    0.018 K/sec
                 0 cpu-migrations            #    0.000 K/sec
               112 page-faults               #    0.404 K/sec
       650,780,115 cycles                    #    2.346 GHz                     [82.74%]
       365,836,274 stalled-cycles-frontend   #   56.22% frontend cycles idle    [82.72%]
       377,885,001 stalled-cycles-backend    #   58.07% backend  cycles idle    [67.70%]
       423,892,636 instructions              #    0.65  insns per cycle
                                             #    0.89  stalled cycles per insn [84.15%]
       208,884,768 branches                  #  752.898 M/sec                   [84.14%]
        12,251,769 branch-misses             #    5.87% of all branches         [82.71%]

       0.278114864 seconds time elapsed

naruse@chkbuild008:~/threading$ perf stat ../direct-gcc54

 Performance counter stats for '../direct-gcc54':

        155.542201 task-clock (msec)         #    0.996 CPUs utilized
                 3 context-switches          #    0.019 K/sec
                 0 cpu-migrations            #    0.000 K/sec
               113 page-faults               #    0.726 K/sec
       352,393,558 cycles                    #    2.266 GHz                     [82.03%]
       141,991,479 stalled-cycles-frontend   #   40.29% frontend cycles idle    [82.23%]
       160,691,365 stalled-cycles-backend    #   45.60% backend  cycles idle    [69.17%]
       379,813,966 instructions              #    1.08  insns per cycle
                                             #    0.42  stalled cycles per insn [84.58%]
       160,216,299 branches                  # 1030.050 M/sec                   [84.57%]
             3,933 branch-misses             #    0.00% of all branches         [82.03%]

       0.156168350 seconds time elapsed

Ivy Bridge

% grep -m1 'model name' /proc/cpuinfo
model name      : Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz

%  perf stat ../direct-gcc48

 Performance counter stats for '../direct-gcc48':

        238.146900      task-clock (msec)         #    0.982 CPUs utilized
                37      context-switches          #    0.155 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                42      page-faults               #    0.176 K/sec
         689162737      cycles                    #    2.894 GHz
         403352479      stalled-cycles-frontend   #   58.53% frontend cycles idle
   <not supported>      stalled-cycles-backend
         430913321      instructions              #    0.63  insns per cycle
                                                  #    0.94  stalled cycles per insn
         210172241      branches                  #  882.532 M/sec
          14205738      branch-misses             #    6.76% of all branches

       0.242429416 seconds time elapsed

% perf stat ./direct-gcc54

 Performance counter stats for './direct-gcc54':

        120.812507      task-clock (msec)         #    0.996 CPUs utilized
                 0      context-switches          #    0.000 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                41      page-faults               #    0.339 K/sec
         355605784      cycles                    #    2.943 GHz
         170213145      stalled-cycles-frontend   #   47.87% frontend cycles idle
   <not supported>      stalled-cycles-backend
         380562594      instructions              #    1.07  insns per cycle
                                                  #    0.45  stalled cycles per insn
         160106383      branches                  # 1325.247 M/sec
              9808      branch-misses             #    0.01% of all branches

       0.121333298 seconds time elapsed

Haswell

% grep -m1 'model name' /proc/cpuinfo
model name      : Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz
%  perf stat ./direct

 Performance counter stats for './direct':

        159.226456      task-clock:u (msec)       #    0.996 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
                35      page-faults:u             #    0.220 K/sec
         321780650      cycles:u                  #    2.021 GHz
         380085245      instructions:u            #    1.18  insn per cycle
         160015808      branches:u                # 1004.957 M/sec
              5206      branch-misses:u           #    0.00% of all branches

       0.159844405 seconds time elapsed

%  perf stat ../direct-gcc48

 Performance counter stats for '../direct-gcc48':

        205.179841      task-clock:u (msec)       #    0.995 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
                36      page-faults:u             #    0.175 K/sec
         448041978      cycles:u                  #    2.184 GHz
         430085324      instructions:u            #    0.96  insn per cycle
         210015836      branches:u                # 1023.570 M/sec
              4887      branch-misses:u           #    0.00% of all branches

       0.206141759 seconds time elapsed

%  perf stat ../direct-gcc54

 Performance counter stats for '../direct':

        158.532437      task-clock:u (msec)       #    0.995 CPUs utilized
                 0      context-switches:u        #    0.000 K/sec
                 0      cpu-migrations:u          #    0.000 K/sec
                35      page-faults:u             #    0.221 K/sec
         315471369      cycles:u                  #    1.990 GHz
         380085288      instructions:u            #    1.20  insn per cycle
         160015810      branches:u                # 1009.357 M/sec
              6829      branch-misses:u           #    0.00% of all branches

       0.159275797 seconds time elapsed

Skylake

% grep -m1 'model name' /proc/cpuinfo
model name      : Intel(R) Xeon(R) CPU E3-1245 v5 @ 3.50GHz
% perf stat ./direct

 Performance counter stats for './direct':

         84.458565      task-clock (msec)         #    0.996 CPUs utilized
                 0      context-switches          #    0.000 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                38      page-faults               #    0.450 K/sec
         300759565      cycles                    #    3.561 GHz
         380503237      instructions              #    1.27  insn per cycle
         160093203      branches                  # 1895.524 M/sec
              9349      branch-misses             #    0.01% of all branches

       0.084794713 seconds time elapsed


% perf stat ../direct-gcc54

 Performance counter stats for '../direct':

        101.940704      task-clock (msec)         #    0.996 CPUs utilized
                 0      context-switches          #    0.000 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                37      page-faults               #    0.363 K/sec
         361064330      cycles                    #    3.542 GHz
         380540900      instructions              #    1.05  insn per cycle
         160100883      branches                  # 1570.530 M/sec
             18006      branch-misses             #    0.01% of all branches

       0.102305561 seconds time elapsed

訂正: 初出の記事ではSkylakeの値が-O3にしたものになっていました。-Oだと以上の通りです。

考察

所要時間はCPUの周波数も影響するのでその分は差し引いてみてくださいね。(本当はTurbo Boostオフにするべきなんだけど、手元のマシンじゃないんだゴメンな……)

考察と言ってもそこまで詳しいわけではないので実のあることは言えないのですが、今でもその進化が続いていることは見ればわかるでしょう。また、分岐予測に詳しい人ほど最近のIntel CPUの分岐予測的中率には驚かれるのではないかと思いました。

まとめ

あんまり賢い解説もないまま締めに入りますが、あんまり最近のIntel CPUの分岐予測について言及した記事って英語含めてもないと思うので、これで盛り上がって誰か解説してくれるといいなと思います!

追記

Sandy Bridgeが著しく悪かったのはgcc5.4以降が賢いからっぽい。

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

000000000040052d <main>:
  40052d:       48 8b 35 2c 0b 20 00    mov    0x200b2c(%rip),%rsi        # 601060 <prog.1723>
  400534:       48 89 f2                mov    %rsi,%rdx
  400537:       b9 80 96 98 00          mov    $0x989680,%ecx
  40053c:       b8 68 10 60 00          mov    $0x601068,%eax
  400541:       ff e2                   jmpq   *%rdx
  400543:       48 8b 10                mov    (%rax),%rdx
  400546:       48 8d 40 08             lea    0x8(%rax),%rax
  40054a:       eb f5                   jmp    400541 <main+0x14>
  40054c:       48 8b 10                mov    (%rax),%rdx
  40054f:       48 8d 40 08             lea    0x8(%rax),%rax
  400553:       eb ec                   jmp    400541 <main+0x14>
  400555:       48 8b 10                mov    (%rax),%rdx
  400558:       48 8d 40 08             lea    0x8(%rax),%rax
  40055c:       eb e3                   jmp    400541 <main+0x14>
  40055e:       48 8b 10                mov    (%rax),%rdx
  400561:       48 8d 40 08             lea    0x8(%rax),%rax
  400565:       eb da                   jmp    400541 <main+0x14>
  400567:       48 8b 10                mov    (%rax),%rdx
  40056a:       48 8d 40 08             lea    0x8(%rax),%rax
  40056e:       eb d1                   jmp    400541 <main+0x14>
  400570:       85 c9                   test   %ecx,%ecx
  400572:       7e 0d                   jle    400581 <main+0x54>
  400574:       83 e9 01                sub    $0x1,%ecx
  400577:       48 89 f2                mov    %rsi,%rdx
  40057a:       b8 68 10 60 00          mov    $0x601068,%eax
  40057f:       eb c0                   jmp    400541 <main+0x14>
  400581:       48 83 ec 08             sub    $0x8,%rsp
  400585:       bf 00 00 00 00          mov    $0x0,%edi
  40058a:       e8 a1 fe ff ff          callq  400430 <exit@plt>
  40058f:       90                      nop
%  gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.2) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

0000000000400526 <main>:                                                                   [37/1887]
  400526:       48 8b 35 33 0b 20 00    mov    0x200b33(%rip),%rsi        # 601060 <prog.1832>
  40052d:       48 89 f2                mov    %rsi,%rdx
  400530:       b9 80 96 98 00          mov    $0x989680,%ecx
  400535:       b8 68 10 60 00          mov    $0x601068,%eax
  40053a:       eb 07                   jmp    400543 <main+0x1d>
  40053c:       48 8b 10                mov    (%rax),%rdx
  40053f:       48 8d 40 08             lea    0x8(%rax),%rax
  400543:       ff e2                   jmpq   *%rdx
  400545:       48 8b 10                mov    (%rax),%rdx
  400548:       48 8d 40 08             lea    0x8(%rax),%rax
  40054c:       eb f5                   jmp    400543 <main+0x1d>
  40054e:       48 8b 10                mov    (%rax),%rdx
  400551:       48 8d 40 08             lea    0x8(%rax),%rax
  400555:       eb ec                   jmp    400543 <main+0x1d>
  400557:       48 8b 10                mov    (%rax),%rdx
  40055a:       48 8d 40 08             lea    0x8(%rax),%rax
  40055e:       eb e3                   jmp    400543 <main+0x1d>
  400560:       48 8b 10                mov    (%rax),%rdx
  400563:       48 8d 40 08             lea    0x8(%rax),%rax
  400567:       eb da                   jmp    400543 <main+0x1d>
  400569:       85 c9                   test   %ecx,%ecx
  40056b:       7e 0d                   jle    40057a <main+0x54>
  40056d:       83 e9 01                sub    $0x1,%ecx
  400570:       48 89 f2                mov    %rsi,%rdx
  400573:       b8 68 10 60 00          mov    $0x601068,%eax
  400578:       eb c9                   jmp    400543 <main+0x1d>
  40057a:       48 83 ec 08             sub    $0x8,%rsp
  40057e:       bf 00 00 00 00          mov    $0x0,%edi
  400583:       e8 88 fe ff ff          callq  400410 <exit@plt>
  400588:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
  40058f:       00

追記2

かと思われたが、HaswellだとGCC4.8で作ったバイナリでも分岐予測ミスは0.00%だった。なお、GCC4.8バイナリをIvy Bridgeマシンで実行するとSandyと大差ない結果なので、分岐予測能力はSandyでもそれなりにすごくて、Haswellはもっとすごいってことかな。

追記3

なんか前にやろうとしてできなかった気がしたんだけど、今改めてGCCのマニュアル見たら-fprofile-generateつけて-fprofile-useつけるだけだった。

%  perf stat ./direct

 Performance counter stats for './direct':

        121.760309      task-clock (msec)         #    0.993 CPUs utilized
                 2      context-switches          #    0.016 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                42      page-faults               #    0.345 K/sec
         353933863      cycles                    #    2.907 GHz
         167429077      stalled-cycles-frontend   #   47.31% frontend cycles idle
   <not supported>      stalled-cycles-backend
         380553084      instructions              #    1.08  insns per cycle
                                                  #    0.44  stalled cycles per insn
         160104472      branches                  # 1314.915 M/sec
              7542      branch-misses             #    0.00% of all branches

       0.122630111 seconds time elapsed

0000000000400526 <main>:
  400526:       48 8b 0d 33 0b 20 00    mov    0x200b33(%rip),%rcx        # 601060 <prog.1832>
  40052d:       48 89 ca                mov    %rcx,%rdx
  400530:       be 80 96 98 00          mov    $0x989680,%esi
  400535:       b8 68 10 60 00          mov    $0x601068,%eax
  40053a:       eb 07                   jmp    400543 <main+0x1d>
  40053c:       48 8b 10                mov    (%rax),%rdx
  40053f:       48 8d 40 08             lea    0x8(%rax),%rax
  400543:       ff e2                   jmpq   *%rdx
  400545:       48 8b 10                mov    (%rax),%rdx
  400548:       48 8d 40 08             lea    0x8(%rax),%rax
  40054c:       eb f5                   jmp    400543 <main+0x1d>
  40054e:       48 8b 10                mov    (%rax),%rdx
  400551:       48 8d 40 08             lea    0x8(%rax),%rax
  400555:       eb ec                   jmp    400543 <main+0x1d>
  400557:       48 8b 10                mov    (%rax),%rdx
  40055a:       48 8d 40 08             lea    0x8(%rax),%rax
  40055e:       eb e3                   jmp    400543 <main+0x1d>
  400560:       48 8b 10                mov    (%rax),%rdx
  400563:       48 8d 40 08             lea    0x8(%rax),%rax
  400567:       eb da                   jmp    400543 <main+0x1d>
  400569:       85 f6                   test   %esi,%esi
  40056b:       7e 0d                   jle    40057a <main+0x54>
  40056d:       83 ee 01                sub    $0x1,%esi
  400570:       48 89 ca                mov    %rcx,%rdx
  400573:       b8 68 10 60 00          mov    $0x601068,%eax
  400578:       eb c9                   jmp    400543 <main+0x1d>
  40057a:       48 83 ec 08             sub    $0x8,%rsp
  40057e:       bf 00 00 00 00          mov    $0x0,%edi
  400583:       e8 88 fe ff ff          callq  400410 <exit@plt>
  400588:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)
  40058f:       00

あんまかわりませんね。

ちなみに-O3だと以下のような調子なので、最適化レベルを上げると意味がある模様。

%  gcc -O3 -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
 main()
 ^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
   exit(0);
   ^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360659 0:17:39 naruse@tk2-243-31075:~/threading
% perf stat ./direct

 Performance counter stats for './direct':

         46.157782      task-clock (msec)         #    0.980 CPUs utilized
                 0      context-switches          #    0.000 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                41      page-faults               #    0.888 K/sec
         135493298      cycles                    #    2.935 GHz
          49319786      stalled-cycles-frontend   #   36.40% frontend cycles idle
   <not supported>      stalled-cycles-backend
         320446132      instructions              #    2.37  insns per cycle
                                                  #    0.15  stalled cycles per insn
         110085385      branches                  # 2384.980 M/sec
              6551      branch-misses             #    0.01% of all branches

       0.047097047 seconds time elapsed

0000000000400430 <main>:
  400430:       48 8b 35 29 0c 20 00    mov    0x200c29(%rip),%rsi        # 601060 <prog.1832>
  400437:       b9 80 96 98 00          mov    $0x989680,%ecx
  40043c:       b8 68 10 60 00          mov    $0x601068,%eax
  400441:       ff e6                   jmpq   *%rsi
  400443:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  400448:       85 c9                   test   %ecx,%ecx
  40044a:       7e 64                   jle    4004b0 <main+0x80>
  40044c:       83 e9 01                sub    $0x1,%ecx
  40044f:       b8 68 10 60 00          mov    $0x601068,%eax
  400454:       ff e6                   jmpq   *%rsi
  400456:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  40045d:       00 00 00
  400460:       48 8b 10                mov    (%rax),%rdx
  400463:       48 83 c0 08             add    $0x8,%rax
  400467:       ff e2                   jmpq   *%rdx
  400469:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  400470:       48 8b 10                mov    (%rax),%rdx
  400473:       48 83 c0 08             add    $0x8,%rax
  400477:       ff e2                   jmpq   *%rdx
  400479:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  400480:       48 8b 10                mov    (%rax),%rdx
  400483:       48 83 c0 08             add    $0x8,%rax
  400487:       ff e2                   jmpq   *%rdx
  400489:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  400490:       48 8b 10                mov    (%rax),%rdx
  400493:       48 83 c0 08             add    $0x8,%rax
  400497:       ff e2                   jmpq   *%rdx
  400499:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  4004a0:       48 8b 10                mov    (%rax),%rdx
  4004a3:       48 83 c0 08             add    $0x8,%rax
  4004a7:       ff e2                   jmpq   *%rdx
  4004a9:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  4004b0:       48 83 ec 08             sub    $0x8,%rsp
  4004b4:       31 ff                   xor    %edi,%edi
  4004b6:       e8 55 ff ff ff          callq  400410 <exit@plt>
  4004bb:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
% gcc -O3 -fprofile-use -fomit-frame-pointer direct.c -o direct
direct.c:4:1: warning: return type defaults to 'int' [-Wimplicit-int]
 main()
 ^
direct.c: In function 'main':
direct.c:32:3: warning: implicit declaration of function 'exit' [-Wimplicit-function-declaration]
   exit(0);
   ^
direct.c:32:3: warning: incompatible implicit declaration of built-in function 'exit'
direct.c:32:3: note: include '<stdlib.h>' or provide a declaration of 'exit'
# 1471360636 0:17:16 naruse@tk2-243-31075:~/threading
%  perf stat ./direct

 Performance counter stats for './direct':

         46.108716      task-clock (msec)         #    0.981 CPUs utilized
                 0      context-switches          #    0.000 K/sec
                 0      cpu-migrations            #    0.000 K/sec
                41      page-faults               #    0.889 K/sec
         123812228      cycles                    #    2.685 GHz
          39859092      stalled-cycles-frontend   #   32.19% frontend cycles idle
   <not supported>      stalled-cycles-backend
         320466395      instructions              #    2.59  insns per cycle
                                                  #    0.12  stalled cycles per insn
         110090077      branches                  # 2387.620 M/sec
              6079      branch-misses             #    0.01% of all branches

       0.046992565 seconds time elapsed


0000000000400430 <main>:
  400430:       48 8b 0d 29 0c 20 00    mov    0x200c29(%rip),%rcx        # 601060 <prog.1832>
  400437:       be 80 96 98 00          mov    $0x989680,%esi
  40043c:       b8 68 10 60 00          mov    $0x601068,%eax
  400441:       ff e1                   jmpq   *%rcx
  400443:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  400448:       48 8b 10                mov    (%rax),%rdx
  40044b:       48 83 c0 08             add    $0x8,%rax
  40044f:       ff e2                   jmpq   *%rdx
  400451:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  400458:       4c 8b 18                mov    (%rax),%r11
  40045b:       48 83 c0 08             add    $0x8,%rax
  40045f:       41 ff e3                jmpq   *%r11
  400462:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  400468:       85 f6                   test   %esi,%esi
  40046a:       7e 3e                   jle    4004aa <main+0x7a>
  40046c:       83 ee 01                sub    $0x1,%esi
  40046f:       b8 68 10 60 00          mov    $0x601068,%eax
  400474:       ff e1                   jmpq   *%rcx
  400476:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  40047d:       00 00 00
  400480:       4c 8b 00                mov    (%rax),%r8
  400483:       48 83 c0 08             add    $0x8,%rax
  400487:       41 ff e0                jmpq   *%r8
  40048a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  400490:       4c 8b 08                mov    (%rax),%r9
  400493:       48 83 c0 08             add    $0x8,%rax
  400497:       41 ff e1                jmpq   *%r9
  40049a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  4004a0:       4c 8b 10                mov    (%rax),%r10
  4004a3:       48 83 c0 08             add    $0x8,%rax
  4004a7:       41 ff e2                jmpq   *%r10
  4004aa:       50                      push   %rax
  4004ab:       31 ff                   xor    %edi,%edi
  4004ad:       e8 5e ff ff ff          callq  400410 <exit@plt>
  4004b2:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  4004b9:       00 00 00
  4004bc:       0f 1f 40 00             nopl   0x0(%rax)

*1:ムーアの法則の初出は1965年だが、IntelがTick-Tockモデルを採用したのは2006年のCoreマイクロアーキテクチャからである。

*2:2002年の頃を思い出して欲しいのだが、21世紀になってまもなくフリーランチの時代は終わっていたのではなかったか?

YARV命令ごとの実行コストを知るには

プログラムのボトルネックを探すには大きく分けて二つの方法があります。心眼を研ぎ澄ましていきなり最適化してみてから考えるのと、何かしらのツールでサイクル数やCPU時間を計測して地道に探す方法ですね。皆さん普通は前者だと思うんですが、それが行き詰まってしまうこともあります。

後者のようにprofileを取っていく場合、手軽にCレベルでのprofileがとれて今わたしの中で一大ブームを巻き起こしているのがperf(3)なわけですが、Rubyのprofileを取ると往々にして以下のような結果になるわけです。(よい子のみんなはCレベルでのprofileではなく、stackprofを使ってRubyレベルでのprofileをとろうな!)

sudo perf report --stdio --no-children -g none -d miniruby
# To display the perf.data header info, please use --header/--header-only options.
#
# dso: miniruby
#
# Total Lost Samples: 0
#
# Samples: 19K of event 'cycles'
# Event count (approx.): 15175910905
#
# Overhead  Command   Symbol
# ........  ........  ....................................................
#
    52.76%  miniruby  [.] vm_exec_core
     4.07%  miniruby  [.] rb_vm_cref_replace_with_duplicated_cref
     3.02%  miniruby  [.] rb_callable_method_entry_with_refinements
     2.70%  miniruby  [.] rb_ary_unshift
     2.66%  miniruby  [.] rb_clear_method_cache_by_class
     2.25%  miniruby  [.] vm_call_iseq_setup_normal_0start_1params_4locals
     1.91%  miniruby  [.] ary_ensure_room_for_push
     1.43%  miniruby  [.] match_at
     1.12%  miniruby  [.] st_init_strtable_with_size
     1.06%  miniruby  [.] vm_call_iseq_setup_normal_0start_0params_2locals
     0.95%  miniruby  [.] rb_ary_tmp_new_fill
     0.82%  miniruby  [.] st_init_strtable
     0.80%  miniruby  [.] rb_ary_transpose
     0.80%  miniruby  [.] rb_ary_modify
     0.78%  miniruby  [.] rb_ary_rotate_bang
     0.77%  miniruby  [.] vm_call_iseq_setup_normal_0start_0params_1locals
     0.64%  miniruby  [.] int_and
     0.64%  miniruby  [.] rb_respond_to
     0.58%  miniruby  [.] vm_call_iseq_setup
     0.56%  miniruby  [.] rb_ary_free
     0.56%  miniruby  [.] flo_eql
     0.48%  miniruby  [.] st_init_numtable_with_size
     0.46%  miniruby  [.] vm_exec
     0.46%  miniruby  [.] rb_iv_set
     0.44%  miniruby  [.] gc_mark_children
     0.31%  miniruby  [.] rb_free_method_entry
     0.29%  miniruby  [.] rb_check_convert_type
     0.28%  miniruby  [.] rb_ary_splice
     0.27%  miniruby  [.] rb_mod_protected_method_defined
     0.26%  miniruby  [.] rb_int_rshift
     0.25%  miniruby  [.] ruby_yyparse
     0.23%  miniruby  [.] gc_mark_maybe
     0.23%  miniruby  [.] forward_search_range
     0.23%  miniruby  [.] gc_sweep_step
     0.20%  miniruby  [.] st_foreach
     0.19%  miniruby  [.] rb_ary_initialize

vm_exec_coreというのはYARVの中核である命令ディスパッチ部分ですね。まぁ、そりゃそうなるかという感じではあるのですが、アセンブラで7000命令ほどある関数にぱらぱらと0.xx%の負荷を出されてもどこがボトルネックかわかりません。

そもそも知りたいのはYARV命令ごとの負荷なのですから、その通り集計すればいいはずですね。命令のアドレスとコストは既にあります。insns.defやそれから生成するvm.incYARV命令との紐付けはソースコードを上から順に正規表現マッチして見ていくだけですから、あとは命令アドレスとソースコードを紐付けるだけです。

この一見絶望的に困難に思われる仕事ですが、実際はそれほどでもありません。gdbデバッグする際や、RubyがSEGVした時のバックトレースにソースコードのファイル名と行数が出ているのを見た人も多いでしょう。実行バイナリには各種デバッグ用の情報が格納されているので、それを参照すればよいのです。

さぁ、道具は全て揃いました。あとはつなげるだけです。つなげたものは以下の通り。

% ./yarv-profile.rb
            opt_aref: 17.75
           opt_minus: 13.45
    opt_newarray_min: 11.16
    opt_newarray_max:  8.40
            opt_aset:  6.01
                    :  5.82
 setinstancevariable:  5.45
          splatarray:  4.96
        checkkeyword:  4.69
            opt_plus:  3.73
      getinlinecache:  3.13
               leave:  2.48
            duparray:  2.31
            newarray:  2.27
                once:  1.97
            opt_size:  1.22
         adjuststack:  1.07
            getlocal:  0.89
           branchnil:  0.84
         defineclass:  0.80
           getglobal:  0.51
         invokeblock:  0.48
                 nop:  0.39
            branchif:  0.25
      setinlinecache:  0.22
        branchunless:  0.12
              opt_ge:  0.11
    setclassvariable:  0.11

opt_arefで時間を食っているのはまぁよいとして、opt_minusでの時間が多いのはちょっと気になりますね。絶対数が多いだけかな。まぁ今までわかりづらかったことが数値で見えるようになりました。

めでたしめでたし