末尾再帰の話続きです。
(コンパイラに最適化ができるという他に)何がうれしいのか、むしろプログラマからみるとかっこ悪いだけじゃないのか。と思って、Web上のリソースをいろいろあさってみました。末尾再帰に関する、Web上の日本語の資料でたぶんもっとも有名なもののひとつ、「なんでも再帰」を読んでみました。
「なんでも再帰」ではまず軽く末尾再帰の例が出てから、相互末尾再帰の例がでてきます。そしてだんだん複雑な例になっていきます。
なるほど状態遷移に使える、つまりStateパタンのように使えるのか。
...あれ、「天啓が降りてきた!」くらいにおもったのに、かいてみるとなんてことないな。
でも、わたしにとっては、「あ、Stateパタン」と思った瞬間に、関数がfirst-class objectであることと、末尾再帰の概念がセットになってすとんと腑に落ちたのでした。継続がいまだに腑に落ちないんですが、近々わたしの中ではこれもセットになりそうな予感。
末尾再帰って言葉をはじめてきいたのがいつだったかよく覚えていませんが、最初の印象は「理解できるけどあたまにはいらない」でした。
今日なんとなく気が向いて、末尾再帰についてあらためて確認してみました。
まず何も考えずに、数字のリストの内容を素朴に足すsum1を定義してみます。
gosh>(define (sum1 lst) (cond ((null? lst) 0) (else (+ (car lst) (sum1 (cdr lst)))))) sum1 gosh>(sum1 '(1 2 3 4 5 6 7 8 9 10)) 55 gosh>
これがわたしの思う、素直な再帰です。で、末尾再帰にはなっていません。再帰的に呼ばれたsum1の値は、一個上のレベルで(car lst)と加算されるからです。
では、これを末尾再帰にするとどうなるでしょう。
gosh>(define (sum2 lst) (sum2-loop lst 0)) sum2 gosh> (define (sum2-loop lst n) (cond ((null? lst) n) (else (sum2-int (cdr lst) (+ n (car lst)))))) sum2-loop gosh> (sum2 '(1 2 3 4 5 6 7 8 9 10)) 55
sum2自体は、末尾再帰になっているsum2-loopを呼び出すだけです。sum2-loopでは末尾再帰にするために、ワークエリアになる引数「n」を用意しました
再帰で呼ばれるたびに、第２引数に値が足されていきます。最終的にリストが空になったら、その第2引数をそのままかえす。
...久しぶりに末尾再帰の概念を確認してみました。やっぱりこれ、ループの表現変えただけじゃん。戻り値を保持するための引数ってかっこわるいじゃん。ループと等価だからループに最適化できる、って見るからにあたりまえじゃん(最適化の実装はあたりまえ、じゃないだろうけど)。再帰な問題を再帰でかく喜びというか驚きがかんじられないじゃん。
と、あらためて思いました。
しかし、わたしは間違っていた、末尾再帰(的なモデルの意義)の神髄の片鱗を、きょうはじめて実感できたかも! と思ったのでした。
以下次号。
このブログ(別館)はじめてから3年です。思い出したようにしか更新していませんでしたが、今年からこころを入れ替えました。
唐突にはじめたVirtualMachine本のひとり読書会もそれなりに進んでいます。このあたりで自分むけメモとして、今年の「勉強」の方針を書いておきます。
このブログをはじめる前から数えると10年以上、長らく迷走していましたが、昨年末に簡単な原則に辿り着きました。
この半年くらいでやるつもりのこと・やりたいことは以下の通り。
ここに書いている以外のことは、iPhone楽しそうだし、Haskellも面白そうなんだけど、(原則として)短期的にはやらない。時間は限られているからね。
ソースコード読みをしていて思ったこと
情けないなあー
久々に、まじめにコード読もうと思って、etagsを使おうとして、こんなに面倒だったっけ? と思い、GNU globalをいれてみることにしました。
emacsの設定でやったこと:
gtags.elをemacsのロードパスが通ったところにいれる
emacs.elに次のことをかく
;; gtsgs (load "gtags") (define-key gtags-mode-map [?\C-\M-.] 'gtags-find-tag-other-window) (define-key gtags-mode-map "\M-r" 'gtags-find-rtag) (add-hook 'c-mode-hook '(lambda () (gtags-mode 1) (gtags-make-complete-list) ))
まず、読みたいソースのてっぺんでgtags -vする。
(これでgtagsが使うファイルが作られる)
それから、emacsで何かソースファイルを開く。
関数名のところでM-.すると、定義されてる場所をみつけてくれる。
M-rすると、参照元をみつけてくれる。
Virtual Machines: Versatile Platforms For Systems And Processes
VM本第三章やっと読み終わりました。ProcessVMについてです。
いろいろなVMがあるけど、ここではProcess or Program VMについて語られます。「仮想ABI」です。たとえばIA-32/WindowsのアプリケーションをItaniumのWindows上で動作させるものです。
Process VMのよくある構成について、主なブロック。
ネイティブなプラットフォームとVM環境の互換性について。
"intrinsic compatibility"と"extrinsic compatibility"がある。
intrinsic compatibilityは"complete transparency"ともいわれる。多くの場合は完全な透過性はオーバースペック。
extrinsic compatibilityは、何らかの条件がつく。たとえば、特定のアプリケーションは動作するよ、とcertifyするなど。
intrinsicだろうがextrinsicだろうが、互換性があることを証明するのは大変むつかしい。その話をするためのフレームワークとして、まずはVMを構成要素に分解する。そして、各構成要素について(1)native環境とのステートマップ(2)ステート間遷移のマップをおこなう。このステートは、user-managedとOS-managedに分けることができる。
user-managedなステートマップはそんなに難しくない。guestのレジスタがhostのメモリにマップされるなどの場合があるが。OS-managed stateは、考え方が同じだがもうちょっと複雑。
user codeからOSへ制御がうつるポイントがキー。このマップがつくれれば、そのポイントでの状態が同等かどうかに集中できる。
制御ポイントが明確になると、次のことがいえる:
ここまでをふまえた議論。
ISAの実装が、機能の差として顕れるケースがある。
たとえば、コードセグメントへの書き込みが、コードキャッシュにすぐ反映されない。
このような実装差が問題になるのは、たとえば、CPUの種別判定に使われる時。
逆に、仕様上は「コードキャッシュに反映されない」となっていても、実在の実装がすべてコードキャッシュに反映させているケースもある。そうすると、仕様に従って実装されたVMでは、現実のコード(自己変更含むもの)がうごかないかもしれない。「仕様に従っている」はいいわけにならない。
guest → targetの状態マップ。状態とはレジスタとメモリのことで、要はリソースなので、リソースマップと呼ぶこともある。
ここでのメモリは、論理メモリで実メモリスペースの話じゃない。
レジスタマッピングはstraightforward(ってなんて訳すのがよいかな)。target側に充分なレジスタ数があれば、全部マップすればよいし、ダメならメモリにマップしたり、ダイナミックにマップを変更したりする。
メモリ空間のエミュレーションは、いろんなやり方がある。ソフトウェアの役割が大きいやりかたほど遅くなり、ハードウェアに任せる部分が多いほどパフォーマンスがよくなる。
一番フレキシブル。ランタイムソフトウェアがメモリ管理。
でもバイナリトランレート環境ではかなり遅い。最後の手段。
単純なマッピング。同一アドレスか、単にオフセットを与えるかだけ。
メモリマッピングとアドレス変換に何を使うか、はパフォーマンス・互換性の要求と深い関係がある。
メモリサイズや、ランタイムがアドレス空間を共用するか、など。
extrinsic compatibilityでよい場合も多い。
メモリアーキテクチャのエミュレーションで、考慮しなきゃいけないのは:
メモリプロテクションは、もし変換テーブルが用意されていれば簡単。しかし直接またはオフセットアドレッシングだとそうはいかない。ホストのメモリプロテクション機能に頼ることもできるが、ページサイズがホスト・ゲストで異なるとか、実行中にメモリの権限が変更されることもある。
自己参照はオリジナルの参照をしているからOK。自己書き換えについて、基本的なやりかたはRead onlyにしておくこと。例外のハンドリングで自己書き換えを扱うことができる。
psude-self-modifingという概念がある。code pageのなかに、実際にデータが混じっているもの。デバイスドライバや組み込みのコードに見られる。psude-self-modifing codeについては、「頻繁にwrite exceptionがおきるとき、それがpsude-self-modifingかどうかチェックして、その場合はwrite protectionをはずす」という手がある。
ページ単位ではなく、もっと細かいwrite protectionをソースのコードに用意する。ページ毎にbit mask
ほんとうにSelf-modifing codeがある場合(code regionにデータがあるのではなく、実際にcodeがかきかわる場合)は、idiom recognitionでself modifyじゃないコードに書き換える。
Omniware VMという例では、２の累乗サイズのページごとにアクセス権を設定。それにより、アドレスのシフト演算で権限チェックが簡単にできる。
ランタイム実行中と、エミュレーション中で権限を切り替えるやりかたがある(エミュレーション中はランタイムのアドレスにはアクセスできない、そしてCode Cacheは実行可能。ランタイム実行中は、Code Cacheは読み書き可能、など)。
レジスタがメモリ上にマップされているときの問題もある。
(続く)
昔々、FORTHという言語が好きでした。
なんでもスタックベースで、あたまの中で容易に実行モデルがつくれるのがきもちよかったのだと思われます。
FORTH(Forthって書くんだっけ）も生き残っていますが、派生した言語もいくつかあります。その中でも比較的最近で、なんだかリッチそうな言語Factorについて、ちょっと調べはじめました。
まず、Factorは「concatenative language」だと名乗っています。そりゃなんだ? Concatenative.orgというところに説明があったので読んでみました。
concatenativeとstack言語は違うの? → 似ているけど、違うクラスの言語。しかしほぼ同じと考えて良い、とのこと。しかしそういわれると違いがなんなのか気になるなあ。stack以外でも理論的には構成できる、ってとこかな?
VM本読書記録がいくら自分用メモとはいえ、粒度がむちゃくちゃで読みにくいので、いったんVM本の全体構成をおさらいしてみましょう。(そういうことは先にやれ＞おれ)
現時点(2009.2.4)では、Chapter 3の途中です。読み進むにつれ、このエントリはかきかえていきます。
タイトル通り、仮想マシンへのイントロダクション。コンピュータのアーキテクチャ、「仮想」とはなんであるか、仮想マシンのいろいろ、そして本書の構成について。
命令セットのエミュレーション全般。直観的なインタープリットから始まり、threaded, predecode, binary translationなどの方式や、命令セットのエミュレーションにおけるさまざまな問題について概観します。
プロセスVMを構成するはなし。まずは全体の構成からはじまります。それから互換性・状態のマッピング・エミュレーションいろいろ(メモリアーキテクチャ・命令・例外・OS)・コードキャッシュの管理・そしてシステム環境への埋め込み。FX!32の実例をとりあげてから、まとめです。
ダイナミックバイナリ最適化の話。ここでは主に複数のbasic blockをまたがる最適化について。
まずは最適化の前提としてプロファイルで「どこがよく実行されているのか」を知る。そしてsuperblockをはじめとするブロック最適化。それをベースにした最適化フレームワーク。フレームワークの上でのテクニックとしてのコード再配置。そしてコードの最適化いろいろ(余分なブランチ削除、定数展開、コピー展開等々)。さらに、同一ISAでの最適化についての話題。
以下、じわじわ更新していきます。
実マシンの復習。
Virtual Machines: Versatile Platforms For Systems And Processes
Virtual Machines: Versatile Platforms For Systems And Processes
やっとダイナミックなバイナリトランスレートの話がでてきましたよ。
(2009.2.9 Chapter毎に整理しました)
Source ISAとTarget ISAが異なるときの話。しかし、そうじゃない場合にもこのテクニックは使える。binary optimizationとか、特権命令実行時のemulation的動作とか。
普通のエミュレーション。メインループがあって、デコード・命令ディスパッチを実行。ブランチが多すぎて遅い。
この章で突然「FORTHは"threaded code" interpretation modelで有名」と出てきて驚く。FORTHは昔だいぶ遊んだけど、それ知らないぞ(と思ったのですが、threaded codeのところを読んだら納得できました)
各Instruction emulationの最後に、decodeして対応するインストラクションを実行する。テーブルをひき、そこへ飛ぶコードを追加する。メインループはもういらない。これは、デコード結果からテーブルをひいてジャンプ、なので "indirect" threaded interpretationと呼ばれる。
ループは消えたけど、毎回デコードのオーバーヘッドがある。
そこでプレデコード。デコードして扱いやすい形で再度格納。
デコード結果の「オペランド」のところに、そのオペランドを実行するアドレスを直接いれる。メモリルックアップが1回減らせる。
ここまではPowerPCを例にしていたが、IA32みたいなCISCでは大変。
IA32だと、General Decodeしてから、特殊な処理に分岐するのが基本的な動き。
RISCに比べてdecode処理が複雑ででかい。各instruction interpreterの最後にdecode処理を書いていたら、インタプリタがでかくなる。
ということで、一般的なケースに特化したdecode-and-dispatchルーチンをいれる。特殊なケースはブランチしてとばす。
Direct Threaded Interpretationをやろうとするといろいろ問題。とくに2つ:
また、2段階のdecode-dispatchになる。これもbinary translationと非常に似ている。 binary translationはポータビリティに欠ける、が、retargetable binary translatorが開発されている (p46)
FX!32をベースにした例。オリジナルのAlphaじゃなくて、PowerPCのアセンブラで記述されているが、PowerPCをよく知らないのでほとんど理解できない。IA32の1インストラクションをAlphaの30インストラクション相当で実行できるらしい。
2.4まではインタプリタだけど、target ISAのバイナリコードに変換するとパフォーマンスがあがる。
インタプリタと違って、source ISA状態のマッピングをtarget ISAのレジスタに直接おくことで、コンテクストブロックをメモリから読み込むオーバーヘッドを削除できる。
スタティックにプレデコードしたりバイナリトランスレートしたりすることを考えてみる。(特にCISCなISAでは)これはかならずしも簡単じゃない(それどころか不可能な場合もある)。命令境界がどこかわからないし、生成されたコードのなかにデータとかパディングがはいっていることだってある。
RISCであれば、1命令1ワードだったりするが、たとえばIA32だと、任意のバイトが本当に命令境界なのか判断する方法はない。
間接ジャンプだと、ターゲット側に展開された命令列のどこに飛べばいいかわからない(ただしRISCやJavaVMではこういう問題は起こらない)
2.6節のハイライト! (ってそんなに気合いをいれるほどのことはない)。プレデコードとトランスレーションはきわめて似たプロセスなので、この本では「トランスレーション」と呼びます。
Emulation Manager、インタプリタとトランスレータ、トランスレートされたコード(のキャッシュ)、そしてソースPCからターゲットPCへのマッピングを示すハッシュテーブルをそろえれば、ダイナミックにインクリメンタルなトランスレートができます。
Emulation Managerは、マップを使ってコードキャッシュを探し、ヒットすればトランスレートされたブロックを呼びます。ヒットしなければ、インタプリタ・トランスレータを呼んで、次のブロックをインタープリト・トランスレートし、マップにトランスレートされた結果をいれます。
このときの、トランスレートの単位は「Dynamic Basic Blocks」。ブランチで入ってきたポイントから、ブランチで出るポイントまでを(動的に)認識したものです(これにたいして、Static Basic Blocksは、静的構造を解析してエントリポイント・エグジットポイントで切ったもの)。
Dynamic Basic Blocksの特徴として「他の大きなブロックの一部が、新たに小さなブロックになることがある」です。これは、大きなブロックの途中に、エントリポイントがある場合などですね。(p57の図がわかりやすい) このダブりがあることで、すでにトランスレートされたコードの途中にブランチしたら、みたいな複雑な処理がいらなくなっています
こんどは、ブロックごとに「キャッシュを探す」「Emulation Managerに戻る」オーバーヘッドをへらすことが考えられます。キャッシュを探す、については、SourceのPCをTargetのレジスタにいれとくとか、コードブロックの最後に次のSource PCを置いておき、そこをlink register経由でアクセスする方法とかがあります。
他にも問題がいろいろ。これらはChapter3や4で扱われます。
同じISAでもEmulationがありうる。Emulation Managerが常にコントロールをもち、かつモニタ(= code management)できる。この一例が"simulation"。2.9でcase studyとして扱われる。
2つめの例は、ISAが同じだがOSが異なる場合。このときはsystem callをemulationする。
3つめの例は、特権命令を扱うエミュレーション(Chapter 8)。
4つめは、Chapter10であつかう"program shepherding"。セキュリティ的監視。
さいごが、ランタイムでのbinary optimization。
Chapter 3に突入したけど、ここでの復習が追いつかない!2.6までの「シンプルな」トランスレート方法では、Source PC/Target PCのルックアップや、ブロックごとにEmulation Managerへコントロールが戻ることがどうしても起きる。このオーバーヘッドを減らす方法いろいろ。
インタプリンタのスレッディングと同じようなテクニック(名前から見当つくよね)。トランスレートされたブロックをチェーンするのだ。
次のブロックがまだトランスレートされていない場合は、通常のスタブコードが入る。
ソフトウェア分岐予測! これは本質的には「inline caching」の実装である。分岐先のコードを、出現しそうな順に、ifのなかで即値で埋め込んでおくのです。
なので、profilingとセットでやる必要がある。
sourceのstackへ戻り値を格納すると同時に、target側でEmulation Managerが管理する"shadow stack"にtargetの戻り先PCを格納する。stackからpopするときは値のチェックをしてconsistencyをみる。
VM本2章の終わりのほうです。
インストラクションセットエミュレーションについて、まだまだいろいろあるけどそのうちの一部を扱います。
レジスタはストレージヒエラルキのてっぺんにいるので、パフォーマンスに影響がでかい。
レジスタ割り当ての戦略についてbinary translation, interpreterのそれぞれで、一般論を。
フラグの類について。sourceとtargetでISAが違えば、同じではない。MIPSみたいにcondition codeがないようなものもある。
source instructionの実行のたびにcondition codeを更新する手もあるが、これは遅いし、通常必要でもない。lazy evaluationがよく使われるテクニック。condition codeに影響がある、最近実行された命令とそのオペランドを記録しておき、必要になったらcondition codeを生成する。
この方法でも、実行中にtrapが発生した場合に問題がある。trap発生したら、preciseなソース状態を作らなくてはならない。このへんはあと(4.5.2)で議論する。
浮動小数点のフォーマットはかなり統一されているが、たとえばIA32では80bitの中間結果がつかわれるが、ほかの多くのISAでは64bitみたいな差がある。
ほかにもいろいろ。PowerPCでは連続した乗算・加算のインストラクションがあるが、これはエミュレートできない場合がある(途中でオーバーフローしちゃうとか)。アドレッシングモードが違うとか、即値の長さが違うとか。
sourceとTargetでアクセスできるメモリの単位が違う。たとえばbyte単位でのメモリアクセスができないISAもある。
メモリのアラインメントもISAで違う。いろんなやりかたがあるけど、プロファイルをとるような方法もある。Chapter4で議論する。
BigEndian, LittleEndianなISAがある。
両方サポートしているＩＳＡもある。
サイズが違う、特権レベルが違うなどいろいろ。
"Shade"という、high-performanceなsimulationのケーススタディ。
"simulation"は、「内部動作までのシミュレート」を意味する。emulationは表面の動作のみ。
あまり細かいことはかいていないが、code cacheのメカニズムがシンプル。source PCからhash経由で、translated codeの場所がひかれる。hashのさすさきには、n個の"source/target"ペアがはいってる。新しく使われたのが、せんとうにくる。もしいっぱいになれば、n個目が押し出される。そういうわけで、translateされたけど、danglingになるtranslated codeがある(本文中では"orphan"って表現されてる)。
code cacheはあたまからつめられていく。もし最後に到達したら、単純にすべてフラッシュされる。そういうわけで、danglingなコードはそのうち消える。
このメカニズムはシンプルだけど、効率ほんとにいいのか? と疑問に思うが、いいんだろうな、確かめるためには論文にあたればよさそう。
2章のまとめ。つぎのものたちが出てきています。
