--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/evaluations.tex	Tue Feb 16 14:35:36 2010 +0900
@@ -0,0 +1,457 @@
+\chapter{評価・考察}
+\label{chp:eval}
+
+本章では本研究の評価を行う。
+
+
+\section{本研究での改善による成果}
+本研究では、2008年に実装されたGCCベースコンパイラの改善を行った。
+まずはその改善による成果をここで述べる。
+
+\begin{description}
+  \item [並列代入] \hfill \\
+    並列代入の改善により、これまで存在した軽量継続の際のバグが取り除か
+    れた。特に引数で渡されたコードセグメントポインタへ継続する際に出て
+    いたバグに対する影響が大きい。
+  \item [環境付き継続の実装] \hfill \\
+    この実装により、Cとの互換性が確保できた。これにより名実ともにCwC 
+    コンパイラとして完成したと言える。
+  \item [PowerPCでの間接軽量継続] \hfill \\
+    これまで実質的にはPowerPCでは使用不能であった。
+
+    本研究室ではPS3を用いた研究も行っており、その研究ではPowerPCアーキ
+    テクチャが必要となる。この問題の解決により、当研究室の提案する
+    CeriumはCbCベースへの移行が可能になる。
+  \item [プトロタイプ宣言の自動生成] \hfill \\
+    GCCとmicro-cの間にある、コードセグメントの宣言に関する差異が、この
+    自動生成によって改善された。これにより、これまでmicro-c用に作成さ
+    れていたプログラムはほとんど修正することなく動く。
+  \item [x86でのfastcall] \hfill \\
+    未だに主流であるx86アーキテクチャ（x86\_64への移行は進みつつあるが
+    ）において、若干の速度低下が見られていたものを改善した。この測定に
+    ついては\ref{sec:evaluation}節で行う。
+\end{description}
+
+\section{GCCを使うことの利点・欠点}
+\label{sec:merit}
+
+これまでCbCのコンパイルに使用してきたmicro-cに対し、新しくGCCが
+CwCのフルセットとして使用可能となった。ここでGCCを用いることの利点と欠
+点について考察する。
+
+\subsection*{アーキテクチャ}
+
+micro-cにおいては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)を扱うことがよく
+あるため、共通式除去は非常に効果が高い。同様の効果は同じ式を保持する変
+数を用意することでも実現できるがソースコードの修正が必要になる。
+micro-cにはこの最適化は含まれていないため、複雑な計算式を含むプログラムにお
+いてはGCCの方が良いコンパイル結果を示すものと考えられる。
+
+%\ref{sec:}の性能評価では最適化の効果についても測定する。
+
+\subsection*{デバッガ}
+これまでCbCにはデバッガが存在しなかった。デバッガの実装には出力するア
+センブラに行番号や変数名、関数名などの情報を付加する必要があるが、GCC
+は標準でこれを行っている。そのためCのデバッガとして広く一般的に使われ
+ている gdbをそのままCbCのデバッガとして使用することが可能であり、ソフ
+トウェア開発の大きな助力となる。
+
+%ただし継続制御では``next''コマンドが使いづらいなどの操作性の問題がいく
+%つか確認している。これらは
+
+  %
+\subsection*{関数呼出しの名残り}
+上記の利点に対し、GCCであるゆえの欠点も存在する。
+
+本研究による軽量継続制御の実装には\ref{chp:impl}章で説明したように関数
+の末尾最適化を利用した。それゆえコードセグメントのアセンブラ出力の命令
+列には関数呼び出し時のスタック処理が一部残ってしまうことが分かっている。
+特にレジスタの少ないアーキテクチャ、x86などではそれが顕著に現れる。
+
+micro-cではコードセグメントと関数は完全に別物として取り扱っており、この様な
+スタック操作はコードセグメントには現れないため、このオーバヘッドがGCC
+では不利な点である。
+
+
+\subsection*{互換性、ABI}
+また、同じく関数呼び出しの名残りから、GCCではmicro-cとのバイナリレベル
+での互換性がない。つまりGCCでコンパイルしたコードセグメントからmicro-c
+でコンパイルしたコードセグメントに継続することはできない。
+
+これはmicro-cでの軽量継続のABIが関数とはまったく異なるものだからである
+。今回はtailcallを実装に用いたため、関数としての制限があり、micro-cの
+ABIに合わせることはできなかった。
+
+この問題はGCCの欠点というわけではないが、CbCベースの共有ライブラリを生
+成・使用する場合には注意が必要となる。
+
+
+
+
+\section{性能評価}\label{sec:evaluation}
+次にコンパイラの性能評価を行う。
+
+\subsection{評価項目、比較対象}
+コンパイラの出力した実行ファイルを複数回実行し、その実効速度を測定する
+。CbCは実用的なプログラムの記述を目的としているので、プログラムの動作
+速度は性能の評価として妥当だと考えられる。
+
+またもう一つの項目として、出力した実行ファイルのファイルサイズも評価す
+る。一般的なプログラムではファイルサイズを気にすることは少ないが、CbC
+の用途には組み込みなども考えられているため、ファイルサイズの影響は大き
+い。比較する際はstripコマンドを用いてデバグ情報等を取り除いている。
+
+実効速度、ファイルサイズの比較対象として2つ用意した。
+一つは過去の研究でのGCCベースコンパイラ、つまり今回の改善を含めてない
+ものである。こちらはGCCのバージョン4.2.3をベースとしている。
+
+もう一つの比較対象にはmicro-cベースのコンパイラを用いる。
+さらにGCCでは最適化による効果も評価するため、
+\begin{inparaenum}[\bfseries\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種別]を選択した。（ppcはPowerPCの意であ
+る）
+\begin{itemize}
+  \item ppc/OS X
+  \item ppc/linux
+  \item ppc/linux on PS3
+  \item x86/OS X
+  \item x86/linux
+\end{itemize}
+なお、micro-cは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}{*}{micro-c} \\ \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とmicro-cの速度比較（単位: 秒）}
+  \label{tab:speed-mc-vs-gcc}
+\end{table}
+
+実行ファイル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}{*}{micro-c} \\ \cline{2-5}
+              %& \multicolumn{2}{c|}{デバグ情報(-g)付き} & \multicolumn{2}{c|}{デバグ情報なし} &  \\ \cline{2-5}
+              %& 速度最適化 & サイズ最適化 & 速度最適化 & サイズ最適化 & \\ \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}{*}{micro-c} \\ \cline{2-3}
+              & 速度最適化 & サイズ最適化 & \\ \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
+              &  最適化なし  & 速度最適化 & 最適化なし & 速度最適化 \\ \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}
+
+
+\subsection{評価結果考察}
+% stripするとx86はサイズに変化がない
+\subsubsection{速度面}
+まずどのアーキテクチャにおいても、GCCの最適化が大きな速度差を生み出し
+ている事が分かる。最適化なしと速度最適化を比較すると、x86では2.4倍、
+ppcでは5〜7倍もの差が生じている。ただしppcのこの異常な速度差は
+\ref{sec:impl-parallel}並列代入で示した様に、継続の引数を全て一時変数
+に入れていることが大きい。その場合最適化なしではすべての引数を一度メモ
+リに確保するので、その分逆に遅くなっているのだと考えられる。しかしなが
+ら最適化を有効にすることでそのメモリへの一時変数の確保も解消されるとい
+うことが分かった。
+
+x86はOS XとLinuxの環境で測定を行った。速度最適化のGCCとmicro-cを比べる
+と、 OS Xではmicro-cに比べて20\%ほど早くなった事が分かる。しかし逆に
+Linux環境では6\%の速度低下が示された。どちらにしてもppcほどの良い結果
+ではない。これは自由に使えるレジスタが極めて少ないというx86の特殊なア
+ーキテクチャが要因だと考えられる。そのためGCCの最適化が十分に機能でき
+なかった可能性がある。この6\%の差は実用レベルでは問題なく、プログラム
+の構成によっては結果は逆転する事も十分にある。
+
+ppcにおいてはどのオペレーティングシステムでも、速度最適化を使ったGCCは
+micro-cに比べて早い事が分かる。いずれも約2倍、もしくはそれ以上に速度が
+向上している。これはGCCの最適化機構が十分に働いている要因が大きい。
+
+\subsubsection{アセンブラ比較}
+実際に出力されたアセンブラから速度向上の要因を確かめるため、quicksort 
+プログラムで使用されているコードセグメントを一つ例に挙げる。CbCのプロ
+グラムソースがコード \ref{code:divider-e}である。このコードセグメント
+の速度最適化を使ったGCCによる出力がコード\ref{code:divider-e-gcc}、
+micro-c による出力がコード \ref{code:divider-e-mc}である。どちらもアー
+キテクチャはppcである。
+
+\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のmicro-cによる出力(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| で行
+っている。 micro-cではこれが\verb|mr, addi, mr|という3命令になっている
+。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で
+ある。この様な細かい命令の展開が速度に差が出る要因である。
+
+またこのppcのアセンブラからも、x86での速度差が少ないことが頷ける。引数
+のほとんどをメモリに格納するx86では、計算のために一度レジスタに格納し
+ないといけないことから、この命令は結局3命令になるはずであり、実際にx86
+ではGCC, micro-c共にそのようなコードが出力されていた。
+
+この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度
+の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が
+言えるが、（手続きやメソッドにおける）前の環境を保持する必要がないCbC
+ではその影響がより強い。
+
+%レジスタの数は
+
+\subsubsection{ファイルサイズ}
+
+次に、実行ファイルのファイルサイズの面から考察する。
+
+実行ファイルのファイルサイズは組み込み用途のプログラムには重要な要素と
+なる。多くの場合、組み込み機器では大容量のメモリは用意されておらず、
+OSも存在しないため仮想記憶の概念がない。そのためメモリに乗り切らないプ
+ログラムはそもそも実行不能である。
+
+まず、評価の主な特徴として、strip後のファイルサイズ
+\ref{tab:eval-strip} をみると、x86ではmicro-cとGCCでほとんど差がない事
+が分かる。この環境では速度面でも大きな差はなく、micro-cの精度の良さが
+わかる。
+
+%デバグ情報のあり／なし／strip後との比較で大きな差が出ているのは全て
+%Linux（PS3含む）である。Linuxでは実行ファイルのファイル形式にELFを用い
+%ている。この形式はLinuxの標準的な実行形式で、様々な研究に用いられてい
+%るため、Mach-Oと比べて付加機能が豊富である。そのため多くの情報が含まれ
+%ているのだと考えられる。
+%Linuxは組み込み用途に多く用いられているため、極端にメモリの制限された
+%環境ではデバグが困難になることが考えられる。
+
+また興味深い特徴として、速度最適化とサイズ最適化の差がppc/PS3以外は全
+くないことも分かった。 サイズ最適化は速度最適化の最適化機能から、ファ
+イルサイズが大きくなるものを除外したものである。評価結果にはサイズ最適
+化によるファイルサイズの減少はほとんどなく、しかし速度は少々遅くなって
+いる。このことからCbCによるプログラムではサイズ最適化を用いる必要はな
+く、速度最適化で十分であることが分かった。
+
+
+% 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{メンテナンス性の向上に関する取り組み}\label{sec:mentainance}
+
+本研究室ではこれまでCbCコンパイラとしてmicro-cを利用していた。このコン
+パイラはベースとなるmicro-cには依存せずに、ほぼ独立な開発を続けている。
+
+これに対しGCCは現在も精力的に開発が続けられており、年数回のアップデー
+トではバグの除去や最適化の改善などが行われている。
+そのためCbCコンパイラでもそのリリースに沿ってアップデートすることが望
+ましく、実際に今回の改善の際にも2010年1月現在での最新リリースである
+4.4.2をベースとして行い、本稿執筆中に4.4.3へのアップデートが行われた。
+
+しかしアップデートの度に新しいソースコードを書き換えるのは無理があり、
+現実的ではない。最良の方法はGCCの正式な機能として開発リポジトリにマー
+ジしてもらうことだが、現段階ではそこには至っていない。
+
+そのため現在はMercurialを使ったソースコード管理を行っている。ここでは
+その手法を説明する。
+
+\subsection{二つのリポジトリ}
+Mercurialは分散型のバージョン管理システムである。
+開発環境毎に複数のリポジトリを分散して持つすることができ、そのためそれ
+ぞれのリポジトリのマージの機能に優れる。
+
+CbCコンパイラの管理ではこの特徴を利用する。
+具体的にはCbC開発用に二つのリポジトリを持つ。一つは本家のGCCリリースと
+まったく同一のソースをもったGCC-copyと言うリポジトリである。もう一つは
+この GCC-copyからブランチする形で作成したCbConGCCというリポジトリであ
+る。
+こちらがCbCに関するメインの開発環境となる。図\ref{fig:gcc-repository}
+では中央と右のラインがそのリポジトリを表している。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[width=.7\textwidth]{figures/gcc-repository.eps}
+  \end{center}
+  \caption{CbCコンパイラ開発でのリポジトリ管理（左が本家のリリースタイ
+  ムライン、中央がGCC-copy、右がCbCの開発用リポジトリのタイムライン）}
+  \label{fig:gcc-repository}
+\end{figure}
+
+新しいバージョンがリリースされた際のCbConGCCでのアップデートは次の手順
+で実現できる。
+\begin{itemize}
+  \item GCC-copyリポジトリにて
+    \begin{enumerate}
+      \item GCC-copyリポジトリ中のファイル全てを消す（バージョン管理情
+        報以外）
+      \item gcc-core-{\tt\it version}.tar.gzを展開し、全ファイルをGCC-copyに追加
+      \item \verb|hg status|で追加ファイル、削除ファイルを確認
+      \item コミット
+      \item gcc-{\tt\it version}タグの追加
+    \end{enumerate}
+  \item CbConGCCリポジトリにて
+    \begin{enumerate}
+      \item GCC-copyから\verb|pull|.
+      \item \verb|hg merge|でマージ実行
+      \item 衝突のあったファイルを修正
+      \item 実際にビルドしてテストファイルが動くことを確認
+      \item コミット
+      \item cbc-{\tt\it version}タグの追加
+    \end{enumerate}
+\end{itemize}
+
+以上でアップデートが完了する。
+
+\subsection{このリポジトリ管理方法の評価}
+
+実際にこのリポジトリ管理方法を用いてアップデートを行った。この評価では
+バージョン 4.4.0から4.4.2へのアップデートと、4.4.2から4.4.3へのアップ
+デートを行った。
+
+アップデートの際に何らかの問題が生じるのはCbConGCCリポジトリでの衝突フ
+ァイルの修正だけである。4.4.3へのアップデートでは特になにも衝突するこ
+とはなかったが、4.4.2ではある関数の引数が変わっており、その修正に手作
+業を要した。しかし複雑な作業はこの衝突ファイルの修正だけに抑えられる。
+
+この手法を用いず、これまでの様に一つのリポジトリのみで行っていた場合に
+は、本家GCCの新旧の差分をとるか、もしくは本家の旧GCCとCbCでの差分をと
+り、新しく適用する必要がある。この差分の取得はdiffを使って手動で行う必
+要があるが手順は非常に複雑になり、どこに問題が生じたかも判別しにくくな
+る。
+
+新しいリポジトリ管理方法ではdiffを用いた複雑な作業は必要なく、作業は衝
+突したファイルのみに抑えられる。これによりソースコードアップデートに関
+するメンテナンス性の向上が実現できた。
+
+
+
+