\chapter{性能評価}\label{ch:bench}
本章では, 非破壊的木構造データベース Jungle がマルチコアプロセッサで性能向上を果たせるのか確認する. 
また, 実用的なWebサービスが提供できるのか確認するために Web 掲示板サービスを開発し, Java との比較を行う. 

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

論理コアは, Intel のハイパースレッディング機能のことである. 
ハイパースレッディングは, １つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術であり, 
同時に演算器などを利用することはできないため性能が２倍になるわけではないが, 概ね20 \%程度クロックあたりの性能が向上すると言われている. 

\begin{table}[!htbp]
\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 19 \\ \hline
\end{tabular}
\end{center}
\caption{学科が提供するブレードサーバの仕様}
\label{tab:server_spec}
\end{table}

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

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

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

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

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


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

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

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

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

CPUコア数を増やしていくと, 実行時間が短くなっていることが分かる. 
シングルスレッドで実行した場合と比較して, 2 スレッドで 1.97 倍, 12 スレッドで 7.17 倍の性能向上が見られる. 
13スレッド以上のハイパースレッディングを用いた計測は, 16スレッド実行時に実行時間が最も短くなる.
しかし, それ以降遅くなったりするなど安定しない結果となっている.

Haskell では並列実行時にOSの親和性機能を使ってOSスレッドをCPUコアに固定することができる.
OSスレッドをCPUコアに固定するには, 実行時に-qaオプションを付けてプログラムを起動する.
OSの親和性機能を使った場合、2 スレッドで 1.80 倍, 12 スレッドで 10.37 倍の性能向上が見られ, 12スレッド時の性能向上率が大幅に伸びている.
並列に読み込む場合、スレッドを同じプロセッサ上で実行させると性能が向上することがわかる.
しかし、24 スレッドで実行する場合、実行時間が大幅に伸びている.
スレッドがCPUに固定されるため, 性能計測以外のプログラムが実行される場合にうまくスケジューリングが行われないためだと考えられる.

\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||r|r|} \hline
  CPU数 & 通常実行 & qaオプションあり\\ \hline
  1 & 60.95 s & \\ 61.00 s \hline
  2 & 30.83 s & \\ 33.95 s \hline
  4 & 15.49 s & \\ 16.10 s \hline
  8 & 10.31 s & \\ 8.79 s \hline
  12 & 8.49 s & \\ 5.88 s \hline
  16 & 5.82 s & \\ 5.81 s \hline
  20 & 6.54 s & \\ 5.48 s \hline
  24 & 8.21 s & \\ 125.09 s \hline
\end{tabular}
\end{center}
\caption{読み込みの計測結果}
\label{tab:par_read}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_read}に示す. 
線形に近い形で性能が向上していることが分かる. 
非破壊的木構造データベース Jungle は読み込みにおいてスケールするデータベースであることが分かる. 

\begin{figure}[!htbp]
  \begin{center}
    \includegraphics[width=90mm]{./images/read.pdf}
  \end{center}
  \caption{読み込みの性能向上率}
  \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]
\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}
\caption{書き込みの計測結果}
\label{tab:par_write}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_write}に示す. 
書き込みは性能向上率が低いことが分かる. 

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

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

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

\clearpage

\section{Web サービスに組み込んでの性能評価}
並列データベース Jungle が実用的なWeb サービスを提供できるのか調査する. 
Web掲示板サービスに組み込んで, 性能測定を行った. 

\subsection{Web 掲示板サービスの実装}
木構造データベース Jungle と Haskell の HTTP サーバ Warp\cite{warp} を用いて Web 掲示板サービスを開発する. 
Warp を用いたWeb サービスの構築法については付録に記載する. 
Warp は, ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため, 12 スレッドまでの計測とする. 

Warp は並列に実行可能であり, 並列に実行している Warp に対して, Jungle を繋げるだけで Jungle を並列に動かすことができる. 
掲示板におけるデータベースへの書き込みは, 板の作成と, 板への書き込みがある. 
Jungle において, 板の作成は新しい木構造の作成, 板への書き込みは木構造へのノードの追加で表現する. 
掲示板へ実装した機能を表\ref{tab:bbs_func}に示す. 

\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||c|} \hline
  関数名 & 概要 \\ \hline \hline
  showBoard & 板の一覧を表示 \\ \hline
  createBoard & 板の作成 \\ \hline
  showBoardMessage & 板への書き込みの一覧を表示 \\ \hline
  createBoardMessage & 板への書き込み \\ \hline
  editMessage & 板への書き込みの編集 \\ \hline
\end{tabular}
\end{center}
\caption{Web掲示板サービスへ実装した機能一覧}
\label{tab:bbs_func}
\end{table}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=90mm]{./images/request.pdf}
 \end{center}
 \caption{Warp を用いたWeb掲示板サービス}
 \label{fig:request}
\end{figure}


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

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

\subsubsection{計測結果}

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

並列で実行した場合, 実行時間が短くなっているが性能向上率が低いことが分かる. 
シングルスレッドで実行した場合と比較して, 12 スレッドで 2.14 倍の性能向上が見られる. 
これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる. 

Warp のボトルネックがどれぐらいあるのか調査するために, アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する. 
結果を表\ref{tab:warp}に示す. 
1 スレッドで実行した場合は, Jungle と組み合わせた掲示板より速い. 
しかし, スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう. 
Warp は現状あまり並列化効果がでていない. 

\begin{table}[!htbp]
\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}
\caption{掲示板を利用した読み込みの計測結果}
\label{tab:bbs_read}
\end{table}

\begin{table}[!htbp]
\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}
\caption{Warpの計測結果}
\label{tab:warp}
\end{table}

Web サービスを用いて実験する場合, データベースだけがボトルネックとなるように負荷をかけるのは難しい. 
ただ単にデータを大きくするだけでは, 文字列をHTMLに変換するコストが大きくなってしまうためである. 

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

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

掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す. 
並列で実行した場合, 実行時間が短くなっているが性能向上率が低いことが分かる. 
シングルスレッドで実行した場合と比較して, 12 スレッドで 1.65 倍の性能向上が見られる. 
読み込みに比べて, 書き込みのほうが全体的に遅くなっている. 

\begin{table}[!htbp]
\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}
\caption{掲示板を利用した書き込みの計測結果}
\label{tab:bbs_write}
\end{table}

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

Haskell 版と Java 版の Web 掲示板サービスをブレードサーバ上で実行し, 
weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する. 
Haskell と Java の測定結果を表\ref{tab:compare}に示す. 

\begin{table}[!htbp]
\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}
\caption{HaskellとJavaの比較}
\label{tab:compare}
\end{table}

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

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

\subsection{書き込みごとに読み込みを行った場合}
書き込みごとに毎回読み込みを挟むことで, 遅延評価ではなく即時評価させる. 
計測結果を表\ref{tab:write_read}に示す. 

\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 141.40 s\\ \hline
2 & 70.87 s\\ \hline
4 & 54.32 s\\ \hline
8 & 55.13 s\\ \hline
12 & 58.60 s\\ \hline
\end{tabular}
\end{center}
\caption{書き込みを行うたびに読み込みを挟んだ場合の計測結果}
\label{tab:write_read}
\end{table}

結果が明らかに遅くなっている. 
12 スレッドで実行した際,  Java との書き込みの性能差は, 1.30 倍である. 
シングルスレッドで実行した場合と比較した場合, 12 スレッドで 2.40 倍の性能向上が見られる. 

\section{Haskell の生産性}
Java を用いた Jungle の実装と比較して, コード行数が約 3000 行から約 300 行へと短くなった. 

Haskell では, 独自のデータ型を作成することができる. 
再帰的なデータ構造の定義も容易である. 
また, Haskellは参照透過性を持つため, コードの再利用が行い易く, 関数同士の結合も簡単である. 

同じ機能を実装する場合でも, Java と比較してコード行数が短くなり生産性が向上する.