ラベル プログラミング の投稿を表示しています。 すべての投稿を表示
ラベル プログラミング の投稿を表示しています。 すべての投稿を表示

2015年5月6日水曜日

Altera SoC Helio で SDRAM の HPS/FPGA 共有(作業編)

前回の記事で詳細には踏み込んでいないものの、ほぼ必要な情報が揃っているはずです。
実際の作業を始めましょう。
でもまず、作業を始めるのにあたって必要なものが欠けています。
Helio として最低限動作可能な FPGA 側のリファレンス実装です。

作業編

リファレンスデザインの入手

Helio は GSRD (Golden System Reference Design) というものに則って設計/実装/提供されています。
生憎こちら、GSRD という枠組みについては詳しくなく、どこからどこまでが GSRD なのかはよくわからないのですが説明によると, Altera か Xilinx かにはよらず

FPGA(GHRD) + ARM SoC + Linux 環境  = GSRD

ということのようです。
Altera だろうとそうでなかろうと GSRD に従った設計がなされているものについてはある程度似たような環境が用意されているということですね。
ここで重要なのは、主に FPGA 側の設計のリファレンスデザインである GHRD (Golden Hardware Reference Design) のほうですね。

Getting Start Guide に従ってサンプルを動かした人ならば既に手元にあるはずです。
しかしながらドキュメントに従って cv_soc_devkit_ghrd.tar.gz をゲットしてしまった人は残念。理由はわかりませんがこれは Helio では動かず、 Helio には以下から専用のものを入手しましょう。
helio_ghrd_5csxc4_v14.*.zip が正解です(Quartus II のバージョンに合わせて選んでください)。

http://www.rocketboards.org/foswiki/Documentation/HelioResourcesForRev14

に一通りあります (ボードの Revision が 14 用。 Quartus のバージョンと紛らわしいですが、今はたまたまどっちも 14 です)。
間違えると回路が正しくても Linux がブートしなくなります。
なんというハメでしょうね。僕はこれにハマって二三日悩みました。(.sof イメージは焼いても電源を切ると揮発するので、復旧自体は簡単です)

GHRD の中身は全て Quartus II のプロジェクト及び Qsys で扱う IP とサンプルの helio_ghrd_top.v です。
自分でビルドしない限り、一切のビルド物は含まれていません。

helio_ghrd_top.v を開くと、殆どの信号は soc_system という下位回路に結線されているのがわかります。
その soc_system が GHRD の本体であり、 HPS のインターフェイスを実装した(あるいはこれから実装する)回路であります。

ところが soc_system の実装自体は .v としては付属しません。
soc_system は全て IP として提供されており、 soc_system.qsys から Qsys で生成して入手します。
このへんの手順は Getting Start Guide でも一通り説明されていますので、僕のような noob でも脳細胞が Hi-Z になったり X になったりすることなく進めました。

これからの作業は殆ど Qsys と普通のエディタで行います。 Quartus II はビルド(Analysis & Synthesis, Place & Route, Fitting) と死んで再起動くらいしかしません。

なぜここで GHRD を必要とするかはここまででお解りと思います。
このリファレンスデザインを Qsys でカスタマイズしたり、外部に設計した回路に繋げることでシステムを実装していくわけです。
どれを IP にしてくっつけるか、どれを外部に引き出すかは任意です。

SDRAM Controller のインターフェイスを取り出す

soc_system の hps_0 というインスタンスに結線されている f2h_sdram_data というのが SDRAM Controller のインターフェイスです。
これは信号の種類を見れば解る通り Avalon MM Slave のインターフェイスの形をしております。
hps_0 というインスタンス(下位回路への結線)は、ソフト的にいうと複数のインターフェイスを多重継承したようなイメージですね。
飽くまでこれはイメージで、実際には各信号ごとに wire が結線されております。

Qsys を使ってリファレンスデザインをカスタマイズしていくと書きましたが、 IP を変更すると毎回 "Generate HDL" を実行せねばならず、そこそこ時間がかかってしまいます。
ここはこのインターフェイスを外部に引き出して、 IP の外にある helio_ghrd_top.v で回路を実装したほうがよいでしょう。

helio_ghrd_top.v からは hps_0 の上位回路である soc_system しか見えません。
まずは hps_0 の f2h_sdram_data を soc_system に引き出さねばなりません。
普通の FPGA であればピンに出ているのですが、 SoC では外部といっても内部です。 ピンが出ているとは限りません。
このへんは Qsys を使い慣れていなければわからないので、身近なハード屋さんに助けてもらいました。
引き出したいインターフェイスを右クリックして "Export as" を選べばオッケーのようです。
Export できた!

hps_0 の上のほう、 f2h_sdram0_data の左側がタグのようになっています。これが外部に引き出せた状況です。
各カラムは左から Name, Description, Export name, Associate Clock となっております。
Export の column にある名前で上位回路に自動的に結線されます。
典型的には、
(接続先インスタンス名)_(信号名) 

という名前になるようですね。

バス幅の決定と HDL の再生成


それから hps_0 を右クリックして "Edit" を選ぶと、プロパティシートから細かい設定を変更できます。
デフォルトは f2h_sdram_data のバス幅として 256bit が設定されています。
メモリのデータバスは 16+16bit で 32bit なので、まずはデータバスに合わせておこうと32 に変更します。
そして Generate HDL を再度行います。
この場合はこうなりました。
        input  wire [29:0]  hps_0_f2h_sdram0_data_address,
        input  wire [7:0]   hps_0_f2h_sdram0_data_burstcount,
        output wire         hps_0_f2h_sdram0_data_waitrequest,
        output wire [31:0] hps_0_f2h_sdram0_data_readdata,
        output wire         hps_0_f2h_sdram0_data_readdatavalid,
        input  wire         hps_0_f2h_sdram0_data_read,
        input  wire [31:0] hps_0_f2h_sdram0_data_writedata,
        input  wire [3:0]  hps_0_f2h_sdram0_data_byteenable,
        input  wire         hps_0_f2h_sdram0_data_write,
あとはこれに対して Master となる回路を書けばメモリのアクセスが可能になります。

ところで、元々 f2h_sdram0_data はどこに繋がっているのでしょうか。
Export すればこのインターフェイスを外から使えるようになりますが、それだけでは元々ここに繋がっていた回路は使えなくなってしまいます。
f2sdram_only_master に繋がっているのは Qsys 上でも確認できますが、この副作用を看過できるかどうかは f2sdram_only_master の先を注意深く調べる必要があります。
調べてみたところ、これは幾つかの FIFO を経由して JTAG に繋がっていました。
JTAG からのリクエストを非同期で処理するための回路のようです。
SDRAM Controller はこれを調停可能なはずですが、今回は華麗にカットしました。

Master の回路を書く

Avalon MM の仕様書より、タイミングチャートを調べて実装します。
メモリアクセスの方法は、基本的な同期 RW 以外にもパイプラインリード、バースト転送などがありますが、今回はまず基本的なライトだけを実装します。

Figure 3-3: Read and Write Transfers with Waitrequest の右半分がそれです。

言葉で説明すると、

a. (Master が)パラメータを設定して Write を立てると
b. ビジー状態を示す WaitRequest が(Slave によって) 1 にドライブされ、
c. 書き込みが完了すると (Slave によって) WaitRequest が 0 にドライブされるので、
d. (Master は)パラメータは次のクロックの立ち上がりまでは保持し続けること

ということです。
今度は W と R がゲシュタルト崩壊しそうなので WaitRequest は Busy と読み替えたほうがいいかも知れません。
Write を立てるときには WaitRequest は(あと当然 Write も) 0 でなければいけません。
書き込みのパラメータはアドレス、書き込みマスク(byteenable)、書き込むデータの三つです。
これらパラメータが設定されるのは Write と同時かそれ以前で、クロック同期である必要はありません。(書き込みデータだけは WaitRequest が立つ瞬間まで遅延できるようです)
今回はバーストライトではないので burstcount は 1 のままにします。

byteenable はかなり使い手のあるパラメータで、実際に書き込むバイトを自由に設定できます。バイト同士が連続である必要も、popcount が 2^n でなければならないといった制約もありません。

1 ワードのデータを書き込むだけならただの組み合わせ回路でもできるのですが、やはり沢山書いてみたいので少し凝りましょう。
WaitRequest と書き込み信号をイベントとしたクロック同期する FSM を中心に構成しましょう。
そうしておくことで、連続したリクエストに対しても d の制約を満たすことができます。

メモリレイアウトを考える

回路の構成には関係ありませんが FPGA と HPS で物理アドレスを配分しなければいけません。
しなくてもいいのですが、現時点でバッティングしてよいことは何もありませんのでとりあえず 512MB ずつ半分にして HPS には 0x000000000-0x1fffffff, FPGA には 0x20000000-0x3fffffff としておきましょう。
これは完全に自由にできるわけではありません。FPGA 側がハイアドレスを使うことは決まっていますし、アドレス空間の最上位 1GB の空間は予約されています。
詳細は Device Handbook Volume 3: 9-11 Boot ROM Mapping をご覧ください。
そんなに情熱を注ぐところでもないです。

HPS 側で物理メモリを制限するためには、 Linux の boot に UART で割り込んで抑制し、 代わりに上がってくる SOPC shell 上で editenv コマンドを使って mmcboot 環境変数に書き込めばよいです。
言葉で書くとなんか大変そうに見えますが EFI shell とか EPROM shell みたいなもんです。
こちらの blog の JTAG を使って DDR3 をシェアする記事が大変大変参考になります。

出来上がった回路はこうなりました。
なんか色々怪しいですが。

https://github.com/roentgen/sdram_helio/blob/master/helio_ghrd_top.v

CPU 向けのインターフェイスを用意する

起動したらずっとメモリに書き込み続ける回路ならば不要なのですが、それはちょっと熱や消費電力(それから精神衛生面)に優しくないので、 ARM 上で動くプログラムからメモリの書き込みと停止をコントロールできるようにしましょう。

CPU とのインターフェイスは、今や SDRAM さえ使用可能ですが、最もお気楽な方法としては MemoryMapped-IO があります(以下 MMIO)。
今回はハードウェアらしく MMIO を使います。

MMIO は、CPU からコントロールレジスタが見えないようなデバイスを扱うのにとても歴史がある方法で、個人的にも古い友人のような感慨があります。
この方法では物理アドレスの一部を予約し、そこに対する CPU からのアクセスを(メモリではなく)外部バスにリダイレクトするのです。
リダイレクト先は(典型的には) FPGA のレジスタになります。

……と、理論上は簡単なのですが、 Altera SoC におけるここの実装は相当に複雑です。
Device Handbook Volume3: 8-3 HPS-FPGA Bridges Block Diagram and System Integration の Figure 8-1 をご覧くださいませ。
HPS->FPGA と FPGA->HPS 二つのブリッジがあるのはわかるのですが、その間に Lightweight HPS-to-FPGA Bridge なるものが介在しています。
これらは AHB/AXI なのですが、にも関わらず soc_system の IP 上見えているのは AvalonMM Slave です。
32bit アクセスだけは lightweight を通って、64bit はネイティブにそれぞれのブリッジ上を通る。 128bit はブリッジ上の FIFO で分割される……という風に読めますがそれにしては AHB の Master/Slave が逆のようにも思いますし、よくわからないです

よくわからないものの、使い方は非常に簡単です。
一つだけ注意することがありましたが、それだけです。
GHRD にはとてもよいサンプルとして sysid_qsys と led_pio という二つの IP が組み込まれています。
これな
MMIO の物理アドレス 0x10000 からとなっていますが、実際は FGPA ペリフェラルの物理アドレス空間は 0xff200000 からなのでここからのオフセットです。
物理アドレス 0xff210000 がこのレジスタです。
コードも簡単で、ここへのアクセスに対し定数を readdata に突っ込むだけのコードになっています。
インターフェイスは Avalon-MM Slave になります。

ただし、前述した HPS-to-FPGA Peripheral のよくわからないことの一つでよくわからないままなのですが、どうやら注意しなければいけないことがあります。
IP を設計するときは Avalon-MM Slave と思っておいていいのですが Qsys で繋ぐときに h2f_lw_axi_master とも接続しないとこの単純な回路さえ値が見えません。

(実際 sysid_qsys は接続されています)
sysid_qsys を見てみると fpga_only_master の Avalon MM Master に繋ぐだけでなく、 hps0 の h2f_lw_axi_master とも接続されています。
インターフェイスには出て来ない AXI を接続しなければいけないとは、記述的にはまったく想像がつかないです。
ですがたしかに HPS-to-FPGA Peripheral のブロック図からすると、ここのブリッジは AXI でのみ繋がっているはずで Avalon ではないはずです。
つまり、バスが AXI であっても Avalon に見せる魔術があるのだろうとは予想されますが、今回枝葉なのであまり詳しくみてません。「へー、なるほどねー」くらいのことです。

lw (Lightweight)なのは MMIO の幅が 32bit だからなのでしょうか。64bit か 128bit のときは別のマスタと接続する必要があるのかも知れませんが、オービターがうまいことやってくれるような気もします。

一方、書き込むほうは led_pio を参考にしたほうがよいでしょう。
有意な writedata があるときだけライトストローブが有効になるようにします。

   assign wr_strobe = chipselect && write;

この wr_strobe を見て内部のレジスタを変更するようにすればよいです。
state_splat は 1bit reg, wd は 8bit reg です。 その他、サイクルカウンタに使ったレジスタなどが見えますが、重要なのは state_splat だけです。

   always @(posedge clk or posedge rst) begin
       if (rst == 1) begin
           state_splat = 0;
           wd = 0;
      end
      else if (clk) begin
          if (wr_strobe) begin
              state_splat <= writedata ? 1 : 0;
              wd <= writedata[7:0];
          end
      end
   end
  
   assign readdata[31] = reset_n;
   assign readdata[30] = mem_rst;
   assign readdata[29] = state_splat;
   assign readdata[28:8] = regcc[31:11];
   assign readdata[7:0] = wd;

これを module に仕立て上げ IP として Qsys に追加しましょう。
コードはこちら。
https://github.com/roentgen/sdram_helio/blob/master/mem_sdram_interface.v

具体的な手順は……スクリーンショットを保存しておらずですね……再びこちらの記事がとてもとても参考になります。ありがとうございます。

Qsys は任意の .v を検証し、インターフェイスを明示的に選ばせることで IP として使用可能にします。
(.v はそのまま soc_system/synthesis/submodules/ 以下にコピーされる)
IP として登録するのに clock, reset が超重要です。
これは module の信号リストの順番が結構センシティブですので、信号リスト先頭から clock, reset の順番にしておいたほうが無難のようです。
reset は正論理か負論理かも設定できます(IP をインスタンス化するときにケアされます)。
 
正しく設定しておくと色々ご利益がありそうですが、よくわからんので今回は雑に設定しました。
名前はどうしてこんな長い名前にしてしまったのかと後悔しつつも mem_sdram_interface とし MMIO のベースアドレスは 0x10010 としました。

ちなみに qsys の検証は、簡単なシンタックスチェックが入るだけで合成はしません。
ですのでエラーがあると HDL を生成してからあとで Quartus II で発覚することになります。事前にチェックしときましょうね。面倒だからといって submodules 以下のファイルを直接いじったりしてはいけませんよ(実証済み)。

出来上がりの確認

MMIO で非ゼロを受けて memwrite_master を駆動するシステムができました。
MMIO でゼロが書き込まれるまで、 memwrite_master はアドレスからアドレスまで定数を書き込み続けます。

Qsys ではこうなります。

全体像
一番下の mem_sdram_interface が MMIO の Slave です。
いくつかよぶんな信号線が生えていますが、これは後述するサイクルカウンタの値を設定するためのものです。
memwrite_master は IP にしてないのでここには出ません。

CPU 側のプログラム

とりあえず動かしてみるために、ちょっとしたプログラムを書いて回路をキックします。
MMIO の物理アドレスを指定して mmap し、仮想アドレスに対して 32bit データを書き込むだけです。
1 を書き込むと memwrite_master が動きだし 0 を書くと止まります。
memwrite_master は動き続ける限りあるアドレスの範囲に書き込み続けます。

https://github.com/roentgen/sdram_helio/blob/master/addrmap.cpp

このプログラムは単純に、物理アドレス指定してコントロールレジスタのマップされてる領域と、実際に書き込みが行われる DDR3 上の領域を mmap し、ダンプします。
/dev/mem を open しますので、その権限が必要ですが、全てユーザーランドからコントロールできておりドライバは不要です。
(実際もっとページ属性を細かくコントロールしてやろうとか、カーネルモードでしか触れないレジスタを触ろうとか、 マルチプロセスに対応してやろうとかなるとドライバやカーネルモジュールを作る必要がでてきますが……)

open() システムコールのフラグに O_SYNC を指定しています。
最近のカーネルではこれを立てて /dev/mem を open すると uncached になるらしいです。
(kernel が STRICT_DEVMEM 付きでビルドされてないといけないようですが、たぶんそうなってるでしょう)

サイクルカウンタを実装してパフォーマンスを測定する

これは後付けですが、パフォーマンスを測定するためのサイクルカウンタを実装して、メモリの fill が終わったら fin を上げて自律的にリセットしてサイクルカウンタを MMIO のレジスタに書き込み、 CPU からサイクル数を計測できるようにもしましょう。


この場合のリセットの方法はいろいろあると思いますが、ハードリセットほどは単純でなく自律的にやるのは結構苦労しました。
簡単そうに見えたのですがね、リセット解除しないと次の実行を始められないので。
リセット解除は FSM を別に作るかそもそもワンショットパルスにするべきかはたまた CPU からやったほうがいいのかも知れませんが、この辺はノウハウを溜めないといけないな〜。

ともあれ、満身創痍ですがサイクルの測定はできました。
実行してみると物理アドレス 0x20000000 から 0x2000 * 32bytes の領域に書き込めています。
fin が立ったあと mem_sdram_interface の WE  に間に合わないのかサイクルカウンタが終了時にリセットされてないように見えますが、開始時にリセットされているのでよしとしましょう。

結果

master 側の fpga_clock50 は 50MHz です。
なんと 0x10000 回の 32bit ライトアクセスで 500ms もかかった計算になります。
遅い!!
500KB/s しか出てないじゃないか!
一回のライトリクエストごとに 390 サイクル (7us@50MHz) かかったことになります。
大体 40-50 サイクルじゃないかな〜と思っていたのに……これはちょっと遅過ぎます。

メモリは 200MHz 駆動だけどもコントローラは 50MHz だし、 SDRAM Controller がボトルネックになっているようです。
確かめてみるためにデータレートを上げてみます。

Qsys で HPS のプロパティシートを開き f2sdram0_data のビット幅を 256 に変更します。(32bit にしていた)
デフォルト 256 ですがメモリのデータバスが 32bit だし 256 は厳しかろうと思っていたのですが、メモリバンドネックではなさそうなので 256 で試します。
memwrite_master の wire 幅にも影響があるのでそっちも修正して試してみると……。

結果はトータル 0x061a << 3 カウント。 1 トランザクションあたりのサイクル数は 390 で同じでした。
ただしトランザクション回数が 1/8 になったぶんバスバンドはリニアに向上し 4MB/s 程度出ます。かかった時間も 60msec 程度と大人しめ。
Avalon MM の Master/Slave 間にブリッジが存在しないのであれば、 Multiport SDRAM  Controller のクロックが低過ぎるか、スマートすぎて DDR3 の帯域を生かせないということです。

ただしまだ結論は出せません。
だってメモリコントローラがバスネックになるのじゃ ARM から見ても DDR3 の帯域がでないはずで、じゃあ DDR3 を積む必要なんかないじゃないかということになります。
SDRAM Controller Subsystem の説明ではコントローラへのアクセスは AXI だったはず。

ならば現時点の仮説は

1. Avalon が悪い。 AXI を使え
2. メモリコントローラの実力だ。 バーストモードか DMA を使え
3. GHRD が悪い。 クロックを上げろ

の組み合わせということになります。

なぜ遅いかはまだ解らないにしても、ひとまず実験の結果は出ました。
まとめましょう。
  • FPGA と HPS で SDRAM を共有することは(解ってしまえば)簡単だ
  • Avalon MM 同期 Write を使ったメモリの書き込み@50MHz ではメモリの帯域が出せない(256bit でも 2MB/s が上限)
  • ライトトランザクションにはデータ幅によらず 390 サイクル, 7us@50MHz かかる
以上となりました。

2015年5月5日火曜日

Altera SoC 開発ボード Helio

一時期、なんか上司氏と顔を合わせるたびに「VHDL 書ける?」と聞かれていたのですよ。月刊インターフェイスの読者であった僕は勿論それがどういうものかは大体知っているけど上司に向かって「書けます」というのは純粋な嘘になるので

「知りません、書けません」

と逃げ回っていたのです。
ところが最近身近で FPGA ブームが起きていまして、 DE1 を買って来たのです。
DE1 は低価格で Sound DAC や DSUB を備えた楽しいボードなのですが、気軽に使える IO はプッシュボタンと 7SEG と LED くらいなので LED 光らせる(いわゆる L チカ)などラボの講義を終えたくらいで止まっておりました。
(だっていきなり音とか出したら耳ぶっ壊れそうだし、 DSUB のモニターなんかもうないよ……)
ところが最近よいものが DE1 の価格帯で売っていると聞きました。



Altera SoC Cyclone V の評価ボード Helio です。
CycloneV はデュアルコア ARM SoC に FPGA fabric をオンダイに搭載したものです。
FPGA として見ても、 DE1 の Cyclone II から見ればとても豪華なものです。
Helio ボード上には UART, JTAG, USB Blaster, Ethernet, DDR3, USB(OTG), MMC が実装されており、すぐ MMC で Linux をブートして LAN 上に見ることができます。

Ethernet, DDR3 は説明不要でしょう. UART はシリアルポート, JTAG はデバッグインターフェイス, USB Blaster は FPGA の再構成デバイス, USB(OTG) は Host にもなれる USB コントローラー、 MMC はマルチメディアカードです。
どれも実績と人気のあるパーツでまとまっております。
HDMI や DVI がないくらいです。

Helio のメインコンポネント

さて、ところが FPGA fabric を搭載した ARM なんて使ったことがありません。
例えば ARM はメモリを混成しておらず、ボード上の DDR3 を使いますが、 FPGA から DDR3 を使えるのでしょうか。
FPGA からはどのバスで DDR3 を叩くのがベストな方法でしょうか。

ここでは FPGA から DDR3 に書き込んで ARM から読むのを目標に、 Cyclone V のアーキテクチャを見ていこうと思います。

準備編

Linux の起動

とりあえず Helio ボード上で Linux くらい起動していなければ話になりません。
Helio の開発元である rocketboards のサイトに丁寧な Getting Start Guide がありますのでそれを見て行ってください。
Helio には SD カードが付属していますが漢のブランクであります。
ラズベリなんかだとちょっとお金を払うだけで u-boots で起動する Linux のイメージを焼いたものが付属しますが、イメージは rocketboards に各種ありますので好きなものをダウンロードして dd で焼きます。
一番シンプルなものでも httpd,sshd くらいは動いてくれます。これで充分でしょう。
起動すると DHCP で勝手に IP アドレスを取得します。

UART は Linux の起動に割り込むのに必要ですので常時繋いでおきます。
FPGA の再構成に使うケーブルも繋いでおいたほうがいいので、二本は必要ですね。
なくても Linux のブートくらいはできますが(ありがちな話ですが) UART は IP アドレスを確認するのにも必要です。

Helio では、何かがバグっているものか起動するたびに MAC アドレスが変わってしまいます。
このためルーターで IP を指定することもできません。会社で使うにはトラブルの元でしょう。
しかもブロードキャストに応答しないので、真っ先に static にしておきましょう。

開発環境

ソフトの人向けに、まず開発環境とワークフローについて書いておきます。
Parallels9 for Mac + Ubuntu13.04 の環境に Quartus II 14.1 web edition  を入れて使っています。
Quartus II は Altera によるいわゆる IDE で論理合成、配置配線といったソフトでいうところのビルドを行います。
Cyclone II などの古い FPGA は Quartus II 14.0 以降サポートを切られていますが、 Cyclone V では Quartus II 14.1 を使いましょう。
v14 以降は 64bit サポートもしています。(シミュレータである ModelSim は 64bit 対応ですがインストーラが 32bit というクソです)
詳しくは後述しますが Quartus II よりはその付属の Qsys というツールをよく使います。

Qsys はかつて SoC Builder と呼ばれていたソフトで、ハードウェアの情報から IP (ソフトでいうライブラリみたいなもの)をカスタムした一つの大きな回路とそのインターフェイスを生成するものです。
cmake みたいなもの……といえばいいでしょうか。
IP というと「高そう」とか思ってしまいますが、後述する GHRD というリファレンスデザインが既に IP として提供されています。

シミュレーションには敢えて ModelSim を使わず GHDL や icarus verilog を使っています。
GHDL は幸せでしたがこれは VHDL 用ですんで icarus verilog にしました。

ARM コア用にはツールチェインが提供されていますが、普通に arm-eabi 用の gcc を使うことにします。
(VM で clang ビルドしたら三日四日かかってもリンクが終わらなかったのでいったん諦めました)

ちなみに Quartus II は安定しているときは安定していますが、死ぬときは 10 分で死にます。
調べてみると Talkback を OFF にしていても定期的に CDN に https で何かのリクエストを送っており、これがタイムアウトすると割り込みハンドラの中で死んでいます。
場合によってこのリクエストは一度も発行されない状態で起動することもあるので、その場合は安定します。二度と終了しないでください。
あとアメリカが寝ている、日本時間の昼間には安定しています。
会社から帰って来て夜中に起動すると大体時間を無駄にすることになるので、「なるべく昼間にやる」「安定したら二度と終了しない」ルールで運用しています。

さてフローは、 Quartus II で .sof などのネットリストのファイルを生成し、 Programer という何とも漠然とした名前のツールでそれを FPGA に焼き、ボードの動きを確認することが目的になります。ボードには WARM/COLD のリセットボタンが付いていますが、これはどうやら HPS 側であって FPGA 側は焼いた時にリセットが走っているっぽいので、やらなくてもいいです。
(HPS 側をリセットしても FPGA 側のリセット信号は動きません。よくできている)
.sof は揮発性なので電源スイッチでハードオフすると飛んじゃいます。開発時には便利です。

Programmer は onboard USB Blaster を使って FPGA を再構成します。
Parallels9 for Mac ではゲスト OS の Ubuntu 側で USB Blaster の認識が安定しませんでした。(20 回に一回くらい?)
しかし VM の設定で USB3.0 サポートを切るとすんなり認識するようになりました。
Altera のドキュメント通り udev だけ設定しておけばドライバは不要です。
UART も伝統の FTDI 互換ですので(Linux では)ドライバ不要です。 Mac OSX でも marverics なら不要のはず。うちのは違うので知りませんが Arduino はドライバ不要でいけたのにこれはちょっとダメそうでした。

Quartus II でコンパイル(正確には論理合成)するソースは好きなエディタで書いてかまいませんが、 Qsys が生成する HDL は再度上書きされる可能性があります(標準では soc_system ディレクトリ以下に生成される)。
このへんは Qsys を使うときにまた詳しく書きます。
回路の HDL を書いたら(シミュレーション用のテストベンチも書いて)シミュレータで波形を見ましょう。
僕は icarus verilog と GHDL, gtkwave を使っています。
これらのシミュレータは論理合成をしてくれません。従って、シミュレータでは動いても、論理合成不可能な回路を書いている可能性があります。
その場合 Quartus II でエラーが発見されるので TAT が長くつらいです。

icarus verilog 0.9 では -S を付けてコンパイルすると論理合成を試します。この機能は開発中のようですが、シミュレーションできるが論理合成できない記述を発見するには大変役立ちました。

HPS

HPS とは Hard Processor System (再プログラム不可能なプロセッサとそのシステム)のことで、おそらくはこれは Altera の言葉と思います(Soft Processor ありきの言葉なのでね)。
ここでは、要するに ARM 側のシステムのことです。 ARM の MPU コア以外にも L3 インターコネクトや AXI が含まれます。
Altera が決めてないことは全部 HPS だと思っていいのではないでしょうか。 ARM を主体に見ると軒先を貸して母屋に変な名前を付けられたように見えるかもですが、 ARM はそもそも IP で売ってるものですし、土地は元々 FPGA のものだっりします(今回 HPS の家屋を造り直すことはできませんが)。
これはドキュメントじゅうに現れる言葉ですので、何が何でも最初に覚えておかねばなりません。

本記事で主に扱うのは FPGA 側と ARM 側のやりとりの方法でありますから、これは即ち HPS Subsystem の使い方であるわけです。

HPS SDRAM Controller Subsystem

Cyclone V のマニュアル(の一部. Book3)より https://www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/hb/cyclone-v/cv_5v4.pdf "HPS SDRAM Controller Subsystem" の章、 Figure.11 がまさしく求める情報です。

Altera SoC Cyclone V の全容

右側の赤丸を付けたコンポネント、これがメモリコントローラです。
L2 キャッシュを経由せずに L3 インターコネクトから接続されていますので、ほぼ全コンポネントからこのメモリコントローラにアクセスすることができます。
FPGA fabric から直接このコントローラを叩くには FPGA-to-HPS SDRAM というのがヒントになるようです。

当然ながら——このレベルの混同はないと思いますが念のため断っておくと、ここでいうメモリコントローラは飽くまでメモリモジュールを制御するコントローラで、 MMU は含みません。
ARM の、ちょっと特殊な MMU はコア側に実装されております。つまり、物理アドレスが必要です。

FPGA-to-HPS SDRAM のインターフェイスについて更に調べていきます。
Figure.11-1 SDRAM Controller Subsystem High-Level Block Diagram によるとこの部分についての詳細が記述されています。

32-256bit の AXI か Avalon-MM を使って SDRAM Controller を制御できそうです。(ちなみに、 External Memory へ繋がる DDR PHY から HPS I/O Pins というバスは FPGA を経由しておりまして、メモリを好きなようにできそうです。ただそれをやってしまうと ARM 側が困ってしまうので、やりません)

AXI は ARM の定義する AMBA 第三世代か第四世代のバスアーキテクチャだったはず(うろ覚え)ですが、 Avalon-MM というのはあまり耳馴染みがありません。
Avalon, Altera, ARM, AXI, AMBA, AHB …… A から始まる用語がゲシュタルト崩壊しそうです。電話帳かよ!!
これは Altera が定義するインターフェイスのようで、使い方は簡単です。

仕様はこちらにございました。
https://www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/manual/mnl_avalon_spec.pdf

シンプルな Master/Slave のアーキテクチャで、実際のバスアーキテクチャは任意に選ぶことができる……というようなものだった気がします。
SDRAM Controller に関しては直接繋がってるようなのであまり気にしませんでした。
データのリードライトを要求する側が Master で、物理的なレジスタやメモリにアクセスしてデータを提供するのが Slave です。

従って、この Avalon MM の Master を実装するのが今回の目的です。
実際の作業を始めましょう。

……ところがここまでで非常に長くなってしまったので、作業編は次の記事に回します。
つづく。

2015年1月19日月曜日

すごい erlang のすごさがチョットワカルくらいまで学ぶ。できればゆかいに。

昨日、というか今朝方書き上がったエントリで大枠程度は書けたと思うのですが、バイナリのマッチまでメモって力つきており、あまり実用的な機能に触れられていませんでした。
もう少し学んだところをメモっておかねば消化不良です。

ビット操作


ビット列の生成とマッチングまでは前回メモってあるけども、それだけではパーサーは(大体)書けません。

バイナリの生成いろいろ

バイナリの生成について細かい規則は、公式のここにかなりしっかり書かれているので迷うところは実際少なかったです。
唯一迷ったのは "The Erlang Type Language"  という章に書かれた、バイナリの一般式は <<_:M, _:_*N>> であり他のは省略系だとあったところです。
これが頭の片隅に残っていたので試したところ、 <<1:8, 0:32*8>> などと食わすと無情なシンタックスエラーであります。
他に合わせて << SegList >> とか書けばいいのに……と思ったのですが、これは Erlang の組み込み型を定義する上での記法の記法であり、 Erlang の文法ではありません。

バイナリかビット列か

組み込み型 bitstring は 1 ビットの列です。
 <<1:3>> は 2 進でいう 001です、
組み込み型 binary は 8bits 境界に並んだビット列です。生成時、 <<1>> とビット幅を指定しなければこれは /binary になります。ビット列でいうと <<1:8>> です。
両者は、組み込み型としては別ですが、前項で確認したように組み込み型はあくまで erlang にとっては(ユーザープログラムよりも)事前定義された型に過ぎず、ユーザー定義型と違いはありません。

ならばビット列を使って、わざと 8bits 境界にマッチするようなバイナリを作ったら、それは bitstring と binary のどちらにマッチするのでしょうか。

bytes(<<B/binary>>)->
    io:fwrite("binary B:~w\n", [B]);
bytes(<<B/bitstring>>)->
    io:fwrite("bitstring B:~w\n", [B]).

321> test:bytes(<<0>>).
binary B:<<0>>

322> test:bytes(<<0:7, 0:2>>).
bitstring B:<<0,0:1>>

324> test:bytes(<<0:9>>).
bitstring B:<<0,0:1>>

326> test:bytes(<<0:8>>).
binary B:<<0>>

327> test:bytes(<<1:1, 1:7>>).
binary B:<<129>>

328> test:bytes(<<1:1, 1:7, 1:1>>).
bitstring B:<<129,1:1>>

329> test:bytes(<<0, 0>>).
binary B:<<0,0>>

330> test:bytes(<<0, 1:1, 1:7>>).
binary B:<<0,129>>

332> test:bytes(<<0:4, 0:5, 1:6, 1:1>>).
binary B:<<0,3>>

全体の長さが  8bits アラインであれば、各セグメントのアラインがどうであっても、 binary にマッチするようです。

ビットの展開

バイナリ内からマッチした部分で引数に拘束される値はどうなるでしょうか。
上位 7bit を取り出してみます。

rst(<<R:7, _:1>>)->
    io:fwrite("R:~w\n", [R]).

341> test:rst(<<128>>).
R:64
ok
342> test:rst(<<255>>).
R:127
ok

なるほど。ビット列からそのまま射影されるのでなく、論理右シフトされるのですね。
算術シフトではありませんから符号には注意が要りそうです。
ん……本当? 型修飾には signed/unsigned を書けたはず。そう思って試してみると……

rst(<<R:7/signed, _:1>>)->
    io:fwrite("R:~w\n", [R]).

344> test:rst(<<255>>).
R:-1
ok
345> test:rst(<<128>>).
R:-64
ok

おー、算術シフトになった!
ちなみにデフォルトは unsigned だと仕様にも書かれておりました。
型修飾リストにはエンディアンも書けるようです(デフォルト:big)。
すげえ!!

バイナリのトラバース

公式のドキュメントを参考に、ビット列全体の処理の取り扱いについて調べました。
4.7 Appending to a Binary です。このセクションではごく短い例を挙げています。

繰り返し処理

このコンテキストで書くのも急というか、本来昨日のエントリに書いておいて然るべき内容でありますので、ここでは簡単にしか触れませんが、実のところ erlang にはループがありません。
再帰を使いましょう。昔の Lisp なんかの関数型や、テンプレートメタプログラミングと一緒です。
与えられたリストの中から最下位ビットだけを取り出して、第二引数の binary に追加したものを構築する append_bin() を考えます。

[] はリストです。 car/cdr といったリスト操作を明示的に呼び出す代わりにパターンマッチ [CAR|CDR] を使用します。これは variadic template と同じですね。
この場合は、再帰の終端は append_bin([], Acc) -> Acc. であり、 CDR が空になるとこちらにマッチするので Acc がそのまま返ります。
末尾再帰ですので、この場合は C++ 同様に暗黙にループによる最適化が期待できそうです。
lsb_of(<<_:7, LSB:1>>) -> LSB.

append_bin([CAR|CDR], Acc) ->
    LSB = lsb_of(<<CAR>>),
    append_bin(CDR, <<Acc/binary, LSB>>);
append_bin([], Acc) ->
    Acc.
Acc というのは再帰ステップを通じて与えられる任意の変数ですが、 erlang においてはアキュムレータという名前で親しまれているようです。
379> test:append_bin([1, 2, 3, 4, 5], <<>>).
<<1,0,1,0,1>>
奇数,偶数,奇数,... なのでこれで大丈夫のようです。
結果はバイナリ binary であります。 bitstring に詰め込む場合はもっと簡単で、
append_bin([CAR|CDR], Acc) ->
    append_bin(CDR, <<Acc/bitstring, CAR:1>>);
append_bin([], Acc) ->
    Acc.
だけでよく、 LSB を取り出す操作を関数にする必要さえありません。
ドキュメントによると、最近のバージョン(R12B)から再帰ステップ間の Acc はコピーされなくなっていて効率的になったとあります。意図的に参照を用いる必要はないようです。素晴らしいですね。

非常に美しく書けましたが、不満はあります。
ビット列のトラバースがしたかったのに、いつの間にかリストのトラバースの話になっていた!
再帰の話が混じったので一度リストにしましたが、バイナリを受けるバージョンはもっと簡単になります。
append_bin(<<CAR:8, CDR/binary>>, Acc) ->
    append_bin(CDR, <<Acc/bitstring, CAR:1>>);
append_bin(<<>>, Acc) ->
    Acc.
406> test:append_bin(<<1, 2, 3, 4, 5>>, <<>>).
<<21:5>>
うーん、良い……。

チャンクの扱い

erlang で扱うバイナリはかなり良いことが解ってきましたが、さすがにこれで何百 MB もあるバイナリを扱ってよいかどうか気になります。
上の例では末尾再帰に出来ましたが、そうでない場合はスタックが延々と伸びて行ってしまいます。
できれば適当なチャンクに区切って処理したい。
そういうときは標準ライブラリ (stdlib ではなく kernel) を使いましょう。
file:open() して開いた FD に対してシーク位置を指定した file:pread() すればいいっぽいですが、パフォーマンスについては Performance のセクションにかなり長めの警告が書かれています。
これは言い換えれば、 read()/write() には恐らくライブラリレベルのバッファが存在しないようで、アプリケーションが自分でバッファを作る必要がある。
ストリームリードならさほど気にしなくていい場合が多いでしょうが、この辺はケースバイケースです。
他にも open 時に指定出来る mode によって、遅延書き込みや先読みを有効にさせてシステムコールの削減、スループット向上を期待できそうです。
一通り似たライブラリがありながらも C/C++ の標準ライブラリとはかなり思想が違うなという印象です。

データ構造

erlang のデータはリスト、タプル、マップと人気のあるものは一通り揃えている感じがあって素敵ですが、馴染みのある構造体も使いたいです。
バイナリをパースしたらそれを馴染みのある構造体に入れて取り回したいというのは自然な欲求なのではないでしょうか。
タプルでもいいけどオブジェクトに名前が欲しい……。タプルでもリストでも、 {X=0, Y=1, Z=2} という風に各要素に名前を付けられるけど、同じ構造のタプルを複数扱うとき大変。
レコードを使えばよいようです。
-record(Name, {Field1 [= Value1],
               ...
               FieldN [= ValueN]}).
レコードの定義はやや仰々しく、 -record ディレクティブを使ってコンパイラに示す必要があります。

インスタンス化

#Name{Field1=Expr1,...,FieldK=ExprK}
T = #rec{x, y, z}.
などとして使います。名前付きタプルという感じでしょうか。

アクセス

Expr#Name.Field
Expr はインスタンスで Name はレコード型名、 Field はメンバ名です。
やや気持ちが悪い。オブジェクトの名前を使って各要素にアクセスしたいだけなのにちょっと大袈裟ですね。 erlan shell からアクセスしずらいのも難です。
もっといい方法があるのかも知れませんが……。

まとめ

というわけで、ここ二日で学んだところは概ね以上です。
僕の必要な知識は大体手に入れたのでよしとしましょう。
 

2015年1月18日日曜日

すごい erlang のすごさがわからないくらいまで学ぶ。できればゆかいに。

昨日急に Erlang のコードをいじらなければならなくなりまして。
別にがっつり開発するとかメンテするとか大袈裟な話じゃなく、ちょっと弄ってちょっとの間動かせればいいのです。
目的もバイト列のパーサーだから Erlang らしいスレッドモデルは使わない。
それくらいを目標に、他言語話者が Erlang を学んだところをメモっておきます。

ランタイムや開発環境は brew install erlang で一発です。
パッケージ内には emacs の erlang-mode も入ってますので、

((setq load-path (cons "/usr/local/opt/erlang/lib/erlang/lib/tools-2.6.15/emacs/" load-path))
(setq erlang-root-dir "/usr/local/opt/erlang/")
(setq exec-path (cons "/usr/local/opt/erlang/bin/" exec-path))
(require 'erlang-start))

と書いたら ok.
C-c C-k でコンパイル、 erlang シェルの起動まで一発であります。
らくちんらくちん。

文法

Erlang は結構古い言語で 86 年登場だそうなので C++ と同世代くらいでしょうか。
しかしながら文法はかなりモダンな機能が多く、かと思えば全然モダンじゃないところもあってアクセルを踏んだりエンストするような感じもあり、乗り物酔いしそうです。

他の言語であれば、一つの文は 式; でブロックは { 文 ... } で……みたいな大枠から説明できるのですが、 Erlang の文は文脈依存の構文が多く、なんとも一言では説明できません。
もっとも原始的な文を
Expr.
と言うことはできるですが、多くの手続き型言語がこれの列挙をする文法なのに対し、 Erlang はこれだけ解ってもどうにもならない文法だと思います。
……といってもなかなか伝わらないと思うので、僕の見た厄介な例に目線を合わせる意味で、こんな例を書いておきます。

-module(test).
-export([func/2]).

func({A, B, C, _} = Tuple, A) when A > 1,
            B > 1;
            C > 1 ->
    io:fwrite("func({A,B,C,_}, A)\n"),
    case A of 2 when B > 2 ->
        io:fwrite("Tuple = ~w\n", [Tuple])
    end;
func({A, B, C, _}, _) ->
    io:fwrite("func({A,B,C, _}, _)\n").

手続き型か、いや関数型プログラミング言語か……というよりどことなく BNF 記法による構文解析を思い出します。
なんとなく見てわかるところと、解らないところがあると思います。

解るところは:
  • test モジュールと関数 func が定義されている
  • 関数は複数定義され、 template の特殊化のように動くようだ
  • 特殊化は when 条件式によっても細かく制御できるようだ
  • {} は何らかの無名構造体を構成するようだ
  • io:fwrite() は printf() のようなものだ
C++11 の variadic template はお気に入りの機能で、記述が冗長なことを除けばこれを(大枠では)すんなり理解できると思います。
パッと見、疑問に思うところは
  • 文末の記号があったりなかったり、複数の種類があるのは何なの?
  • . (dot) が文末なのに、本体のコードではたった一回しか登場しないじゃん
  • -> と ; の厳密な定義は何?
  • ; の定義によっては二つ目の func は一つ目の func の中に定義されているようにも見えそうだけど、どうなるの?
  • 一つ目の func({A, B, C, _} = Tuple, A) は特殊バージョンにとしては二つ目の func とあまり違わないように見えるが、パターンマッチが動くのだろうか?
  • when の条件式が複数あるけどこれはどう評価されるの?
  • case も when も条件分岐だと思うけど、二つあるのは何なの?
  • if じゃダメなの?
  • = は何なの?
ということでしょうか。
これらの疑問には、個別の解説を読むより公式のドキュメントが一番わかりやすく答えてくれました。

関数の宣言は関数節の集合

公式ドキュメントによる仕様をみてみましょう。
  • 関数宣言はセミコロンに区切られた関数節からなり、 .(dot) で終端する
  • 関数節は節頭と節本体を -> で繋いだもの
  • 関数節本体は一つ以上のカンマで区切られた式からなる
と書かれています。
つまり、下記は全体で一つの関数 Name の宣言であると言えます。
一つ一つが関数節であり、下線部は各関数節の頭です。関数節はそれぞれセミコロンで区切られ、.(dot) で終端します。
下の構文は公式ドキュメントのものですが、関数節が一つの場合はセミコロンで終端しそうに見えますが、 関数宣言は . で終端すると定義されているのでまぁ、文章で書かれた定義のほうに従うようです。

Name(Pattern11,...,Pattern1N) [when GuardSeq1] ->
    Body1;
...;
Name(PatternK1,...,PatternKN) [when GuardSeqK] ->
    BodyK.
 
各節は構文解析器のノードと一緒です。全ての引数についてパターンがマッチし when 節が還元すれば、その関数が還元します。呼ばれるわけです。
variadic なテンプレート引数展開や特殊化はまず汎用版を宣言してから特殊バージョンを宣言しますが、この場合は逆であり、節ごとに緩くしていきます。
when シークエンスからなる(ガード節というらしい)は省略可能です。
関数節頭の () 内は、仮引数リストというよりパターンであることは予想通りですが、仮引数リストのようにも機能します。
引数の数をアリティと呼び、アリティが違えば別の関数とされるのは他の言語と一緒です。
上の、 func 関数の場合は引数は 2 個で、フルネームは test:func/2 であります。
パターンとは項ですが、未拘束変数が許されています。
詳しくは後述しますが、ここでは C++ の人に解りやすいパターンの例をあげておきます。
func/2 は未拘束変数 A を持ち、第二引数の値によって特殊化……のように動きます。
 

func(A, 0) -> io:fwrite("zero\n");
func(A, 1) -> io:fwrite("one\n");
func(A, 2) -> io:fwrite("two\n");
func(A, _) -> io:fwrite("other\n").

when 節

続いて when 節を見てみましょう。
ここでいう when 節とは when GuardSeq で表現される節です。
ここはドキュメントで明示されるまでは信じられないような仕様でありまして、
  • カンマで区切られたガード式の集合がガードである
  • セミコロンで区切られたガードの集合がガードシーケンスである
とされています。
いやまぁ、 C/C++ だってカンマ演算子を使ってギョッとするようなコードを書くことはできますが、仕様でこう書かれてしまうと「アアア……」となってしまいます。
違いは、ガードは全部評価され全部が true にならなければなりません。ガードシーケンスは順番に評価されて true になればシーケンス全体が還元します。  
ガード式とは、 Erlang の式ですが、全部使えるわけではなく、副作用のあるようなことはできません。
引数リストはパターンでなければならないので、 式は書けません。
仕様では"a subset of the set of valid Erlang expressions" と表現されております。
副作用がないのだから、ガードシーケンスやガードの残りの式は評価されない(will not)ようです。
大体 C++ の条件式の評価と同じですが、この辺は評価が決まっている C++ とは違いますね。

ちなみに、ある解説によるとセミコロンは orelse 演算子の意味とありましたので、ガード節においてはセミコロンは演算子であると考えたほうが意味的には合っていると思います。しかし文法上はセミコロンで区切られていると明示されているので、演算子であるという理解だと無理があるように思います。
僕はそっちの解説を先に読んでしまったので激しく混乱しましたが……。

以上のことを頭に入れて when 節をもう一度よーく見てみましょう。
さっきも書きましたが、引数リストはパターンしか書けません。ガードには式が書けます。

func({A, B, C, _} = Tuple, A) when A > 1,
            B > 1;
            C > 1 ->

これは要するに (A > 1 && B > 1) || C > 1 と解釈できます。
これが true ならこの関数が呼ばれます。

パターンとマッチとパターンマッチと式

さて、 Erlang に特徴的なことのうち、難しい文法の話も大詰めでります。
ここまでナアナアにしていた関数の引数リストを理解しなければなりません。
ちなみに、 {} はタプルの宣言で、変数は大文字で始まらなければなりません。

({A, B, C, _} = Tuple, A)

引数リストはパターンの列挙だということを理解しても尚、上の例には首を捻るところがあります。
  • タプル中の A と第二引数 A の関係は?
  • = は式なのではないのか?
仕様では、パターンは項と同じように表現される構造体であるが、未拘束の名前を使ってもよいとあります。
すなわち、 A とか B といった名前が宣言なしでそこに登場することは問題ありません。
引数は {A, B, C, _} などに拘束されるわけです。(_ は無名オブジェクト)
{A, B, C, _} = Tuple のほうも同様で = はマッチ演算子とされますが、パターン中に現れることを許されております。

マッチ演算子を使って評価を行うことをパターンマッチングと呼びますが、パターンマッチングに成功すると右辺の項を左辺のパターンに拘束します。例えばこうです。

X = 1.
1 = X.

X を 1 に拘束します。一度拘束してしまえば、 1 = X も同じです。右辺が評価可能な項であり、 1 もパターンであるからです。
X=1 は何度も評価できますが、一度拘束してしまえば X=2 は拘束できなくなります。
(erlang shell においては f(X). とすれば X は未拘束になり、再度拘束できるようになります)
これは X が const になってしまうのではなく、エラーメッセージによると「X と 2 はマッチしません」という、要するに X=n. というのは正確には、マッチを使って拘束していた、ということになります。
この仕組みで、引数リストはマッチをしつつ未拘束変数に実引数を拘束している、と思われます
通常、パターンマッチでは右辺は項でなければならず、未拘束変数は項とはならないっぽいです(本当?)が、パターンであれば未拘束変数が許されます(これは本当)。
関数頭の宣言は (Patterns...) とありますので、パターンであることが明白なので、マッチの右辺も常にパターンであると見做され、右辺に未拘束変数が来ることを許されているのかなぁと思いますが……書いてて全然信じられませんね。自分でも何言ってんだろうこの人と思います。
実際、引数リストに = (マッチ演算子)を使ってマッチしつつ拘束を行う場合、 {} = Tuple と Tuple = {} は等価であります。それどころか Tuple = ({} = Tuple1) とかでもいけます。
なぜ解り難いほうを使って例にしたのかというと、公式ドキュメントの例ではこの順番だったからです。僕の見ていたソースでも全部 {} = Tuple のほうでした。

パターンマッチングでは基本は Pattern = Term です。
引数リストにおいてはなぜか Pattern = Pattern です。
右辺はパターンでない限り、未拘束変数はエラーになってしまいます。その代わり、右辺の評価を使って関数呼び出しなどができます。

Ret = func().

という、ごくありふれたあれですね。


さて、パターンマッチングを使って引数を拘束することは解りました。
この関数が呼ばれたということは、全てのパターンマッチングが成功したということですので、全変数が拘束済みであります。

ここまでで大体明確になったと思いますが変数 A はたった一度拘束されるので、関数呼び出しの時に何度評価されても、矛盾がおきればマッチングは失敗し、その関数は呼ばれなくなります。
erlang のタプルは無名で、オブジェクトの名前をつけないでアクセスするので、タプル中の A と第二引数の A は同じ名前でアクセスされます。
従って、タプルの A と第二引数の A は同じでなければマッチングは失敗します。

erlang shell で実際に確かめてみます。
emacs で C-c C-k でコンパイルすると、 erlang shell にモジュールがロードされるっぽいので実行は簡単です。

187> test:func({2, 3, 3, 0}, 2).
func({A,B,C,_}, A)
Tuple = {2,3,3,0}
ok

188> test:func({2, 3, 3, 0}, 5).
func({A,B,C, _}, _)
ok
ちなみにタプルが {A, B, C} がタプルの名前を使わず A, B, C としてアクセスされるなら Tuple という名前は何なのかと思いましたが、タプル全体にアクセスするのにこの名前を使用します。サンプルでは io:fwrite() の引数に使っています。
これは全体にアクセスしたいとき、同じオブジェクトを再構築するのを避けるためのシンタックスシュガーであると仕様にはあります。
更にちなみに、名前付きの、所謂構造体を使う場合は record を使います。
R = #Type { MemberList } で構築されます。アクセスするには R#Type.member という、二日したら多分もう覚えていないであろう変態的文法のようです。型推論あるんだから頼むよ!

case of

大方疑問は解消しましたが、文末の問題についてはまだ一つ気持ち悪いところがあります。
case が -> を還元したあとの終端規則です。予約語 end がいきなり登場してますが、いいんでしょうか。

case Expr of
    Pattern1 [when GuardSeq1] ->
        Body1;
    ...;
    PatternN [when GuardSeqN] ->
        BodyN
end
 
仕様によると、いいんです
ああ、何なのこの煩わしい曖昧な書き方は。Pattern が一個しかないときはセミコロン要るの?要らないの?
関数宣言のときもそうだったでしょう。あっちは自然言語で定義が書かれてたけど。
この書き方を素直に解釈するとダメそうに見えるんですけど、試した限り Pattern が一個しかないときはセミコロンあるとダメっぽいです。
 
パターンにはパターンか定数式しか書けないので、 when ガード節を取ることができます。
待てよ?パターンということは未拘束変数も書けるのだろうか?と試したところ、仕様通り書けました。
しかし未拘束変数とのマッチは失敗するはずだと思いきや、なぜかマッチは成功してしまいました。
 
foo(A) ->
    case A of UnboundX ->
     io:fwrite("matched to unbound\n");
    0 ->
     io:fwrite("matched to zero")
    end.

212> test:foo(0).
matched to unbound
ok

ok じゃねえよ!!
C++ の default ラベルみたいなことができるように無名オブジェクトを使って _ -> ignored が動くようにしてあるのかなぁ。
それともバグかなぁ。バグだとしてももうこれを直したら死人が出ると思うし、直せないよなぁ。

if 文もありますが if 文との最大の違いは、 case はいずれかのパターンにマッチしなければランタイムエラーとなります。

サンプルで動きを確かめる


上にあげたサンプルは、特に意味はありませんが文法のいやらしい所を満載しており、 erlang shell 上で引数を変えて呼び出すといやらしい動きをします。 

C>1 が false でも A>1, B>1 ならば特殊バージョンが呼ばれる

190> test:func({2, 3, 0, 0}, 2).
func({A,B,C,_}, A)
Tuple = {2,3,0,0}

C>1 も A>1 も false なら特殊バージョンは呼ばれない

231> test:func({0, 2, 0, 0}, 0).
func({A,B,C, _}, _)
ok

そもそもタプルの構造が違えば _ であってもマッチしない

235> test:func({2, 3, 2}, 2).
** exception error: no function clause matching test:func({2,3,2},2)

特殊バージョンが呼ばれる。しかし case Expr of Pattern にマッチしないのでエラー

193> test:func({3, 3, 3, 0}, 3).
func({A,B,C,_}, A)
** exception error: no case clause matching 3

特殊バージョンが呼ばれる。しかし case のガードにマッチしないのでエラー

227> test:func({2, 2, 3, 0}, 2).
func({A,B,C,_}, A)
** exception error: no case clause matching 2


バイナリの扱い

例外や悪夢のような -spec の文法、多彩なライブラリや組み込みデータ型についてはスルーします。
まぁ、大体の文法は解りました。
一番興味があるのは erlang の強力なマッチングはバイナリでどうなるかということです。
もう一晩これを書いてるので、簡単なメモを書いて寝たいです。

バイナリは Bin = <<SegList>> で表現されます。
Bin = <<1:1, 0:7>> ならば 0x80 になります。
Bin = <<1:8>> は 0x01 です。 0xff ではありません。
では Bin = <<1:4, 0:4>> ならば 0x10 ですね。
カンマで区切られたゼロ個以上の各要素を、セグメントと呼びます。
セグメントの完全な表記は Value:Size/Type となっています。

ちなみにサイズの合計は 8 bits の境界に揃っている必要はありませんが、他の型と変換する場合など、当然ながら必要となるシーンはあります。

バイナリのマッチング


MSB というか、 8bit 以上の任意の長さのビット列の一番左のビットにマッチし、続く 7bit を取得し、残りは気にしないという関数 bin を考えます。

bin(<<1:1, R:7, _/bitstring>>)->
    io:fwrite("MSB 1 (rest:~w)\n", [R]);
bin(<<0:1, R:7, _/bitstring>>) ->
    io:fwrite("MSB 0 (rest:~w)\n", [R]);
bin(<<_/bitstring>>) ->
    io:fwrite("unmatched <<_>>\n").

/bitstring という型の指定は重要です。
この例では、8bit 以上の任意の長さのビット列を扱いたいので、ビット列のセグメントがどのように作られたかに依存したくはありません。マッチの場合は、これがないとセグメントの数や長さに依存するようになってしまい、 <<1:1, 0:7, 0:*>> などとして生成されたバイナリにしかマッチしなくなってしまいます。
/bitstring は一つのセグメントについてあればよいようです。

最後の bin(<<_/bitstring>>) は、ビット列の長さが 7bits 以下の場合にここに還元します。

では実際の動きを見てみましょう。

MSB=1 のビット列の場合

273> test:bin(<<128:8>>).
MSB 1 (rest:0)
ok

MSB=0 のビット列の場合

274> test:bin(<<127:8>>).
MSB 0 (rest:127)
ok

セグメントを明示して作ったビット列

268> test:bin(<<1:1, 5:7>>).
MSB 1 (rest:5)
ok

/binary を指定しているので、生成時のセグメントには依存しません。

267> test:bin(<<129:8, 0:128>>).
MSB 1 (rest:1)
ok
271> test:bin(<<129>>).
MSB 1 (rest:1)
ok

まとめ

強力なライブラリと list, map などのデータ構造……。興味は尽きないのですが、取り急ぎ、自分が必要とするところだけを駆け足で見てみました。
なかでもバイナリマッチングは強力で、パフォーマンスまではわかりませんが、かなり面白いです。
なんでこんなに俺得仕様なのかといえば、 Erlang は元々携帯電話の基地局などで使われていたと聞きます。当然何層ものパケットを解析してディスパッチ先を決め、割り込みにも高速に応答しなければなりません。そのせいでしょうか。
現在はスケールしやすさが買われているようです。
実際に動かしてみると、仮想マシン上のシステムにしてはなかなか IO の応答性がよくてときめきました。
携帯電話の基地局といえば、かつて WindRiver の VxWorks で動いているシステムを見たことがありますが、ああした環境の小さな OS で動けば、かなり使い手のある言語/環境だと思います。


2013年12月30日月曜日

C++11 と obj-c

別に obj-c を使ってるわけでもなんでもないのですけど、前回の記事で cocoa のコードをつらつら書いてるときに”拡張子を .mm にして clang に食わすとその中身は C++ と obj-c が混在しまくってても OK"というのを知りました。
オブジェクトの互換性はなく、 obj-c のクラスを C++ で継承したりその逆はできないみたいですが、それ以外のことは一通りできており、 C++ で設計、記述したクラスに実に自然に mac の GUI を被せることができて結構感動したものです。
もうこれでくだらない glue を沢山書かなくていいんだ!

それはそれで大変素晴らしいことなのですが、それでは C++11 ではどうなのかというところが気になりました。
気になる事は試してみましょう。

まず、 clang で C++11 を有効にするには -std=c++11 をつけてコンパイルします。
更に、 C++11 の新しい標準ライブラリを使うには -stdlib=libc++ をつけます。
libstdc++ とかではありません。

cmake でいうとこうです。
   set(CMAKE_CXX_FLAGS "-std=c++11 -stdlib=libc++")
ただ一つ問題があります。
cmake の project に .m が混在しているとこれはエラーになってしまいます。
.mm だけならば問題ありません。 project を別けるかしましょう。
無論、自分で makefile を書くならば suffix ルールを別けるだけで済みます。
まぁ、全部 .mm にしちゃいましょう。

これで準備は完了です。
界面に関わらないことであれば、概ね C++11 の機能が使えるようです。

クロージャ

C++ のコンテキストでクロージャを呼び出すことは難なくできました。
これを obj-c のメソッドに渡すことを考えてみましょう。
Test::foobar というクロージャを受け取って呼び出す obj-c のクラスを考えます。

Test* test = [Test alloc];
const char* msg = "Hello";
[test foobar:[msg](){printf ("%s\n", msg);}];
太字がクロージャであります。
Test の実装はこんな感じ。
@interface Test : NSObject
@end

@implementation Test
- (void) foobar:(std::function< void(void) >)closure
{
  printf("call begin\n");
  closure();
  printf("call end\n");
}
@end
結果は以下の通り。

call begin
Hello
call end
問題なく受け渡すことができました。

__attribute__

クロージャが使えるならかなり色々なことができそうです。
界面に関わるうち、構文上どうにもならなそうなもの以外(例えば obj-c メソッドのシグネチャでrvalue 制約や型推論を使う等)は一通り使えそうです。

構文上厳しそうなものといえば [[]] による __attribute__ です。
GNU 拡張の __attribute__ ディレクティブを、 clang は理解しますが、折角仕様に盛り込まれたのだからそっちを使ったほうがいいです(もっとも、 no_inline だけは効いてくれたことがないですが)。
でもこいつは [] で括る obj-c の文法と相性が悪そうです。
    float vec4 [[align(4)]] [1];
    float vec8 [[align(8)]] [1];
    float vec16 [[align(16)]] [1];
    printf("vec4:%p vec8:%p vec16:%p\n", vec4, vec8, vec16);
一応コンパイルは通りました。ですが実行結果は以下の通り。
vec4:0x7fff5fbfee78 vec8:0x7fff5fbfee74 vec16:0x7fff5fbfee70
手元の clang では残念ながら [[align(x)]] 自体が動いていないようです。
gcc-4.9 では大丈夫だったように思うのですが。

まぁ、使えるんじゃないですかね?(鼻をほじりながら)

2013年12月27日金曜日

cmake で Mac のアプリケーションをビルド

働きたくないでござる!
絶対に IDE で働きたくないでござる!!

……というわけで、 mac 用のアプリも CUI ベースで開発してビルドも make で行いたいというような話です。
マルチプラットフォームでビルドしたいので cmake を使います。

mac のバイナリ(?)である bundle は、要するに何の変哲もないディレクトリで中身にお作法があります。
ここにはアプリケーションの実行形式とアプリケーションの MANIFEST である InfoList.plist 、そしてメインウインドウを記述する .nib ファイルが最低限必要です。
それ以外にも、必要に応じて so や、リソースファイルなどが必要になるでしょう。

こうしたものは Xcode を使えば特に気にすることもなく出来てしまうのですが、そもそも Xcode 使いたくないじゃん?というようなところに動機があります。

Linux や cygwin にも対応できるよう、 gnu make をベースにビルドすることを考えます。
makefile を最初から書く覚悟のある人は、バンドルの規則に従ってターゲット書けばいいだけの話ですのでそうしてもらうとして、ここでは cmake を使って makefile や好みにあわせて .xproj なども作れるようにしておきましょう。

CMakeLists.txt を書く

framework の追加

まずは framework を追加しましょう。ぶっちゃけ GUI でチマチマ追加するより簡単ですよ。

cmake_minimum_required(VERSION 2.8)
project(cocoa.app)

if (APPLE)
   add_executable(cocoa MACOSX_BUNDLE main.mm app.mm)
   include_directories ( /System/Library )
   find_library(COCOA_LIBRARY Cocoa)
   find_library(APPKIT_LIBRARY AppKit)
   find_library(APP_SERVICES_LIBRARY ApplicationServices )
   mark_as_advanced (COCOA_LIBRARY
                     APPKIT_LIBRARY
                     APP_SERVICES_LIBRARY)
   set(EXTRA_LIBS ${COCOA_LIBRARY} ${APPKIT_LIBRARY} ${APP_SERVICES_LIBRARY})
   target_link_libraries(cocoa ${EXTRA_LIBS})
endif (APPLE)

小文字は cmake の組み込み関数やディレクティブです。
この場合は project として cocoa.app というバンドル名を指定します。この CMakeLists.txt のルートですので、この場合はバンドル名とするのが自然と思います。さて、これは実行形式の名前とは無関係です。

実行形式は通常 project 名とは無関係で、任意の名前です。(一つのバンドルに複数の実行形式があってかまわないので)
実行形式は、ターゲットとして、  add_executable() で宣言されます。
これは極めて重要な指定で、これを行った以降でないと設定できない属性が沢山あります。実際は依存関係を記述する都合上、後方に書かれることが多いですが、ここでは解りやすさのためには真っ先に書いています。
ここでは特に、 MACOSX_BUNDLE としていることに注意してください。

mac 用の環境を切り離すのには if (APPLE) を使います。
find_library() で framework を探し、 mark_as_advanced() に設定します。
そのリストを target_link_libraries() で(上で宣言した)実行形式にリンクしましょう。
find_library() で指定するのは /System/Library/Frameworks/ 以下にある *.framework のワイルドカードにマッチする名前です。
さてここまでは簡単です。次にバンドルに突っ込むリソース類のレシピを記述します。

InfoList.plist の追加

バンドルに絶対欠かせないものの一つに InfoList.plist があります。こいつはいわゆる MANIFEST です。
バンドルは shell でさっくり実行形式をロードするのとは異なり、 Mac のシステムサービスを経由して実行されるので、これの記述は重要です。

絶対に欠かせないものは
  • 実行形式の場所
  • nib の名前
  • NSPrincipal クラスの名前
です。これがないとバンドルはシステムのロンチサービスに蹴られてエラーになります。
他にも固有識別子やバンドル自体の名前など、重要そうなものがあります。

これらは基本的には cmake 固有の変数に値を設定することで勝手に InfoList.plist が作られるのですが、なぜか nib と NSPrincipal クラスの名前だけ、 cmake 固有の変数がありません。
従ってそのままだとバンドルができても、ロンチサービスに蹴られてしまいます。ありがちですね。
すぐ思いつく対策は、あらかじめ作り込んだ InfoList.plist を用意しておいてビルドのポストコマンドでコピーすることですが、それだとカスタマイズ性がよくありません。

そこでカスタム用の変数を宣言しましょう。カスタム変数は要するに cmake の置換文字列機能です。この場合は、 MACOSX_BUNDLE_INFO_PLIST プロパティを使って、ベースとなる InfoList.plist のテンプレートを指定し、 その中身を任意の変数で置換すればよいわけです。
set_target_properties(cocoa PROPERTIES MACOSX_BUNDLE_INFO_PLIST Info-CMake.plist)
まず一点。プロパティは変数とは違います。変数がプロセッシングの過程で置換されるだけのものだとしたら、プロパティは cmake の振る舞いを変えることができます。
cmake --help-property-list で一覧を見て、 cmake --help-property でその意味を調べられます。 MACOSX で grep すると以下のようになりました。

MACOSX_BUNDLE
MACOSX_BUNDLE_INFO_PLIST
MACOSX_FRAMEWORK_INFO_PLIST
MACOSX_PACKAGE_LOCATION

困ったときに役立つと思いますので、頭に入れておきましょう。

もう一つ気をつけなければならないのは、 自分のテンプレートを指定したらもう cmake 固有のテンプレートはもう使われないというところです。
なのでどこから適当に拾ってきた InfoList.plist からテンプレートを作ると、ここで使わなかった置換変数は使われなくなります。これではカスタマイズ性が下がります。

ここでは cmake が持っているテンプレートを参考にしたほうがよいでしょう。
cmake のテンプレートは、

/Applications/CMake\ 2.8-12.app/Contents//share/cmake-2.8/Templates/AppleInfo.plist

などにあると思います。
これを使うと以下のような plist が出来上がります。
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple Computer//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
        <key>CFBundleDevelopmentRegion</key>
        <string>English</string>
        <key>CFBundleExecutable</key>
        <string>${MACOSX_BUNDLE_EXECUTABLE}</string>
        <key>CFBundleGetInfoString</key>
        <string>${MACOSX_BUNDLE_INFO_STRING}</string>
        <key>CFBundleIconFile</key>
        <string>${MACOSX_BUNDLE_ICON}</string>
        <key>CFBundleIdentifier</key>
        <string>${MACOSX_BUNDLE_GUI_IDENTIFIER}</string>
        <key>CFBundleInfoDictionaryVersion</key>
        <string>6.0</string>
        <key>CFBundleLongVersionString</key>
        <string>${MACOSX_BUNDLE_LONG_VERSION_STRING}</string>
        <key>CFBundleName</key>
        <string>${MACOSX_BUNDLE_NAME}</string>
        <key>CFBundlePackageType</key>
        <string>APPL</string>
        <key>CFBundleShortVersionString</key>
        <string>${MACOSX_BUNDLE_SHORT_VERSION_STRING}</string>
        <key>CFBundleSignature</key>
        <string>????</string>
        <key>CFBundleVersion</key>
        <string>${MACOSX_BUNDLE_BUNDLE_VERSION}</string>
        <key>CSResourcesFileMapped</key>
        <true/>
        <key>LSRequiresCarbon</key>
        <true/>
        <key>NSHumanReadableCopyright</key>
        <string>${MACOSX_BUNDLE_COPYRIGHT}</string>
        <key>NSMainNibFile</key>
        <string>${MACOSX_BUNDLE_NSMAIN_NIB_FILE}</string>
        <key>NSPrincipalClass</key>
        <string>${MACOSX_BUNDLE_NSPRINCIPAL_CLASS}</string>
</dict>
</plist>
せっかく DTD がありますので、必須の要素がどれかなどは DTD か Apple のドキュメントを参照してください。
しかしながら、一点問題があります。
CFBundleExecutable の値を、デフォルトの cmake のテンプレートはターゲット名から自動で埋めてくれるのですが、カスタムテンプレートを使うとどうもその機能が動かなくなってしまいます。従って、 MACOS_BUNDLE_EXECUTABLE は明示的に指定するようにしましょう。(なくっても、バンドル名が 実行形式名.app なら勝手にそれを実行してくれるようですが)  
   set(MACOSX_BUNDLE_EXECUTABLE "cocoa")
   set(MACOSX_BUNDLE_INFO_STRING "${PROJECT_NAME}")
   set(MACOSX_BUNDLE_GUI_IDENTIFIER "com.example")
   set(MACOSX_BUNDLE_LONG_VERSION_STRING "${PROJECT_NAME} Version ${VERSION}")
   set(MACOSX_BUNDLE_BUNDLE_NAME ${PROJECT_NAME})
   set(MACOSX_BUNDLE_SHORT_VERSION_STRING ${VERSION})
   set(MACOSX_BUNDLE_BUNDLE_VERSION ${VERSION})
   set(MACOSX_BUNDLE_COPYRIGHT "Copyright 2013.")
   set(MACOSX_BUNDLE_NSMAIN_NIB_FILE "MainMenu")
   set(MACOSX_BUNDLE_NSPRINCIPAL_CLASS "NSApplication")
   set_target_properties(cocoa PROPERTIES MACOSX_BUNDLE_INFO_PLIST Info-CMake.plist)
まとめるとこんな感じでしょうか。
InfoList.plist については以上です。

.nib などのリソース類

最後にして大物です。
リソースは bundle.app/Contents/Resources 以下にある雑多なものですが、 .nib のようにウインドウシステムレベルで重要なものも含まれます。
雑多なリソースは依存を書いておけば勝手にコピーされますが、 nib に関してはそうはいきません。 .xib から .nib へのコンパイルなどはカスタムコマンドを定義してビルドのポストフェイズに走らせる必要があります。

これについては以下のようにするのがよいようです。

   set(XIB MainMenu)
   set_source_files_properties(
       ${MACOSX_RESOURCE_FILES}
       # 任意のリソース群 (.nib は除く)
       PROPERTIES
       MACOSX_PACKAGE_LOCATION Resources)

   find_program(IBTOOL ibtool HINTS "/usr/bin" "${OSX_DEVELOPER_ROOT}/usr/bin")

   add_custom_command (TARGET cocoa PRE_BUILD
       COMMAND mkdir -p ${PROJECT_NAME}/Contents/Resources)
   add_custom_command (TARGET cocoa POST_BUILD
           COMMAND ${IBTOOL} --errors --warnings --notices --output-format human-readable-text
           --compile ${PROJECT_NAME}/Contents/Resources/${XIB}.nib
           ${XIB}.xib
           COMMENT "Compiling ${XIB}.xib -> ${MODULE}/Contents/Resources/${XIB}.nib")
新たな変数が登場していますが、全部デフォルトでよいです。
基本は set_source_files_properties() でリソースファイルの MACOSX_PACKAGE_LOCATION を指定してやることと、 ibtool を探してビルドのポストフェイズに明示的にコンパイルするようにしてやることです。
.xib はこの場合一つですが、複数ある場合は foreach でリスト要素ごとに add_custom_command() でポストフェイズのコマンドを追加してやる必要があります。

パスを自分で指定しなおしてやったりと少々冗長なところもありますが汎用の関数だし、これでいいのです。

重要じゃありませんが、 find_program() も find_library() と同様よくつかう関数です。

さて、問題はどうやって .xib を用意するか、です。
XML エディタで作ってもいいですが、なんせ結構煩雑ですし、ドキュメントも DTD すらもありません。
ノードを削っていって最小限の .xib を作るというのも面白いところですが、結構でかいファイルですんでここは Xcode 様にご登場願いましょう。
一個作って使い回しましょう。直したいところだけ XML エディタで直しゃーいいじゃないですか。
ibtool は結構便利なプロセッサですが、真面目に UI を作ろうと思ったらどうしたって Interface Builder を使うことになりますから。

ではそういったところでお疲れさん。

2013年5月30日木曜日

Wine 64bit 版は mac で動かないのか

Wine 1.5 系の開発が進んでいます。
僕はそんなに wine 詳しくないんですけど、そういえば 64bit 版って mac 向けにビルドできるのかな?と思い立ちやってみました。

結論からいうと結構あちこち直す必要があります。
大変です。カジュアルにはとてもいきません。

まずもって Xcode に付属の gcc-4.2 では wine のビルドがとおりません。
どうも可変長引数のスタックレイアウトが Win64 と互換性がないみたいで、これをサポートしてくれる gcc-4.4.4 が必要です。 mac ports で入れる分には簡単でいいですが。

そのあとはインラインasmでやたらエラーが出るのでこれを直して回ります。
movq で GP レジスタから XMM レジスタへロードするところが軒並み通らないので、メモリからのロードに変更しました。
GP レジスタへのロードはそのまま残さねばなりません。ABI の都合上、必要そうだからです。
インラインアセンブリはどこでエラーになったのかパッと見解り難いのが難ですよねぇ。
temp が残っててくれればいいのですけども。

あとは signal ハンドラのレジスタロードです。
mac 版は 32bit レジスタ用の実装しかないので、 64bit レジスタを取るように修正して回ります。

これで大体通るのですが、大きな悩みどころが残ってしまいました。
スレッドエントリの初期化で fs.base を退避/取得するところがあります。
BSD/Linux は syscall やコールゲートを使ってユーザーランドから fs.base にアクセスできるのですが、mac にはこの syscall がありません。
fs.base には rdmsr/wrmsr 命令を使ってアクセスする必要がありますが、これは特権命令なので特権モードである必要があります。

まぁ、無理に特権レジスタにアクセスすることもないか……。
ネイティブスレッドの TLS にでも入れときゃいいじゃん、ということでそういう風に書き換えたのですが、 Wow 側が fs.base に特定の値を期待してたらまずいことになります。
Win32 の頃はカーネルが FS にスレッドコンテキストのディスクリプタを入れていることも期待しており、これなら i386_set_ldt API を使って mac でも実装が可能です。
でもまぁ、プロセッサが命令レベルで特権命令だっていってるんだから、 Wow でもユーザープログラムが勝手に何かを期待することもないだろう……と祈ることにします。

(ちなみに、ユーザーランドから fs.base をリードできる新しい命令があるのですが、まだ Sandybridge では実装されてないようです。それにしても AVX はあるけど積和演算(FMA3)は実装されてないとか、色々新しい命令に取り残されている気がする。案外使えないな Sandybridge)

というわけで色々禍根を残したのですが、問題はそれだけに留まらない。
危なそうな警告を眺めていると int とポインタのキャストが結構たくさんある。
Wine の各種 driver (デバイスドライバじゃなくてプラットフォームごとのモジュールを driver と呼んでるみたい)は、例えばクリップボードの列挙を行うときに 32bit 版であれば、 Mac のネイティブ API が返すポインタを識別子としてそのまま int へキャストして返しています。

Win64 API でもそうした列挙に使う識別子はぜんぶ int のまま。一方で Mac のプロセス(Mac に限らず大抵の OS はそうだと思うが)プロセスイメージの仮想アドレスマッピングを 32bit 以上のアドレスで使います。
 仮想アドレスの割当からコントロールして 32bit に収まるアドレス空間を使うことも不可能ではないでしょうが、 OS レベルのメモリ割当を細かく使うと非常に高くつくし手間がかかる。
かといってキャストでは死んでしまいます。
下位ビット払って上位は固定……なんてのじゃダメかな。 Mac の API がどんなアドレス返すのか期待するのはかなり無理があるかな。

なのであちこちに map を作って、自分で払い出した識別子とアドレスを変換するようにしなければならない……ですね。
ああ、面倒くさい。
仕事ならやるよやりますよ。
でもこんな時間に疲れて帰って来て、寝る前にやることとしてはちょっと気が重い。

というわけで時間あるときにまたリトライしようと思います。

2013年5月25日土曜日

Wolfram Alpha で演算するメモ

ビット演算

 普段は google 電卓で間に合わせてしまうことも多いのですけど、 ビット論理演算は苦手な部分です。
さらに四則演算においても 64bit 整数を扱っているとどうにも使い難いことが結構あります。なぜか実数扱いになってしまって in hex で16進表示にできないようなパターンですね。

そういうときは Wolfram Alpha を使うことにしています。
しかしこれも、技術専用の計算機ではなくて幅が広いものなので、プログラミング気分で式を書くとエラーになったり assume されたりすることもしばしばあります。

例えば 0x プレフィックスの16進記法は文脈によって解釈されません。 '|' や '&' といった論理演算子は使えますが、 xor がありません。
そういうときは関数フォームを使いましょう。
関数フォームといっても bitxor() ではありません。 bitxor[] です。
bitxor[ bitor[0xdead000000000000, 0x0c00000000000000, 0x00a0000000000000], 0x5555000000000000]
結果は以下のようになります。

http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427ea3esf8qete

まぁ、少々煩わしい。
通常、 wolfram alpha は、
to base16
で HEX 変換してくれますが、入力が既に HEX で計算している場合に to base16 を付けてしまうとなぜか Result が表示されなくなり other base conversions にも base16 の結果だけが抜けてしまうのでめんどいです。
たぶんバグだと思うのですが……。ずっとこうですから……諦めてます。

この場合は、 to base16 を付けずに other base conversions の base16 結果を使うか、その下の other data types のところの more と big endian ボタンを押して 64bit integer 且つ Big Endian 表示の結果を手に入れましょう。
なぜデフォルトが Little なのか理解に苦しみますが、これももうずっとこうなので……。
more を押さないと 64bit integer や double precision floating point の結果が見られないのも、もう 21 世紀なんだから一つ頼むよ!と思うところです。

行列計算

あれば octave、 3D に特化した計算なら blender コンソールを使うのですけどちょっと今持ち合わせが……なときとかに重宝します。
特に Blender コンソールは python 使える人には絶賛お勧めですよ。クォータニオンも使えるし。でも Matrix3, Matrix4 といったクラスベースなので、変態的な行列を使うときは逆にちょっと厳しい。

wolfram alpha での行列記法は, 2x2 の単位行列が
{{1, 0}, {0, 1}}
です。 octave と大体一緒ですかね。むしろ却って馴染み易いかも。

行ベクトルが {0, 0} で列ベクトルが {{0, 0}} です。
注意するべきは、行列の転置は
transpose M
または M^T です。 M' でもなければ M^t でもありません。

簡単な例で言うと、2Dベクトル(0, 0)の平行移動(-1, -1)は
{{1 , 0, -1}, {0, 1, -1}, {0, 0, 1}} * {0, 0, 1}
宗教上の理由で列ベクトルが使いたい人は
{{0, 0, 1}} * {{1 , 0, -1}, {0, 1, -1}, {0, 0, 1}}^T
です。DirectX 脳の人は注意してください。
例えば以下。 上向き単位ベクトルを 30deg 回転させるには
{{sqrt(3)/2 , -1/2}, {1/2, sqrt(3)/2}} * {0, 1}
または
{{0, 1}} * {{sqrt(3)/2 , -1/2}, {1/2, sqrt(3)/2}}^T

結果は,
http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427ecq2au706qv



2013年5月6日月曜日

リアルタイムプログラミングの最適化

というわけでリアルタイムシステムの前提が確認できたところで技術的な問題ーー実際の最適化手法の話に移りましょう。

遅い命令を速い命令に変える


アナクロな話題ですが、たとえば除算命令は大抵のプロセッサで遅いことが解っています。
だからわざとらしい例では、

x = y / 8;

は共に整数型である場合は x = y >> 3 ; に置き換えられることが解っています。
ですが、さすがにこれくらいの最適化はコンパイラが自動で行ってくれるというのもまた事実です。
しかし x, y が浮動小数点型であった場合は話が別です。

では x = y / 2; より x = y * 0.5; がよいというのは本当でしょうか?
これは昔から言われていることですので事実はどうあれ、手が勝手に x = y * 0.5 と書いてしまう気持ちはわかります。
浮動小数点なら x86 では fdiv/fmul 命令(最近は divss/mulss) が使われるはずで、 fdiv は fmul より 30 cycle ほどの多いレイテンシがあります。
ですから大抵の場合は本当です。
しかし定数の事前演算はコンパイラにとって得意な最適化の部類であります。これくらいであれば最適化コンパイラが使える場合は自動で最適なコードが出力されると考えられます。


整数の除算、整数/浮動小数点のキャストに気をつける


ほぼ ARM 固有の話です。
ARM が整数の除算命令やキャスト命令を持っていない(いや、コプロにはあるよ)せいで、コンパイラの開発者は泣いています。
コンパイラの開発者が泣く時、利用者も泣くのです。
なので整数除算とキャストをしれっと C のプログラマが書いてしまうと、コンパイラは代理のコードを一生懸命出力します。
で、これが大抵遅いです。 gcc をお使いなら、ライセンスを一通り読んでください。 GNU Runtime Exception という特殊条項でしょう?これの解釈だって残念ながら一つじゃありません。……おっと、これは最適化よりも厄介な問題ですね。

浮動小数点コプロにしましょう。NEON 命令セットだったらキャストなんか一発なのです。
逆に言えば、ベクトル化しなくても SIMD 命令を使って最適化できる余地は案外あるよということなのです。
この場合はコンパイラに NEON 使用許可を出せば、コンパイラがいい感じにやってくれるでしょう。
NEON がないプロセッサもターゲットにしているなら……残念。他のところで速度を稼ぎましょう。

一つの命令で複数データを処理する


y0 = x0 * a;
y1 = x1 * a;
y2 = x2 * a;
y3 = x3 * a;

という例を考えましょう。全て float (単精度浮動小数点)とします。
これは乗算の右辺が変数ですのでコンパイラによる最適化はそもそも期待できません。
4回の乗算ですが、例えば、 [x0, x1, x2, x3] * [a, a, a, a] というベクトル演算と捉えれば一回の乗算と同じです。
こういう時は SIMD 命令の利用を検討しましょう。
x86 なら SSE2/AVX, ARM なら NEON, PPC なら Altivec です。

SIMD は Single Instruction Multi Data の略で一つの命令で複数データを処理できる命令体型です。
(お望みであれば一つのデータだけを処理することもできます)
具体的にコレはベクトルデータのことを意味します。
例えば、ピクセルデータの処理には 8bit 整数の 16 要素ベクトルから 16bit 8要素ベクトル、 32bit 4要素ベクトルまで幅広く使います。
普通の幾何学ベクトル演算なら 32bit 浮動小数点の 4 ベクトルでしょう。
128bit ベクトルレジスタを持つプロセッサなら 64bit 倍精度浮動小数点 2 要素ベクトルまでですが、 256bit ベクトルレジスタを持つ AVX 対応プロセッサなら 64bit 倍精度浮動小数点 4 要素ベクトルもいけます。

清水さんの4次補間関数での例を見てみましょう。

元のコードは C++ で書くとこんな感じであります。
(stroke オブジェクトへの add() 操作はシリアルバッファへの書き出しという風にぼかしていますが、当たらずとも遠からずってところでしょうよ)

    for(int i = 0; i < num; i++, deltaT += invertNum){
        x =  ((xfact1n + xfact2) * deltaT + xv0) * deltaT + xp1;
        y =  ((yfact1n + yfact2) * deltaT + yv0) * deltaT + yp1;
        p =  ((pfact1n + pfact2) * deltaT + pv0) * deltaT + pp1;
       
        xfact1n += xFact1step;
        yfact1n += xFact1step;
        pfact1n += xFact1step;
        //stroke.add(x,y,p);
        *(buf ++) = x;
        *(buf ++) = y;
        *(buf ++) = p;
        *(buf ++) = 0.f;
    }

SSE2 命令を使ってこれを最適化します。
使いたい命令が解っている場合、イントリンジックス (intrinsics) というものを使って C/C++ のコードで命令を指定することができます。

gcc の場合、 emm_intrin.h をインクルードしてください。

    __m128 fact2 = {xfact2, yfact2, pfact2, 0.f};
    __m128 v = {xv0, yv0, pv0, 0.f};
    __m128 p1 = {xp1, yp1, pp1, 0.f};
    __m128 fact1 = {xfact1n, yfact1n, pfact1n, 0.f};
    __m128 step = {xFact1step, yFact1step, pFact1step, 0.f};
    __m128 delta = _mm_set1_ps(0.f);
    __m128 inv = _mm_set1_ps(invertNum);

    for(int i = 0; i < num; i++){
        __m128 r = _mm_add_ps(_mm_mul_ps(_mm_add_ps(_mm_mul_ps(_mm_add_ps(fact1, fact2), delta), v), delta), p1);
        delta = _mm_add_ps(delta, inv);
        fact1 = _mm_add_ps(fact1, step);
        *(((__m128*)buf) ++) = r;
   }

_mm_add_ps() は二つの float4 ベクトルの加算、 _mm_mul_ps() は float4 ベクトルの積算です。
積和命令が大抵あるんですけど……SSE には見当たりませんね。
_mm_set1_ps() は所謂 splat 命令で、スカラー値をベクトルスロットへコピーします。
でも、意外と簡単でしょう?

ベクトル化前のアセンブリコードは、ループ内だけで以下のようなものでした。

LBB1_2:
    movaps    %xmm4, %xmm9
    addss    %xmm10, %xmm9
    mulss    %xmm5, %xmm9
    addss    %xmm0, %xmm9
    mulss    %xmm5, %xmm9
    addss    -24(%rbp), %xmm9
    movss    %xmm9, -12(%rbx)
    movaps    %xmm2, %xmm9
    addss    %xmm8, %xmm9
    mulss    %xmm5, %xmm9
    addss    -12(%rbp), %xmm9
    mulss    %xmm5, %xmm9
    addss    -20(%rbp), %xmm9
    movss    %xmm9, -8(%rbx)
    movaps    %xmm1, %xmm9
    addss    %xmm11, %xmm9
    mulss    %xmm5, %xmm9
    addss    %xmm6, %xmm9
    mulss    %xmm5, %xmm9
    addss    %xmm3, %xmm9
    movss    %xmm9, -4(%rbx)
    movl    $0, (%rbx)
    movss    -16(%rbp), %xmm9
    addss    %xmm9, %xmm4
    addss    %xmm9, %xmm2
    addss    %xmm9, %xmm1
    addss    %xmm7, %xmm5
    addq    $16, %rbx
    decq    %rax
    jne    LBB1_2

ベクトル化の後は以下のようにシンプルになります。

LBB1_2:
    movaps    %xmm2, %xmm3
    addps    %xmm6, %xmm3
    mulps    %xmm1, %xmm3
    addps    %xmm8, %xmm3
    mulps    %xmm1, %xmm3
    addps    -32(%rbp), %xmm3
    movaps    %xmm3, (%rbx)
    addps    -48(%rbp), %xmm2
    addps    %xmm0, %xmm1
    addq    $16, %rbx
    decl    %r14d
    jne    LBB1_2

なんか無駄にスタックからロードしているのは気に入らないですが。
この場合はスタック以外には buf のアドレスにしかアクセスしてませんし、これを修正した程度ではベンチマークに影響なかったのでよしとしましょう。

本来はレジスタを使い切るまでループアンロールすべきですが、今回はループ回数が補間する点の距離に応じてダイナミックに変わるためそこまではしないものとします。
[x1, x2] - [y1, y2] として[1,1]-[1000000, 1000000] のような極端なデータを与え、 282843 回のループになるようにしています。これを10回ループさせて簡単なベンチを取得しました。

すると、ベクトル化前に 11ms だったコストがベクトル化後には 5ms になっていました。2.2倍も速くなったわけです!
Sandybridge の i7 ではそうだったというわけで、例えば NEON を実装した ARM ではもっと大きな伸びが予想されます。
経験的には 2.5 倍はカタいです。(もっとも NEON の実装がしょぼく、殆ど速くならないバカ実装のバカプロセッサもあるにはありますが……。その辺で売ってるようなやつは大丈夫でしょう)

でも実際に使うには飽和演算や、ベクトルレジスタへのロード/ストアについてはアドレスアラインメント,  permute (ベクトル要素の並べ替え) や splat など結構事前に要求される知識があるもんです。
そのへんには注意してくださいね。

ところで蛇足になりますが、ベクトル化する前のコードをよく見ると、


        *(buf ++) = 0.f;

という謎の行が追加されてます。  stroke.add() が未定義なのをいいことに、単純な比較が可能なように追加させてもらいました。
ベクトル命令は 128bit レジスタ前提なので 16byte ごとにしか読み書きできないからです。
メモリの読み書きを 16 の倍数にする(メモリのアドレスも)というのはベクトル最適化ではごくごく当たり前のことです。
ミスアラインアクセスも不可能なわけじゃないですが、アラインがマッチする場合についてベクトルレジスタの読み書きでは二倍程度遅いと思っていてください。

ループをアンロールする


ループを展開して条件分岐を削減します。
ですがループのアンロールが最適化にとって有意かどうか、実は常に議論の対象となります。
なぜなら条件分岐の予測はプロセッサにとって重要なテーマですし、昨今のプロセッサにとっては多くの場合ブランチミスプレディクションよりロードストアのほうがずっとパフォーマンスにインパクトがあるから無意味なことも多いのです。

for (int i = 0; i < 32; i ++)
   foobar(x[i]);

という極めて単純なパターンでは、インライン展開しないとした場合、何回ほどループを展開すべきでしょうか。
仮に4とすると

for (int i = 0; i < 32; i += 4) {
   foobar(x[i]);
   foobar(x[i+1]);
   foobar(x[i+2]);
   foobar(x[i+3]);
}

となります。この場合条件分岐の回数は1/4になります。
しかしながら関数の呼び出し毎に x の配列から値をロードしているのはそのままであることに注意してください。

コンパイラはループ内のコードが充分小さいなら結構積極的にループを展開します。ループ内のコードの量は、分岐予測までの最低サイクル数、命令キャッシュの量に依存します。
そしてループ回数が可変の場合も、予測が可能である場合かなり頑張って予測します。

つまりループのアンロールは考慮すべき条件が多過ぎて、コンパイラに任せるのが無難です。
しかしながら、ある条件下ではプログラマが自分で展開したほうがよい場合もあるのです。
どういう場合でしょうか?
それは以下のような場合です。
  1. ロード/ストア回数を削減できる場合
  2. レジスタが余っている場合
1の場合、要するにメモリアクセスが実は極めて遅くなり得るという事実に注目した最適化です。

たとえば上記のループでは

for (int i = 0; i < 32; i += 4) {
   register int x0, x1, x2, x3;
   x0 = x[i];
   x1 = x[i+1];
   x2 = x[i+2];
   x3 = x[i+3];   foobar(x0); foobar(x1); foobar(x2); foobar(x3);
}

というようなコードが書けるかも知れません。命令のプリフェッチは別ですが、メモリからのロードを1/4にできたことを意味します。
もっともデータキャッシュは一般に16バイト以上ありますので、キャッシュアウトしてなければこんなことをしなくてもそこそこ速いのですが、キャッシュが汚染されるような場合にはこちらのほうが速いことがあります。
この例ではループを展開したことに大した意味はありません。
しかしながら別の方法を併用することでスループットを増大することができるのです。
次のループで使うデータを先にロードしておくといった工夫でスループットを上げる方法や、場合によってはキャッシュ制御命令を使ってストリームロードを行うなど様々な工夫を施すことができます。

当然、データの先読みというのは保存しておくためのレジスタが充分余っていることが前提です。
レジスタが沢山あるプロセッサの場合はぜひ検討しましょう。
例えば、SPU にはレジスタが128個ありました。そこまでではなくとも SSE2, およびSandybridge 以降搭載されている AVX 命令では XMM/YMM レジスタを 16 個利用できますし、 NEON では 16個のベクトルレジスタを ABI に配慮することなく自由に使えます。

ところで、上記のようなデータの先読みをコンパイラが自動的に行うことはできないのでしょうか?
残念ながら、基本的にはできません。先読みに関してはプログラマが明示的に最適化を行わねばならないことが殆どです。
なぜなら foobar() 関数の副作用で x の配列の中身が書き換えられるかも知れないからです。
x がグローバル変数で、 foobar() から見えるならコンパイラは先読みを行いません。
詳しくは後述します。

……とこのように細かい話が続くと「ああ、じゃあコンパイラ任せね」と思うかも知れません。
ところがあなたが使っているソフトウェアの殆どは、こういう最適化を行っています。
ブラウザが使っている cairo を始め、某ブラウザプラグインもそうです。基本的に画像を扱うソフトウェアでループのアンロールを用いて複数ピクセルを一度にロード/ストアする最適化をしていないソフトというのを、僕は見た事がありません。
画像を扱うソフトはほぼ100%、4pixel (時には 16pixel) 同時処理するためループをアンロールしています。
でもその動機はブランチミスプレディクションを減らすためではなく、データのロードストアを減らし、ストリーミング命令を駆使し、キャッシュのヒット率を上げてスループットを向上させるためです。
お間違えなきよう。

インライン展開する


ループアンロールに関する話は少々難しかったでしょうが、インライン展開は簡単です。
C++/C99 では関数をヘッダに書いて inline と関数の前に書くだけです。
マクロと同じではありません。マクロは必ず展開されますが、インライン関数は展開されないかも知れません。
マクロは関数ではありませんが、インライン関数は関数です。(この違いは実は大きいもので、マクロではリンクエラーになるようなコードもインライン関数では平気です)
インライン関数は、昔の VC のコンパイラがだらしなかったせいで未だに色々都市伝説がありますが煩わしいのでここでは無視します。

間抜けな会社のコーディングルールではヘッダに実装を書くことを禁止していることもあるでしょうが、そういうところでは仕事をしないほうがいいと思います。

ただやはりインライン展開されて良いコードとされて困るコードというのはあります。あまり大きなコードは避けるべきです。
小さい関数であれば、インライン展開することで飛躍的にコードサイズを減らす事もできるのです。
ABI のコーリングコンベンションという、関数を呼び出すために守らなければいけない決まりというのがプラットフォームによって決まっていまして、これが余りにも厳しいような場合では、積極的にインライン展開してかまいません。
インライン展開されたコードはもはやコーリングコンベンションを無視したものです。コードサイズの削減と同時にパフォーマンスも向上します。
個人的な経験では、PPC でインライン展開を完全に禁止すると 10MB くらいになってしまうコードが、インライン展開をすることで 9MB 程度まで押さえられたこともあります。

PPC 以外でそこまで ABI が大きい例というのは知りませんが、 ARM や x86 であっても、ただの薄いラッパ関数などなら迷わずインライン展開すべきです。
リーフ関数の場合は呼び出し側の削減にしかならないので(コードサイズという点では)逆に大きな効果がないかも知れません。

小さいコードは効率がよいと思われるかも知れませんが、逆ということがあります。
例えば他の関数を呼び出すだけの関数といった薄いラッパーでは、コンパイラはそれ以上最適化する余地も殆ど残されていないのです。
レイテンシーを隠蔽するために命令同士を数サイクル離すのは(アセンブリレベルの最適化において)基本中の基本ですが、そもそも命令が絶対的に少なければコンパイラは諦めてしまいます。
かといってあまりに巨大なループは命令キャッシュから外れ、インライン展開により巨大になった関数ではプロファイラの運用やデバッグを困難にしてしまいます。

適度な大きさを保つことが重要です。
ラッパーやリーフから積極的にインライン展開し、マクロよりもコンパイルオプションで展開を制御できるインライン関数を使いましょう。


エイリアッシングの問題を避ける


void copy(void* dst, void* src, size_t len)
{
     void* end = (char*)dst + len;
     while (dst < end)
          *(((char*)dst) ++) = *(((char*)src) ++);
}

なーんにも考えずに書いたコピーのコードです。とりあえず前述のループアンロールの指針に基づいてループを展開しましょう。


void copy4w(void* dst, void* src, size_t len)
{
    void* end = (char*)dst + len;
    while (dst < ((char*)end + 4)) {
        *(((int*)dst) ++) = *(((int*)src) ++);
    }
    while (dst < end) {
        *(((char*)dst) ++) = *(((char*)src) ++);
    }
}

(見易さのためにアラインメントの評価をさぼっているのでこれはダメなコードですがそれはさておき……)
さて、このコードは期待通りのパフォーマンスが出るでしょうか?
ロードストアがレジスタ長に一致するのでたぶんパフォーマンスは出ます(というか下がらなくなります。ですが最適化前の copy() とは意味が違っています
なぜかというと、 dst, src が示す領域に重複した部分があると動きが違ってしまうからです。
このことは memcpy と memmove では memcpy は最適化によって高速化できるが memmove はそうではないという事実に結びついています。
(最適化できる可能性がある、というだけで全ての実装で memcpy のほうが速いとは限りません。同じかも知れません)


同様の問題を更に見てみます。

void copy4(void* __restrict__ dst, void* __restrict__ src, size_t len)
{
    void* end = (char*)dst + len;

    while (dst < ((char*)end + 4)) {
        *(((char*)dst) ++) = *(((char*)src) ++);
        *(((char*)dst) ++) = *(((char*)src) ++);
        *(((char*)dst) ++) = *(((char*)src) ++);
        *(((char*)dst) ++) = *(((char*)src) ++);
    }
    while (dst < end) {
        *(((char*)dst) ++) = *(((char*)src) ++);
    }
}

これは愚直にインライン展開した場合です。
展開した部分のアセンブリを見てみましょう。

LBB2_3:
        movb    (%rsi,%r8), %r9b
        movb    %r9b, (%rdi,%r8)
        movb    1(%rsi,%r8), %r9b
        movb    %r9b, 1(%rdi,%r8)
        movb    2(%rsi,%r8), %r9b
        movb    %r9b, 2(%rdi,%r8)
        movb    3(%rsi,%r8), %r9b
        movb    %r9b, 3(%rdi,%r8)
        addq    $4, %r8
        cmpq    %r8, %rcx
        jg      LBB2_3

レジスタへのロードからメモリへのストアが近過ぎます。
ロードしたレジスタを実際に使うまでに命令を稼いでレイテンシを隠蔽するというアセンブリの最適化の基本方針が生かされていません。
レジスタはまだ6つ余ってますので、どうにかならないのでしょうか。
せめてこんな感じ
        movb    (%rsi,%r8), %r9b
        movb    1(%rsi,%r8), %r10b
        movb    2(%rsi,%r8), %r11b
        movb    3(%rsi,%r8), %r12b
        movb    %r9b, (%rdi,%r8)
        movb    %r10b, 1(%rdi,%r8)
        movb    %r11b, 2(%rdi,%r8)
        movb    %r12b, 3(%rdi,%r8)
の最適化をコンパイラが勝手にやってくれてもいいのになぁ〜〜と思うかも知れません。
ですがこれも、前述した src/dst が互いに重複したアドレスを指しているかも、という可能性のために、コンパイラは決してこのような最適化を行いません。
この例では、 mov の順番を多少入れ替えたところでレイテンシを隠蔽する効果は殆ど期待できませんけど、もし仮に効果があるとしても、コンパイラは最適化しません

同じメモリ領域を指す複数の異なるポインタをエイリアスと呼び、最適化においては重要なテーマです。
エイリアッシングが発生すると、コンパイラは(仮に可能だったとしても)最適化を行えなくなるのです。

こういうときには、 __restrict__ キーワードを使って src と dst が互いにエイリアスとはならないことをコンパイラに示します。
(もちろん、本当にエイリアスにならない場合だけです。仕様上エイリアスを許容する memmove ではだめです)
void copy4(void* __restrict__ src, void* __restrict__ dst, size_t len)
{


エイリアッシングによる不要なロードを避ける


再びエイリアッシングの話題です。
話を簡単にするために、まず簡単な例から見てみます。
これも少々わざとらしい例ですが……。

void copyi(int* dst, int* src, size_t* len)
{
    size_t l = 0;
    for (size_t i = 0; i < *len; i ++) {
        *(((int*)dst) ++) = *(((int*)src) ++);
        l ++;
    }
    *len = l;
}

長さをアドレス渡ししています。これくらいは戻り値で返せよ!と思うでしょうが、まぁお付き合い下さい。
アセンブリを見てみましょう。

LBB4_2:
        movl    (%rsi,%rax,4), %ecx
        movl    %ecx, (%rdi,%rax,4)
        incq    %rax
        cmpq    %rax, (%rdx)
        ja      LBB4_2
LBB4_3:
        movq    %rax, (%rdx)

len に渡したアドレスは rdx に入ってます。rsi が  src, rdi が dst です。
大体予想通りかと思いますが、もしかすると一点奇妙なロードがあるとお思いかもしれませんね。
        cmpq    %rax, (%rdx)
copyi() の len は一回渡ったら関数の実行中に変更されないはず。
ならなんで比較の度にわざわざメモリから値をロードしているのでしょうか?
まぁ、 C のコードが自分で len から値を引っ張ってループの比較に使えばよいのですが……コンパイラの最適化とはこの程度のこともできないのでしょうか?
実はコンパイラは目ざとくも、ここでもエイリアスの問題が発生する可能性に気付いているのです。
len が dst のエイリアスーーつまり、 len のインスタンスが、 copyi() が書き換える dst の領域に配置されている可能性があることを気にして毎回ロードしているのです。
つまり呼び出し元が
copyi(dst, src, (size_t)dst[0]);
とやらかしているんじゃないか、という配慮ですね。
この場合も __restrict__ キーワードが使えます。
void copyi(int* dst, int* src, size_t* __restrict__ len)
{
としてコンパイルした結果をご覧ください。
        movq    (%rdx), %rax
        testq   %rax, %rax
        je      LBB4_4
        xorl    %ecx, %ecx
        .align  4, 0x90
LBB4_2:
        movl    (%rsi,%rcx,4), %r8d
        movl    %r8d, (%rdi,%rcx,4)
        incq    %rcx
        cmpq    %rcx, %rax
        ja      LBB4_2
LBB4_3:
        movq    %rcx, (%rdx)
        popq    %rbp
        ret

len はループに入る前に rax にロードされ、 cmpq で比較する際にいちいちロードされたりはしません。

まぁでも、こんな変なコードは書かないから俺関係ないよ、という方がほとんどでしょう。

では以下の例はどうですか?

struct wstr {
    short len;
    short* ptr;
};

void copywstr(wstr& dst, wstr& src)
{
    for (short i = 0; i < src.len; i ++)
        *(dst.ptr ++) = *(src.ptr ++);
    dst.len = src.len;
}

ずっとありそうですね。
事前に short l = src.len; としておくより1行少なく、よっぽどスマートなコードに見えます。
……が、これもエイリアスの問題を踏むのでコンパイルした結果は残念ながらループのたびにロードをしています。
小さいコードが効率よいとは限らないのです。
(無駄かどうかは本当にエイリアスを意図したかどうかによります)

エイリアスの場合の振る舞いを正しくするため、 STL の実装では意図的に上記のようなものが多いように思います。
STL を使うなという話じゃありません。真似するときは本当にエイリアスの場合があるかどうか考えてやりましょうということです。

エイリアスの問題に慌てて取り組んだところで、プログラムの全体が何パーセントも向上することは期待できませんし、ホットスポットに対応するにはもっとずっと効果的な方法があるはずと考えるのが普通です。
それどころか、本来エイリアスを受け入れるべきところを潰してしまい、バグを生む可能性のほうがずっと高いです。

ですが——ARMのようなプロセッサで何百KBにもなるデータを処理する場合を考えてみてください。
ARM の実装により、 LRU キャッシュアルゴリズムを持たない実装というのが結構あります。そういうバカキャッシュのプロセッサでキャッシュの汚染が発生するというのはパフォーマンスを大きく下げる原因になります。
(4way キャッシュくらいあるのは普通なのでコピーくらいは救われるかも知れませんが、他に src/dst 以外に係数テーブルやらスタックやらで消費されるでしょう)
L1/L2キャッシュミスしたら数十usから百数十usのオーダーで時間が無駄になることを覚悟せねばなりません。それがループ回数だけ積み重なるとあっという間に 1ms なくなってしまう場合もあるのです。

遅いコードを速くするのは最適化の基本ですが、リアルタイムプログラミングにおいては遅くなる可能性を徹底的に排除しなければいけないコンテキストが存在します。
そのようなコードにおいては気をつけましょう。

-fno-strict-aliasing を回避する


最近の最適化コンパイラは、非互換型のキャストに際して発生する偽のエイリアッシングを無視して最適化することがあります。
これをこのまま使うと予期せぬバグが顕在化することも少なくありません。
というか、すごい発生します。

そこで、最適化を抑制するためのコンパイルオプションとして、 gcc では -fno-strict-aliasing というのがあります。
これは最適化を保守的にする代わりに、非互換キャストを行った場合でもエイリアッシングを無視した先読みをさせなくなり、ルーズなキャストまみれのコードが問題を起こすのを避けることができます。

経験上、オープンソースの大半のプロジェクトで -fno-strict-aliasing がついてます。
パフォーマンスの観点からは避けるべきです。
ホットスポットの翻訳単位から順番に外していけるようにしましょう。

エイリアッシングの問題はそもそもわかりにくく、更に非互換キャストでのみ発生する偽のエイリアスなんて人間が自分で見つけるのは困難です。

そこで -Wstrict-aliasing オプションでコンパイルすると、最適化を妨げるエイリアッシングを警告してくれるようになります。


インラインアセンブリの運用


インラインアセンブリを書いていると、解ってない人からは
「今時アセンブリなんて……バカじゃないの?」
と言われます。

一方、よく解っている人からは
「インラインアセンブリなんか使うな。フルアセンブリで書け」
と言われます。

アセンブリが時代遅れなんてのはそりゃー昔から言われてます。
最近の複雑化したプロセッサにおいて人間の書いたアセンブリがコンパイラの最適化に勝てるなんて、そういう理由から書くわけじゃないのです。
ピンポイントで、どうしてもここだけコンパイラの最適化じゃ足りないとか、どうしても使うべき命令が他にあるというような止むに止まれぬ事情から使うのです。

で、そういう状況はみなさんが思うよりずっとあります。
cairo, dlmalloc, avm+, webkit, fiber……名前は伏せるけど商用アプリケーションの数々、これらは全部使ってます。人気のあるソフトでインラインアセンブリを全く使っていない例というほうが少ないです。 zlib とか Freetype は使ってないかな。 STLport とか DB の実装とかでも使ってなさそう。
必ずといっていいほどどこかに登場します。

僕はデバッグ目的で書く事も多いのですけど、その目的は皆パフォーマンスのためです。
時代遅れと誹られつつも100%全員がインラインアセンブリのお世話になっている。

または、時代遅れだよなと鼻で笑った当人が裏ではこっそりインラインアセンブリを書いている。アイツも、……アイツもだ!

まぁ、そうはいってもコンパイラのイントリンジックスが充実しているお陰で、本当にインラインアセンブリを書かねばいけないケースというのはだいぶ減ってきたと思います。

ところで、本当に解っている人がインラインアセンブリを嫌う理由は何でしょうか?
それはインラインアセンブリのオペランド制約が gcc info を見ても載っておらず、 gcc のソースを見てその通りにやっても上手くいかずイライラすることがとても多いからです。
コンパイラとプロセッサ、そしてそれぞれのバージョンへの依存がとても大きいのですね。
逆説的ですが、保守のことを考えるとインラインより関数全部をアセンブリで書いたほうがマシ、ということすらあり得ます。

じゃあ実際、どういうときに使うの?ということをここでは書いておきます。

ビットを数える

値の何ビット目が立っているか?値の中に立っている立っているビットはいくつあるか?
そういうことを調べたいのはよくあります。
hacker's delight の実装を使っている例もありますが dlmalloc などではプロセッサの命令を使うようなコンフィギュレーションも存在します。
popcount 命令や bcl/bcr 命令なんかですね。
x86 ではイントリンジックスにありますので不要でしょう。

SIMD命令

計算そのものはイントリンジックスで行えることが殆どですが、特定レジスタへの値のロードなどではイントリンジックスが使えないもあります。
そもそもイントリンジックスがなければしょうがありません。
例えば AVX 命令を使いたい!と思っても手元の gcc4.2 では対応してません。
gcc を気軽にアップデートできない事情は皆さんよくご存知でしょう。
そういうときには活躍します。

スピンロック

マルチスレッドプログラミングにおいて、マシン固有のスピンロックは人気があります。
もはやマルチスレッドプログラミングでは必須といってよいでしょう。
mutex/semaphore などのシステムコールと異なり特権モードにスイッチする必要がないので非常に軽いです。
(その代わり使うときにはデッドロックに注意せねばなりませんが)

大抵の場合、イントリンジックスにはなくてそれ以外の組み込み関数にはあるかも知れません。
処理系が持っているならそれを使いましょう。だってテストするの面倒じゃないですか。狙った通りにバスロック横取りしたりキャッシュラインロックロストしないとならないんですから。
でも、そうでない場合や処理系依存の実装を使いたくない(スピンロックを使う以上、可及的速やかにクリティカルセクションを通過する場合なんですからそういうこともあるでしょう)場合自分で作るほかありません。

ABIを無視、またはABIに強烈に依存するコード

余程レアケースとは思いますが VM の実装なんかでは結構あります。
レジスタのアサインメントは ABI (Application Binary Interface) により固定なので、コーリングコンベンションを利用したデバッグルーチンや特殊なサンク関数などはアセンブリで書くよりありません。



2013年5月3日金曜日

最適化 etc, リアルタイム作戦大失敗

とりあえず前回のエントリでリアルタイム処理は特殊だ、ということだけ解ってもらったと思います。
まぁこれは100メートルリレー400mとフルマラソンの違いであります。

リレーでは前の走者をトリガーに自分が全力で走ります。
「ここまで勝ってるからゆっくり走っていいよね」ではシバかれます。
お前は全力で100m走れ、最低でも11秒で走れ、速ければ速い程いい、 と言われるのがリアルタイム処理の世界だと思ってください。

実際に失敗例と成功例を見てみましょう。
便宜上失敗例といいますが、本当に大失敗したものは消えていますので同世代の比較ができません。ここでは「非常に優れているが、比較的の上では一歩及ばないもの」のことです。失敗例扱いされたといって気にしないでください。


Android のタッチパネル


僕は詳しくないのですが、どうも iPhone と比べて遅いらしいのです。
どのデバイスもハードウェアは常にポーリングを行っておりデータの入力があればメインのプロセッサに報せます。
このときに使われるのが割り込みというシステムです(敢えて割り込みを使わないということも考えられますが、ここでは割り込みとします)。
具体的には、ポーリングを行っているタッチパネルの制御用マイコンから、ホストのメイン CPU に信号がくるわけですね。
この信号を受けてホストのメイン CPU がデータの処理用のコードを呼び出すのですが

  • CPU の割当が遅い
  • いつタッチポイントのデータ転送を開始できるかわからない
  • そもそもタッチパネルの制御用マイコンというやつの素性がわからない
  • データの処理が遅い

などの理由で、データの処理開始が遅れます。
スタートが遅いとデータを取りこぼしたり、ユーザーへの反映までがずるずると遅れることになります。
データを取りこぼさないテクニックとしてはデータを取ったら後続のデータ処理をキックし、可及的速やかに処理を戻す、ということも考えられます。
割り込み処理中のイベントに対応するため、割り込み処理は可能な限り軽くしておくというのが基本なのですね。

ですがそもそも割り込みが入るのが遅い、となるとシステムレベルのプログラマにとっても厳しい事態となります。
iPhone の場合は、タッチパネルの制御マイコンによく知ったものを使っているので、 OS は最も最適な方法で一連の処理を終えることができます。
Android はベンダーの提供するドライバを呼び出すしかなく、全てをドライバの出来に左右されてしまいます。
ARM というプロセッサは割り込み処理がとても速くなるよう設計されているのですが、海のものとも山のものとも知れないドライバに処理を移すには、やっぱり最悪ケースを考えて移すよりありません。
不要なレジスタを退避し、いつ終わるとも知れないデータ転送を待つか、諦めてコンテキストを分離する……そういう世界です。

更に、タッチパネルというのは一見するよりも扱い難いものです。というのはマウスなどにはないノイズが多く、一回のスキャンで得られたポイント情報をアプリに全部渡すわけにはいきません。
システムはノイズを取り除き、有意な情報として処理したものをアプリケーションに渡します。この処理には、実際には数フレーム分の時間をとってしまうことがあります。


これら全て、ユーザーから見ればほんの一瞬の出来事ですが、下手をするとその一瞬は 0.1 秒くらいになってしまうかも知れません。或いは 0.03 秒で済むかも知れません。出来によります。
iPhone と Android では iPhone のほうがパネルの反応がよいとされるのは、ドライバやタッチパネルの制御用チップの出来の善し悪しに以外にもそうした事情があると思われます。
このことはユーザーにとっても、とても大きな問題です。詳しくは後述するような理由からです。


3d-coat 「書き味」の問題


3D-coat というとても素晴らしいソフトがあります。
これはスカルプチュアと呼ばれる 3D モデリングに使うソフトで、他に著名なものでは ZBrush や modo というのがありますね。
3d-coat もとても優れたソフトなのですが、フォーラムでは常に ZBrush と比較されてしまいます。
なぜか?
僕はアーティストでないのでそこまで拘りがないのですが、3D のアーティストの間では「書き味」というのがしばしば話題になり、 3d-coat の書き味は ZBrush には及ばないというのですね。
これはアーティストがペンタブで描いたものが、どれくらいよくポリゴン上に反映されるかというものです。
3D-coat はマルチレベルのボクセルを使用しており、これはとても高度で造形しやすいのですが、計算は重くなります。
アプリケーションはタブレットの入力を受け、2Dがボクセルモデルのどこに対応するかを計算し、ブラシを適用します。ブラシの適用は一回ではなく、内部的に何度も適用しますので、単位時間あたりの処理回数が多ければ多いほどアーティストのニュアンスを適用しやすくなります。
従って、重たいボクセルモデルを使用しているときと軽いボクセルモデルのときとでは、同じようにペンを走らせても結果が全く異なるのです。
重い場合はまず描いたものが飛び飛びに反映されてしまいますし、同じだけペイントしたつもりでも適応量がささやか過ぎたりします。ですからユーザーは(画面に反映したかどうか確認しつつ)ゆっくりとペンを動かさねばなりません。
ユーザーへの反映——これをフィードバックと呼びますが——フィードバックが細かく、速く、正確であるほど人間の動きも正確になります。ですので、フィードバックが遅いということはアーティストにとって手足を繋がれているのも同然だという意味です。

アーティストのいう「書き味」を科学的に考察すると、それはフィードバックの速度と精度のことであります。

enchantMOON が拘っているという「書き味」もまったく同様に、フィードバックの速度と精度だと思われます。


Android 4.1 以前 のサウンドシステム


Android は linux をベースとしています。
これはリアルタイムシステムではありませんので比較的時間にルーズな OS であります。
CPU の計算資源が足りない時にルーズになるのは仕方がないとしても、日頃から結構ルーズであります。
たとえば linux のサウンド出力のシステムは /dev にマップされた抽象化デバイスとして実現されており、プログラムはいくつものバッファを経て音を再生します。
バッファを経るということは、たとえば CPU の計算資源が割当られず、サウンドデータを出力できない期間があったとしても、割当てられたタイミングで沢山データをバッファを供給しておけば音が途切れずに再生できるというメリットがあります。
その一方、出力しようとした音が実際に出力されるのがいつになるかはっきりと解らないというデメリットがあります。
一般には、 1000ms 分のバッファがあったとしたら音が出力されるのは 1000ms 後です。遅過ぎます。
まぁ 1000ms というのは極端で、実際は 100ms くらいでしょうが、効果音がズレるなどという事態はゲームにとっては非常に致命的です。
その代わり1秒くらい CPU の時間が回ってこなくても大丈夫ですし、レート変換などもシステム側で行うことができるので、アプリは音を出すのがずっと簡単になります。もしレート変換を自分で行うとしたら結構大変です。変換するレートの最小公倍数ぶんの時間がかかると思ってください。

一方、 iPhone は MacOS の CoreAudio という薄いレイヤのアーキテクチャを利用しています。
これは OS がサウンドデバイスの管理をアプリに任せる反面、プログラムがデータを出力してから即座に音を出す事ができます。

さらに、前述したタッチパネルの遅延があることも思い出してください。
このため、 Android にはリアルタイム演奏のアプリケーションが少ないですし、奥深いアクションゲームの体験といった点においても遅れをとっているわけです。

チケットゲート


生憎、皆さんが比較体験できない例です。
もう大分前の話ですが、仕事でオンラインチケットを検査してゲートを開閉するシステムを作っていたことがあります。
正確には僕が作ったわけではなく、最初につくったシステムがあまりにも遅かったら、その高速化を頼まれたのです。
研究所からの要求はチケットの検査から結果が出るまで 120ms  というものでした。それが実際は 2000ms 以上かかっていたのです。
仮に、駅の自動改札に Suica をタッチして2秒待たされたと考えてください。
事故になりますよね。
ETC とか考えただけで憂鬱になります。
僕のはそこまでシビアなシステムではありませんでしたが、最終的には目標の性能を達成できました。
Suica もえらい苦労したと聞きます。
自動改札を通るとき、たまには思い出してあげてください。ゲートを速やかに開けるために何ヶ月も休まないでプログラムを書いた人がいることを。

卑近な例としてチケットゲートを上げましたが、所謂組み込みでは大概リアルタイムです。
ロボットや車の操縦なんかですね。
人工衛星やロケットなど真空に近い状況下で動作するシステムは

USB

リアルタイムシステムというと組み込みプログラミングという印象強いでしょうが、デバイスドライバだって優れた応答性が要求されます。
USB デバイスは言わずと知れた拡張端子の傑作であります。
USB 以前のことを考えてください。RS-232C, パラレル、 SCSI のアンフェノールピン……。
USB コントローラチップはパワフルですが、反面システムに対する要求も高いものでした(OHCI と UHCI で仕様が分かれたのもまずかったけど)。

まず 32bit の PCI アドレス空間が必要です。これで Win3.1/DOS は対応できなくなりました。さようなら。 Windows95 ですら OSR2.1 以降のスペシャルバージョンが必要でした。
PCI アドレス空間の問題を解決したあと、待っていたのは CPU 計算資源の問題でした。
USB には割り込み転送モードやアイソクラナス転送モード、バルク転送モードがあります。
バルク転送モードは CPU を消費せずに大容量データを転送できるモードですが、それ以外では USB コントーラーの割り込みに対して CPU が高速に反応しなければ、HUD ではマウスカーソルが飛びますし Web カメラの映像は途切れてしまいます。
高速な CPU と優れたOS/ドライバがなくては USB のように CPU 食いのバスを快適に利用することはできません。USB3.0 が失敗例にならないことを祈っております。


焼きガニ、TCP/IP, Ethernet, ブロードバンドネットワーク


TCP/IP や Ethernet が失敗?いえいえそんなことは決してありません。
ただ TCP/IP がそれまでのネットワークプロトコルのなかで最も CPU 資源を食うということを知って欲しかっただけです。
TCP/IP は沢山のポートやソケットを使って並列的に通信を行い、アプリケーションの実装とも分離されているのでそれまでの PC のシングルタスク OS では実装が困難でした。
タイマ割り込みという方法で、擬似的に TSS (時分割スケジューリング)を行ってCPU資源を分散する実装もありました。(Waterloo TCP など)

そして Ethernet カードはコモディティ化に伴い、高価なハードウェアのバッファをケチるようになりました。
Ethernet カードに内蔵するバッファが小さいということはブロードバンドネットワークで大容量のデータを転送する際に頻繁に CPU に割り込む必要があるということです。
「バッファが一杯だから速くデータを拾ってくれ!」と CPU に言うわけですね。CPU が割り込みを受けてデータを拾ってくれるまで、 Ethernet は次のデータグラムを受信できません。
USB のときと同様、帯域を使いこなすにはリアルタイム性の高い処理をこなす必要があるのです。
かといってあまりにケチると Realtek のチップのように燃えてしまうこともあります。俗にいう焼きガニというやつです。

不出来なチップとドライバの組み合わせでは、一度に大容量データを転送するとシステムが死んでしまうこともありました。
当時の遅い CPU と OS の組み合わせでは、 100Base の LAN の帯域を使えないことがありました。
現在でも、不出来なルーターを使うとルータのCPUの処理が追いつかず、ネットワークのスループットを下げることがあります。それは仕方がないことで 1Gbps もの帯域を非力な組み込みプロセッサで処理し、ルーターやファイヤーウォールを実現するのは簡単なことではないのです。

ゲーム機


ゲーム!
まさにゲームというのセンシティブな入力のフィードバックのスピードが要求されるシステムの最たるものです。

ファミコンのコントローラが優れていたのは、ただのスイッチではなくマイコンを内蔵していたことでした。
いちいち本体まで信号を送らずとも、その場で処理していたからこそ細かい入力のニュアンスを伝えるだけのクロックを実現できたのです。
もしコントローラがスイッチを並べただけのデバイスだったら、本体までの長いケーブルを考えると高いクロックを供給できませんし、遅延や電圧降下の問題はプレイヤーに及んでいたことでしょう。
そうでなければカセットビジョンのように本体とコントローラをまとめるしかないのです。

最近ですと、例えば PS3 版と Xbox360 版のスト4とでは遅延が PS3 で大きいということは問題視されました。
さらに同じ PS3 であっても、発売直後と現在のハードウェアとではゲーム中に PS ボタンを押したときの快適さが大分異なります。
ゲームプラットフォームの世界ですと、ほんの1ms以下の違いがフレームをまたぐかまたがないかというところで体感可能な差に見えてしまうものなのです。
Rocksmith という実物ギターで遊ぶ音ゲーは、信号レベルの遅延を嫌って音声をアナログ出力することを推奨しています。

……というのはソフトウェアの話ばかりでなくハードウェアレベルでの応答性の話になってしまいましたが。
Xbox360 では kinnect といった入力システムを備え、ユーザーの体全体の動きをゲームに反映させることに成功しています。
PS2 では Eyetoy, PS3 では PSEye/Move といった入力システムもあります。
こうした入力デバイスはフィードバックの時間差の問題が関わりますから、 システムの消費する CPU 時間が大きくなってしまいがちです。そのためゲーム開発者からは支持を得難いという側面があります。
フィードバックはゲーミングの命であるからです。

かつて Windows CE を採用してしまった失敗ハードウェアというのが少数ながら存在します。 Gizmond, Dreamcast などです。
Pipin@ やマーティがどうだったかは知りませんが、池袋GIGOで料理の注文受付システムとして余生を過ごす Pipin@ を見た事があるので、きっと似たようなものだったのでしょう。
これまで見て来たように、リアルタイムシステムに求められるものは高速な割り込みアーキテクチャと、TCP/IP や USB のように CPU を浪費するコンポーネントが身の丈にあっていること(=コストがコントローラブルであること)です。
先進的な(CPUを食う)デバイスと、高速な処理は互いに矛盾する要求に見えますが——何も不可能を可能にしなければいけないわけではありません。
リアルタイムシステムは、アプリケーションに対して「〜この処理をするのに最悪xx秒かかるよ」ということを保証すればいいのです。
アプリケーションはそういうものだと思ってシステムを使用すればいいのですから。

そうしたものをざっくりオーバーヘッドと呼んでしまいましょう。
システムを利用するのにアプリケーションが犠牲にする実行時間のコストのことです。
WindowsCE を利用したゲーム機はこの高価なオーバーヘッドを支払う必要がありました。早い話が、遅い OS だったわけです。
幸い、 Dreamcast  は WindowsCE を使うか使わないかをゲームが選べました。なので本当に失敗したゲームはほんの僅かです。使ってしまったゲームはフレームレートや描画オブジェクトの数などに多大なペナルティを受けました。

誤解なきよう、 Linux や BSD, Windows など現存する OS の出来が悪いのではありません。
そうした OS は不出来なアプリケーションから他のプロセスやシステム自身を守るため特権モードを備え、アプリケーションが動作するユーザーモードとは異なる空間を保護しています。
ですので特権モードにスイッチするシステムコールで、オーバーヘッドが大きいのはどれも共通です。
重要なのはユーザー(アプリケーション)の要求に合っているかどうか、だけなのです。
だって今時、インターネットやLAN/Wi-Fi, Bluetooth, USB などはどのゲーム機でも対応必須じゃないですか。機能を削れないのなら仕方がないことです。

従ってゲーム機では時として、アプリケーションは OS の機能を OS を使わずに実現する、というようなことすら行います。
ゲームに限ったことではありませんけれど、ゲームでは特に重要度の高い OS の代替技術があるものです。例えばスレッドコンテキストスイッチングを減らす fiber, メモリの割当を自前で行う dlmalloc などはとても人気がありますね。

iPhone

最後に、失敗例ではありませんが、 iPhone についても言及しましょう。
iPhone はとてもゲーム機に似たシステムです。
個人的には iPhone のプログラミングなど真面目にやったことはないのですが、 WWDC で聞いた内容からして、ゲーム機そっくりのアーキテクチャです。少なくとも Android とは基本的な発想からして異なっています。
iPhone のスレッドスケジューラは Mach と同様 PC ライクでリアルタイム的ではないのですが、それ以外はとてもゲーム機に似ていると言えるでしょう。

iPhone3G 当時、システムのオーバーヘッドを軽くするためにマルチタスキングを廃し、60Hz のメインループを共有するアーキテクチャでした。
Jobs CEO は基調演説で、マルチタスクを行うとこうなってしまう、と WindowsCE の画面を見せました。
身の丈に合わないシステムは外すという思い切りはそんじょそこらのアーキテクトには到底真似できない決定でした。
iPhone はハードウェアを一本化して VM なしのネイティブコードですし、 Android とは正反対のアーキテクチャであります。
CoreAudio, CoreGraphics などの薄いレイヤを備えた応答性の高いシステム、 Cocoa はバグだらけの実装でしたが、まぁそれは未だに Android だってバグだらけです。

ともあれ、その実直なアーキテクチャが指に吸い付くような素敵なホーム画面(アイコン一覧)を提供してくれていたのです。
もっとも、 iPhone3G は CPU が遅い上、ネットワークもゴミ以下ときていたのでアイコンの一覧を華麗にスワイプする以外では何の意味もありませんでしたが……。
今僕が特に不満もなく Android を使えているのはあの頃の iPhone を触っていたからだと思います。
素晴らしいメニュー画面と劇遅のブラウザ、一週間遅れて届くメール、認証中に画面がブラックアウトする IMAP4……それらの対比が、いい感じの中庸を齎してくれた Android 端末の登場によって媒介されているのです。

ですがよい話ばかりではありません。
iPhone3G が日本で発売された直後、そのあまりにも遅い OSK (On Screen Keyboard) は問題になりました。
何やら色々あったと聞きますが——最終的に、ある方が泥を被って寝ないで修正したのだそうです。
悪い事に、 OSK が遅いとフィードバックが得られずに誤入力が増えるばかりか、他のアプリケーションをもブロッキングしてしまいます。
これは致命的でした。
それでも今尚 1GHz の snapdragon の Android と iPhone3G の改善版の OSK とを比べると(漢字変換精度はともかく)入力しやすさという点では圧倒的に iPhone のものが優れているとさえ思えます。

当時の iPhone3G を使っていた人なら、リアルタイムシステムの難しさというのを身に染みて体感できたと思います。