a21_memo01 のバックアップ(No.44)

a21に関する雑記#1

(by K, 2021.01.26)

↑

2021.01.25(月)

今日はa21_txt01_3のTL-3を書きました。我ながらシンプルにわかりやすく書けた気がします。
ラベル名をうまく使って、分岐先のpc値を高速に求められるようにしたので、結構高速に動いてくれそうな気がします。
でもなあ、goto命令だからなあ。やっぱり嫌がられてしまうかなあ・・・。

↑

2021.01.26(火)

うーん、この先の拡張を考えると、トークンコードの処理は別の関数に切り出しておくほうがよさそうだなあ・・・。じゃあさかのぼってTL-2から修正するかな。
TL-4で高速化して、TL-5で「式」を扱えるようにして、TL-6で型を導入したらいいかなあ・・・。

↑

2021.01.27(水)

TL-4での高速化はやっぱりやめます。それはTL-5でやることにします。
TL-4でやるべきは「REPLの導入」だと思いなおしました。・・・TLシリーズはせっかくのスクリプト言語（インタプリタ）なので、そのメリットを生かさないともったいないです。だからREPLの導入はぜひやるべきだと確信しました！
その後の予定としては、TL-5で少し高速化して、TL-6でもっと高速化して、TL-7でwihleループやブロックifなどを導入して、TL-8かそれ以降でグラフィック命令を導入します。
そのあたりまでできたら、次はTJシリーズに移行して、JITコンパイラかな・・・。

TL-4ができました。REPLできるのはすごく楽しいです。これがたった7.5KBのアプリで実現できるなんて！ →a21_txt01

↑

2021.01.28(木)

TLシリーズでどこまでやるかで少し悩んでいます。たぶんやりすぎないほうがいいんです。道半ばにしておいて、「自分だったらこうするのに」をいくつか残しておくほうが、その後の開発にチャレンジする人が増えると思うのです。
ということで型も浮動小数点演算も配列も構造体も関数もローカル変数も全部見送ろうかなと思っているのですが、どうかなあ。
具体的な改造コードを提示しないまでも、こうすればできそうだよね？くらいの話は書くかなあ。

[memo]あとでどこか別のところにまとめるつもりだけど、インタプリタ言語のメリット：
- [1] 実行ファイルがいらない。ソースコードだけあればよい。あとで、実行ファイルだけになって、「ソースは失われてしまった」みたいな事故が起きない。
- [2] インタプリタ言語のソースコードは（たいてい）機種依存しないので、移植しなくていい。将来新しいCPUとかOSが出ても無修正で対応できる。
- [3] JITコンパイラとかであれば、それぞれの環境に応じた実行コードを生成して実行してくれる（可能性がある）。
- [4] インタプリタはREPLができる。
対応するデメリット：
- [1] ソースがあっても処理系がないと動かない（どのバージョンで動かすかわからなくなったとか）。

現在手元で開発中のTL-6ですが、どうせやるならJITコンパイルしない範囲での最速を目指してやろうということで、ちょっと頑張ってみました。結果はgcc比で13.7倍。我ながら、これはなかなかいいんじゃないかなと思いました。
- その後さらに頑張って、11.3倍まで速くできました。

↑

2021.02.02(火)

現在、TL-7で、演算子をどこまでサポートするかで悩んでいます。
たくさんサポートすると、それだけでプログラムはかなり長くなってしまいます。
でも少なすぎると、おんぼろすぎて、TL-7が魅力的には見えなくなってしまいます。

↑

2021.02.05(金)

プログラムで変数に対する説明が省略されすぎじゃないかと言われて、その通りだと思ったので少しずつ直していきます！

↑

2021.02.06(土)

今になって、lexer()とgetTc()を統合すればもっとすっきりと書けるということに気づきました。
それで、どういう話の流れにしたら最小の手間で自然にその結論に到達できるかを悩み中です。

↑

2021.02.15(月)

私はTL-7でどうにかしてスタックマシンを構成しないで、式の評価をやりたいです。しかもできるだけ自然な感じで。・・・アイデアはあるんです。きっとできると思っています。

↑

2021.02.16(火)

TL-7が手元ではできた！・・・454行で、9.50KB。これはかなりコンパクトだと自分では思います。それでいて、ちゃんと優先順位を反映して計算できています。やったね！

↑

2021.02.17(水)

プログラムを差分で書いて説明しているけど、差分ではなく全部が欲しいという人もいるだろうなあ・・・。TL-1から全部をまとめてzipとかでダウンロードできるようにしたらいいのかなあ。

↑

2021.02.18(木)

現在、手元では開発中のTL-9で、マンデルブロー集合の描画プログラムが動いています。しかもかなり高速で、同じことをC言語で書いて gcc -O3 でビルドして動かしたものと比べて、4.0倍しか遅くありません。これはすごい！
今のTL-9は725行で、実行ファイルでは17.0KBです。グラフィック描画のためにaclライブラリを使っています（17.0KBの中にaclライブラリも含まれます）。

↑

2021.02.19(金)

TL-9でどこまでやるかを考えています。
- 演算子:%
- 組み込み関数:xorShift()
- 組み込み関数:getPix()
- 組み込み関数:fillRect0()
- この4つがあれば、esbasic02aの (4-3)「迷路作成（穴掘り法）」が移植できるはずです。演算子も組み込み関数も簡単にできるのでこれは余裕そうです。

さらに、
- 配列変数のサポート。
- 関数定義と関数呼び出し。
- 演算子:&
- 演算子:/
- 演算子:< >= <=
- 組み込み関数:ff16sin()
- 組み込み関数:ff16cos()
- 組み込み関数:inkey()
- 組み込み関数:wait()
- ここまでやれば、esbasic02aの (4-4)「キューブ回転」が移植できるはずです。

その先も、文字列の簡易サポートをして、組み込み関数をさらに増やせば、
- (4-5)「インベーダゲーム」
- (4-6)「ブロック崩し」
も移植できると思うのですが、そこまでやるかどうかは悩みどころです・・・。
でも、やったほうがおもしろいかなあとは思います。

さらに考えを進めて、一つのソースコードで、gccでコンパイルして動かすことができて、かつTL-9でも動作できるような、そんな仕様ができないものかと検討中です。
- [1] lexer()を改造して、#を記号として認識させる。
- [2] ついでにコメントも書けるようにしてやる（おまけ）。
- [3] #ifndef TL9 ～ #endif で囲まれた範囲は、TL-9からはコメントとして無視してやる（gccには認識される）。
- [4] #ifdef TL9 ～ #endif で囲まれた範囲は、TL-9からは通常通り解釈してやる（gccには無視される）。
- [5] #includeは無視する。
- [6] 組み込み関数の名前や仕様をaclライブラリの本来のものに似せる。

↑

2021.02.26(金)

TL-9aまで作ってみて、自分で「これはとても良い出来栄えだ」と思いました。こんなにいいゴールに行けるのなら、今のようなレベルではなく、もっと気合を入れて説明を書きたいです。
ということでTLシリーズを書き直して、HLシリーズとして出直します。
- TL-9aについては、ここで詳しく紹介しています。→a21_tl9a

↑

2021.03.12(金)

[1]
今日はtwitterで、「10日くらいでできる！プログラミング自作入門」のことを紹介しました。たくさんの人からいいね！してもらえて、たくさんの人にテキストを見てもらえて、私はとっても嬉しいです！本当にどうもありがとうございます。
- https://twitter.com/hkawai3/status/1370198988096368643

[2]
やっぱり、言語の自作といえば、セルフホストは目標の一つだよなあ。HL-9aにあと何を足したら、HL-1を実行できるようになるかなあ。
- 関数の定義と呼び出し機能。
- char型の配列をどうするか問題。ついに型に手を出すべきか？（簡易なものならまあできそう）
- printf()をどうするか。まあprintfを使って実装してしまえばいいだけかもしれないけど。
うーん、これは100行じゃできなさそうだなあ。300行くらいかなあ。
300行頑張って、HL-9aが動かせるようになるなら本気でやりたいけど、HL-1だもんなあ。・・・うーむー。
まあでもそこからさらに数百行頑張れば、HL-9aくらいはできるかもしれないけれど・・・。

↑

2021.03.23(火)

自作言語を作る場合に、セルフホスト（自分自身のソースコードをコンパイルできる）を目指す目標設定があります。
私はこれがいい目標になっていることを認めつつも、しかしこれだけが目標だとそもそも何のために言語を作るのかというところが怪しくなると思っていて、だから今まではこれを目標に設定しないでやってきました。
私としては、かっこいいグラフィックが表示できてデモの見栄えが良いような言語を目指していたのです。
しかしいざそこまでできて、この言語でさらに高みを目指すにはどうしたらいいのかを考えると、私は「生産性の高い言語」を作りたいと思うようになりました。
そして生産性をどう測るかですが、やっぱり同じプログラムを書いて記述量が少なくて済むほうこそが、生産性が高いと言えると思うのです。
さて私は何を作る際に生産性を高めたいのかというと、今は言語を作っているので、言語を作りやすい言語を目指したいです。・・・あれ？そうなると、セルフホストできるようにした上で、自分自身を簡潔に記述できればよさそうです。
ということで、私は次はセルフホストを目指します！

↑

2021.04.05(月)

HL-9aをJITコンパイラ化しても、全然速くならない！もとのHL-9aが速すぎた！！・・・まさかそんなことがあるのか・・・。

↑

2021.04.06(火)

やはりレジスタ変数をサポートしたほうがいいのだろうか・・・。もはやそれ以外に勝ち目がないからなあ（レジスタ変数を使えば目に見えて速くなるのは確認済み）。
うーん、説明が面倒になるから、できればレジスタ変数は話題にしたくはなかったんだけどなあ・・・。
しかしレジスタ変数を扱わないと、結局JITコンパイラのメリットは何もわからないということになってしまうよなあ。それは避けたいよなあ。

よし、いろいろ試行錯誤した結果、難易度をあまり上げずに高速化するめどが立ちました！

↑

2021.04.08(木)

JITコンパイラで性能を出すためにどうしたらいいのかを試行錯誤した結果、レジスタ変数を使うようにしたら十分な効果があることがわかりました（前述のとおり）。
それでふと思いついたのですが、HL-9aだってレジスタ変数を使うように改造することが可能なのです。それでそのように書いてみました。・・・しかし速くなりませんでした。
原因を調べてみたところ、HL-9aの場合は変数アクセスのほかに、ic[]（＝内部コードを格納した配列）へのアクセスも必要で、そこをどうにかしない限りメモリアクセスは少ししか減らないので、速さが大して変わらなかったのだとわかりました。
なるほどなあ。

↑

2021.04.09(金)

mandel.cの実行速度比較メモ。
- gcc(x86の32bit): 4.0秒（さすがに速い！）
- HL-9a(x86の32bit): 27.6秒
- HL-14(仮)(x86の32bit, JITコンパイラ版, レジスタ変数なし): 5.9秒
- HL-14(仮)(x86の32bit, JITコンパイラ版, レジスタ変数あり): 3.7秒
おお、かなり速くなった！・・・あれ？gccよりも速くなってしまった？！64bitと比較したらどうかな？
- gcc(x64): 3.2秒（おおー！さすがだー）

↑

2021.04.23(金)

いつの間にか登録されていた。ありがたやー。
- https://b.hatena.ne.jp/entry/essen.osask.jp/?a21_txt01
「作者の作風が活かされていて、気軽で実践的なテイスト。とても面白い。」っていうコメントがすごく的確。そして面白いと思ってもらえてよかった。

↑

2021.05.01(土)

gcc-O3と同じくらいの速さが906行のHL-14aで実現できてしまったので、なんだー最適化って結構簡単かもしれないぞ！と調子に乗りつつあった私ですが、-Osを選択してサイズ最適化で勝負したら、もうまったく勝ち目がないことがよくわかりました。gccは本当によくできていて賢いです。
そしてサイズを小さくすることは、ひいてはキャッシュヒット率にも直結することなので、最終的には速度にも影響するはずです。だからもっと規模の大きいプログラムになったら、速度でも追いつけなくなりそうだなと思いました。

↑

2021.05.07(金)

どうにかがんばって、HL-17のプログラムはできた。もっと頑張ってHL-17aまでは今日中に書いてしまいたいのだけど、間に合うかなあ。

↑

2021.05.17(月)

HL-22aまでやって、アセンブラ出力もやって、それでそろそろインタプリタとJITコンパイラの統合をやってみたい。
そして言語に「型」を導入して、構造体も使えるようになりたい。さらにセルフホストができたら、既存のCコンパイラから卒業したい。

↑

2021.05.28(金)

HL-13以降の説明が、どんどん雑になっている気がする。これはよくない。
これは私が教材の開発のほうが面白くなってしまって、文章まで気が回らなくなっていたせいだと思う。
少しずつ直さなければ！

↑

2021.05.31(月)

ちょっと思いついたのでメモ。

x86やx64は、機械語をそのまま出すよりも、一回以下の構造体に出して、それで最適化して、最後に機械語で出力するほうがシンプルに作れるんじゃないかという気がする。

??? {
    int op; // オペコード
    signed char preg, mreg, bas, idx, scl;
        // pregはmod r/mの真ん中のレジスタ
        // mregはmod r/mで表すレジスタ（ここが-1だとレジスタではなくメモリになる）
        // basはmod r/mで表すベースレジスタ（使わないのなら-1）
        // idxはsibで表すインデックスレジスタ（使わないのなら-1）
        // sclはsibで表すスケールファクタ（使わないのなら0）
    int dsp; // mod r/mのディスプレースメント
    int imm32;
    AInt64 imm64;
};

↑

2021.06.01(火)

HL-22bが終わったら真っ先にやりたいこと。
- [1] HL-9a, HL-16b, HL-22b を統合する。
- [2] 整数型以外も扱えるようにする。

↑

2021.06.03(木)

HL-22bを書いているうちに気づいたこと。ややや、HL-18以降には、ひどいバグがあるじゃないか。これは直さなければ・・・。

↑

2021.06.30(水)

ここしばらく、ずっとHLX-001の開発をやっているのですが、何をどう書いても「うーん、作りたかったのはこんなものだったのだろうか？」という気持ちになります。
なんでなかなかしっくりこない気がするんだろうって考えてみたら、ようやくわかりました。
それはきっと判断の基準が無意識のうちにHL-22bになっているからなんです（まあHLX-001はHL-22b（HL-16b）の続きなのだから、当然といえば当然）。
HL-22bのできが良かったんです。自分でも驚くくらいに良かったのです。だからこれに匹敵するレベルにするのが難しいのです。
まあそんなことがわかっても何の解決にもならないのですが、とにかく満足できるまで頑張ります！

↑

2021.07.08(木)

HLX-001では、命令長も自動で最適なものを選べるようにしたいと思っています。そのためにどうしたらいいのか、試行錯誤中です。たとえばJMP先のアドレスが近いのか遠いのか、メモリアクセス時のディスプレースメントが大きいのか小さいのか、そういうことで命令長は変わります。
できるだけ柔軟にこれを処理できるようになりたいです。

（数時間後）

ついに「しっくりくる」内部構成にたどり着いたかも？！期待している処理を、期待している複雑さで（簡単さで）記述できるようになった・・・気がします。ここまで長かったー！

↑

2021.07.09(金)

[今日の勉強]
- x64で「CALL RAX」の機械語は、REXプリフィクスなしの「ff d0」。そして「CALL EAX」はできない（まあそれが正しいとも思う）。

↑

2021.07.14(水)

HLX-001でprintくらいはできるようになりました。しかしまだ定数式しか動きません。でもここまでできれば、あとはトントン拍子に進んでいくはずです。

↑

2021.07.16(金)

HLX-001で加減乗除などの演算もできるようになりました！これでループができればいろいろ動かせるのはわかっているのですが、分岐処理は near-jmp, short-jmp の両方を自動で最適化させるために複雑にしたので、ここを書き上げるのはもう少し時間がかかりそうです。

↑

2021.07.20(火)

HLX-001での分岐処理、うまくできるようになりました。これを実現するための改造でもあったので、大きい山を越えた感じです！
- 遠くに飛ぶときはHL-22bなどと同様に 0f 8x xx xx xx xx を出力しますが、ジャンプ先が-128～+127のときは、7x xxという短い形式を出力するようになりました。前方参照でも届くときはちゃんと短い形式を使うようになっています。

↑

2021.07.26(月)

JITコンパイラのコード生成の質の比較：
grd.c mande.cl maze.c kcube.c invader.c
HL-16a 158 622 1274 3125 1958
HLX-001 (2021.07.21版) 266 1004 1931 4486 2901
こうしてみると、HL-16aにはまだまだ及ばないことがよくわかります。
これは現状のHLX-001がほとんど最適化をやっていないせいです。それでこれをなんとかしたいので、まずは「先を実行しても参照されることのない」演算を探し出して、その演算を自動で削除する仕組みを導入しようと思います（というかもうすぐできそう）。
これがあれば、それより上位では、無駄な計算を書いてしまっても問題ないことになります。

↑

こめんと欄

コメント	お名前	NameLink

	grd.c	mande.cl	maze.c	kcube.c	invader.c
HL-16a	158	622	1274	3125	1958
HLX-001 (2021.07.21版)	266	1004	1931	4486	2901