0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \chapter{評価・考察}
|
|
10
|
2 今回の研究で改良を行ったた LLVM/clang 上での CbC コンパイラの評価を試みる. 評価は, コンパイルして出力されたアセンブリコードの確認, 改良前の LLVM, 改良後の LLVM, Micro-C, GCC でコンパイルして得られたプログラムによる実行速度の比較, C で実装した類似のプログラムとの速度比較により行う.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 \section{アセンブリコードの評価}
|
|
8
|
4 以下のリスト \ref{evalCbC},\ref{evalAsmB}, \ref{evalAsmA} はそれぞれコンパイル前の CbC の code segment とコンパイル後のアセンブリコードを示している. リスト \ref{evalAsmB} は omit leaf frame pointer 強制前のアセンブリコード, リスト \ref{evalAsmA} は omit leaf frame pointer 強制後のアセンブリコードである. リスト \ref{evalAsmB} には push, pop 命令によるフレームポインタの操作が入っているのに対し, リスト \ref{evalAsmA} にはその操作がない. このことから, omit leaf frame pointer が正しく動作していることがわかる.
|
|
7
|
5 \begin{lstlisting}[frame=lrbt,label=evalCbC,caption={コンパイル前}]
|
|
|
6 __code f(int i,stack sp) {
|
|
|
7 int k,j;
|
|
|
8 k = 3+i;
|
|
|
9 goto f_g0(i,k,sp);
|
|
|
10 }
|
|
|
11 \end{lstlisting}
|
|
|
12
|
|
|
13 \begin{lstlisting}[frame=lrbt,label=evalAsmB,caption={omit leaf frame pointer 強制前}]
|
|
|
14 _f: ## @f
|
|
|
15 .cfi_startproc
|
|
|
16 ## BB#0: ## %entry
|
|
|
17 pushq %rbp
|
|
|
18 Ltmp9:
|
|
|
19 .cfi_def_cfa_offset 16
|
|
|
20 Ltmp10:
|
|
|
21 .cfi_offset %rbp, -16
|
|
|
22 movq %rsp, %rbp
|
|
|
23 Ltmp11:
|
|
|
24 .cfi_def_cfa_register %rbp
|
|
|
25 movl %edi, %eax
|
|
|
26 addl $3, %eax
|
|
|
27 movq %rsi, -8(%rbp) ## 8-byte Spill
|
|
|
28 movl %eax, %esi
|
|
|
29 movq -8(%rbp), %rdx ## 8-byte Reload
|
|
|
30 popq %rbp
|
|
|
31 jmp _f_g0 ## TAILCALL
|
|
|
32 .cfi_endproc
|
|
|
33 \end{lstlisting}
|
|
|
34
|
|
8
|
35 \begin{lstlisting}[frame=lrbt,label=evalAsmA,caption={omit leaf frame pointer 強制後}]
|
|
7
|
36 _f: ## @f
|
|
|
37 .cfi_startproc
|
|
|
38 ## BB#0: ## %entry
|
|
|
39 subq $24, %rsp
|
|
|
40 Ltmp9:
|
|
|
41 .cfi_def_cfa_offset 32
|
|
|
42 movl %edi, %eax
|
|
|
43 addl $3, %eax
|
|
|
44 movq %rsi, 16(%rsp) ## 8-byte Spill
|
|
|
45 movl %eax, %esi
|
|
|
46 movq 16(%rsp), %rdx ## 8-byte Reload
|
|
|
47 addq $24, %rsp
|
|
|
48 jmp _f_g0 ## TAILCALL
|
|
|
49 .cfi_endproc
|
|
|
50 \end{lstlisting}
|
|
|
51
|
|
8
|
52 \section{実行速度の評価}
|
|
17
|
53 今回測定に使用したプログラムは環境付き継続と計算を繰り返すプログラムである(リスト \ref{gotowithenv}). 測定は x86-84 アーキテクチャの OS X 上で行った. 表 \ref{result} が測定結果である.
|
|
|
54
|
|
|
55 \begin{lstlisting}[frame=lrbt,label=gotowithenv,caption={環境付き継続を繰り返すプログラム}]
|
|
|
56 #define LOOP 50000000
|
|
|
57
|
|
|
58 #include <stdio.h>
|
|
|
59
|
|
|
60 __code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env);
|
|
|
61
|
|
|
62 __code factorial(int n,int result,int orig,__code(*print)(int,int,int,__code(*)(),__code(*)(),void*),__code(*exit1)(int,void *), void *exit1env)
|
|
|
63 {
|
|
|
64 if (n<0) {
|
|
|
65 printf("#0008:err %d!\n",n);
|
|
|
66 goto (*exit1)(0,exit1env);
|
|
|
67 }
|
|
|
68 if (n==0)
|
|
|
69 goto (*print)(n,result,orig,print,exit1,exit1env);
|
|
|
70 else {
|
|
|
71 result += n;
|
|
|
72 n--;
|
|
|
73 goto factorial(n,result,orig,print,exit1,exit1env);
|
|
|
74 }
|
|
|
75 }
|
|
|
76
|
|
|
77
|
|
|
78 int calc(int n){
|
|
|
79 __code (*ret)(int,void *) = __return;
|
|
|
80 void* env = __environment;
|
|
|
81 goto factorial(n,1,n,print,ret,env);
|
|
|
82 return 0;
|
|
|
83 }
|
|
|
84
|
|
|
85 int main( int ac, char *av[])
|
|
|
86 {
|
|
|
87 int i;
|
|
|
88 long ans;
|
|
|
89 for(i=LOOP,ans=0;i>0;i--){
|
|
|
90 ans += calc(10);
|
|
|
91 }
|
|
|
92
|
|
|
93 printf("%ld\n",ans);
|
|
|
94 }
|
|
|
95
|
|
|
96 __code print(int n,int result,int orig,__code(*print)(),__code (*exit1)(int, void*),void*exit1env)
|
|
|
97 {
|
|
|
98 goto (*exit1)(result,exit1env);
|
|
|
99 }
|
|
|
100 \end{lstlisting}
|
|
|
101
|
|
10
|
102 \begin{table}[htpb]
|
|
|
103 \centering
|
|
|
104 \begin{tabular}{|l|r|} \hline
|
|
17
|
105 コンパイラ名 & 実行速度 (s) \\ \hline
|
|
10
|
106 LLVM/clang & 3.35 \\ \hline
|
|
|
107 LLVM/clang -O2 & 1.30 \\ \hline
|
|
|
108 LLVM/clang (old) & 23.30 \\ \hline
|
|
|
109 Micro-C & 1.29 \\ \hline
|
|
|
110 GCC & 14.73 \\ \hline
|
|
|
111 GCC -O2 & 12.96 \\ \hline
|
|
|
112 \end{tabular}
|
|
17
|
113 \caption{Mac OS X での Micro-C, GCC, LLVM/clang の環境付き継続の速度比較}
|
|
10
|
114 \label{result}
|
|
|
115 \end{table}
|
|
|
116
|
|
|
117
|
|
|
118 結果から、改良前の LLVM/clang とくらべて現在のものが最適化込みで 10 倍以上, 最適化を除いても 7 倍近い速度が出ていることがわかる. このことから通常の setjmp, longjmp の処理の重さが伺える. また, GCC のコンパイラの速度を大きく上回っていることから, nested function を用いた実装よりもこちらのほうが速いということがわかる. Micro-C コンパイラは直接アセンブラを生成しているので非常に高速であるが, 最適化を利用することで同等の速度が実現できている.
|
|
|
119
|
|
|
120 \section{C, Scheme との比較}
|
|
17
|
121 CbC と他の言語との比較を行う. 比較対象は C, 継続を用いることのできる Scheme とした. Scheme のコンパイラには Chicken を使用した.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122
|
|
17
|
123 比較に使用したプログラムは C の関数呼び出し, CbC の軽量継続, Scheme の継続 を繰り返し行うものである (リスト \ref{calc}, \ref{calcCbC}, \ref{calcScheme}).
|
|
10
|
124
|
|
|
125 結果は以下のようになった.
|
|
|
126
|
|
17
|
127 \begin{lstlisting}[frame=lrbt,label=calc,caption={Cの計測用コード}]
|
|
|
128 #define LOOP 500000000
|
|
|
129
|
|
|
130 #include <stdio.h>
|
|
|
131 #include <stdlib.h>
|
|
|
132
|
|
|
133 int func4(int a, int b){
|
|
|
134 return a+b;
|
|
|
135 }
|
|
|
136
|
|
|
137 int func3(int a, int b){
|
|
|
138 return func4(b,b/a);
|
|
|
139 }
|
|
|
140
|
|
|
141 int func2(int a, int b){
|
|
|
142 return func3(b,a*b);
|
|
|
143 }
|
|
|
144
|
|
|
145 int func1(int a, int b){
|
|
|
146 return func2(b,a+b);
|
|
|
147 }
|
|
|
148
|
|
|
149 int start_func(int loop){
|
|
|
150 int i, a;
|
|
|
151 a = 0;
|
|
|
152 for (i=0;i<loop;i++)
|
|
|
153 a += func1(1,2);
|
|
|
154 return a;
|
|
|
155 }
|
|
|
156
|
|
|
157 int main( int ac, char *av[]){
|
|
|
158 printf("%d\n",start_func(LOOP));
|
|
|
159 return 0;
|
|
|
160 }
|
|
|
161 \end{lstlisting}
|
|
|
162
|
|
|
163 \begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCの計測用コード}]
|
|
|
164 #define LOOP 500000000
|
|
|
165
|
|
|
166 #include <stdio.h>
|
|
|
167 #include <stdlib.h>
|
|
|
168
|
|
|
169 __code code4(int a, int b, int loop, int ans){
|
|
|
170 goto start_code(ans+a+b, loop-1);
|
|
|
171 }
|
|
|
172
|
|
|
173 __code code3(int a, int b, int loop, int ans){
|
|
|
174 goto code4(b,b/a,loop, ans);
|
|
|
175 }
|
|
|
176
|
|
|
177 __code code2(int a, int b, int loop, int ans){
|
|
|
178 goto code3(b,a*b,loop, ans);
|
|
|
179 }
|
|
|
180
|
|
|
181 __code code1(int a, int b, int loop, int ans){
|
|
|
182 goto code2(b,a+b,loop, ans);
|
|
|
183 }
|
|
|
184
|
|
|
185 __code start_code(int ans, int loop){
|
|
|
186 if (loop>0)
|
|
|
187 goto code1(1,2,loop, ans);
|
|
|
188 else
|
|
|
189 goto print(ans);
|
|
|
190 }
|
|
|
191
|
|
|
192 int main( int ac, char *av[]){
|
|
|
193 goto start_code(0,LOOP);
|
|
|
194 return 0;
|
|
|
195 }
|
|
|
196
|
|
|
197 __code print(int a){
|
|
|
198 printf("%d\n",a);
|
|
|
199 exit(0);
|
|
|
200 }
|
|
|
201 \end{lstlisting}
|
|
|
202
|
|
|
203 \begin{lstlisting}[frame=lrbt,label=calcScheme,caption={Schemeの測定用コード}]
|
|
|
204 (define LOOP 500000000)
|
|
|
205
|
|
|
206 (define (print_ans ans)
|
|
|
207 (print ans))
|
|
|
208
|
|
|
209 (define (code4 a b loop ans)
|
|
|
210 (start_code (+ ans (+ a b)) (- loop 1)))
|
|
|
211
|
|
|
212 (define (code3 a b loop ans)
|
|
|
213 (code4 b (/ b a) loop ans))
|
|
|
214
|
|
|
215 (define (code2 a b loop ans)
|
|
|
216 (code3 b (* a b) loop ans))
|
|
|
217
|
|
|
218 (define (code1 a b loop ans)
|
|
|
219 (code2 b (+ a b) loop ans))
|
|
|
220
|
|
|
221 (define (start_code ans loop)
|
|
|
222 (if (> loop 0) (code1 1 2 loop ans) (print_ans ans) ))
|
|
|
223
|
|
|
224 (start_code 0 LOOP)
|
|
|
225 \end{lstlisting}
|
|
|
226
|
|
10
|
227 \begin{table}[htpb]
|
|
|
228 \centering
|
|
|
229 \begin{tabular}{|l|r|} \hline
|
|
17
|
230 言語 & 実行速度 (s) \\ \hline
|
|
10
|
231 C & 4.85 \\ \hline
|
|
|
232 CbC & 3.10 \\ \hline
|
|
|
233 Scheme & 39.24 \\ \hline
|
|
|
234 \end{tabular}
|
|
17
|
235 \caption{Mac OS X での C, CbC, Scheme の実行速度比較}
|
|
12
|
236 \label{comp}
|
|
10
|
237 \end{table}
|
|
|
238
|
|
12
|
239 結果より, CbC の軽量継続が関数呼び出しよりも高速であることがわかる. このことからも関数呼び出し, return の際に行われるスタック操作の処理の重さがわかるだろう.
|
