9キロバイトのコードで関数型言語を実装 - 自作言語revappの理由
これは言語実装のカレンダー | Advent Calendar 2023 - Qiitaの1日目の記事です。
このカレンダーを読んでいる皆さんなら、論文 「なぜ関数プログラミングは重要か」 に感銘を受けたりして、関数型言語を実装したいと思ったことがあるでしょう。 とはいえ、haskellやMLのような複雑な仕様を持つ言語では、 それに見合った複雑な実装が必要となって手に負えない、 と思った方も多いと思います。 しかし、LISPやforthのような単純な実装で済む処理系であれば、 一度は実装してみたことが、このカレンダーを読んでいる皆さんにはあるはずです。 私の自作言語revapp は、先の論文で挙げられた関数型言語の二つの主要機能である 高階関数と遅延評価を持ちながら、 静的リンクされた9キロバイトのLinux-i386実行ファイルで実装できます。 Unix系のOSをお使いであれば、終了コード0を返すだけの trueコマンド が用意されているかと思います。 あるいは、このカレンダー読んでいる皆さんであれば helloworldプログラムよりも簡単に実装できるでしょう。 そのtureコマンド、 Linux-amd64の場合は20キロバイトを越えるようです 。 それを下回るコードサイズで実装できるほどに、revapp言語は単純なのです。
関数適用の語順が逆のラムダ式
実装を単純にするため、計算モデルとしてラムダ計算をrevappは採用しています。 このモデルでは、変数定義と関数適用のたった二つの構文で、 高階関数が書けてしまいます。 ただし構文解析の実装を単純にするため、 一般に使われている「ラムダ式」の文法ではなく、 De Bruijn notation - Wikipedia に類似した文法を使います。 ラムダ式の構文のうち関数適用については、 結合規則が左結合優先になっていて、左再帰の形になっています。
S -> x (変数参照)
S -> λx.( S ) (変数定義)
S -> S ( S ) (関数適用)
実装の単純な構文解析手法として再帰下降構文解析が有名ですが、 この手法では左再帰の構文を扱えません。 この関数適用の語順がDe Bruijn notationではラムダ式の逆になっており、 左再帰ではなく右再帰になっています。
S -> x (変数参照)
S -> [x] S (変数定義)
S -> ( S ) S (関数適用)
さらに実装を単純にするためにrevappでは、 関数末尾を表現する構文を追加して、変数参照構文も右再帰にします。
S -> 0文字の文字列 (関数末尾)
S -> x S (変数への関数適用)
S -> =x S (変数定義)
S -> ( S ) S (関数への関数適用)
勿論、「0文字の文字列」なんて表記も検出もできないので、 この文法は構文解析できません。 しかし、この構文解析不能なソースコードの末尾に 閉じ括弧')'を一文字だけ加えたものは、 以下の文法で構文解析できます。
S -> ) (関数末尾)
S -> (S S (関数への関数適用)
S -> =x S (変数定義)
S -> x S (変数への関数適用)
ここで、関数末尾以外の全ての構文を右再帰の形にしたことが効いてきます。 インタプリタの中間表現としてよく使われる、 バイトコードの文法と比べてみましょう。
S -> "復帰を示す1byte" (サブルーチンから復帰)
S -> "命令1を示す1byte" operand S (仮想命令1)
S -> "命令2を示す1byte" operand S (仮想命令2)
...
どちらも、1byte目で処理内容を決定できる、右再帰の文法です。 revappソースコード(の末尾に閉じ括弧を足したもの)の構文解析の実装は、 バイトコードのそれと同じくらい単純なのです。 勿論、バイトコードが中間表現として用いられているのは、 構文解析が単純だからだけではありません。 メモリ上に並んでいるのと同じ順番で仮想命令を逐次処理する、 単純な方法での解釈実行ができるからです。 このバイトコードの利点をrevappで利用するため、 私の書いたrevappインタプリタ実装では、 ローカル環境を加えた仮想スタックマシンを用いています。 revappでは引数が関数本体よりも先に記述されるので、forth言語などと同様に、 スタックマシンを基にした仮想マシンでの解釈実行が自然でしょう。 勿論、バイトコードと違って命令末尾以外にも再帰箇所がある、 関数への関数適用構文の処理だけは単純ではなく、 引数として再帰的に記述されたrevappソースコードを構文解析する必要があります。 しかし、引数として記述される関数は遅延評価されるので、 解釈はしても実行までする必要はありません。 スタックに積むのがthunkである点を除いて、 変数への関数適用構文の場合と制御の流れは同じです。 結果として、既にお気付きかと思いますがこの仮想マシン、 先述のrevapp文法を直接解釈実行します。 仮想マシンなのに中間表現の仮想命令セットがないという怪しげな点が不安ですが、 ソースコードを中間表現へ変換するコードが省け、実装が単純になるのは確かです。
言語自身による言語機能の実装
さらに私の書いたインタプリタでは実装を単純にするために、 値呼び機構の実装を省いています。 ファイル操作などの入出力には必須だし、 いくらラムダ計算がチューリング完全とはいえ 整数演算はCPU組み込みの演算命令を使う方が圧倒的に効率的なので、 バイナリデータを扱うプリミティブ関数群なら実装しているのですが。 それらの引数として、バイナリデータではなくそれを生成するthunkを渡すと、 thunkを評価して値を求める代わりに、 このインタプリタは異常終了扱いで停止します。 なので、プリミティブ関数に渡すバイナリデータを生成するときは、 バイナリデータを関数に渡す
(=プリミティブ関数 バイナリデータ プリミティブ関数)
の形のrevappコードで表される、 バイナリデータをラップするthunkを代わりに生成します。 そして、
引数thunk プリミティブ関数
と書く代わりに語順を入れ替えて
プリミティブ関数 引数thunk
と書きます。 語順を入れ替えることにより、遅延評価なので、 関数の位置にある引数thunkがプリミティブ関数より先に評価され、 値呼びの場合と同じ評価順序になります。 とはいえ、語順を入れ替える表記は見た目に悪いし、 複数の引数を取るプリミティブ関数では
((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3
と括弧の入れ子が生じるので、関数にもラッパーを用意します。
(=引数thunk1 =引数thunk2 =引数thunk3
((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3
)=ラッパー関数
( 使い方 )=
引数thunk3 引数thunk2 引数thunk1 ラッパー関数
これらのラッパーは、機械語ではなくrevapp言語自身で実装できます。 なので、このインタプリタの実行ファイルには テキスト形式のままのrevappソースコードが組み込まれています。 例えば、条件が成立した場合と不成立の場合の両方の処理を引数とする関数として ブール値を定義することで、条件分岐構文に当たる機能を実装しています。
(=t =f t)=true
(=t =f f)=false
遅延評価なので、片方の引数を捨てるだけで、 捨てた方の処理の実行を避けることができます。 高階関数と遅延評価があれば、制御構文の実装は省けるのです。 ループ構文に当たるものは、 ラムダ計算に於ける不動点コンビネータをrevapp言語で定義した関数です。
数値や文字列のリテラル構文の実装も省いています。
(=done done)=[
(=done =head =isend (done head cons) isend)=,
(nil ,)=]
の三つの記号を名前とする関数を定義することにより、
[ 要素 , 要素 ]
のような形式のリスト表記が可能になります。 リストが表記できるなら、記述密度は6倍ほど悪くなりますが、 一文字を要素とするリスト構造として文字列リテラルを表記できます。
([ 'H' , 'e' , 'l' , 'l' , 'o' ])=Hello
数値リテラル機能は、数字を要素とするリストから数値を計算する関数で足ります。
(([ 1 , 0 , 0 ]) decimal)=100
文字自身の定義は厄介で、
...
('@' one plus)='A'
('A' one plus)='B'
('B' one plus)='C'
('C' one plus)='D'
...
のようなコードを私の代わりに生成するプログラムを用意するハメになりました。 遅延評価によるメモ化が効くので、 1の加算を繰り返す効率の悪い計算方法でも使い物になるようです。
バイナリハック
残念ながら当然それらだけでは、無駄だらけのOS添付trueコマンドならともかく、 手書きのtrueコマンドより実装サイズが小さくなることはありません。
int main(void)
{
return 0;
}
なので、くだんの9キロバイトバイナリについては、 アセンブラ中の.rodataセクションを.textセクションに書き換えたり、 ファイルヘッダを自前生成したりして、セクション領域の数を減らしています。 ヘッダや各セクション領域は開始位置がページサイズ単位で揃えられているので、 いくらコードサイズを減らしても、 ページサイズに合わせる分のパディングによって帳消しとなります。 このセクション統合ハックの効果を上げるため、 Tiny Forthインタープリタ と同様にベアメタルプログラミングに倣って、ライブラリの動的リンクを避けます。 メモリについては動的確保を行わず、 巨大な固定サイズのグローバル配列から切り出す方式を採っています。 ファイルなどの入出力は、OSのシステムコールを直接叩きます。 移植性は失いましたが、 このハックで4キロバイト以上ファイルサイズを削れました。
終わりに
jonesforth.s.txtより
Can you imagine writing C's 'if' in C? And that brings me to my third reason: If you can write 'if' in FORTH, then why restrict yourself to the usual if/while/for/switch constructs?
C言語のif構文をC言語で記述するなんて想像できるかい? ここから、私がforthを勧める理由の3番目が出て来るんだ。 もしforthでif構文を書けるのなら、 どうして、いつものif/while/for/switch構文に拘る必要があるんだい?
以上が、revapp言語の処理系を9キロバイトで実装できる主な理由だと私は考えます。 forthやLISPがしぶとく生き残っていて、新しい処理系まで現れるのは、 動作速度や強力な言語機能は勿論ですが、 実装のし易さが一番の原因だと私は思います。 そして、強力な言語機能、実装のし易さ、 この二点はこれらの言語では別々のものではなく 車の両輪のように分かち難いものです。 言語機能のうち、言語自身で記述できる部分が多いほど、 機械語で実装しなければならない部分が少なくなるからです。 機能の弱い言語では機械語で実装しなければならない部分でも、 強い言語であれば、その言語自身で記述できます。 逆に言えば、機械語で実装しなければならない部分こそ、 その言語で最も強力な機能と言えます。 forthに於いては、 機械語で書かれたルーチンと仮想命令で書かれたルーチンとを同一に扱う仕組み (threaded codeのヘッダに位置するcode field)。 LISPに於いては、特殊形式quote。 これが関数型言語についても当て嵌まると、revapp言語は示せたでしょうか? 高階関数と遅延評価の力は その機能を持つ言語自身の実装のし易さに繋げることができると。
外部関数呼び出し規約を考慮した累積レジスタ割り付け
この記事は 言語実装 Advent Calendar 2022 - Qiita の5日目のために書いた。
累積レジスタマシンで命令単位JITコンパイラの夢を見るで書いた去年の方法では、AOTコンパイラがJITコンパイラに伝達した情報は、
だけだった。
外部関数で破壊される物理レジスタをcN(clobbered register)(Nは適当につけたレジスタ番号)、保存されるレジスタをsN(saved register)、仮想累積レジスタをVN(Virtual register)(累積レジスタなら、Nは適当ではなく優先順位)とすると、以下の図1のように仮想レジスタに物理レジスタが割り付けられることになる。
図1
[V0][V1][V2][V3][V4][V5]...
[s0][s1][s2][c0][c1]
累積レジスタ割付では、仮想レジスタの優先順位が高いほど高性能の記憶装置が割り付けられるというのが、AOTコンパイラに対するJITコンパイラのお約束だ。 なので、外部関数呼出を跨ぐ場合はメモリに保存場所がコンパイルされてしまう物理破壊レジスタは優先順位のやや低い仮想レジスタに割り付けられ、優先順位最高の仮想レジスタには物理保存レジスタが割り付けられる。 一方、変数にレジスタを割り付けるアルゴリズムの多くは、なるべく多くの変数に物理レジスタを割り付けるため、寿命の短い変数に優先度の高い記憶装置を割り付けがちだ。 このため、外部関数呼出により寿命の制限される破壊変数の方が、保存変数より優先順位の高い仮想レジスタを割り付けられがちになる。 つまり、優先順位の高い累積レジスタには破壊変数と物理保存レジスタが割り付けられ、優先度の低い累積レジスタには保存変数と物理破壊レジスタが割り付けられる。 変数と物理レジスタで、破壊・保存のミスマッチが生じるのだ。
これの改善策が11月に見つかった。
まず、累積レジスタ列をふたつ、仮想破壊レジスタの列と仮想保存レジスタの列を用意する。 そして、それぞれの仮想破壊レジスタに変数を格納する度に、その変数より優先度が高くて同時に生存する変数を格納する仮想保存レジスタの、最大レジスタ番号を付記するのだ。 仮想保存レジスタ側にも同様に、仮想破壊レジスタについての情報を付記する。 そしてJITコンパイル時には、図2のように、仮想破壊レジスタ列(図2での[Sn])と仮想保存レジスタ列([Cn])とで向きを反転させ、物理レジスタの数だけ重複させて、物理レジスタと対応させる。
図2
...[S5][S4][S3][S2][S1][S0]
[s0][s2][s3]
[c1][c0]
[C0][C1][C2][C3][C4][C5]...
破壊専用・保存専用に累積レジスタ列が別々になっており、変数と物理レジスタとの間での破壊・保存のミスマッチはなくなる。 問題は、破壊・保存のどちらにも使い回せる、物理保存レジスタの割付だ。 ここで変数格納時に付記していた、他方のレジスタ列についての情報が役立つ。 それにより、優先度の高い値を格納している仮想破壊レジスタ・仮想保存レジスタの最大個数をJITコンパイラは決定できる。 例えば、ある仮想破壊レジスタに割り付ける記憶装置を考える時。 優先度の高い仮想破壊レジスタの数は、当該仮想破壊レジスタのレジスタ番号そのものだし。 仮想保存レジスタの方は、付記された最大レジスタ番号になる。 これら、当該仮想レジスタより優先度の高い仮想レジスタの数と、扱える物理レジスタの数とを比べれば、当該仮想レジスタに物理レジスタを割り付けるかメモリで済ますか、JITコンパイラは判断できる。
レジスタ割り付け - Wikipediaでは、各変数が別の変数と同時生存するか否かを表す二項関係を「干渉グラフ」と呼ぶ。 この干渉グラフは構築だけでも変数の数の二乗の計算量が掛かるので、線形の計算量しか掛けられないJITコンパイラでは扱えないが、処理時間の制限が緩いAOTコンパイラでは扱える。 変数に仮想レジスタを割り付けたあと、変数を仮想レジスタに置き換えて、同じ仮想レジスタを割り付けられた頂点を統合した干渉グラフも、AOTコンパイラで扱える。 なので原理上は、任意の変数や仮想レジスタについて、それより優先度が高くて同時生存し、破壊・保存の別が異なる変数・仮想レジスタの「集合」をAOTコンパイラは扱える。 なのに、その集合の最大レジスタ番号しかJITコンパイラに伝達しないのは、これもJITコンパイラの時間制限のためだ。
取り敢えずの概念実証コードをGitHub - abo-junghichi/crjitに上げた。 JITコンパイラまでの道程のスタート地点に過ぎないが、興味のある向きによる追試に役立てば良し。
深層学習での勾配逆伝搬を三値化してみた
深層学習といえば、その膨大な計算量を贖うためのGPUと、それを駆動するためのGPUプログラミングが必須と見られがちだが。
ニューラルネットワークの量子化についての最近の研究の進展と、その重要性 - SmartNews Engineering Blog
https://developer.smartnews.com/blog/2017/03/neural-network-quantization/
で述べられているように、各ニューロンのパラメータなどを浮動小数点数ではなく、表現範囲が1bit程度の整数で表すことで、GPUではなく通常のCPUプログラミングで深層学習が可能になる。
1bit程度の整数ならば
Linux Parallel Processing HOWTO: SIMD Within A Register(例えば MMX を利用)
http://linuxjf.osdn.jp/JFdocs/Parallel-Processing-HOWTO-4.html
のテクニックを使って、C言語での整数プログラミングの範囲内で多くのパラメータを一括処理できるからだ。
先述のBlogで述べられているように、学習済みのニューラルネットワークについては、出力やパラメータを1bit化しても十分に動作することがわかっているが。
その学習済みのニューラルネットワークを得るのは、1bit程度の整数で可能だろうか?
ニューラルネットワークに学習させる手法としては、当該ニューラルネットワークの出力の微分を計算して勾配を求める
バックプロパゲーション - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AF%E3%83%97%E3%83%AD%E3%83%91%E3%82%B2%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3
が典型であり、先述のBlogで紹介されている研究も、この手法を無理やり使っている。
どこが無理やりかというと、出力が1bit化されていて0と1しかなく連続な値をとれないので、本当は微分可能ではない点だ。
先述のBlogより
アクティベーションを二値化するのは、アクティベーションにステップ関数を適用してから次のレイヤーに入力することほぼ（=小さい側の値が0ではなく-1なのがステップ関数と少し違う）と同じですから、そういう非線形な関数を適用している、と数式上で真面目に考えてバックプロパゲーションの計算を行うと、ほとんどいたるところで勾配が0になってしまいます。
そこで、forward時はステップ関数（しつこいけどちょっと違う）なんだけど、backward時には(-1, -1)から(1, 1)の間を直線でつないだ関数を考えます。
これをStraight Through Estimator (STE)と言います。
なのでこれらの研究では、出力が0から1に切り替わる不連続点とその周囲を、0と1とを結ぶ直線に置き換えて近似している。
この近似により、勾配の値が実数の形で出てくるので、あとは通常の深層学習と同じ手法が使えるのだが。
勾配の値が実数≒浮動小数点数である、その通常の深層学習の手法ではGPUが必須なわけで、GPUプログラミングを避けたい自分としては美味しくない。
代わりに、学生の頃に物理を学んだ自分としては、不連続点での微分に
ディラックのデルタ関数 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%87%E3%82%A3%E3%83%A9%E3%83%83%E3%82%AF%E3%81%AE%E3%83%87%E3%83%AB%E3%82%BF%E9%96%A2%E6%95%B0
を使い、このデルタ関数の近似によって勾配を得る手法を使ってみた。
すると、近似方法を上手く選べば、得られた勾配分布は-∞,0,+∞の三値しか取らないことに気付いた。
デルタ関数の近似方法の一つとして、
正規分布 - Wikipedia
https://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83
の分散値を0に近づけた極限がある。
これを使って得られる勾配分布は、無限に大きくなる数を底とし不連続点からの距離の二乗を冪指数とする関数を、当該ニューロンが各シナプスから受け取った各入力の重み付き総和に適用したものになり。
底が無限に大きくなるため、不連続点からの距離に少しでも差がある勾配の比は、片方が0で無い限りは無限に大きくなる。
なので、この勾配分布に正規化を掛け、シナプスからの重み付き総和が不連続点に最も近いニューロンの勾配を適当な有限値にしようとすると、それ以外のニューロンの勾配は無限に大きい値で除算されて0になってしまうのだ。
おまけに、無限値に加減算・乗除算を掛けても無限値のままなので、乗除算が不要になる。
普通のCPUでも乗除算命令は加減算やビット演算より遅いし、FPGAや組み込み向けのような極小CPUに至っては乗除算命令が省かれているのが普通だ。
パラメータの更新などに欠かせない乱数には
メルセンヌ・ツイスタ - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E3%83%BB%E3%83%84%E3%82%A4%E3%82%B9%E3%82%BF
のようにビット演算だけで高品質なものがあるので、-∞,0,+∞の三値化と合わせれば、RISC-VのRV32I命令セットのような低コストの演算だけで、深層学習ができることになる。
機械学習でお馴染みの
MNISTデータベース
http://yann.lecun.com/exdb/mnist/
で試したところ、275回もデータベースを舐めさせたとはいえ、7層全結合ニューラルネットワークでも訓練用データの3/4を学習できている。
勾配伝搬に浮動小数点数を用いる通常のニューラルネットワークでも7層での学習は困難を伴うことを考えれば、-∞,0,+∞の勾配伝搬三値化は十分実用に耐えるはずだ。
この7層用と動作確認向けに4層のコードをGitHubに上げたので
https://github.com/abo-junghichi/ternary-backprop
興味のある向きはコードを覗いてみてほしい。
累積レジスタマシンで命令単位JITコンパイラの夢を見る
この記事は
言語実装のカレンダー | Advent Calendar 2021 - Qiita
https://qiita.com/advent-calendar/2021/lang_dev
の1日目のために書いた。
以前の投稿で紹介した「累積レジスタ割付による仮想マシンの高速化」。
https://abo-junghichi.hatenablog.jp/entry/2019/11/14/001142
興味深いのは、そこで使われるJITコンパイルが仮想命令単位ということ。
世の中には既に、実行時コンパイラ作成ツールが幾つかある。
SLJITやlightningやLibJIT、MIR、LLVM、PyPy…。
これらのJITツールは、最小のコンパイル単位が関数だ。
ということは、それより小さいな単位でのJIT手法が書きにくいということだ。
例えば、仮想マシンエミュレータとして有名なQEMUで使われるJIT手法では、分岐命令に達するまでのコードである「基本ブロック」までは一気にコンパイルするが、分岐命令以後のコードからは、先のJIT済み基本ブロックを走らせて分岐結果が得られるまで、コンパイルを後回しにする。
そして基本ブロック末尾の分岐命令は、最初はJITコンパイラの呼び出しだが、後続ブロックのJIT後は、その後続ブロックへの分岐命令に書き換えられる。
最近Ruby本家にmergeされたYJITも、QEMUと同様に基本ブロック末尾の書き換えをしている。
なのでこれらのJIT手法を用いるには、関数よりも小さな単位でコードをコンパイルしなければならない。
上記JITツールでも、末尾呼び関数で基本ブロックのエミュレーションはできるだろうが、分岐命令の書き換えについては、本来は分岐命令ひとつ書き換えれば済むところ、基本ブロック丸ごとJITし直すハメになる。
そもそもJITで一番辛いのは、異なる物理命令セット間での移植性がないことだ。
逆に言えば、仮想ISAによる移植性確保以上の機能は、JITツールには不要じゃないだろうか?
少なくとも、実行時コンパイル負荷の増加とのトレードオフにはなるはずで、ならば、コンパイル負荷低減の方向に思いっきり振った、仮想ISAを命令単位で機械語バイト列に変換するJITツールの意義はあるはず。
そんな累積レジスタ割付だが、ひとつ問題がある。
C言語の標準ライブラリ関数など、標準的なコンパイラで生成されたサブルーチンを呼び出すと、一部の物理レジスタの内容が書き換えられてしまうことだ。
関数呼び出しには
呼出規約 - Wikipedia
https://ja.wikipedia.org/wiki/%E5%91%BC%E5%87%BA%E8%A6%8F%E7%B4%84
という約束事がある。
関数を呼び出す側と呼び出された関数側の双方でこの約束事を守ることで、呼び出し側のプログラムと呼び出される関数を別々にコンパイルしたり、極端な話、別々の言語処理系でコンパイルしても、呼び出し側のプログラムでその関数を利用できる。
JITツールを作成する場合も呼出規約を利用することで、自分で機械語バイトを並べずに外部のコンパイラに仮想ISAの実装を丸投げできるし、ライブラリなどJITツール外のコードをJITコードから呼び出せる。
丸投げの例としては、
YETI: a graduallY Extensible Trace Interpreter
http://www.cs.toronto.edu/~matz/dissertation/matzDissertation-latex2html/matzDissertation-latex2html.html
で確立された、仮想命令のうちジャンプや分岐を伴わないものは全て外部関数呼び出しで済ませるcontext threadingがある。
というより、外部関数を扱えないというのは、言語処理系として致命的だ。
ファイル操作からウィンドウの描画まで、コンピュータの持つ機能のほぼ全ては、それらの機能をユーザーに直接触れさせない現代的なOSでは、ライブラリ関数として提供されているのだから。
その約束事の中に物理レジスタの使い方も含まれており、格納している値が関数呼び出し後に不定になる物理レジスタが定められている。
ここでは、外部関数呼び出しで値が不定になる物理レジスタを「破壊レジスタ」、値が保たれる物理レジスタを「保存レジスタ」と呼ぼう。
関数呼び出しを跨ぐ値には破壊レジスタを割り付けられないので、通常のAOTコンパイラでは、外部関数呼び出しを跨いで使用される値と跨がない値とを区別して、跨がない値には優先的に破壊レジスタを割り付ける。
ここで注意したいのは、保存レジスタならば、関数呼び出しを跨ぐ値と跨がない値のどちらにも割り付けできることだ。
破壊レジスタ・保存レジスタの数を知っている通常のAOTコンパイラであれば、破壊レジスタを使い尽くしたか保存レジスタが余るかどうかを考慮して、保存レジスタを破壊レジスタの用途に転用できる。
しかし、破壊・保存レジスタの数以前に物理レジスタの数を知ることが出来ない累積レジスタマシン用のAOTコンパイラでは、この転用の判断ができない。
これを改善する一つの方法が、破壊レジスタを割り付けられた仮想レジスタには保存用のメモリ領域も同時に割り付け、どちらの領域を使うかは仮想命令のJIT毎に、レジスタ番号と同時に指定することだ。
保存レジスタを割り付けられた仮想レジスタや、物理レジスタを割り付けられなかった仮想レジスタでは、破壊レジスタか保存用メモリ領域かの選択を無視する。
値が外部関数呼び出しを跨ぐかどうかまではAOTコンパイラで把握できるので、それをJITコンパイラに伝達する仕組みだ。
割り付けられている物理レジスタの種類に依らず仮想レジスタの使い方が揃っているので、AOTコンパイラ側では破壊・保存レジスタの数を気にする必要がなくなる。
逆に言えば、どの仮想レジスタに破壊レジスタの割り付けられているかをAOTコンパイラは分からず、破壊レジスタが空いているのに、関数呼び出しを跨がない値に保存レジスタを割り付けてしまう。
もっと良い方法があるかも知れない。
日本の高レベル放射性廃棄物最終処分地は、活断層の真上に選定されるのが理性的
先に北海道寿都町で応募の動きがある、高レベル放射性廃棄物の最終処分地選定。
調査だけなら、莫大な交付金を貰ってお終いという、おいしい話だが。
選定されれば当然、安全なレベルに落ち着くのに何万年もかかる放射性物質を郷里に埋めることになる。
そんな恐るべき調査への応募の動きが、北海道神恵内村でもあるようだ。
一見すると危険な賭けのようにも見えるが、最終処分地決定までは進まない理由が、神恵内村にはある。
経済産業省資源エネルギー庁の公表した「科学的特性マップ」では、村域の大半を覆う「好ましくない特性が推定される地域」が、円を描いているからだ。
不適性地域が円を描いているのは、その中心に火山があることを意味している。
富士山の宝永火口のように、火山の火口の位置は移動することがあるので、円の境界の外側と内側で、安全性が極端に異なるわけではない。
村南部の一部のみが辛うじて不適性地域の範囲からはみ出ているが、大した意味はない。
将来、地元合意の原則を国が捨てて最終処分地選定を行っても、神恵内村が選ばれることは狂気の沙汰だろう。
よって、神恵内村の調査への応募は、賭けにもならない当然の結果だ。
神恵内村商工会、頭良い。
むしろ、先に動きのあった寿都町の方が、適性地域を抱える分だけ、神恵内村と異なり最終処分地の当たる危険な賭けだ。
最後に、神恵内村のように不適性地域で占められ、最終処分地になる危険を冒さず安全に交付金をゲットできる自治体は、中央構造線断層体上にある伊方町など、他にもある。
暫くは、最終処分地への応募はこれら不適性な自治体で占められ、徐々に、ギリギリ微妙な自治体へ調査が広がるのだろう。
最終処分地に最適な自治体は、最後まで応募しない。
もし、応募した自治体に処分地を限定したら、エネルギー庁側が短気であるほど、最終処分地は不適性な危険地域に選定され易くなるわけだ。
日本の原発依存度、つまり核のごみの生成速度を考えると、エネルギー庁側に残された時間は多くない。
地元合意を前提に考えると、日本の高レベル放射性廃棄物最終処分地は、活断層の真上とか火山付近とか、狂気の沙汰になるのが理性的なのだ。
IPCが2命令多ければ、RISC系CPUの周波数当たり性能はx86のと並ぶ
CPUに使われる一般的な命令セットと言えばx86だが、最近は怪しくなっている。
【後藤弘茂のWeekly海外ニュース】AppleがArmベースのSoCをMacに採用する背景 - PC Watch
https://pc.watch.impress.co.jp/docs/column/kaigai/1261696.html
それらのCPUの性能を、既存のCPUと比較したいこともあるだろう。
勿論、簡単ではない。
同じ命令のCPU同士ですら、キャッシュ容量とか各命令のレイテンシとか動作周波数の変化とかの所為で、性能は大きく変わる。
走らせるプログラムが変われば、性能差が逆転する事も珍しいことではない。
それを承知で敢えて注目すべき性能指標を挙げるとすれば、IPC(Instructions Per Cycle 動作周波数あたりの命令実行数)の最大値だろう。
他の指標のほとんどは、半導体プロセスを変えるとか小規模の手直しなどで、割と頻繁に変わるが、CPUコアの大規模な設計変更でもない限り、最大IPCはなかなか変わらない。
しかし命令セットが異なると、IPCの意味が変わってくる。
ある命令セットで2命令を要する処理が、別の命令セットでは1命令で済む場合が出てくるからだ。
同じ処理をするときに多くの命令を要する命令セットと、少ない数で済む命令セットでは、前者の方がより大きなIPCを持たなければ、後者と同等の周波数当たり性能を出せない。
件のAppleのCPUはARMの64ビット命令セットだが、ほぼ典型的なRISC命令セットらしい。
典型的なRISC命令セットでは、レジスタ間演算とメモリアクセスを同時に行う命令は、存在しない。
これに対してx86の基本命令では、演算処理とメモリアクセスを一つの命令に纏めることができる。
演算処理だけならば、RISCもx86も似たような数の命令数で処理できるが、メモリアクセスが絡むと、その回数だけRISCの方が命令数が多くなる。
ところが、動作周波数1サイクル当たりで考えると、x86命令の強力なメモリアクセス表現力は過剰になる。
現在最も強力なx86のCPUですら、1サイクル当たりに処理できるメモリアクセスは2回が限度だからだ。
このため、メモリアクセス処理能力の限界により、x86のCPUのサイクル当たり処理能力は、サイクル当たり命令実行数が2命令多いRISCと同等になる。
例えば、最近のx86のCPUではIPCは4、つまり1サイクルでx86命令を4個処理できる。
演算は4命令分できるわけだ。
ところがメモリアクセスは2命令分しか処理できない。
このため、その4命令すべてにメモリアクセスが伴っている場合、2命令分のメモリアクセスは次のCPUサイクルに繰り越されてしまう。
サイクル当たりにできる処理は、RISC命令での演算4命令とメモリアクセス2命令の6命令分が限界なのだ。
x86のCPUの構造解析で有名なAgner Fog氏によると、IntelのCPUのIPCは4命令/サイクルが最大らしい。
The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers
https://www.agner.org/optimize/microarchitecture.pdf
対してAppleのCPUの最大IPCは7。
IntelよりもIPCが2ではなく3多いということは、周波数当たり処理能力では同等ではなく上回っていることになる。
動作周波数ではIntelに大差をつけられているので、動作周波数と周波数当たり処理能力の積であるAppleのCPUの性能は、現時点ではIntelより低い。
しかし、動作周波数の引き上げはIPCほどは難しくないはず。
電力消費を気にしないデスクトップ向けにAppleがCPUを出したとき、何が起こるだろう?
新型コロナでの突然の重症化の一部には予兆がある
コロナ｢突然重症化した人｣の驚くべき共通点 | The New York Times | 東洋経済オンライン | 経済ニュースの新基準
https://toyokeizai.net/articles/-/346423
によると、新型コロナで突然重症化する仕組みの一つが、自覚症状がないまま進行する肺炎らしい。
この仕組みの場合だと、自分では気付き辛いから重症化が突然発覚するだけで、肺炎の進行自体はもっとゆっくりしている。
だから、肺炎の進行度合いを調べれば予兆がわかる。
上の記事で紹介されている、「パルスオキシメーター」ってものを使う方法は、体温計やマスク並に手遅れのようだ。
血液中の酸素濃度測定機器「一般家庭の購入控えて」新型コロナ | NHKニュース
http://www3.nhk.or.jp/news/html/20200502/k10012414901000.html
しかし、呼吸数の多さなら、時計さえあれば自分で計って自覚できる。
呼吸の変化を自覚できない人が目立つ点は、逆に光明かもしれない。
恐らく、一見しただけでは植物の成長が分からないの同様に、変化がゆっくり過ぎるからで、肺炎の進行も同様にゆっくりしているはずで光明だ。
元気なうちに、呼吸数など正常な呼吸状態を覚えておきたい。
残念ながら、サイトカインストームとか、突然の重症化の仕組みは他にもあるかもしれない。
緊急性の高い13の症状 厚労省がリスト公表
http://www3.nhk.or.jp/news/special/coronavirus/consultation/
確実を期すなら厚労省の方がいい。
緊急には違いないけど新型コロナとは関係ないものが混じっていそうだし。
「いつもと違う、様子がおかしい」って、コロナだろうがなかろうが関係なく緊急だろう。
