Mercurial > hg > Papers > 2016 > kaito-master
view paper/chapter5.tex @ 12:a077276f53cc
add graph
author | Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 14 Feb 2016 05:26:19 +0900 |
parents | 571f9f8d99e1 |
children | 3afb4bfe1100 |
line wrap: on
line source
\chapter{評価・考察} 今回の研究で改良を行ったた LLVM/clang 上での CbC コンパイラの評価を試みる. 評価は, コンパイルして出力されたアセンブリコードの確認, 改良前の LLVM, 改良後の LLVM, Micro-C, GCC でコンパイルして得られたプログラムによる実行速度の比較, C で実装した類似のプログラムとの速度比較により行う. \section{アセンブリコードの評価} 以下のリスト \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 が正しく動作していることがわかる. \begin{lstlisting}[frame=lrbt,label=evalCbC,caption={コンパイル前}] __code f(int i,stack sp) { int k,j; k = 3+i; goto f_g0(i,k,sp); } \end{lstlisting} \begin{lstlisting}[frame=lrbt,label=evalAsmB,caption={omit leaf frame pointer 強制前}] _f: ## @f .cfi_startproc ## BB#0: ## %entry pushq %rbp Ltmp9: .cfi_def_cfa_offset 16 Ltmp10: .cfi_offset %rbp, -16 movq %rsp, %rbp Ltmp11: .cfi_def_cfa_register %rbp movl %edi, %eax addl $3, %eax movq %rsi, -8(%rbp) ## 8-byte Spill movl %eax, %esi movq -8(%rbp), %rdx ## 8-byte Reload popq %rbp jmp _f_g0 ## TAILCALL .cfi_endproc \end{lstlisting} \begin{lstlisting}[frame=lrbt,label=evalAsmA,caption={omit leaf frame pointer 強制後}] _f: ## @f .cfi_startproc ## BB#0: ## %entry subq $24, %rsp Ltmp9: .cfi_def_cfa_offset 32 movl %edi, %eax addl $3, %eax movq %rsi, 16(%rsp) ## 8-byte Spill movl %eax, %esi movq 16(%rsp), %rdx ## 8-byte Reload addq $24, %rsp jmp _f_g0 ## TAILCALL .cfi_endproc \end{lstlisting} \section{実行速度の評価} 今回測定に使用したプログラムは環境付き継続と計算を繰り返すプログラムである. \footnote{ ソースコードは付録に掲載する. } 測定は x86-84 アーキテクチャの OS X 上で行った. 表 \ref{result}, 図 \ref{fig:result} が測定結果である. \begin{table}[htpb] \centering \begin{tabular}{|l|r|} \hline LLVM/clang & 3.35 \\ \hline LLVM/clang -O2 & 1.30 \\ \hline LLVM/clang (old) & 23.30 \\ \hline Micro-C & 1.29 \\ \hline GCC & 14.73 \\ \hline GCC -O2 & 12.96 \\ \hline \end{tabular} \caption{Mac OS X での Micro-C, GCC, LLVM/clang の実行速度比較 (単位 : 秒)} \label{result} \end{table} \begin{figure}[htpb] \begin{center} \scalebox{0.65}{\includegraphics{fig/env.eps}} \end{center} \caption{Mac OS X での Micro-C, GCC, LLVM/clang の実行速度比較グラフ} \label{fig:result} \end{figure} 結果から、改良前の LLVM/clang とくらべて現在のものが最適化込みで 10 倍以上, 最適化を除いても 7 倍近い速度が出ていることがわかる. このことから通常の setjmp, longjmp の処理の重さが伺える. また, GCC のコンパイラの速度を大きく上回っていることから, nested function を用いた実装よりもこちらのほうが速いということがわかる. Micro-C コンパイラは直接アセンブラを生成しているので非常に高速であるが, 最適化を利用することで同等の速度が実現できている. \section{C, Scheme との比較} CbC と他の言語との比較を行う. 比較対象は構文が殆ど一緒である C, 継続を用いることのできる Scheme とした. Scheme のコンパイラには Chicken を使用した. %最初に比較に使用したプログラムはフィボナッチ数を求めるプログラムである. 50000000 番目のフィボナッチ数を再帰を用いて求めるよう記述したところ, C ではスタックオーバーフローにより正しく結果を求めることが出来なかった. 比較に使用したプログラムは四則演算を何度も繰り返し行うプログラムである. \footnote{ソースコードは付録に掲載する. } C はループにより計算を行い, CbC は goto による軽量継続を用いて計算を行う. 結果は以下のようになった. \begin{table}[htpb] \centering \begin{tabular}{|l|r|} \hline C & 4.85 \\ \hline CbC & 3.10 \\ \hline Scheme & 39.24 \\ \hline \end{tabular} \caption{Mac OS X での C, CbC, Scheme の実行速度比較 (単位 : 秒)} \label{comp} \end{table} \begin{figure}[htpb] \begin{center} \scalebox{0.55}{\includegraphics{fig/comp.eps}} \end{center} \caption{Mac OS X での C, CbC, Scheme の実行速度比較グラフ} \label{fig:comp} \end{figure} 結果より, CbC の軽量継続が関数呼び出しよりも高速であることがわかる. このことからも関数呼び出し, return の際に行われるスタック操作の処理の重さがわかるだろう. %Scheme は書き方が行けない気がする. というか比べるなら環境付き継続とcall/cc?