Mercurial > hg > Papers > 2016 > masa-master
annotate paper/c5.tex @ 97:c1738511433c
add tSearch Source code
| author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 18 Feb 2016 20:40:30 +0900 |
| parents | ca50770a7fde |
| children |
| 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 が走る際ファイルアクセスはランダムアクセスとなる。 | |
|
89
a4af6428370a
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
76
diff
changeset
|
22 mmap はランダムアクセスを想定していなくて結果がばらつきが起こっていると考えられる。 |
| 66 | 23 Blocked Read では読み込みをプログラムの書き手が制御しており、ファイルの読み込みもファイルの先頭から順次読み込みを行なっている。 |
| 24 そのため、読み込みを含めた結果にばらつきが起こりにくくなっていると予想される。 | |
| 25 | |
| 26 \begin{tiny} | |
| 27 \begin{table}[ht] | |
| 28 \begin{center} | |
| 75 | 29 ファイルサイズ : 500MB(単語数約8500万)\\ |
| 30 ファイル読み込みも含む\\ | |
| 66 | 31 \begin{tabular}[t]{|r|r|r|r|} |
| 32 \hline | |
| 33 CPU Num / 実行方式 & Mac(wc) & mmap & Blocked Read\\ | |
| 34 \hline | |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
35 1 & 10.59 & 9.96 & 9.33 \\ |
| 66 | 36 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
37 4 & --- & 8.63 & 8.52 \\ |
| 66 | 38 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
39 8 & --- & 10.35 & 8.04 \\ |
| 66 | 40 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
41 12 & --- & 9.26 & 7.82 \\ |
| 66 | 42 \hline |
| 43 \end{tabular} | |
| 44 \caption{ファイル読み込みを含む Word Count} | |
| 45 \label{table:IOwordcount} | |
| 46 \end{center} | |
| 47 \end{table} | |
| 48 \end{tiny} | |
| 49 | |
| 50 \newpage | |
| 51 表\ref{fig:wordcount} はファイル読み込みを含まない Word Count の結果である。 | |
| 50 | 52 |
| 56 | 53 Mac の wc ではこのファイルを処理するのに 4.08 秒かかる。それに対して、Cerium Word Count は 1 CPU で 3.70 秒、12 CPU だと 0.40 秒で処理できる。 |
| 53 | 54 |
| 56 | 55 1 CPU で動作させると Mac の wc よりも 1.1 倍ほど速くなり、12 CPU で動作させると wc よりも 10.2 倍ほど速くなった。 |
| 66 | 56 1 CPU と 12 CPU で比較すると、9.25 倍ほど速くなった。 |
| 56 | 57 |
| 66 | 58 ファイルを読み込んだ結果と比較すると、ファイルを読み込まないで実行したほうが 6,7 秒ほど速くなる。 |
| 59 これよりファイルを読み込んだ文字列処理の場合、処理時間の60\%から90\% はファイルの読み込みであることがわかる。 | |
| 53 | 60 |
| 56 | 61 \begin{tiny} |
| 62 \begin{table}[ht] | |
| 63 \begin{center} | |
| 75 | 64 ファイルサイズ : 500MB(単語数約8500万)\\ |
| 65 ファイル読み込みは含まない\\ | |
| 66 | 66 \begin{tabular}[t]{|r|r|} |
| 56 | 67 \hline |
| 68 実行方式 & 実行速度(秒)\\ | |
| 69 \hline | |
| 70 Mac(wc) & 4.08 \\ | |
| 71 \hline | |
| 72 Cerium Word Count(CPU 1) & 3.70\\ | |
| 73 \hline | |
| 74 Cerium Word Count(CPU 4) & 1.00\\ | |
| 75 \hline | |
| 76 Cerium Word Count(CPU 8) & 0.52\\ | |
| 77 \hline | |
| 78 Cerium Word Count(CPU 12) & 0.40\\ | |
| 79 \hline | |
| 80 \end{tabular} | |
| 81 \caption{ファイル読み込み無しの Word Count} | |
| 82 \label{fig:wordcount} | |
| 83 \end{center} | |
| 84 \end{table} | |
| 85 \end{tiny} | |
| 54 | 86 |
| 75 | 87 \section{Boyer-Moore Stirng Search} |
| 88 ファイルの大きさは 約500MByte で、このファイルには、約8300万単語が含まれている。このファイルに `Paskistan' という文字列がいくつマッチするかカウントしている。(マッチ数 約400万) | |
| 89 | |
| 90 表\ref{table:bmsearch} | |
| 91 はファイル読み込みを含まないで計測している。力任せ法と比較すると、Boyer-Moore String Search が最大 63 \% ほど速くなる。 | |
| 92 | |
| 93 \begin{tiny} | |
| 94 \begin{table}[ht] | |
| 95 \begin{center} | |
| 96 ファイルサイズ : 500MB(単語数約8500万)\\ | |
| 97 検索文字列 : Pakistan\\ | |
| 98 マッチ数約400万 \\ | |
| 99 ファイル読み込みは含まない\\ | |
| 100 \begin{tabular}[t]{|r|r|r|} | |
| 101 \hline | |
| 102 CPU 数 & 力任せ法 & Boyer-Moore String Search\\ | |
| 103 \hline | |
| 104 1 & 3.17 & 1.70 \\ | |
| 105 \hline | |
| 106 4 & 0.87 & 0.49 \\ | |
| 107 \hline | |
| 108 8 & 0.47 & 0.27 \\ | |
| 109 \hline | |
| 110 12 & 0.33 & 0.21 \\ | |
| 111 \hline | |
| 112 \end{tabular} | |
| 113 \caption{力任せ法と Boyer-Moore String Search の比較} | |
| 114 \label{table:bmsearch} | |
| 115 \end{center} | |
| 116 \end{table} | |
| 117 \end{tiny} | |
| 118 | |
|
16
a3c5125aea03
add images
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
119 \section{正規表現} |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
120 当実験では、Mac の egrep 、C で実装した逐次に DFA の状態遷移と照らし合わせマッチングをする single thread grep、Cerium で並列処理をする CeriumGrep を比較している。 |
| 74 | 121 |
| 75 | 122 表\ref{table:metachar}は500MB(単語数約8500万) のファイルに対して正規表現 `[A-Z][A-Za-z0-9]*s' をマッチングした結果である。 |
| 74 | 123 これはファイル読み込みを含めた結果と読み込みを含めていない結果の比較である。 |
| 47 | 124 |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
125 single thread grep や CeriumGrep は繰返し実行をすると実行速度が短くなる。 |
| 74 | 126 これは、読み込んだファイルがキャッシュに残っており、ファイル読み込みが省略されるためである。 |
| 127 同じファイルに対して違う正規表現でマッチングさせたとしてもファイル読み込みが省略されるため、高速に結果が返ってくる。 | |
| 128 | |
| 129 しかし egrep は繰返し実行しても同じ速度で実行されるため、毎回ファイルを読み込む。 | |
| 130 そのため、同じファイルに違う正規表現をマッチさせようとすると毎回読み込みが行われる。 | |
| 53 | 131 |
| 56 | 132 \begin{tiny} |
| 133 \begin{table}[ht] | |
| 134 \begin{center} | |
| 75 | 135 正規表現 `[A-Z][A-Za-z0-9]*s'\\ |
| 136 ファイルサイズ : 500MB(単語数約8500万)\\ | |
| 74 | 137 \begin{tabular}[t]{|c|r|r|} |
| 138 \hline | |
| 139 実行方式 & ファイル読み込み有 & ファイル読み込み無\\ | |
| 140 \hline | |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
141 single thread grep & 21.17 & 16.15\\ |
| 74 | 142 \hline |
| 143 CeriumGrep(CPU 12) mmap & 18.00 & 5.12\\ | |
| 144 \hline | |
| 145 CeriumGrep(CPU 12) bread & 15.76 & 5.18\\ | |
| 146 \hline | |
| 147 egrep & 59.51 & 59.51 \\ | |
| 148 \hline | |
| 149 \end{tabular} | |
| 150 \caption{ファイル読み込み有りと無しを変化させた各 grep の結果} | |
| 151 \label{table:metachar} | |
| 152 \end{center} | |
| 153 \end{table} | |
| 154 \end{tiny} | |
| 155 | |
| 156 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 157 | |
| 75 | 158 表\ref{table:AZaz} は正規表現 `[A-Z][A-Za-z0-9]*s' を 500MB(単語数約8500万)、1GB(単語数約1.7億語)のファイルに対してマッチングを行なった。 |
| 74 | 159 |
| 160 ファイルサイズに比例して処理時間も長くなっていく。 | |
| 161 | |
| 162 \begin{tiny} | |
| 163 \begin{table}[ht] | |
| 164 \begin{center} | |
| 75 | 165 正規表現 `[A-Z][A-Za-z0-9]*s'\\ |
| 74 | 166 ファイルサイズ : 500MB(単語数約8500万)\\ |
| 75 | 167 ファイル読み込みを含む\\ |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
168 \begin{tabular}[t]{|c|r|r|r|r|} |
| 56 | 169 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
170 実行方式/File Size(Match Num) & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\ |
| 56 | 171 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
172 single thread grep & 4.51 & 9.42 & 20.62 & 40.10\\ |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
173 \hline |
|
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
174 CeriumGrep(CPU 12) mmap & 8.97 & 10.79 & 18.00 & 29.16\\ |
| 56 | 175 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
176 CeriumGrep(CPU 12) bread & 7.75 & 10.49 & 15.76 & 26.83\\ |
| 56 | 177 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
178 egrep & 6.42 & 12.80 & 59.51 & 119.23\\ |
| 56 | 179 \hline |
| 180 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
181 \caption{ファイルサイズを変化させた各 grep の結果} |
| 56 | 182 \label{table:AZaz} |
| 183 \end{center} | |
| 184 \end{table} | |
| 185 \end{tiny} | |
| 186 | |
| 65 | 187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 66 | 188 |
| 74 | 189 表\ref{table:abab} |
| 190 は aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。 | |
| 191 これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。 | |
| 66 | 192 |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
193 |
| 74 | 194 この例題で使用した正規表現は `(a \textbar b)' を `*a' の直後に付け加えていくと、それだけ状態数が指数関数的に増えていく。 |
| 195 CeriumGrep は状態数が指数関数的に増加しても 1 秒ほど増加するが、egrep では 5,6 秒ほど増加していく。 | |
| 75 | 196 \newpage |
| 65 | 197 |
| 198 \begin{tiny} | |
| 199 \begin{table}[ht] | |
| 200 \begin{center} | |
| 74 | 201 ファイルサイズ : 500MB(単語数約2400万)\\ |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
202 状態数の内訳 : 状態割当時の状態数/subset 後の状態数\\ |
| 75 | 203 ファイル読み込みを含む\\ |
| 73 | 204 \begin{tabular}[t]{|l|r|r|r|r|} |
| 65 | 205 \hline |
| 74 | 206 正規表現 & 状態数 & マッチ数 & CeriumGrep (CPU 12) bread & egrep \\ |
| 65 | 207 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
208 '(a \textbar b)*a(a \textbar b)(a \textbar b)z' & 5/12 & 約10万 & 26.58 & 70.11 \\ |
| 65 | 209 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
210 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z' & 6/21 & 約8万 & 27.89 & 76.78 \\ |
| 65 | 211 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
212 '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z' & 7/38 & 約4万 & 28.86 & 81.88 \\ |
| 65 | 213 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
214 '(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 \\ |
| 65 | 215 \hline |
| 216 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
217 \caption{正規表現の状態数を増やした Grep の結果} |
| 65 | 218 \label{table:abab} |
| 219 \end{center} | |
| 220 \end{table} | |
| 221 \end{tiny} | |
| 222 | |
| 223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
| 53 | 224 |
| 66 | 225 表\ref{table:nomatch} ab の文字列がならんでいるところに (W \textbar w)ord の正規表現 |
| 75 | 226 aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、全くマッチしない正規表現を与えてマッチングさせてみた。 |
| 61 | 227 |
| 75 | 228 マッチングしない場合でも egrep と比較して CeriumGrep bread のほうが 30 \% ほど速くなる。 |
| 61 | 229 \begin{tiny} |
| 230 \begin{table}[ht] | |
| 231 \begin{center} | |
| 74 | 232 ファイルサイズ : 500MB(単語数約2400万)\\ |
| 233 正規表現 : (W \textbar w)ord\\ | |
| 75 | 234 ファイル読み込みを含む\\ |
| 66 | 235 \begin{tabular}[t]{|c|r|} |
| 61 | 236 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
237 実行方式 & time (s)\\ |
| 61 | 238 \hline |
|
91
ca50770a7fde
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
89
diff
changeset
|
239 single thread grep & 27.13\\ |
| 61 | 240 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
241 CeriumGrep(CPU 12) mmap & 21.58\\ |
| 61 | 242 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
243 CeriumGrep(CPU 12) bread & 19.99\\ |
| 61 | 244 \hline |
|
71
c01a514d33f7
add bm_search
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
67
diff
changeset
|
245 egrep & 28.33\\ |
| 61 | 246 \hline |
| 247 \end{tabular} | |
|
67
9c16f6b18100
add result
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
66
diff
changeset
|
248 \caption{全くマッチングしないパターンを grep した結果} |
|
62
0d13c52a54fd
remove bm_search explain
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
61
diff
changeset
|
249 \label{table:nomatch} |
| 61 | 250 \end{center} |
| 251 \end{table} | |
| 252 \end{tiny} |