Commonlispのダイナミック変数
- CLでためしにWiki書いてる。
- 再帰的にかくとオーバーフローしそうなので反復的に書きたいが、反復的変換が難しい箇所が出てきた。
- そこで、ダイナミック変数で何とかなるかなーと思ってテストしてみた。
;再帰版 (defun rec-tes1 (x) (if (= x 100000) ;1000とかだとうまく動く。 0 (+ x (rec-tes1 (+ x 1))))) (rec-tes1 0) ;-> Control stack guard page temporarily disabled: proceed with caution ; 0: (SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR) ; 1: ("foreign function: call_into_lisp") ; 2: ("foreign function: post_signal_tramp") ; 3: (REC-TES1 65243) ; 4: (REC-TES1 65242) ; 5: (REC-TES1 65241) ;オーバーフローしたっぽい。 ;ダイナミック変数束縛 (defparameter *result* 0) (defun rec-tes2 (x) (if (= x 100000) *result* (let ((*result* (+ *result* x))) (rec-tes2 (+ x 1))))) (rec-tes2 0) ;-> Control stack guard page temporarily disabled: proceed with caution ; 0: (SB-KERNEL::CONTROL-STACK-EXHAUSTED-ERROR) ; 1: ("foreign function: call_into_lisp") ; 2: ("foreign function: post_signal_tramp") ; 3: (SB-KERNEL:TWO-ARG-+ 2128161420 65241) ; 4: (REC-TES2 65241) ; 5: (REC-TES2 65240) ; 6: (REC-TES2 65239) ;あら？オーバーフローした？
- ご覧のとおり、ダイナミック変数に束縛し、末尾再帰呼び出し内でのみ環境を更新していく。
- 関数の形自体は末尾再帰となっているので大丈夫かなーと思ったが･･･結果は再帰と同じ。
- 落ちてる場所もほとんど同じみたい（(REC-TES1 65243)と(REC-TES2 65241)）だし、内部の構造はわからないが、内部では再帰的なアルゴリズムになっているのか、末尾再帰最適化がかからないのか。
- とにかくパフォーマンスは再帰と同じようだから気をつけないといけない。
- おちないように1000に変更して、時間も計ってみる。
(defun rec-tes1 (x) (if (= x 1000) 0 (+ x (rec-tes1 (+ x 1))))) CL-USER> (time (dotimes (i 100000) (rec-tes1 0))) ;took : 3.420 seconds of real ;time : 3.420000 seconds of total run time (3.420000 user, 0.000000 system) (defparameter *result* 0) (defun rec-tes2 (x) (if (= x 1000) *result* (let ((*result* (+ *result* x))) (rec-tes2 (+ x 1))))) CL-USER> (time (dotimes (i 100000) (rec-tes2 0))) ;took : 2.930 seconds of real ;time : 2.930000 seconds of total run time (2.930000 user, 0.000000 system)
- なぜか速度はちょっと速いみたいｗ
なんとなく高速性を求めてみる。
末尾再帰型
(defun rec-tes3 (x result) (if (= x 1000) result (rec-tes3 (+ x 1) (+ result x)))) CL-USER> (time (dotimes (i 100000) (rec-tes3 0 0))) ;took : 2.100 seconds of real ;time : 2.100000 seconds of total run time (2.100000 user, 0.000000 system)
組み込みのdotimes(もはや手続き)
(defun rec-tes4 (x) (progn (dotimes (i 1000) (setq x (+ x i))) x)) CL-USER> (time (dotimes (i 100000) (rec-tes4 0))) ;took : 0.870 seconds of real ;time : 0.870000 seconds of total run time (0.870000 user, 0.000000 system) ;disassembleしてみる CL-USER> (disassemble 'rec-tes4) ; 0B84EE61: 31F6 XOR ESI, ESI ; no-arg-parsing entry point ; 63: EB18 JMP L2 ; 65: L0: 8975F4 MOV [EBP-12], ESI ; 68: 8BD0 MOV EDX, EAX ; 6A: 8BFE MOV EDI, ESI ; 6C: E8D7127BF5 CALL #x1000148 ; GENERIC-+ ; 71: 7302 JNB L1 ; 73: 8BE3 MOV ESP, EBX ; 75: L1: 8BC2 MOV EAX, EDX ; 77: 8B75F4 MOV ESI, [EBP-12] ; 7A: 83C604 ADD ESI, 4 ; 7D: L2: 81FEA00F0000 CMP ESI, 4000 ; 83: 7CE0 JL L0 ; 85: 8BD0 MOV EDX, EAX ; 87: 8D65F8 LEA ESP, [EBP-8] ; 8A: F8 CLC ; 8B: 8B6DFC MOV EBP, [EBP-4] ; 8E: C20400 RET 4 ; 91: 90 NOP ; 92: 90 NOP ; 93: 90 NOP ; 94: 90 NOP ; 95: 90 NOP ; 96: 90 NOP ; 97: 90 NOP ; 98: CC0A BREAK 10 ; error trap ; 9A: 02 BYTE #X02 ; 9B: 18 BYTE #X18 ; INVALID-ARG-COUNT-ERROR ; 9C: 4D BYTE #X4D ; ECX ;
さらに高速化
型宣言をつける。
(defun rec-tes5 (x) (declare (optimize (speed 3) (safety 0))) (declare (fixnum x)) (progn (dotimes (i 1000) (setq x (the fixnum (+ x i)))) x)) CL-USER> (time (dotimes (i 100000) (rec-tes5 0))) ;took : 0.150 seconds of real ;time : 0.150000 seconds of total run time (0.150000 user, 0.000000 system) ;かなり速くなった。 ;初期と比べて20倍以上。 ;disassembleしてみる CL-USER> (disassemble 'rec-tes5) ; 0ABE96EC: 31C0 XOR EAX, EAX ; 6EE: EB05 JMP L1 ; 6F0: L0: 01C1 ADD ECX, EAX ; 6F2: 83C004 ADD EAX, 4 ; 6F5: L1: 3DA00F0000 CMP EAX, 4000 ; 6FA: 7CF4 JL L0 ; 6FC: 8BD1 MOV EDX, ECX ; 6FE: 8D65F8 LEA ESP, [EBP-8] ; 701: F8 CLC ; 702: 8B6DFC MOV EBP, [EBP-4] ; 705: C20400 RET 4 ;rec-tes4と同じアルゴリズムだがだいぶ小さくなってる。
#include <stdio.h> #include <time.h> long int rec_tes6(long int t){ int i = 0; while(i<1000){ t += i; i++; } return t; } int main(){ int i=0; clock_t t1; clock_t t2; t1 = clock(); while(i<100000){ long int x = rec_tes6(0); i++; } t2 = clock(); printf("time = %10.30f\n", (double)(((double)t2 - t1)/CLOCKS_PER_SEC)); return 0; }
- gccでコンパイル、実行。
$ gcc tes.c $ ./a.out time = 0.560000000000000053290705182008
- あれ？意外と遅い。
- lispのほうが4倍程度速い。
- アルゴリズムがまずいのかも。大体最速の書き方だと思うのだが･･･。
まとめ
- そういえばダイナミック変数について。
- ダイナミック変数束縛すると末尾再帰最適化がかからないみたいなので気をつける。
