# HG changeset patch # User Masataka Kohagura # Date 1455689509 -32400 # Node ID 1f1ef47ba38024782f2d72e27f678b10ac9580e1 # Parent a2004b9f1517f304a4ab764962cfd809801b559c fix diff -r a2004b9f1517 -r 1f1ef47ba380 paper/c5.tex --- a/paper/c5.tex Wed Feb 17 14:32:16 2016 +0900 +++ b/paper/c5.tex Wed Feb 17 15:11:49 2016 +0900 @@ -81,19 +81,59 @@ \end{tiny} \section{正規表現} -当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせる CGrep、Cerium で並列処理をする CeriumGrep を比較している。 +当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをするC実装の Grep、Cerium で並列処理をする CeriumGrep を比較している。 + + +表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 +これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 -表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。 +C実装Grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。 +これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。 +同じファイルに対して違う正規表現でマッチングさせたとしてもファイル読み込みが省略されるため、高速に結果が返ってくる。 + +しかし egrep は繰返し実行しても同じ速度で実行されるため、毎回ファイルを読み込む。 +そのため、同じファイルに違う正規表現をマッチさせようとすると毎回読み込みが行われる。 \begin{tiny} \begin{table}[ht] \begin{center} - 正規表現 '[A-Z][A-Za-z0-9]*s' + 正規表現 '[A-Z][A-Za-z0-9]*s'\\ + ファイルサイズ : 500MB(単語数約8500万) + \begin{tabular}[t]{|c|r|r|} + \hline + 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ + \hline + C実装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 - CGrep & 4.51 & 9.42 & 20.62 & 40.10\\ + C実装 Grep & 4.51 & 9.42 & 20.62 & 40.10\\ \hline CeriumGrep(CPU 12) mmap & 8.97 & 10.79 & 18.00 & 29.16\\ \hline @@ -110,42 +150,20 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 -これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 -egrep は実行するたびにファイル読み込みを行うため、ファイル読み込み無しの測定はなし。 -\begin{tiny} - \begin{table}[ht] - \begin{center} - \begin{tabular}[t]{|c|r|r|} - \hline - 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ - \hline - CGrep & 21.17 & 16.15\\ - \hline - CeriumGrep(CPU 2) & 27.06 & 15.40\\ - \hline - CeriumGrep(CPU 12) & 12.48 & 7.39\\ - \hline - egrep & 59.51 & 59.51 \\ - \hline - \end{tabular} - \caption{ファイル読み込み有りと無しを変化させた各 grep の結果} - \label{table:metachar} - \end{center} - \end{table} -\end{tiny} +表\ref{table:abab} +は aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。 +これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -表\ref{table:abab} -aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。 -これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 +この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。 +CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。 \begin{tiny} \begin{table}[ht] \begin{center} + ファイルサイズ : 500MB(単語数約2400万)\\ \begin{tabular}[t]{|l|r|r|r|r|} \hline - 正規表現 & 状態数 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\ + 正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\ \hline '(a \textbar b)*a(a \textbar b)(a \textbar b)z' & 12 & 約10万 & 26.58 & 70.11 \\ \hline @@ -167,9 +185,13 @@ 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてパターンマッチングさせてみた。 + + \begin{tiny} \begin{table}[ht] \begin{center} + ファイルサイズ : 500MB(単語数約2400万)\\ + 正規表現 : (W \textbar w)ord\\ \begin{tabular}[t]{|c|r|} \hline 実行方式/File Size(Match Num) & time (s)\\ diff -r a2004b9f1517 -r 1f1ef47ba380 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed