\chapter{性能評価}\label{ch:bench}
本章では、非破壊的木構造データベース Jungle がマルチコアプロセッサで性能向上を果たせるのか確認する。
まずはじめに、並列読み込みと並列書き込みの性能の計測を行う。
また、掲示板ウェブアプリケーションを作成し、Java を用いた非破壊的木構造データベースとの性能比較を行う。

\section{計測環境}
マルチコアプロセッサでの性能を確認するためコア数の多いサーバを用いる。
本研究では、学科が提供するブレードサーバを用いて、計測環境を構築する。
ブレードサーバの仕様を表\ref{tab:server_spec}に示す。

\begin{table}[!htbp]
\caption{学科が提供するブレードサーバの仕様}
\label{tab:server_spec}
\begin{center}
\begin{tabular}{|c||c|} \hline
名前 & 概要 \\ \hline \hline
CPU & Intel(R) Xeon(R) CPU X5650@2.67GHz * 2\\ \hline
物理コア数 & 12 \\ \hline
論理コア数 & 24 \\ \hline
Memory & 126GB \\ \hline
OS & Fedora 14 \\ \hline
\end{tabular}
\end{center}
\end{table}

非破壊的木構造データベース Jungle の並列読み込みと並列書き込みの性能の計測には１台、
掲示板ウェブアプリケーションを用いた Java との性能比較には２台のブレードサーバを利用する。
２台使用するのは、サーバと負荷をかけるクライアントを別々に実行するためである。

\subsubsection{Haskell および Java のバージョン}
Haskell のコンパイラには The Glasgow Haskell Compiler（GHC）を使用する。
GHC は、Haskell で最も広く使われているコンパイラである。
ソフトウェア・トランザクショナル・メモリをサポートするなど、並列プログラミングのためのHaskellの拡張が行われている。

Haskell および Java のバージョンを表\ref{tab:compiler}に示す。

\begin{table}[!ht]
\caption{ベンチマークで利用したHaskellとJavaのバージョン}
\label{tab:compiler}
\begin{center}
\begin{tabular}{|c||c|} \hline
言語 & バージョン \\ \hline \hline
Haskell & Glasgow Haskell Compiler, Version 7.6.3 \\ \hline
Java & Java(TM) SE Runtime Environment (build 1.7.0\_51-b13) \\ \hline
\end{tabular}
\end{center}
\end{table}

計測環境の構築方法については付録に記載する。


\section{読み込みの性能計測}
非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に読み込みを行い、線形に性能向上ができるか調査する。

\subsubsection{計測方法}
ブレードサーバ上で、Jungle で作成した木構造を並列に読み込んで性能計測を行う。
まず、Jungle を利用して木構造を作成する。
並列に実行する際に、読み込みに負荷がかかるように木構造はある程度の大きさとする。
今回は木の深さが 8、ノードの数が約 80 万の大きさの木構造を使用する。

木構造を読み込み、ノードの数を数えるタスクを 1,000 個作成し並列実行する。
非破壊的木構造は、木構造に変更を加えても他の読み込みのタスクに影響を与えない。
そのことを確認するために、木構造は各タスクに渡す前に無作為にノードを追加する。

\subsubsection{計測結果}
非破壊的木構造データベース Jungle の読み込みの計測結果を表\ref{tab:par_read}に示す。

CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。
シングルスレッドで実行した場合と比較して、2 スレッドで 1.79 倍、12 スレッドで 10.77 倍の性能向上が見られる。
13 スレッド以上は、Intel のハイパースレッディング機能を利用して計測した。
ハイパースレッディングは、１つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術である。
同時に演算器などを利用することはできないため性能が２倍になるわけではないが、概ね20 \%程度クロックあたりの性能が向上すると言われている。
実際の計測では、13 スレッド以上は、12スレッドより速くなることもあるが、遅くなる場合もあるなど安定しない結果となっている。


\begin{table}[!htbp]
\caption{読み込みの計測結果}
\label{tab:par_read}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 59.77 s\\ \hline
2 & 33.36 s\\ \hline
4 & 15.63 s\\ \hline
8 & 8.10 s\\ \hline
12 & 5.55 s\\ \hline
16 & 5.65 s\\ \hline
20 & 5.23 s\\ \hline
24 & 5.77 s\\ \hline
\end{tabular}
\end{center}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_read}に示す。
線形に近い形で性能が向上していることが分かる。
12 スレッドで実行した場合の並列化率は 98.96 \%で、非破壊的木構造データベース Jungle は読み込みにおいてスケールするデータベースであることが分かる。

\begin{figure}[!htbp]
 \caption{読み込みの性能向上率}
 \begin{center}
  \includegraphics[width=90mm]{./images/read.pdf}
 \end{center}
 \label{fig:benchmark_read}
\end{figure}

\clearpage
\section{書き込みの性能計測}
非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に書き込みを行い、線形に性能向上ができるか調査する。

\subsubsection{計測方法}
ブレードサーバ上で、Jungle に木構造を並列に書き込んで性能計測を行う。
木の深さが 6、ノードの数が約 1 万の大きさの木構造を作成しJungle に登録するタスクを 1,000 個作成し、並列に実行する。
書き込んだ木構造はノードの数が整合しているかどうか確認する。その後正確に書き込まれてるタスクの数を出力する。
Haskell は遅延評価のため、出力などを挟むことで評価が行われるようにしなければならない。

\subsubsection{計測結果}
非破壊的木構造データベース Jungle の書き込みの計測結果を表\ref{tab:par_write}に示す。

CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。
シングルスレッドで実行した場合と比較して、2 スレッドで 1.55 倍、12 スレッドで 3.86 倍の性能向上が見られる。
読み込みと比べ、書き込みはJungleへの登録作業があるため並列化率が下がり、性能向上率が低いことが分かる。

ハイパースレッディングは効果がなく、13 スレッド以上では実行時間が遅くなっている。


\begin{table}[!htbp]
\caption{書き込みの計測結果}
\label{tab:par_write}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 52.68 s\\ \hline
2 & 33.92 s\\ \hline
4 & 20.11 s\\ \hline
8 & 15.31 s\\ \hline
12 & 13.62 s\\ \hline
16 & 14.92 s\\ \hline
20 & 18.62 s\\ \hline
24 & 16.63 s\\ \hline
\end{tabular}
\end{center}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_write}に示す。
書き込みは並列化率が低く、性能向上が 4 倍程度で止まっている。
12 スレッドで実行した場合の並列化率は 80.8 \%である。

\newpage
\begin{figure}[!htbp]
 \caption{書き込みの性能向上率}
 \begin{center}
  \includegraphics[width=90mm]{./images/write.pdf}
 \end{center}
 \label{fig:benchmark_write}
\end{figure}

Jungle へ登録する際に他のスレッドから登録があった場合に、ソフトウェア・トランザクショナル・メモリが処理をやり直すため、並列度が下がっていると思われるが、GHCの問題も考えられる。
GHC の IO マネージャーは、マルチスレッドでうまくスケールしないという問題があり、並列度が下がってしまう。
GHCの次期バージョンではIO マネージャーが改善され、スケールするようになる見込みである\cite{iomanager}。

非破壊的木構造データベース Jungle は、書き込みは並列化率が低くなってしまっている。
読み込みが高速なため、書き込みより読み込みが多用されるシステムに向いているといえる。

\clearpage

\section{ウェブアプリケーションに組み込んでの性能評価}
実用的なウェブアプリケーションに組み込んで、妥当な性能が出るか調査を行う。

\subsection{掲示板ウェブアプリケーションの実装}
木構造データベース Jungle と Haskell の HTTP サーバ Warp を用いて掲示板ウェブアプリケーションを開発する。
Warp を用いたウェブアプリケーションの構築法については付録に記載する。

掲示板におけるデータベースへの書き込みは、板の作成と、板への書き込みがある。
Jungle において、板の作成は新しい木構造の作成、板への書き込みは木構造へのノードの追加で表現する。
掲示板へ実装した機能を表\ref{tab:bbs_func}に示す。

\begin{table}[!htbp]
\caption{掲示板ウェブアプリケーションへ実装した機能一覧}
\label{tab:bbs_func}
\begin{center}
\begin{tabular}{|c||c|} \hline
  関数名 & 概要 \\ \hline \hline
  showBoard & 板の一覧を表示 \\ \hline
  createBoard & 板の作成 \\ \hline
  showBoardMessage & 板への書き込みの一覧を表示 \\ \hline
  createBoardMessage & 板への書き込み \\ \hline
  editMessage & 板への書き込みの編集 \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{読み込み}
\subsubsection{計測方法}
掲示板に対して読み込みを行い、負荷をかける。
掲示板を立ち上げるサーバと、性能測定ツール weighttp\cite{weighttp} を用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。

weighttpの設定は、リクエストの総数 100 万、同時に接続するコネクションの数 1,000、実行時のスレッド数 10、HTTP Keep-Alivesを有効とする。

HTTP サーバ Warp は、ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため、12 スレッドまでの計測とする。

\subsubsection{計測結果}

掲示板の読み込みの計測結果を表\ref{tab:bbs_read}に示す。

並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。
これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。

Warp を用いてアクセスした際に、"hello, world"と返すだけのプログラムを作成し測定する。
結果を表\ref{tab:warp}に示す。
1 スレッドで実行した場合は、Jungle と組み合わせた掲示板より速い。
しかしながら、スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう。
Warpは、HTTP サーバのため IO 処理を多用する。この問題は、GHC の IO マネージャーの改良で改善される可能性が高い。

\begin{table}[!htbp]
\caption{掲示板を利用した読み込みの計測結果}
\label{tab:bbs_read}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 60.72 s\\ \hline
2 & 37.74 s\\ \hline
4 & 28.97 s\\ \hline
8 & 27.73 s\\ \hline
12 & 28.33 s\\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[!htbp]
\caption{Warpの計測結果}
\label{tab:warp}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 49.28 s\\ \hline
2 & 35.45 s\\ \hline
4 & 25.70 s\\ \hline
8 & 27.90 s\\ \hline
12 & 29.23 s\\ \hline
\end{tabular}
\end{center}
\end{table}

ウェブアプリケーションを用いて実験する場合、データベースだけがボトルネックとなるように負荷をかけるのは難しい。
ただ単にデータを大きくするだけでは、文字列をHTMLに変換するコストが大きくなってしまうためである。

\subsection{書き込み}
\subsubsection{計測方法}
掲示板に対して書き込みを行い、負荷をかける。
掲示板を立ち上げるサーバと、weighttpを用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。

weighttpでは、GET しかできないためURLのクエリ文字列でデータを書き込めるように掲示板ウェブアプリケーションを変更した。
weighttp起動時のオプションは、読み込みと同じである。
\subsubsection{計測結果}

掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す。
並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。
これも HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。

\begin{table}[!htbp]
\caption{掲示板を利用した書き込みの計測結果}
\label{tab:bbs_write}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 54.16 s\\ \hline
2 & 36.71 s\\ \hline
4 & 31.74 s\\ \hline
8 & 31.58 s\\ \hline
10 & 32.64 s\\ \hline
12 & 32.68 s\\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Javaを用いた非破壊的木構造データベースとの比較}
非破壊的木構造データベースは、Haskell 版と Java 版の2つ存在する。
掲示板ウェブアプリケーションを両方の言語で実装し、比較を行う。
Haskell ではフロントエンドとして Warp を利用したが、Java では Jetty を利用する。
Jetty のバージョンは 6.1.26 を用いる。

Haskell 版と Java 版の掲示板ウェブアプリケーションをブレードサーバ上で実行し、
weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する。
Haskell と Java の測定結果を表\ref{tab:compare}に示す。

\begin{table}[!htbp]
\caption{HaskellとJavaの比較}
\label{tab:compare}
\begin{center}
\begin{tabular}{|c||r|r|} \hline
  測定 & Haskell & Java \\ \hline \hline
  読み込み & 28.33 s & 53.13 s \\ \hline
  書き込み & 32.68 s & 76.4 s \\ \hline
\end{tabular}
\end{center}
\end{table}

Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能が出ている。

書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。
Haskell では書き込みを行う際、完全に評価せず thunk として積み上げていく。
thunkとは、未評価の式を追跡するのに使われるものである。
遅延評価は、グラフ簡約があるため先行評価より簡約ステップ数が増えることはない。
また、不要な計算が省かれるので簡約ステップ数が少なくなることもある。
しかしながら、計算の所用領域が増えてしまうのが難点で、
ハードウェアが効率的に利用できるメモリの範囲内に収まらなければ即時評価より実行時間が遅くなってしまうことがあるので注意が必要である。
本実験では、潤沢にメモリを割り当てているためそういった問題は起きない。