Mercurial > hg > Papers > 2016 > masa-master

\chapter{ベンチマーク}
本項で行なった実験の環境は以下の通りである。
\begin{itemize}
\item Mac OS X 10.10.5
\item 2*2.66 GHz 6-Core Intel Xeon
\item Memory 16GB 1333MHz DDR3
\item 1TB HDD
\end{itemize}

Cerium で実装した Word Count と Mac の wc の比較と、実装した正規表現と Mac の egrep の比較を行なった。
また、それぞれの結果に実装した並列処理向け I/O の結果も含む。

\section{Word Count}
ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。

表\ref{table:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。
Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。
Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。

mmap は読み込みを OS が制御しており、書き手が制御できない。
また Word Count が走る際ファイルアクセスはランダムアクセスとなる。
mmap はランダムアクセスを想定していなくて結果がばらつきが起こっていると考えられる。
Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。
そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        ファイルサイズ : 500MB(単語数約8500万)\\
        ファイル読み込みも含む\\
      \begin{tabular}[t]{|r|r|r|r|}
        \hline
        CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\
        \hline
         1 & 10.59  & 9.96  & 9.33 \\
        \hline
         4 & ---    & 8.63  & 8.52 \\
        \hline
         8 & ---    & 10.35 & 8.04 \\
        \hline
        12 & ---    & 9.26  & 7.82 \\
        \hline
      \end{tabular}
  \caption{ファイル読み込みを含む Word Count}
  \label{table:IOwordcount}
    \end{center}
  \end{table}
\end{tiny}

\newpage
表\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。

Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。

1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。
1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。

ファイルを読み込んだ結果と比較すると、ファイルを読み込まないで実行したほうが 6,7 秒ほど速くなる。
これよりファイルを読み込んだ文字列処理の場合、処理時間の60\%から90\% はファイルの読み込みであることがわかる。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        ファイルサイズ : 500MB(単語数約8500万)\\
        ファイル読み込みは含まない\\
      \begin{tabular}[t]{|r|r|}
        \hline
        実行方式 & 実行速度(秒)\\
        \hline
        Mac(wc) & 4.08 \\
        \hline
        Cerium Word Count(CPU 1) & 3.70\\
        \hline
        Cerium Word Count(CPU 4) & 1.00\\
        \hline
        Cerium Word Count(CPU 8) & 0.52\\
        \hline
        Cerium Word Count(CPU 12) & 0.40\\
        \hline
      \end{tabular}
      \caption{ファイル読み込み無しの Word Count}
      \label{fig:wordcount}
    \end{center}
  \end{table}
\end{tiny}

\section{Boyer-Moore Stirng Search}
ファイルの大きさは 約500MByte で、このファイルには、約8300万単語が含まれている。このファイルに `Paskistan' という文字列がいくつマッチするかカウントしている。(マッチ数 約400万)

表\ref{table:bmsearch}
はファイル読み込みを含まないで計測している。力任せ法と比較すると、Boyer-Moore String Search が最大 63 \% ほど速くなる。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        ファイルサイズ : 500MB(単語数約8500万)\\
        検索文字列 : Pakistan\\
        マッチ数約400万 \\
        ファイル読み込みは含まない\\
      \begin{tabular}[t]{|r|r|r|}
        \hline
        CPU 数 & 力任せ法 & Boyer-Moore String Search\\
        \hline
         1 & 3.17  & 1.70  \\
        \hline
         4 & 0.87  & 0.49  \\
        \hline
         8 & 0.47  & 0.27  \\
        \hline
        12 & 0.33  & 0.21  \\
        \hline
      \end{tabular}
  \caption{力任せ法と Boyer-Moore String Search の比較}
  \label{table:bmsearch}
    \end{center}
  \end{table}
\end{tiny}

\section{正規表現}
当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをする single thread grep、Cerium で並列処理をする CeriumGrep を比較している。

表\ref{table:metachar}は500MB(単語数約8500万) のファイルに対して正規表現 `[A-Z][A-Za-z0-9]*s' をマッチングした結果である。
これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。

single thread grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。
これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。
同じファイルに対して違う正規表現でマッチングさせたとしてもファイル読み込みが省略されるため、高速に結果が返ってくる。

しかし egrep は繰返し実行しても同じ速度で実行されるため、毎回ファイルを読み込む。
そのため、同じファイルに違う正規表現をマッチさせようとすると毎回読み込みが行われる。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        正規表現 `[A-Z][A-Za-z0-9]*s'\\
        ファイルサイズ : 500MB(単語数約8500万)\\
      \begin{tabular}[t]{|c|r|r|}
        \hline
        実行方式 & ファイル読み込み有 & ファイル読み込み無\\
        \hline
        single thread grep & 21.17 & 16.15\\
        \hline
        CeriumGrep(CPU 12) mmap  & 18.00 & 5.12\\
        \hline
        CeriumGrep(CPU 12) bread & 15.76 & 5.18\\
        \hline
        egrep & 59.51 & 59.51 \\
        \hline
      \end{tabular}
      \caption{ファイル読み込み有りと無しを変化させた各 grep の結果}
      \label{table:metachar}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:AZaz} は正規表現 `[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。

ファイルサイズに比例して処理時間も長くなっていく。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        正規表現 `[A-Z][A-Za-z0-9]*s'\\
        ファイルサイズ : 500MB(単語数約8500万)\\
        ファイル読み込みを含む\\
      \begin{tabular}[t]{|c|r|r|r|r|}
        \hline
        実行方式/File Size(Match Num)    & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\
        \hline
        single thread grep                            & 4.51 &  9.42 & 20.62 & 40.10\\
        \hline
        CeriumGrep(CPU 12) mmap          & 8.97 & 10.79 & 18.00 & 29.16\\
        \hline
        CeriumGrep(CPU 12) bread         & 7.75 & 10.49 & 15.76 & 26.83\\
        \hline
        egrep                            & 6.42 & 12.80 & 59.51 & 119.23\\
        \hline
      \end{tabular}
  \caption{ファイルサイズを変化させた各 grep の結果}
  \label{table:AZaz}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:abab}
は aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。
これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。


この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。
CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。
\newpage

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        ファイルサイズ : 500MB(単語数約2400万)\\
        状態数の内訳 : 状態割当時の状態数/subset 後の状態数\\
        ファイル読み込みを含む\\
      \begin{tabular}[t]{|l|r|r|r|r|}
        \hline
        正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\
        \hline
        '(a \textbar b)*a(a \textbar b)(a \textbar b)z'                                               & 5/12 & 約10万 & 26.58 &  70.11 \\
        \hline
        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z'                                 & 6/21 & 約8万 & 27.89 &  76.78 \\
        \hline
        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z'                   & 7/38 & 約4万 & 28.86 & 81.88 \\
        \hline
        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z'     & 8/71 & 約2万 & 29.15 & 86.93 \\
        \hline
      \end{tabular}
  \caption{正規表現の状態数を増やした Grep の結果}
  \label{table:abab}
    \end{center}
  \end{table}
\end{tiny}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現
aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてマッチングさせてみた。

マッチングしない場合でも egrep と比較して CeriumGrep bread のほうが 30 \% ほど速くなる。
\begin{tiny}
  \begin{table}[ht]
    \begin{center}
        ファイルサイズ : 500MB(単語数約2400万)\\
        正規表現 : (W \textbar w)ord\\
        ファイル読み込みを含む\\
      \begin{tabular}[t]{|c|r|}
        \hline
        実行方式 & time (s)\\
        \hline
        single thread grep & 27.13\\
        \hline
        CeriumGrep(CPU 12) mmap  & 21.58\\
        \hline
        CeriumGrep(CPU 12) bread & 19.99\\
        \hline
        egrep & 28.33\\
        \hline
      \end{tabular}
  \caption{全くマッチングしないパターンを grep した結果}
  \label{table:nomatch}
    \end{center}
  \end{table}
\end{tiny}
author	Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date	Thu, 18 Feb 2016 15:59:22 +0900
parents	a4af6428370a
children