\chapter{評価・考察}
\label{chp:eval}

本章では本研究の評価を行う。
まず、gccでのCbCコンパイルにおける利点と欠点を考察する。
次にgccベースのCbCコンパイラの性能評価を行う。
最後に、\ref{chp:task}章のTaskManagerの開発を元に、CbC言語そのものの記述性、プログラミング手法などについて考察する。


\section{gccを使うことの利点・欠点}
\label{sec:merit}

これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくgccが
CwCのフルセットとして使用可能となった。ここでgccを用いることの利点と欠
点について考察する。

\subsection*{アーキテクチャ}

mcにおいてはPPC,x86,MIPS,ARM,SPUなど、多数のCPUアーキテクチャをサポー
トしてきた。しかしあるCPUに新しく対応するには多大な時間、労力が必要と
なる。
gccは現在、既に20を越えるCPUに対応しており、またOS毎のABIの差異も吸収
可能である。これはgccをコンパイラとすることに最大の利点である。

またそれだけでなく、gccは新しいアーキテクチャへの対応も早い。この特徴
は、gccがフロントエンドとバックエンドという形で言語実装とアーキテクチ
ャを分離していることからくる。一般的に新しいCPUアーキテクチャが開発さ
れた場合にはその開発者自身がgccにコミットすることが多いため、組み込み
用途を目的の一つとするCbCではよりその強みがます。

\subsection*{最適化の恩恵}
gccは豊富な最適化機構を備えている。
代表的な最適化だけでもループ最適化、分岐スレッディング(jump threading)
、共通式除去(common subexpression elimination)、命令スケジューリング
(instruction scheduling)などがある。

とくに、プログラムにおいては類似した形の式(expression)を扱うことがよく
あるため、共通式除去は非常に効果が高い。同様の効果は同じ式を保持する変
数を用意することでも実現できるがソースコードの修正が必要になる。
mcにはこの最適化は含まれていないため、複雑な計算式を含むプログラムにお
いてはgccの方が良いコンパイル結果を示すものと考えられる。

%\ref{sec:}の性能評価では最適化の効果についても測定する。

\subsection*{デバッガ}
これまでCbCにはデバッガが存在しなかった。デバッガの実装には出力するア
センブラに行番号や変数名、関数名などの情報を付加する必要があるが、gcc
は標準でこれを行っている。そのためCのデバッガとして広く一般的に使われ
ている gdbをそのままCbCのデバッガとして使用することが可能であり、ソフ
トウェア開発の大きな助力となる。

%ただし継続制御では``next''コマンドが使いづらいなどの操作性の問題がいく
%つか確認している。これらは

  %
\subsection*{関数呼出しの名残り}
上記の利点に対し、gccであるゆえの欠点も存在する。

本研究による軽量継続制御の実装には\ref{chp:impl}章で説明したように関数
の末尾最適化を利用した。それゆえコードセグメントのアセンブラ出力の命令
列には一部関数呼び出し時のスタック処理が残ってしまうことが分かっている。
特にレジスタの少ないアーキテクチャ、x86などではそれが顕著に現れる。

mcではコードセグメントと関数は完全に別物として取り扱っており、この様な
スタック操作はコードセグメントには現れないため、このオーバヘッドがgcc
では不利な点である。

% TODO: 取り除くには…

  % スタック処理が残ってしまう
  % 同じくcpuに特化したコンパイルに比べると


\subsection*{互換性、ABI}
%これは最後の考察に入れよう
ソースコードレベルでの互換性の問題がある。
また、継続制御のパラメタを
  % 関数宣言
  % 型推定
  % ABI、特にppc


% 最適化
% SPUでのベクトル演算
% gdb
% architecture

% 関数呼び出しのオーバヘッド
% 互換性,ソースコード、ABI





\section{性能評価}

\subsection{評価項目、比較対象}
コンパイラの出力した実行ファイルを複数回実行し、その実効速度を測定する
。CbCは実用的なプログラムの記述を目的としているので、プログラムの動作
速度は性能の評価として妥当だと考えられる。

またもう一つの項目として、出力した実行ファイルのファイルサイズも評価す
る。一般的なプログラムではファイルサイズを気にすることは少ないが、CbC
の用途には組み込みなども考えられているため、ファイルサイズの影響は大き
い。比較する際はstripコマンドを用いてデバグ情報等を取り除いている。
%SPUはm..

実効速度、ファイルサイズの比較対象として2つ用意した。
一つは過去の研究でのGCCベースコンパイラ、つまり今回の改善を含めてない
ものである。こちらはGCCのバージョン4.2.3をベースとしている。

もう一つの比較対象にはmicro-cベースのコンパイラ（以下mc）を用いる。
さらにGCCでは最適化による効果も評価するため、
\begin{inparaenum}[\itshape 1)\ttfamily]
  \item 最適化なし ``-O0''
  \item 速度最適化 ``-O2 -fomit-framepointer''
  \item サイズ最適化 ``-Os''
\end{inparaenum}
についてもそれぞれ比較する。

\subsection{評価手法と環境}
実行するプログラムとして、クイックソートのテストプログラムを作成した。
クイックソートは再帰呼び出しを伴うため、スタック操作が必須となる。その
ためより様々な状態でコードセグメントへの継続制御が使用されることになり、
CbCの性能評価に適していると考えられる。クイックソートはCbCに先立ってC
で実装し、参考文献\cite{bib:kinjo-2005}で紹介する手法を用いてCbCに変換
した。このプログラムは付録\ref{apx:quicksort}に添付する。

測定環境は両コンパイラが対応しているアーキテクチャ、OSから以下の5つの
組み合わせ[CPUアーキテクチャ/OS種別]を選択した。
\begin{itemize}
  \item ppc/OS X
  \item ppc/linux
  \item ppc/linux on PS3
  \item x86/OS X
  \item x86/linux
\end{itemize}
なお、mcはmips,armにも対応しているが、現在その処理系が用意できなかった
ので割愛している。また、GCC-4.2.3ベースコンパイラはppcでは実行不能であ
ったためx86のみとなる。

各評価マシンの詳細は付録\ref{sec:machine-specs}に掲載する。

%gccのコンパイルでは``-O2 -fomit-pointer''の最適化を付加して測定している。
% noreturnもON.
% x86ではfastcallもON,

\subsection{評価結果}
実効速度の測定結果を表\ref{tab:speed-mc-vs-gcc}に示す。
ただし環境毎にCPU速度は異なるので、上下の比較には意味はない。
% -O2で約10秒になる要素数を選んだ方がいいかもしれない
\begin{table}[htpb]
  \centering
  \begin{tabular}{|c|c|c|c|c|} \hline
    \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
              & \multicolumn{3}{c|}{gcc} & \multirow{2}{*}{mc} \\ \cline{2-4}
              &最適化なし&速度最適化&サイズ最適化&  \\ \hline
    x86/OS X  & 5.901 & 2.434 & 2.785 & 2.857 \\ \hline
    x86/Linux & 5.732 & 2.401 & 2.876 & 2.254 \\ \hline
    ppc/OS X  &14.875 & 2.146 & 2.170 & 4.811 \\ \hline
    ppc/Linux &19.793 & 3.955 & 4.013 & 6.454 \\ \hline
    ppc/PS3   &39.176 & 5.874 & 6.111 &11.121 \\ \hline
  \end{tabular}
  \caption{アーキテクチャ毎のgccとmcの速度比較（単位: 秒）}
  \label{tab:speed-mc-vs-gcc}
\end{table}

次に実行ファイルのstrip前のファイルサイズを表\ref{tab:eval-nostrip}
に、strip後のファイルサイズを表\ref{tab:eval-strip}に示す。

\begin{table}[htpb]
  \centering
  \begin{tabular}{|c|c|c|c|c|c|} \hline
    \multirow{3}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
              & \multicolumn{4}{c|}{GCC} & \multirow{3}{*}{mc} \\ \cline{2-5}
              & \multicolumn{2}{c|}{デバグ情報(-g)付き} & \multicolumn{2}{c|}{デバグ情報なし} &  \\ \cline{2-5}
              & -O2 & -Os & -O2 & -Os & \\ \hline
    x86/OS X  & 11100 & 11100 &  9804 &  9804 & 11136 \\ \hline
    x86/Linux & 18444 & 17310 &  8216 &  8214 &  9844 \\ \hline
    ppc/OS X  & 10392 & 10392 &  9172 &  9172 & 14396 \\ \hline
    ppc/Linux & 25138 & 23876 & 13030 & 13028 & 15453 \\ \hline
    ppc/PS3   & 22142 & 20452 &  9906 &  9672 & 15463 \\ \hline
  \end{tabular}
  \caption{実行ファイルのファイルサイズ比較 not stripped（単位: bytes）}
  \label{tab:eval-nostrip}
\end{table}
\begin{table}[htpb]
  \centering
  \begin{tabular}{|c|c|c|c|} \hline
    \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
              & \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{mc} \\ \cline{2-3}
              & -O2 & -Os & \\ \hline
    x86/OS X  &  9176 &  9176 &  9172 \\ \hline
    x86/Linux &  5752 &  5752 &  5796 \\ \hline
    ppc/OS X  &  8576 &  8576 & 12664 \\ \hline
    ppc/Linux & 10068 & 10068 &  9876 \\ \hline
    ppc/PS3   &  6960 &  6728 &  8636 \\ \hline
  \end{tabular}
  \caption{実行ファイルのファイルサイズ比較 stripped（単位: bytes）}
  \label{tab:eval-strip}
\end{table}

最後に、本研究での実装GCC-4.4.2と以前のバージョンGCC-4.2.3との比較を表
\ref{tab:speed-old-vs-new}に示す。こちらはx86のみ、最適化も-Osは対応し
ていない。
\begin{table}[htpb]
  \centering
  \begin{tabular}{|c|c|c|c|c|} \hline
    \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
              & \multicolumn{2}{c|}{CbC on GCC-4.4.2} &
              \multicolumn{2}{c|}{CbC on GCC-4.2.3} \\ \hline
              &  -O0  &  -O2  &  -O0  &  -O2  \\ \hline
    x86/OS X  & 5.907 & 2.434 & 4.668 & 3.048 \\ \hline
    x86/Linux & 5.715 & 2.401 & 4.525 & 2.851 \\ \hline
  \end{tabular}
  \caption{GCC-4.2.3ベースとGCC-4.4.2ベースの速度比較（単位: 秒）}
  \label{tab:speed-old-vs-new}
\end{table}


% ppcのが圧倒的に早い
% x86ではあまりさはでない
% 最適化が効いている
% TODO: ファイルサイズの比較
%       SPUに送るのに有利
% コンパイルにかかる時間？

\subsection{評価結果考察}
% stripするとx86はサイズに変化がない
\subsubsection{速度面}
まずは速度面からこの測定結果を考察する。

まずどのアーキテクチャにおいても、GCCの最適化が大きな速度差を生み出し
ている事が分かる。最適化なしと速度最適化を比較すると、x86では2.4倍、
ppcでは5〜7倍もの差が生じている。
ただしppcのこの以上な速度差は\ref{sec:impl-parallel}並列代入で示した様に、継続の引
数を全て一時変数に入れていることが大きい。その場合最適化なしではすべて
の引数を一度メモリに確保するので、その分逆に遅くなっているのだと考えら
れる。しかしながら最適化を有効にすることでそのメモリへの一時変数の確保
も解消されるということが分かった。

x86はOS XとLinuxの環境で測定を行った。速度最適化のGCCとmcを比べると、
OS Xではmcに比べて20\%ほど早くなった事が分かる。しかし逆にLinux環境で
は6\%の速度低下が示された。どちらにしてもppcほどの良い結果ではない。こ
れは自由に使えるレジスタが極めて少ないというx86の特殊なアーキテクチャ
が要因だと考えられる。そのためGCCの最適化が十分に機能できなかった可能
性がある。この6\%の差は実用レベルでは問題なく、プログラムの構成によっ
ては結果は逆転する事も十分にある。

ppcにおいてはどのオペレーティングシステムでも、速度最適化を使ったGCCは
mcに比べて早い事が分かる。いずれも約2倍、もしくはそれ以上に速度が向上
している。これはGCCの最適化機構が十分に働いている要因が大きい。

\subsubsection{アセンブラ比較}
実際に出力されたアセンブラから速度向上の要因を確かめるため、quicksort 
プログラムで使用されているコードセグメントを一つ例に挙げる。CbCのプロ
グラムソースがコード \ref{code:divider-e}である。このコードセグメント
の速度最適化を使ったGCCによる出力がコード\ref{code:divider-e-gcc}、mc
による出力がコード \ref{code:divider-e-mc}である。
どちらもアーキテクチャはppcである。

%まずどのアーキテクチャにおいてもgccの最適化の効果が大きいことが分かる
%。 x86では約2.5倍、ppcでは4~7倍もの差が生じている。ppcの方で異様に効果
%が高いように見えるのは、関数やコードセグメントの引数渡しがレジスタベー
%スのため、最適化なしの場合には無駄なメモリアクセスが生じているためであ
%る。

%x86はOS XとLinuxの環境で測定を行った。OS Xではmcに比べて20\%ほど早くな
%ったことが分かる。しかし逆にLinux環境では6\%の速度低下が示された。
%どちらにおいてもppcほどの良い結果ではない。これは自由に使えるレジスタ
%が極めて少ないというx86の特殊なアーキテクチャが要因だと考えられる。そ
%のためにgccの最適化が十分に働かなかった可能性がある。逆に言うとmcが高
%いレベルでx86のアセンブラ命令を実行しているともとれる。この6\%の差は実
%用レベルでは問題なく、プログラムの構成によっては結果は逆転する事も十分
%にある。

%ppcではどのオペレーティングシステムでもmcに比べてgccが早いことが分かる
%。いずれも約2倍近くあるいはそれ以上に速度が向上している。これはgccの最
%適化機構が十分に働いている要因が大きい。

%\subsubsection{アセンブラ比較}
%比較のため、quicksortプログラムで使われているコードセグメントを一つ例
%にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン
%トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー
%ド \ref{code:divider_s_mc} である。
%
\lstinputlisting[
  caption=quicksortプログラムで使われているコードセグメント,
  label=code:divider-e]
  {sources/divider-e.cbc}
\begin{minipage}[t]{.45\textwidth}
  \lstinputlisting[
    caption=divider\_eのgccによる出力(ppc),
    label=code:divider-e-gcc]
    {sources/divider-e-gcc.asm}
\end{minipage}
\hfill
\begin{minipage}[t]{.45\textwidth}
  \lstinputlisting[
    caption=divider\_eのmcによる出力(ppc),
    label=code:divider-e-mc]
    {sources/divider-e-mc.asm}
\end{minipage}

もっとも比較しやすい箇所は\verb|e-1|の処理である。
コード\ref{code:divider-e-gcc}のgccではこれを1命令の\verb|addi 5,5,-1| 
で行っている。 mcではこれが\verb|mr, addi, mr|という3命令になっている
。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で
ある。この様な細かい命令の展開が速度に差が出る要因である。

またこのppcのアセンブラからも、x86での速度差が少ないことが頷ける。引数
のほとんどをメモリに格納するx86では、計算のために一度レジスタに格納し
ないといけないことから、この命令は結局3命令になるはずであり、実際にx86
ではGCC,mc共にそのようなコードが出力されていた。

この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度
の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が
言えるが、（手続きやメソッドにおける）前の環境を保持する必要がないCbC
ではその影響がより強い。

%レジスタの数は

\subsubsection{ファイルサイズ}

次に、実行ファイルのファイルサイズの面から考察する。

実行ファイルのファイルサイズは組み込み用途のプログラムには重要な要素と
なる。多くの場合、組み込み機器では大容量のメモリは用意されておらず、
OSも存在しないため仮想記憶の概念がない。そのためメモリに乗り切らないプ
ログラムはそもそも実行不能である。

まず、評価の主な特徴として、strip後のファイルサイズ\ref{tab:eval-strip}
をみると、x86ではmcとGCCでほとんど差がない事が分かる。この環境では速度
面でも大きな差はなく、mcの精度の良さがわかる。

デバグ情報のあり／なし／strip後との比較で大きな差が出ているのは全て
Linux（PS3含む）である。Linuxでは実行ファイルのファイル形式にELFを用い
ている。この形式はLinuxの標準的な実行形式で、様々な研究に用いられてい
るため、Mach-Oと比べて付加機能が豊富である。そのため多くの情報が含まれ
ているのだと考えられる。
Linuxは組み込み用途に多く用いられているため、極端にメモリの制限された
環境ではデバグが困難になることが考えられる。

また興味深い特徴として、-O2と-Osの差がppc/PS3以外は全くないことも分か
った。 -Osは-O2の最適化機能から、ファイルサイズが大きくなるものを除外
したものである。評価結果には-Osによるファイルサイズの減少はほとんどな
く、しかし速度は少々遅くなっている。このことからCbCによるプログラムで
は-Osを用いる必要はなく、-O2で十分であることが分かった。


% ELF, Mach-O
% o OS Xはデバグ情報が少ない。逆か、ELFが多いのか
% o x86でほぼ同じサイズ
%   - mcがんばってる
% o -Osと-O2が変わらない、でも速度は-O2
% o PS3とLinuxで大きく違う
% 

\subsubsection{以前のバージョンとの速度比較}\label{sec:compare2old}

古いバージョンとの速度差についても考察を重ねる。
実行環境にppcが存在しないのは、\ref{sec:impl-indirect}節における問題の
ためである。今回用意したプログラムは間接継続を用いているため、古いバー
ジョンではバグにより実行できなかった。
また、速度向上に関する改善は\ref{sec:impl-fastcall}節におけるfastcall
の追加のみなであり、このfastcallはx86環境にしか影響しないはずである。

表を見ると、\verb|-O0|の場合は新バージョンの方が旧バージョンより遅くな
っているのが分かる。これは\ref{sec:impl-parallel}節の一時変数への退避
処理のためだと考えられる。この処理では、最適化により無駄なスタックへの
アクセスは排除されることを期待して実装していた。\verb|-O0|は最適化を行
わないので、この場合は逆に遅くなっている。これは予想通りの結果である。
しかし最適化を行った場合は新バージョンに劣化はない。したがって一時変数
への退避処理においては、期待通り無駄な命令は十分に排除されていることが
分かった。

また、それだけなら速度はほぼ同じ結果がでるところだが、ここではいずれの
環境でも新しいバージョンの方が速い。15~20\%ほど高速化していることがわ
かる。これは本研究で行った改善の一つ、fastcallの影響である。






\section{CbCでのプログラミング}

% TODO:


\section{バージョン管理}

% TODO: version management




\section{本研究における成果}
本研究では、これまでバグが多くプログラムの動作に問題のあった GCCベース
のCbCコンパイラを、実用的なプログラムが動くレベルまで改善することがで
きた。

2008年の研究にて、GCCベースのCbCコンパイラは一部実装されていた。
そして本研究により、そのコンパイラの改善が行われた。

\begin{itemize}
  \item CwCの全機能に対応
  \item 一部バグのあったアーキテクチャに対応
  \item バージョン管理の
  \item 宣言の簡略化
  \item 
\end{itemize}