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

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

論理コアは, Intel のハイパースレッディング機能のことである. 
ハイパースレッディングは, 1 つのプロセッサをあたかも 2 つのプロセッサであるかのように扱う技術であり, 
同時に演算器などを利用することはできないため性能が 2 倍になるわけではないが, 概ね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}

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

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

\begin{table}[!htbp]
\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}

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

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

\subsubsection{計測方法}
ブレードサーバ上で, Jungle で作成した木構造を並列に読み込んで性能計測を行う. 
並列に実行する際に, 読み込みに負荷がかかるように木構造はある程度の大きさとする. 
今回は木の深さが 8, ノードの数が約 80 万の大きさの木構造を使用する.  
木構造を読み込み, ノードの数を数えるタスクを 1,000 個作成し並列実行する. 
非破壊的木構造は, 木構造に変更を加えても他の読み込みのタスクに影響を与えない. 
そのことを確認するために, 木構造は各タスクに渡す前に無作為にノードを追加する. 

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

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

Haskell では並列実行時にOSのaffinity（親和性）機能を使って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数 & 通常実行 & 親和性機能利用\\ \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}に示す. 
親和性機能を使わない場合は, 6スレッドまではほぼ線形に性能が向上する.
親和性機能を使った場合は, 12スレッドまではほぼ線形に性能が向上する.
ハイパースレッディング機能を用いた13 スレッド以上では性能向上率が落ちる.

親和性機能を使った場合, 6スレッド以降で性能差が出る理由として, 6 コアCPUを 2 個積んでいることが考えられる.
スレッドがCPUをまたいでスケジューリングされなくなるため, 親和性機能を使うことで性能が向上するのだと考えられる.

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

非破壊的木構造データベース Jungle は 12 スレッドで 10.37 倍の性能向上が得ることができる.
読み込みにおいて, スケールするデータベースであると言える.

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

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

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

CPUコア数を増やしていくと, 実行時間が短くなっていることが分かる. 
シングルスレッドで実行した場合と比較して, 2 スレッドで 1.79 倍, 12 スレッドで 3.18 倍の性能向上が見られる. 
OSの親和性機能を使った場合, 2 スレッドで 1.61 倍, 12 スレッドで 3.82 倍の性能向上が見られ, 4 スレッド以上では親和性機能を使ったほうが実行時間が短くなる. 
また, 読み込みと同様に親和性機能を使った場合 24 スレッドでの実行時間が大幅に伸びる.

書き込みは, 読み込みと比べるとJungleへの木構造の登録作業があるため性能向上率が下がる.

\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||r|r|} \hline
  CPU数 & 通常実行 & 親和性機能利用\\ \hline
  1 & 49.70 s & 49.61 s \\\hline
  2 & 27.77 s & 30.76 s \\\hline
  4 & 18.06 s & 18.05 s \\\hline
  8 & 16.66 s & 12.50 s \\\hline
  12 & 15.62 s & 12.96 s \\\hline
  16 & 14.91 s & 13.11 s \\\hline
  20 & 15.31 s & 13.84 s \\\hline
  24 & 18.11 s & 71.66 s \\\hline
\end{tabular}
\end{center}
\caption{書き込みの計測結果}
\label{tab:par_write}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_write}に示す. 
Jungle へ木の登録する際に他のスレッドから登録があった場合, ソフトウェア・トランザクショナル・メモリが処理をやり直すため, 並列度が下がっていると考えられる.
速度向上が親和性機能を使った8スレッド実行時の 3.96 倍で頭打ちになっている.

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

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

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

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

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}

Warp は並列 HTTP サーバであるが, 計測環境ではネットワークがボトルネックとなってしまう.
ネットワークのボトルネックがどれぐらいあるのか調査するために, アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する. 
ネットワークを介さずに性能測定する場合, 性能測定ツール weighttp に 3 スレッド利用するため, Warp で利用するのは 8 スレッドまでとする.
weighttpの設定は, リクエストの総数 100 万, 同時に接続するコネクションの数 1,000, 実行時のスレッド数 3, HTTP Keep-Alivesを有効とする. 
また, 現在の安定版である 7.6.3 は IO マネージャーに問題があるが, どの程度影響があるか調べるためにGHC 7.6.3 でコンパイルし, ネットワークを介さない状態での測定も行う.
結果を表\ref{tab:warp}に示す.

\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||r|r|r|} \hline
  CPU数 & ネットワーク介す & ネットワークを介さない & GHC 7.6.3\\ \hline
  1 & 44,008 req/s & 44,504 req/s  & 31,602 req/s \\\hline
  2 & 57,396 req/s & 95,760 req/s  & 69,265 req/s \\\hline
  4 & 60,593 req/s & 179,791 req/s & 133,897 req/s \\\hline
  6 & 57,159 req/s & 241,240 req/s & 83,131 req/s \\\hline
  8 & 59,697 req/s & 264,231 req/s & 31,694 req/s \\\hline
\end{tabular}
\end{center}
\caption{Warp の 性能測定結果}
\label{tab:warp}
\end{table}

1 秒間あたりどれだけのリクエストを捌けるかという指標で比較を行う.
大きければ大きいほど性能が良い.
ネットワークを介する場合と介さない場合で, 8 コア時に4.4倍の性能差がある.

ネットワークを介さない場合は, 線形にスケールしている（図\ref{fig:warp_benchmark}）.
ネットワークを介した場合, およそ 60,000 req/s 程度で頭打ちとなってしまっている.

GHC 7.6.3 は, 5 スレッドあたりまでスケールするものの, それ以降遅くなり, 8スレッド実行時はシングルスレッドで実行した場合と変わらないといったバグが存在することがわかる.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/warp.pdf}
 \end{center}
 \caption{Warp の 性能測定結果}
 \label{fig:warp_benchmark}
\end{figure}

Web掲示板サービスの性能測定には, 並列環境でどのようにスケールするか計測したいため, ネットワークを介さずに実験を行う.
実験環境を図\ref{fig:request}に示す.

\begin{figure}[!htbp]
 \begin{center}
   \includegraphics[scale=0.6]{./images/request.pdf}
 \end{center}
 \caption{実験環境}
 \label{fig:request}
\end{figure}
\newpage

\subsection{読み込みと書き込み}
\subsubsection{計測方法}
掲示板に対して読み込みと書き込みを行い, 負荷をかける. 
weighttpの設定は, リクエストの総数 100 万, 同時に接続するコネクションの数 1,000, 実行時のスレッド数 3, HTTP Keep-Alivesを有効とする. 

\subsubsection{計測結果}

掲示板の読み込みと書き込みの計測結果を表\ref{tab:bbs_read}および図\ref{fig:bbs}に示す. 
少ないスレッド数の場合に, 読み込みより書き込みのスループットが高いのは, 読み込みにあるデータベースの内容をHTML形式に変換する作業がないためだと考えられる.

性能向上率を読み込みと書き込みで比較する.
読み込みは, シングルスレッドで実行した場合と比較して, 8 スレッドで 6.18 倍の性能向上が見られる. 
書き込みは, シングルスレッドで実行した場合と比較して, 8 スレッドで 3.93 倍の性能向上が見られる. 
この結果は, 並列データベース Jungle が書き込みに比べて読み込みが高速であると示した Jungle 単体での実験結果と一致する.


\begin{table}[!htbp]
\begin{center}
\begin{tabular}{|c||r|r|} \hline
  CPU数 & 読み込み & 書き込み \\ \hline
  1 & 22,624 req/s & 28,552 req/s \\ \hline
  2 & 43,083 req/s & 53,765 req/s \\ \hline
  4 & 92,548 req/s & 98,691 req/s \\ \hline
  6 & 119,310 req/s & 99,009 req/s \\ \hline
  8 & 139,965 req/s & 112,212 req/s \\ \hline
\end{tabular}
\end{center}
\caption{掲示板を利用した読み込みと書き込みの計測結果}
\label{tab:bbs_read}
\end{table}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/bbs.pdf}
 \end{center}
 \caption{掲示板を利用した読み込みと書き込みの計測結果}
 \label{fig:bbs}
\end{figure}

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

Haskell 版と Java 版の Web 掲示板サービスをブレードサーバ上で実行する. 
実際の利用を想定して計測を行うため, ブレードサーバをもう1台用意し, ネットワークを介して weightttpで負荷をかける.
10 スレッドから, 1 スレッドあたり 100 並列にリクエストを投げ, 合計100万リクエストを処理するのにかかる時間を計測する. 
Haskell と Java の測定結果を表\ref{tab:compare}に示す. 

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

Haskell 版は, Java 版と比較して読み込みで 3.25 倍, 書き込みで 3.78 倍の性能差が出ている. 
Haskell は 実用的な Web サービスが開発できる.

\subsubsection{Haskell の生産性}
Haskell 版 Jungle が公開している関数の数は 18 で, コード行数は284行である.
Java を用いた Jungle の実装は, 3390行で, Haskell の実装は 1/12 程度のサイズとなっている.

コード行数が短くなった要因としては, Haskellが独自の再帰的データ構造の定義を言語としてサポートしていることや, 
関数が参照透過性を持つため再利用が行いやすいということが考えられる.

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