Mercurial > hg > Papers > 2016 > masa-master
annotate paper/c5.tex @ 71:c01a514d33f7
add bm_search
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 17 Feb 2016 00:07:04 +0900 |
| parents | 9c16f6b18100 |
| children | 69742d52fd7d |
| rev | line source |
|---|---|
| 53 | 1 \chapter{ベンチマーク} |
| 2 本項で行なった実験の環境は以下の通りである。 | |
| 3 \begin{itemize} | |
| 4 \item Mac OS X 10.10.5 | |
| 5 \item 2*2.66 GHz 6-Core Intel Xeon | |
| 6 \item Memory 16GB 1333MHz DDR3 | |
| 7 \item 1TB HDD | |
| 8 \end{itemize} | |
| 45 | 9 |
| 66 | 10 Cerium で実装した Word Count と Mac の wc の比較と、実装した正規表現と Mac の egrep の比較を行なった。 |
| 56 | 11 また、それぞれの結果に実装した並列処理向け I/O の結果も含む。 |
| 54 | 12 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
13 \section{Word Count} |
| 56 | 14 ファイルの大きさは 約500MByte で、このファイルには 約650万行、約8300万単語が含まれている。 |
| 66 | 15 |
| 16 表\ref{table:IOwordcount} は、ファイル読み込みを含めた Word Count の結果である。 | |
| 17 Mac の wc ではこのファイルを処理するのに 10.59 秒かかる。それに対して、Cerium Word Count は mmap Blocked Read 全ての状況で Mac の wc よりも速いことを示している。 | |
| 18 Cerium Word Count 12 CPU のとき、7.83 秒で処理をしており、Mac の wc の 1.4 倍ほど速くなっている。 | |
| 19 | |
| 20 mmap は読み込みを OS が制御しており、書き手が制御できない。 | |
| 21 また Word Count が走る際ファイルアクセスはランダムアクセスとなる。 | |
| 22 mmap はランダムアクセスを想定していなくてグラフにばらつきが起こっていると考えられる。 | |
| 23 Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。 | |
| 24 そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。 | |
| 25 | |
| 26 \begin{tiny} | |
| 27 \begin{table}[ht] | |
| 28 \begin{center} | |
| 29 \begin{tabular}[t]{|r|r|r|r|} | |
| 30 \hline | |
| 31 CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\ | |
| 32 \hline | |
| 33 1 & 10.590 & 9.96 & 9.33 \\ | |
| 34 \hline | |
| 35 4 & --- & 8.63 & 8.52 \\ | |
| 36 \hline | |
| 37 8 & --- & 10.35 & 8.04 \\ | |
| 38 \hline | |
| 39 12 & --- & 9.26 & 7.82 \\ | |
| 40 \hline | |
| 41 \end{tabular} | |
| 42 \caption{ファイル読み込みを含む Word Count} | |
| 43 \label{table:IOwordcount} | |
| 44 \end{center} | |
| 45 \end{table} | |
| 46 \end{tiny} | |
| 47 | |
| 48 \newpage | |
| 49 表\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。 | |
| 50 | 50 |
| 56 | 51 Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。 |
| 53 | 52 |
| 56 | 53 1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。 |
| 66 | 54 1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。 |
| 56 | 55 |
| 66 | 56 ファイルを読み込んだ結果と比較すると、ファイルを読み込まないで実行したほうが 6,7 秒ほど速くなる。 |
| 57 これよりファイルを読み込んだ文字列処理の場合、処理時間の60\%から90\% はファイルの読み込みであることがわかる。 | |
| 53 | 58 |
| 56 | 59 \begin{tiny} |
| 60 \begin{table}[ht] | |
| 61 \begin{center} | |
| 66 | 62 \begin{tabular}[t]{|r|r|} |
| 56 | 63 \hline |
| 64 実行方式 & 実行速度(秒)\\ | |
| 65 \hline | |
| 66 Mac(wc) & 4.08 \\ | |
| 67 \hline | |
| 68 Cerium Word Count(CPU 1) & 3.70\\ | |
| 69 \hline | |
| 70 Cerium Word Count(CPU 4) & 1.00\\ | |
| 71 \hline | |
| 72 Cerium Word Count(CPU 8) & 0.52\\ | |
| 73 \hline | |
| 74 Cerium Word Count(CPU 12) & 0.40\\ | |
| 75 \hline | |
| 76 \end{tabular} | |
| 77 \caption{ファイル読み込み無しの Word Count} | |
| 78 \label{fig:wordcount} | |
| 79 \end{center} | |
| 80 \end{table} | |
| 81 \end{tiny} | |
| 54 | 82 |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
83 \section{正規表現} |
| 66 | 84 当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせる CGrep、Cerium で並列処理をする CeriumGrep を比較している。 |
| 47 | 85 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
86 表\ref{table:AZaz} は正規表現 '[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。 |
| 53 | 87 |
| 56 | 88 \begin{tiny} |
| 89 \begin{table}[ht] | |
| 90 \begin{center} | |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
91 正規表現 '[A-Z][A-Za-z0-9]*s' |
|
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
92 \begin{tabular}[t]{|c|r|r|r|r|} |
| 56 | 93 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
94 実行方式/File Size(Match Num) & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\ |
| 56 | 95 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
96 CGrep & 4.51 & 9.42 & 20.62 & 40.10\\ |
|
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
97 \hline |
|
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
98 CeriumGrep(CPU 12) mmap & 8.97 & 10.79 & 18.00 & 29.16\\ |
| 56 | 99 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
100 CeriumGrep(CPU 12) bread & 7.75 & 10.49 & 15.76 & 26.83\\ |
| 56 | 101 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
102 egrep & 6.42 & 12.80 & 59.51 & 119.23\\ |
| 56 | 103 \hline |
| 104 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
105 \caption{ファイルサイズを変化させた各 grep の結果} |
| 56 | 106 \label{table:AZaz} |
| 107 \end{center} | |
| 108 \end{table} | |
| 109 \end{tiny} | |
| 110 | |
| 65 | 111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 66 | 112 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
113 表\ref{table:metachar} 500MB(単語数約8500万) のファイルに対して正規表現 '[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 |
|
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
114 これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 |
|
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
115 egrep は実行するたびにファイル読み込みを行うため、ファイル読み込み無しの測定はなし。 |
| 66 | 116 \begin{tiny} |
| 117 \begin{table}[ht] | |
| 118 \begin{center} | |
| 119 \begin{tabular}[t]{|c|r|r|} | |
| 120 \hline | |
| 121 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ | |
| 122 \hline | |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
123 CGrep & 21.17 & 16.15\\ |
| 66 | 124 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
125 CeriumGrep(CPU 2) & 27.06 & 15.40\\ |
| 66 | 126 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
127 CeriumGrep(CPU 12) & 12.48 & 7.39\\ |
| 66 | 128 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
129 egrep & 59.51 & 59.51 \\ |
| 66 | 130 \hline |
| 131 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
132 \caption{ファイル読み込み有りと無しを変化させた各 grep の結果} |
| 66 | 133 \label{table:metachar} |
| 134 \end{center} | |
| 135 \end{table} | |
| 136 \end{tiny} | |
| 137 | |
| 138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 65 | 139 表\ref{table:abab} |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
140 aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
141 これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 |
| 65 | 142 |
| 143 \begin{tiny} | |
| 144 \begin{table}[ht] | |
| 145 \begin{center} | |
| 66 | 146 \begin{tabular}[t]{|l|r|r|r|} |
| 65 | 147 \hline |
| 148 正規表現 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\ | |
| 149 \hline | |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
150 '(a \textbar b)*a(a \textbar b)(a \textbar b)z' & 約10万 & 26.58 & 70.11 \\ |
| 65 | 151 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
152 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z' & 約10000 & 27.89 & 76.78 \\ |
| 65 | 153 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
154 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 約7000 & & 81.88 \\ |
| 65 | 155 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
156 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 約4000 & & 86.93 \\ |
| 65 | 157 \hline |
| 158 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
159 \caption{正規表現の状態数を増やした Grep の結果} |
| 65 | 160 \label{table:abab} |
| 161 \end{center} | |
| 162 \end{table} | |
| 163 \end{tiny} | |
| 164 | |
| 165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 53 | 166 |
| 66 | 167 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現 |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
168 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてパターンマッチングさせてみた。 |
| 61 | 169 |
| 170 \begin{tiny} | |
| 171 \begin{table}[ht] | |
| 172 \begin{center} | |
| 66 | 173 \begin{tabular}[t]{|c|r|} |
| 61 | 174 \hline |
| 66 | 175 実行方式/File Size(Match Num) & time (s)\\ |
| 61 | 176 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
177 CGrep & 27.13\\ |
| 61 | 178 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
179 CeriumGrep(CPU 12) mmap & 21.58\\ |
| 61 | 180 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
181 CeriumGrep(CPU 12) bread & 19.99\\ |
| 61 | 182 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
183 egrep & 28.33\\ |
| 61 | 184 \hline |
| 185 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
186 \caption{全くマッチングしないパターンを grep した結果} |
|
62
0d13c52a54fd
remove bm_search explain
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
187 \label{table:nomatch} |
| 61 | 188 \end{center} |
| 189 \end{table} | |
| 190 \end{tiny} |