a21_txt01_6
の編集
https://essen.osask.jp/?a21_txt01_6
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
BracketName
EssenRev4
FormattingRules
FrontPage
Help
InterWiki
InterWikiName
InterWikiSandBox
K
MenuBar
PHP
PukiWiki
PukiWiki/1.4
PukiWiki/1.4/Manual
PukiWiki/1.4/Manual/Plugin
PukiWiki/1.4/Manual/Plugin/A-D
PukiWiki/1.4/Manual/Plugin/E-G
PukiWiki/1.4/Manual/Plugin/H-K
PukiWiki/1.4/Manual/Plugin/L-N
PukiWiki/1.4/Manual/Plugin/O-R
PukiWiki/1.4/Manual/Plugin/S-U
PukiWiki/1.4/Manual/Plugin/V-Z
RecentDeleted
SDL2_01
SandBox
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
a21
a21_acl01
a21_bbs01
a21_challengers
a21_count
a21_edu01
a21_edu02
a21_edu03
a21_edu04
a21_edu05
a21_edu06
a21_edu07
a21_edu08
a21_edu09
a21_edu10
a21_edu11
a21_hlx000
a21_hlx001
a21_hlx001_1
a21_hlx001_2
a21_hlx001_3
a21_hlx002
a21_hlx002_1
a21_hlx003
a21_hlx003_1
a21_hlx004_1
a21_memo01
a21_opt
a21_opt02
a21_opt03
a21_p01
a21_special
a21_tl9a
a21_todo
a21_txt01
a21_txt01_10
a21_txt01_1a
a21_txt01_2
a21_txt01_2a
a21_txt01_2b
a21_txt01_3
a21_txt01_4
a21_txt01_5
a21_txt01_6
a21_txt01_6a
a21_txt01_7
a21_txt01_8
a21_txt01_8a
a21_txt01_9
a21_txt01_9a
a21_txt02
a21_txt02_10
a21_txt02_10a
a21_txt02_10b
a21_txt02_11
a21_txt02_11a
a21_txt02_12
a21_txt02_12a
a21_txt02_12b
a21_txt02_1a
a21_txt02_1b
a21_txt02_2
a21_txt02_2a
a21_txt02_3
a21_txt02_3a
a21_txt02_4
a21_txt02_4a
a21_txt02_5
a21_txt02_5a
a21_txt02_6
a21_txt02_6a
a21_txt02_6b
a21_txt02_6b_rev0
a21_txt02_6x
a21_txt02_7
a21_txt02_7a
a21_txt02_8
a21_txt02_8a
a21_txt02_9
a21_txt02_9a
a22_acl2_01
a22_acl2_02
a22_edu12
a22_intro01
a22_intro02
a22_intro03
a22_memman01
a22_memman02
a22_memman03
a22_memman04
a22_memman05
a22_memman06
a22_memman07
a22_memo01
a22_mingw_debug
a22_txt03
a22_txt03_1a
a22_txt03_1b
a22_txt03_2
a22_txt03_2a
a22_ufcs01
a23_bbs
a23_ec001
a23_ec002
a23_intro00
a23_intro000
a23_intro01
a23_intro02
a23_intro03
a23_intro04
a23_intro05
a23_intro06
a23_intro07
a23_intro08
a23_intro09
a23_intro10
a23_intro10wk1
a23_intro10wk2
a23_intro10wk3
a23_intro11
a23_intro12
a23_intro13
a23_intro13wk1
a23_intro14
a23_intro15
a23_intro16
a23_intro90
a23_intro91
a23_neopixel1
a23_os01
a23_useSelfMade
a23_usm001
a23_usm002
a23_usm003
a23_usm004
a23_usm005
a23_usm006
a23_usm007
a23_usm008
a23_usm009
aclib00
aclib01
aclib02
aclib03
aclib04
aclib05
aclib06
aclib07
aclib08
aclib09
aclib10
aclib11
aclib12
aclib13
aclib14
aclib15
aclib16
aclib17
aclib18
aclib19
aclib20
aclib21
aclib22
aclib23
aclib24
aclib25
aclib_bbs
arm64_01
avm0001
edu0001
edu0002
edu0003
esb02b_hrb
esb_dbg
esbasic0001
esbasic0002
esbasic0003
esbasic0004
esbasic0005
esbasic0006
esbasic0007
esbasic0008
esbasic0009
esbasic0010
esbasic0011
esbasic0012
esbasic0013
esbasic0014
esbasic0015
esbasic0016
esbasic0017
esbasic02a
esc0001
escm0001
essen_hist
esvm0001
esvm0002
esvm0003
esvm0004
esvm0005
esvm0006
esvm_i0
hh4a
idea0001
idea0002
idea0003
impressions
jck_0000
jck_0001
kawai
kbcl0_0000
kbcl0_0001
kbcl0_0002
kbcl0_0003
kbcl0_0004
kbcl0_0005
kbcl0_0006
kbcl0_0007
kclib1_0000
kclib1_0001
kclib1_0002
kclib1_0003
kclib1_0004
kclib1_0005
kclib1_0006
kclib1_0007
kclib1_0008
kclib1_0009
kclib1_0010
kpap0001
members
memo0001
osask4g
osask4g_r2
p20200311a
p20200610a
p20200610b
p20200624a
p20200711a
p20200716a
page0001
page0002
page0003
page0004
page0005
page0006
page0007
page0008
page0009
page0010
page0011
page0012
page0013
page0014
page0015
page0016
page0017
page0018
page0019
page0020
page0021
page0022
page0023
populars
seccamp
seccamp2019
sechack
sechack2019
seclang01
sh3_2020
sh3_2020_kw
sh3_2020_nk
sh3_2021_kw
sh3_2021_nk
sh3_2022_kw
sh3_2023_kw
sh3_kw_hist
termux001
termux002
text0001
text0001a
text0002
text0002a
text0003
text0004
text0005
text0006
text0006a
text0007
text0008
text0010
text0011
text0012
text0013
text0014
text0015
text0016
text0017
text0018
text0019
text0020
text0021
tl1c
tl2c
tl3c
tl3d
* 川合のプログラミング言語自作のためのテキスト第三版#6 -(by [[K]], 2021.03.02) ** (1) HL-6 -HL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。 |ページ名|名前|行数|.exeの大きさ|説明|速度のめやす| |[[a21_txt01]]|HL-1|RIGHT:49行|RIGHT:6.0KB|初めの一歩、たった49行のシンプルすぎる言語処理系|RIGHT:計測不能| |[[a21_txt01_2]]|HL-2|128行|RIGHT:6.5KB|変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに|RIGHT:計測不能| |[[a21_txt01_3]]|HL-3|148行|RIGHT:7.0KB|条件分岐などをサポートしてループ処理が可能に|RIGHT:1520倍| |[[a21_txt01_4]]|HL-4|186行|RIGHT:7.5KB|REPLの導入(これは楽しい!)|RIGHT:1520倍| |[[a21_txt01_5]]|HL-5|214行|RIGHT:7.5KB|少し高速化|RIGHT:260倍| -ということで本気を出してどこまで速くなるか挑戦します。JITコンパイラに作り替えれば劇的に速くなるのはわかっているのですが、それはCPUに依存するようになるので後回しにして、ここではJITコンパイラやインラインアセンブラを使わない範囲での最速を目指してみたいと思います。 -基本方針としては、tc[]をphrCmp()で一致しているかどうか調べながら実行するのはやめて、もっとシンプルで高速に実行できそうなデータ列に変換し(内部コードへのコンパイル)、その後そのデータ列だけを見て高速に実行します。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる. int loadText(String path, String t, int siz) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// #define MAX_TC 255 // トークンコードの最大値. String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶. int tl[MAX_TC + 1]; // トークンの長さ. unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定. int tcs = 0, tcb = 0; int var[MAX_TC + 1]; // 変数. int getTc(String s, int len) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int isAlphabet(unsigned char c) → HL-2と同じなので省略 int lexer(String s, int tc[]) → HL-2と同じなので省略 int tc[10000]; // トークンコード. enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt }; char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 == != < >= <= >"; /////////////////////////////////////////////////////////////////////////////// int phrCmp_tc[32 * 100], ppc1, wpc[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす. int phrCmp(int pid, String phr, int pc) → HL-5と同じなので省略 /////////////////////////////////////////////////////////////////////////////// typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる. enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpTime, OpEnd, OpAdd1 }; IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ. void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) // ic[]へ簡単に書き込むための便利関数. { icq[0] = (IntP) op; icq[1] = p1; icq[2] = p2; icq[3] = p3; icq[4] = p4; icq += 5; } /////////////////////////////////////////////////////////////////////////////// int compile(String s) { int pc, pc1, i; IntP *icq1; pc1 = lexer(s, tc); tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる. tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく. icq = ic; // これで、icqはic[0]を指すようになる. ここから書き始める. for (pc = 0; pc < pc1; ) { // コンパイル開始. if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入. putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0); } else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません). putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算. putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 4, "print !!*0;", pc)) { // print. putIc(OpPrint, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令. var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく. } else if (phrCmp( 5, "goto !!*0;", pc)) { // goto. putIc(OpGoto, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) { putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 7, "time;", pc)) { putIc(OpTime, 0, 0, 0, 0); } else if (phrCmp( 8, ";", pc)) { // 何もしない. } else goto err; pc = ppc1; } putIc(OpEnd, 0, 0, 0, 0); icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpJgt) { icq[1] = (IntP) (*icq[1] + ic); } } return icq1 - ic; err: printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]); return -1; } void exec() { clock_t t0 = clock(); IntP *icp = ic; // これによりicpはic[0]を指すようになる. for (;;) { switch ((int) icp[0]) { case OpCpy: *icp[1] = *icp[2]; icp += 5; continue; case OpAdd: *icp[1] = *icp[2] + *icp[3]; icp += 5; continue; case OpSub: *icp[1] = *icp[2] - *icp[3]; icp += 5; continue; case OpPrint: printf("%d\n", *icp[1]); icp += 5; continue; case OpGoto: icp = (IntP *) icp[1]; continue; case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpAdd1: (*icp[1])++; icp += 5; continue; } } } int run(String s) { if (compile(s) < 0) return 1; exec(); return 0; } /////////////////////////////////////////////////////////////////////////////// int main(int argc, const char **argv) → HL-5と同じなので省略 -トータルの行数は285行まで一気に増えてしまいました。でもかなり高速になって、C言語との比較で13.2倍というところまで速くなりました! HL-5と比較すると20倍速です。 ** (2) HL-6の簡単な説明 -関数: --void loadText(String path, String t, int siz) ---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す(これを超える長さのファイルは途中で打ち切られる)。 --int getTc(String s, int len) ---トークン(単語)をsに渡すと、それに対応するトークンコード(整数)を返す。 --int isAlphabetOrNumber(unsigned char c) ---引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。 ---アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。 ---この関数は以下のlexer()の下請け。 --int lexer(String s, int tc[]) ---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード(単語番号)に変換させられた数列が入って返される。 ---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。 --int phrCmp(int pid, String phr, int pc) ---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。 ---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。 ---なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。 --void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) ---引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。 --int compile(String s) ---与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。 ---関数run()の下請け関数。 --void exec() ---ic[]に格納された内部コードを高速に実行する。 ---関数run()の下請け関数。 --int run(String s) ---言語処理の本体。HL-3までのmain()に相当。 ---内部的にはcompile()してrun()しているだけ。 --int main(int argc, const char **argv) ---REPLの処理をしている。 -変数: --String ts[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。 --int tl[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。 --unsigned char tcBuf[] ---getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。 --int tcs, tcb ---どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数(0~tcs-1が発行済み)。 ---tcbはtcBuf[]の未使用領域を指している。 ---もしtcBuf[]やtcbの役割がピンとこない場合は、[[a21_txt01_2b]]を参照。 --int var[] ---変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。 --int tc[] ---プログラムをトークンコード列に変換したものがここに入る。 --int phrCmp_tc[] ---phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。 --int ppc1, wpc[] ---フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。 ---wpc[]にはワイルドカードで一致した位置が入る。 --IntP ic[], *icq ---ic[]は内部コード(internal-code)を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。 ---- -まず、高速かつ簡潔に書くためにどうしたらいいかを検討しましたが、ポインタを多用することになってしまいました。だからポインタが苦手な人にはHL-6の理解が難しくなってしまったと思います。どうもすみません。 ** (3) 内部コードに関する詳しい説明(compile(), exec()など) -まず最初に、exec()から説明したいと思います。exec()の基本構造は、 for (;;) { ... } ループの中にswitch...case文が一つ入っているだけです。 -内部コードは、以下のような仕様にしています。 |icp[0]|icp[1]|icp[2]|icp[3]|icp[4]|動作|説明| |OpCpy |p1|p2| | |*p1 = *p2;|単純代入| |OpAdd |p1|p2|p3| |*p1 = *p2 + *p3;|加算| |OpSub |p1|p2|p3| |*p1 = *p2 - *p3;|減算| |OpPrint|p1| | | |print *p1;|値の表示| |OpGoto |p1| | | |goto p1;|無条件分岐(icp = p1;しているだけ)| |OpJeq |p1|p2|p3| |if (*p2 == *p3) goto p1;|条件分岐(jump if equal)| |OpJne |p1|p2|p3| |if (*p2 != *p3) goto p1;|条件分岐(jump if not equal)| |OpJlt |p1|p2|p3| |if (*p2 < *p3) goto p1;|条件分岐(jump if less than)| |OpTime | | | | |時間表示|exec()を開始してからの経過時間を表示| |OpEnd | | | | |exec()を終了|内部的にはreturnするだけ| |OpAdd1 |p1| | | |(*p1)++;|変数に1を加算。OpAddで1を加算するよりも少し速い| --表の中のp1~p3は、ポインタです。しかもgotoや条件分岐のp1以外のpは、すべてvar[]を指し示すようになっています。 --もしポインタを扱うのが嫌なら、p1~p3ではなくて、i1~i3という整数値にして、 var[i1] = var[i2] + var[i3]; のようにすることもできます。しかしこうするとOpAddの実行にあたって、var値とi値の加算演算をしながら実行されるので、実行速度が落ちてしまいます。しかし *p1 = *p2 + *p3; にすれば、varとの加算演算が内部で発生することはなくなるので、より速く実行することができます。 --これがやむなくポインタを多用することになった理由です。 --この表と見比べると、exec()で不可解なところはほぼないのではないかと思われます。 --あ、そうだ。OpGotoのところで、「icp = (IntP *) icp[1];」となっていて、(IntP *)というキャストが付いている理由は、icpが IntP * 型で、icp[1]の IntP 型と型が合わなくて、そのままだと警告やエラーが出てしまうので、付けています。OpJeqとかでも同じ理由で同じキャストが付いています。 -次はcompile()です。 --HL-5と比較すれば、より分かりやすいだろうと思うので、比較してみます。 [HL-5] } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. var[tc[wpc[0]]] = var[tc[wpc[1]]] + var[tc[wpc[2]]]; [HL-6] } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); --HL-5のときは、実際に変数の値を2つ読み取って加算して、結果を書き込めばいいだけでした。しかし今回は変数の値は読みません。書き込むこともしません。その代わり、どこを読むのか、どこに書くのかというポインタだけを確定させて計算して、それを内部コードに書き込みます。 --C言語では、変数名を書けば変数の値を意味しますが、その前に&を付ければ、変数の値ではなくポインタを意味するようになります。だから&を付けて、それをputIc()の引数に渡しているのです。 --これでexec()でうまく実行できるようになります。 --compile()でちょっとわかりにくいかもしれないのは、gotoのところでしょう。 --まずラベル定義命令が来たら、内部コードは何も出力しないで、ラベル名の変数にその時のicq値を記録しておきます。しかしvar[]はint型なので、ポインタを記憶することはできません。仕方ないので、icを引いて、その差を記憶させておきます。 --(C言語では、2つのポインタの差は整数値になります。) --この整数値は、icqがic[]の何番目になっているかを表す整数値です。 --そしてgoto命令を見つけたら、OpGoto命令を生成して第一引数にラベル名変数へのポインタを指定しておきます。 --HL-5までだったら、ここでpc値を更新してgoto先に移動するのですが、HL-6では実際に分岐するのはexec()のときで、今は全部の命令を内部コードに変換したいだけなので、gotoが来てもpc値は更新しません。他の普通の命令と同様に、pc値はそのまま次の命令へ進みます。 --そうして、最後まで内部コードへの変換が終わると、OpEnd命令を付加した後に、goto先の調整があります。 icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpJgt) { icq[1] = (IntP) (*icq[1] + ic); } } --ここでやっているのは、もしOpGotoやOpJeqのように、p1がジャンプ先の変数へのポインタになっているものがあったら、それにic値を加算して、icq値に戻して、それで上書きします。 --ここでもやはり型が合わないので、(IntP)でキャストしてエラーにならないようにしています。 ---- -あとは、こまごましたことをQ&A形式で説明します。 -[Q]なぜジャンプ先の計算を後になってやっているんですか?goto命令の時に putIc(OpGoto, (IntP) (var[tc[wpc[0]]] + ic), 0, 0, 0); --ってやっちゃえばいいじゃないですか。 --[A]それは良い質問です。実は私もそうしたいのですが、このやり方だとこのgotoより前に定義されたラベルにしかジャンプできません。なぜならこれから定義されるラベルの変数にはvar[]に値が入っていないからです。・・・それでしょうがなく、現状のようなやり方になりました。 -[Q]なぜ内部コードは全部長さが5なのか?単純代入なんて3つしか使っていないのだから、長さ3でいいではないか。2つ分も無駄になっている。長さをそろえずに詰め込むほうがメモリの使用効率がよくなって性能が上がるのではないか? --[A]実は私も最初はそのように思っていたのですが、キャッシュメモリの都合なのか、どの命令も長さを5にしてそろえたほうが1~2割くらい高速になりました。だから無駄を承知で長さ5にしています。 ** (4) 発展的な改造 -HL-6では、少しでも高速化するために、+1するための専用の命令OpAdd1を付けてあります。しかしこの考え方をさらに発展させて、カウンタのインクリメントと、条件分岐を1命令にまとめたOpLop命令を付けたらどのくらい速くできるでしょうか。興味を持ったら以下のページを見てみてください。 --[[a21_txt01_6a]] ** 次回に続く -次回: [[a21_txt01_7]] *こめんと欄 #comment
タイムスタンプを変更しない
* 川合のプログラミング言語自作のためのテキスト第三版#6 -(by [[K]], 2021.03.02) ** (1) HL-6 -HL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。 |ページ名|名前|行数|.exeの大きさ|説明|速度のめやす| |[[a21_txt01]]|HL-1|RIGHT:49行|RIGHT:6.0KB|初めの一歩、たった49行のシンプルすぎる言語処理系|RIGHT:計測不能| |[[a21_txt01_2]]|HL-2|128行|RIGHT:6.5KB|変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに|RIGHT:計測不能| |[[a21_txt01_3]]|HL-3|148行|RIGHT:7.0KB|条件分岐などをサポートしてループ処理が可能に|RIGHT:1520倍| |[[a21_txt01_4]]|HL-4|186行|RIGHT:7.5KB|REPLの導入(これは楽しい!)|RIGHT:1520倍| |[[a21_txt01_5]]|HL-5|214行|RIGHT:7.5KB|少し高速化|RIGHT:260倍| -ということで本気を出してどこまで速くなるか挑戦します。JITコンパイラに作り替えれば劇的に速くなるのはわかっているのですが、それはCPUに依存するようになるので後回しにして、ここではJITコンパイラやインラインアセンブラを使わない範囲での最速を目指してみたいと思います。 -基本方針としては、tc[]をphrCmp()で一致しているかどうか調べながら実行するのはやめて、もっとシンプルで高速に実行できそうなデータ列に変換し(内部コードへのコンパイル)、その後そのデータ列だけを見て高速に実行します。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる. int loadText(String path, String t, int siz) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// #define MAX_TC 255 // トークンコードの最大値. String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶. int tl[MAX_TC + 1]; // トークンの長さ. unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定. int tcs = 0, tcb = 0; int var[MAX_TC + 1]; // 変数. int getTc(String s, int len) → HL-4と同じなので省略 /////////////////////////////////////////////////////////////////////////////// int isAlphabet(unsigned char c) → HL-2と同じなので省略 int lexer(String s, int tc[]) → HL-2と同じなので省略 int tc[10000]; // トークンコード. enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt }; char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 == != < >= <= >"; /////////////////////////////////////////////////////////////////////////////// int phrCmp_tc[32 * 100], ppc1, wpc[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす. int phrCmp(int pid, String phr, int pc) → HL-5と同じなので省略 /////////////////////////////////////////////////////////////////////////////// typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる. enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpTime, OpEnd, OpAdd1 }; IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ. void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) // ic[]へ簡単に書き込むための便利関数. { icq[0] = (IntP) op; icq[1] = p1; icq[2] = p2; icq[3] = p3; icq[4] = p4; icq += 5; } /////////////////////////////////////////////////////////////////////////////// int compile(String s) { int pc, pc1, i; IntP *icq1; pc1 = lexer(s, tc); tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる. tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく. icq = ic; // これで、icqはic[0]を指すようになる. ここから書き始める. for (pc = 0; pc < pc1; ) { // コンパイル開始. if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入. putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0); } else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません). putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算. putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 4, "print !!*0;", pc)) { // print. putIc(OpPrint, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令. var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく. } else if (phrCmp( 5, "goto !!*0;", pc)) { // goto. putIc(OpGoto, &var[tc[wpc[0]]], 0, 0, 0); } else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) { putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0); } else if (phrCmp( 7, "time;", pc)) { putIc(OpTime, 0, 0, 0, 0); } else if (phrCmp( 8, ";", pc)) { // 何もしない. } else goto err; pc = ppc1; } putIc(OpEnd, 0, 0, 0, 0); icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpJgt) { icq[1] = (IntP) (*icq[1] + ic); } } return icq1 - ic; err: printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]); return -1; } void exec() { clock_t t0 = clock(); IntP *icp = ic; // これによりicpはic[0]を指すようになる. for (;;) { switch ((int) icp[0]) { case OpCpy: *icp[1] = *icp[2]; icp += 5; continue; case OpAdd: *icp[1] = *icp[2] + *icp[3]; icp += 5; continue; case OpSub: *icp[1] = *icp[2] - *icp[3]; icp += 5; continue; case OpPrint: printf("%d\n", *icp[1]); icp += 5; continue; case OpGoto: icp = (IntP *) icp[1]; continue; case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpAdd1: (*icp[1])++; icp += 5; continue; } } } int run(String s) { if (compile(s) < 0) return 1; exec(); return 0; } /////////////////////////////////////////////////////////////////////////////// int main(int argc, const char **argv) → HL-5と同じなので省略 -トータルの行数は285行まで一気に増えてしまいました。でもかなり高速になって、C言語との比較で13.2倍というところまで速くなりました! HL-5と比較すると20倍速です。 ** (2) HL-6の簡単な説明 -関数: --void loadText(String path, String t, int siz) ---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す(これを超える長さのファイルは途中で打ち切られる)。 --int getTc(String s, int len) ---トークン(単語)をsに渡すと、それに対応するトークンコード(整数)を返す。 --int isAlphabetOrNumber(unsigned char c) ---引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。 ---アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。 ---この関数は以下のlexer()の下請け。 --int lexer(String s, int tc[]) ---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード(単語番号)に変換させられた数列が入って返される。 ---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。 --int phrCmp(int pid, String phr, int pc) ---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。 ---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。 ---なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。 --void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) ---引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。 --int compile(String s) ---与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。 ---関数run()の下請け関数。 --void exec() ---ic[]に格納された内部コードを高速に実行する。 ---関数run()の下請け関数。 --int run(String s) ---言語処理の本体。HL-3までのmain()に相当。 ---内部的にはcompile()してrun()しているだけ。 --int main(int argc, const char **argv) ---REPLの処理をしている。 -変数: --String ts[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。 --int tl[] ---getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。 --unsigned char tcBuf[] ---getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。 --int tcs, tcb ---どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数(0~tcs-1が発行済み)。 ---tcbはtcBuf[]の未使用領域を指している。 ---もしtcBuf[]やtcbの役割がピンとこない場合は、[[a21_txt01_2b]]を参照。 --int var[] ---変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。 --int tc[] ---プログラムをトークンコード列に変換したものがここに入る。 --int phrCmp_tc[] ---phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。 --int ppc1, wpc[] ---フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。 ---wpc[]にはワイルドカードで一致した位置が入る。 --IntP ic[], *icq ---ic[]は内部コード(internal-code)を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。 ---- -まず、高速かつ簡潔に書くためにどうしたらいいかを検討しましたが、ポインタを多用することになってしまいました。だからポインタが苦手な人にはHL-6の理解が難しくなってしまったと思います。どうもすみません。 ** (3) 内部コードに関する詳しい説明(compile(), exec()など) -まず最初に、exec()から説明したいと思います。exec()の基本構造は、 for (;;) { ... } ループの中にswitch...case文が一つ入っているだけです。 -内部コードは、以下のような仕様にしています。 |icp[0]|icp[1]|icp[2]|icp[3]|icp[4]|動作|説明| |OpCpy |p1|p2| | |*p1 = *p2;|単純代入| |OpAdd |p1|p2|p3| |*p1 = *p2 + *p3;|加算| |OpSub |p1|p2|p3| |*p1 = *p2 - *p3;|減算| |OpPrint|p1| | | |print *p1;|値の表示| |OpGoto |p1| | | |goto p1;|無条件分岐(icp = p1;しているだけ)| |OpJeq |p1|p2|p3| |if (*p2 == *p3) goto p1;|条件分岐(jump if equal)| |OpJne |p1|p2|p3| |if (*p2 != *p3) goto p1;|条件分岐(jump if not equal)| |OpJlt |p1|p2|p3| |if (*p2 < *p3) goto p1;|条件分岐(jump if less than)| |OpTime | | | | |時間表示|exec()を開始してからの経過時間を表示| |OpEnd | | | | |exec()を終了|内部的にはreturnするだけ| |OpAdd1 |p1| | | |(*p1)++;|変数に1を加算。OpAddで1を加算するよりも少し速い| --表の中のp1~p3は、ポインタです。しかもgotoや条件分岐のp1以外のpは、すべてvar[]を指し示すようになっています。 --もしポインタを扱うのが嫌なら、p1~p3ではなくて、i1~i3という整数値にして、 var[i1] = var[i2] + var[i3]; のようにすることもできます。しかしこうするとOpAddの実行にあたって、var値とi値の加算演算をしながら実行されるので、実行速度が落ちてしまいます。しかし *p1 = *p2 + *p3; にすれば、varとの加算演算が内部で発生することはなくなるので、より速く実行することができます。 --これがやむなくポインタを多用することになった理由です。 --この表と見比べると、exec()で不可解なところはほぼないのではないかと思われます。 --あ、そうだ。OpGotoのところで、「icp = (IntP *) icp[1];」となっていて、(IntP *)というキャストが付いている理由は、icpが IntP * 型で、icp[1]の IntP 型と型が合わなくて、そのままだと警告やエラーが出てしまうので、付けています。OpJeqとかでも同じ理由で同じキャストが付いています。 -次はcompile()です。 --HL-5と比較すれば、より分かりやすいだろうと思うので、比較してみます。 [HL-5] } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. var[tc[wpc[0]]] = var[tc[wpc[1]]] + var[tc[wpc[2]]]; [HL-6] } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算. putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0); --HL-5のときは、実際に変数の値を2つ読み取って加算して、結果を書き込めばいいだけでした。しかし今回は変数の値は読みません。書き込むこともしません。その代わり、どこを読むのか、どこに書くのかというポインタだけを確定させて計算して、それを内部コードに書き込みます。 --C言語では、変数名を書けば変数の値を意味しますが、その前に&を付ければ、変数の値ではなくポインタを意味するようになります。だから&を付けて、それをputIc()の引数に渡しているのです。 --これでexec()でうまく実行できるようになります。 --compile()でちょっとわかりにくいかもしれないのは、gotoのところでしょう。 --まずラベル定義命令が来たら、内部コードは何も出力しないで、ラベル名の変数にその時のicq値を記録しておきます。しかしvar[]はint型なので、ポインタを記憶することはできません。仕方ないので、icを引いて、その差を記憶させておきます。 --(C言語では、2つのポインタの差は整数値になります。) --この整数値は、icqがic[]の何番目になっているかを表す整数値です。 --そしてgoto命令を見つけたら、OpGoto命令を生成して第一引数にラベル名変数へのポインタを指定しておきます。 --HL-5までだったら、ここでpc値を更新してgoto先に移動するのですが、HL-6では実際に分岐するのはexec()のときで、今は全部の命令を内部コードに変換したいだけなので、gotoが来てもpc値は更新しません。他の普通の命令と同様に、pc値はそのまま次の命令へ進みます。 --そうして、最後まで内部コードへの変換が終わると、OpEnd命令を付加した後に、goto先の調整があります。 icq1 = icq; for (icq = ic; icq < icq1; icq += 5) { // goto先の設定. i = (int) icq[0]; if (OpGoto <= i && i <= OpJgt) { icq[1] = (IntP) (*icq[1] + ic); } } --ここでやっているのは、もしOpGotoやOpJeqのように、p1がジャンプ先の変数へのポインタになっているものがあったら、それにic値を加算して、icq値に戻して、それで上書きします。 --ここでもやはり型が合わないので、(IntP)でキャストしてエラーにならないようにしています。 ---- -あとは、こまごましたことをQ&A形式で説明します。 -[Q]なぜジャンプ先の計算を後になってやっているんですか?goto命令の時に putIc(OpGoto, (IntP) (var[tc[wpc[0]]] + ic), 0, 0, 0); --ってやっちゃえばいいじゃないですか。 --[A]それは良い質問です。実は私もそうしたいのですが、このやり方だとこのgotoより前に定義されたラベルにしかジャンプできません。なぜならこれから定義されるラベルの変数にはvar[]に値が入っていないからです。・・・それでしょうがなく、現状のようなやり方になりました。 -[Q]なぜ内部コードは全部長さが5なのか?単純代入なんて3つしか使っていないのだから、長さ3でいいではないか。2つ分も無駄になっている。長さをそろえずに詰め込むほうがメモリの使用効率がよくなって性能が上がるのではないか? --[A]実は私も最初はそのように思っていたのですが、キャッシュメモリの都合なのか、どの命令も長さを5にしてそろえたほうが1~2割くらい高速になりました。だから無駄を承知で長さ5にしています。 ** (4) 発展的な改造 -HL-6では、少しでも高速化するために、+1するための専用の命令OpAdd1を付けてあります。しかしこの考え方をさらに発展させて、カウンタのインクリメントと、条件分岐を1命令にまとめたOpLop命令を付けたらどのくらい速くできるでしょうか。興味を持ったら以下のページを見てみてください。 --[[a21_txt01_6a]] ** 次回に続く -次回: [[a21_txt01_7]] *こめんと欄 #comment
テキスト整形のルールを表示する