# HG changeset patch # User Ryoma SHINYA # Date 1282906342 -32400 # Node ID c2aaa766746a2c6bc9addca5aeae404df3e3b6ad # Parent a612af877e5ab97f2d31662160fd8934e32f2993 edit diff -r a612af877e5a -r c2aaa766746a paper.pdf Binary file paper.pdf has changed diff -r a612af877e5a -r c2aaa766746a paper.tex --- a/paper.tex Fri Aug 27 15:51:59 2010 +0900 +++ b/paper.tex Fri Aug 27 19:52:22 2010 +0900 @@ -332,58 +332,80 @@ \newpage \section{評価} -\subsection{CbC/C/LLVM - 三つの実装の比較} +\subsection{実験} 本実験で実装した正規表現評価器のCbC/C/LLVMによる三つの実装に対して, コンパイル時間及びマッチングにかかる時間の比較を行った. +なお, GCCによるコンパイルには最適化オプション ``-O3'' を, LLVMのも同様の +最適化オプションを用いてコンパイル/マッチングを行っている. -{\bf コンパイル時間} +{\bf 実験環境} +\begin{itemize} +\item CPU : Core 2 Duo 950 @3.0GHz +\item Memory : 16GB +\item GCC (c) : 4.0.1 +\item LLVM: 2.4 +\end{itemize} + +{\bf コンパイル}\\ n個の単語を正規表現のOR演算で繋げたパターンに対し, 各実装のコンパイル時 間の比較を行った. -{\bf マッチング時間} -... -本実験で実装した正規表現評価器を用いて grep に相当するプログラムを実装し, -実際にテキストファイルからのパターンマッチを行い, それぞれの評価を行った. +\begin{table}[h] +\caption{ベンチマーク:compile} +\label{table:benchmark1} +\begin{tabular}[t]{|l||l|l|l||l|} +\hline +n (単語数)& 1 & 10 & 50 & 100 \\ +\hline +DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\ +状態数[個]& 8 & 50 & 187 & 381\\ +\hline +GCC-C [s] & 0.34 & 0.78 & 2.18 & 4.27\\ +\hline +GCC-CbC[s] & 0.75 & 1.03 & 9.14 & 9.43\\ +\hline +LLVM [s] & 0.044 & 0.08 & 0.246 & 0.472\\ +\hline +\end{tabular} +\end{table} -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ -　\\ +表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速 +に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作 +することで, I/Oやパース等のオーバーヘッドもない. -\subsection{grepとの比較} -... -実験環境及びテキストファイルとして +{\bf マッチング}\\ +マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実 +装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ +グメント/関数と, switch文によるシンプルな実装であることから, コンパイル +されたバイナリの性能にあまり差が出ていないものだと思われる. + +本実装の中で最もマッチングが高速だったGCC-Cで生成した正規表現評価器を用 +いてgrep に相当するプログラムを実装し,実際にテキストファイルからのパター +ンマッチを行い, それぞれの評価を行った. + +{\bf 実験環境}\\ \begin{itemize} \item CPU : Core i7 950 @3.0GHz \item Memory : 16GB +\item GCC : 4.4.1 \item Text : Wikipedia 日本語版全記事\\ (XML, UTF-8, 4.7GB, 8000万行) \end{itemize} -を用いた. 表\ref{table:benchmark2}に結果を示す. + +表\ref{table:benchmark2}に結果を示す. \begin{table}[h] \caption{ベンチマーク:grep} \label{table:benchmark2} \begin{tabular}[t]{|l||l|l|l|} \hline -テストケース & fixed-string & simple-regex & complex-regex \\ +テストケース & fixed-string & simple-regex & complex-regex\\ \hline -本実装 & 13.90[s] & 15.45 & 14.83[s] \\ -コンパイル時間 & 0.15[s] & 0.17[s] & 0.23[s]\\ +本実装(GCC-C)[s] & 13.90 & 15.45 & 14.83\\ +(コンパイル[s]) & 0.15 & 0.17 & 0.23\\ \hline -GNU grep 2.6.3 & 2.93[s] & 5.65[s] & 16.86[s] \\ +GNU grep 2.6.3[s] & 2.93 & 5.65 & 16.86\\ \hline -GNU grep 2.5.4 & 2.96[s] & 6.37[s] & 188.51[s] \\ +GNU grep 2.5.4[s] & 2.96 & 6.37 & 188.51\\ \hline \end{tabular} \end{table} @@ -460,13 +482,13 @@ いる. 2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている. -\begin{figure*}[H] +\begin{figure}[!t] \begin{center} -\scalebox{0.80}{\includegraphics{fig6.eps}} +\scalebox{0.50}{\includegraphics{fig6.eps}} \caption{正規表現``(あ$|$い)*う''に対応するDFA} \label{figure:multibyte-dfamaple} \end{center} -\end{figure*} +\end{figure} {\bf 柔軟な実装}\\ 本実験で実装した正規表現評価器は, Pythonによって実装されており,全体 @@ -478,13 +500,14 @@ 化技術を利用することで実行速度も非常に高速なものとなっていることが実験結 果から分かる. -... - \section{まとめと今後の課題} 本実験では, 正規表現をコードセグメント/関数による状態遷移を行うコードに -変換し, GNU grep との比較を行い良好な結果を得た. +変換し, GNU grep との比較を行い良好な結果を得た. また, コードセグメント +と継続を基本とした言語であるCbCでの実装に適した例題の生成系として, 今後 +のCbCコンパイラ開発に役立てて行きたい. -... +今後の課題として, バックリファレンス等の拡張された正規表現の機能への対 +応, Boyer-Moore法等のフィルタの導入による高速化などにあたっていきたい. \begin{adjustvboxheight} % needed only when Appendix follows \begin{thebibliography}{99} @@ -504,8 +527,6 @@ \bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968 -\bibitem{H} 長谷川 勇 : 国際正規表現ライブラリの開発 - \bibitem{Y} 与儀 健人 : 組込み向け言語Continuation based CのGCC上の実装, 2010