Mercurial > hg > Papers > 2010 > jsst-shinya

comparison paper.tex @ 13:c113bb7d6381

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify preamble. correct typo.
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Fri, 27 Aug 2010 22:06:23 +0900
parents c2aaa766746a
children bd07b27b2b97
comparison
equal deleted inserted replaced
12:c2aaa766746a 13:c113bb7d6381
1 % Sample file for the use of compsoft style file. 1 % Sample file for the use of compsoft style file.
2 % 2 %
3 \documentclass{compsoft} 3 \documentclass[T]{compsoft}
4 % \documentclass[L]{compsoft} 4 % \documentclass[L]{compsoft}
5 % \documentclass[S]{compsoft} 5 % \documentclass[S]{compsoft}
6 % \documentclass[S,L]{compsoft} 6 % \documentclass[S,L]{compsoft}
7 % \documentclass[K]{compsoft} 7 % \documentclass[K]{compsoft}
8 % \documentclass[K,L]{compsoft} 8 % \documentclass[K,L]{compsoft}
11 11
12 % Preamble 12 % Preamble
13 % 13 %
14 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で 14 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
15 % 巻数，号数，開始ページ，終了ページを指定する． 15 % 巻数，号数，開始ページ，終了ページを指定する．
16 \volNoPp{16}{5}{78}{83} 16 % \volNoPp{16}{5}{78}{83}
17 17
18 % ワークショップによる推薦論文の場合，ワークショップ名を指定する． 18 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
19 % \suisen{ワークショップ名} 19 % \suisen{ワークショップ名}
20 20
21 % 特集の場合，特集のタイトルを与える． 21 % 特集の場合，特集のタイトルを与える．
22 % \tokushu{特集のタイトル} 22 % \tokushu{特集のタイトル}
23 23
24 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から 24 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
25 % 大会の回数は計算される． 25 % 大会の回数は計算される．
26 % \taikai{2009} 26 \taikai{2010}
27 27
28 % ここに，使用するパッケージを列挙する． 28 % ここに，使用するパッケージを列挙する．
29 \usepackage[dvips]{graphics} 29 \usepackage[dvips]{graphics}
30 30
31 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの 31 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
55 % 55 %
56 % 出典情報は \shutten とすれば出力される． 56 % 出典情報は \shutten とすれば出力される．
57 \shutten 57 \shutten
58 % 58 %
59 % 受付年月日，記事カテゴリなどは自動的に生成される． 59 % 受付年月日，記事カテゴリなどは自動的に生成される．
60 \uketsuke{2010}{8}{25} 60 \uketsuke{2010}{8}{27}
61 % 61 %
62 % その他，脚注に入れるものがあれば，\note に記述する． 62 % その他，脚注に入れるものがあれば，\note に記述する．
63 %\note{脚注に入れる内容} 63 %\note{脚注に入れる内容}
64 } 64 }
65 65
69 当研究室では, Concinuation based C という, 状態遷移記述に適した C の下位 69 当研究室では, Concinuation based C という, 状態遷移記述に適した C の下位
70 言語を提案している.Continuation based C は ステートメントより大きく, 関数よりも小さなプログラ 70 言語を提案している.Continuation based C は ステートメントより大きく, 関数よりも小さなプログラ
71 ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている. 71 ミング単位としてコードセグメントを持ち, コードセグメントからの継続を基本としている.
72 本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し, 72 本研究では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
73 オートマトンにおける状態遷遷移を Continuation based Cによる継続に変換する 73 オートマトンにおける状態遷遷移を Continuation based Cによる継続に変換する
74 正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルは, 74 正規表現コンパイラ を Python で実装した. なお, ここで言うコンパイルとは,
75 内部形式/中 間表現への変換だけでなく,実行時バイナリの生成までを指す.} 75 プログラム内部での中間表現への変換だけでなく,実行時バイナリの生成までを指す.}
76 % 76 %
77 \maketitle 77 \maketitle
78 78
79 \section{はじめに} 79 \section{はじめに}
80 コンパイラ理論の発展と共に, コンパイルにかかる時間はより短く, また得られ 80 コンパイラ理論の発展と共に, コンパイルにかかる時間はより短く, また得られ
238 238
239 \subsection{DFAから実行バイナリの生成}\label{subsection:compile} 239 \subsection{DFAから実行バイナリの生成}\label{subsection:compile}
240 DFAからの実行バイナリ生成には, 3種類の実装を行った. 240 DFAからの実行バイナリ生成には, 3種類の実装を行った.
241 241
242 \begin{enumerate} 242 \begin{enumerate}
243 \item DFA $\rightarrow$ Continuation based C $\rightarrow$ gccによるコンパ 243 \item DFA $\rightarrow$ Continuation based C $\rightarrow$ GCCによるコンパ
244 イル 244 イル
245 \item DFA $\rightarrow$ C $\rightarrow$ gccによるコンパイル 245 \item DFA $\rightarrow$ C $\rightarrow$ GCCによるコンパイル
246 \item DFA $\rightarrow$ LLVM中間表現 $\rightarrow$ LLVMによるコンパイル 246 \item DFA $\rightarrow$ LLVM中間表現 $\rightarrow$ LLVMによるコンパイル
247 \end{enumerate} 247 \end{enumerate}
248 % 248 %
249 249
250 以下, Continuation based C, LLVMの説明と, それを利用したDFAからの 250 以下, Continuation based C, LLVMの説明と, それを利用したDFAからの
251 実行バイナリ生成の方法を説明する. 251 実行バイナリ生成の方法を説明する.
252 252
253 \subsubsection{Continuation based C} 253 \subsubsection{Continuation based C}
254 Continuation based C(以下CbC)は, ... 254 Continuation based C(以下CbC)は, プログラミングの基本単位としてコードセ
255 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装されて 255 グメントを持ち, コードセグメント間の軽量継続を基本としたCの下位言語であ
256 いる\cite{Y},本研究ではgcc-4.5上に実装されたCbCコンパイラを用いた. 256 る. 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装さ
257 れており\cite{Y}, GCCの末尾再帰最適化を強制することで, 関数と同様の記述
258 が可能で, かつ関数呼び出しに伴なうリターンアドレスの保存や,スタックの成
259 長のない, ``引数付きgoto''として継続を実装している.本研究ではgcc-4.5上に
260 実装されたCbCコンパイラを用いた.
257 261
258 以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC 262 以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC
259 のコードセグメントの生成例を示す. 263 のコードセグメントの生成例を示す.
260 264
261 \newpage
262 \begin{figure}[t] 265 \begin{figure}[t]
263 \begin{center} 266 \begin{center}
264 \scalebox{0.60}{\includegraphics{fig5.eps}} 267 \scalebox{0.60}{\includegraphics{fig5.eps}}
265 \caption{正規表現``$(A|B)*C$''に対応するDFA} 268 \caption{正規表現``$(A|B)*C$''に対応するDFA}
266 \label{figure:dfasmaple} 269 \label{figure:dfasmaple}
314 えた, モジュール単位で利用可能なコンパイラ基盤である\cite{L}. 317 えた, モジュール単位で利用可能なコンパイラ基盤である\cite{L}.
315 318
316 CbC/Cによる実装では,DFAからCbC/Cのソースコードに変換し,GCCによってコンパ 319 CbC/Cによる実装では,DFAからCbC/Cのソースコードに変換し,GCCによってコンパ
317 イルを行っている. LLVMによる実装では, LLVMの中間表現であるLLVM-IRを,提供 320 イルを行っている. LLVMによる実装では, LLVMの中間表現であるLLVM-IRを,提供
318 されているAPIを用いて直接操作を行い, コンパイルを経て実行バイナリを得る. 321 されているAPIを用いて直接操作を行い, コンパイルを経て実行バイナリを得る.
319 PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-pyを使用した. 322 PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-py\footnote{http://www.mdevan.org/llvm-py/}を使用した.
320 323
321 \begin{figure}[t] 324 \begin{figure}[t]
322 \begin{center} 325 \begin{center}
323 \scalebox{0.60}{\includegraphics{fig7.eps}} 326 \scalebox{0.60}{\includegraphics{fig7.eps}}
324 \caption{LLVMを用いた実装} 327 \caption{LLVMを用いた実装}
340 343
341 {\bf 実験環境} 344 {\bf 実験環境}
342 \begin{itemize} 345 \begin{itemize}
343 \item CPU : Core 2 Duo 950 @3.0GHz 346 \item CPU : Core 2 Duo 950 @3.0GHz
344 \item Memory : 16GB 347 \item Memory : 16GB
345 \item GCC (c) : 4.0.1 348 \item GCC : 4.5.0
346 \item LLVM: 2.4 349 \item LLVM: 2.4
347 \end{itemize} 350 \end{itemize}
348 351
349 {\bf コンパイル}\\ 352 {\bf コンパイル}\\
350 n個の単語を正規表現のOR演算で繋げたパターンに対し, 各実装のコンパイル時 353 n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
351 間の比較を行った. 354 間の比較を行った.
352 355
353 \begin{table}[h] 356 \begin{table}[h]
354 \caption{ベンチマーク:compile} 357 \caption{ベンチマーク:compile}
355 \label{table:benchmark1} 358 \label{table:benchmark1}
356 \begin{tabular}[t]{|l||l|l|l||l|} 359 \begin{tabular}[t]{|l||l|l|l||l|}
357 \hline 360 \hline
358 n (単語数)& 1 & 10 & 50 & 100 \\ 361 n (単語数)& 1 & 10 & 50 & 100 \\
359 \hline 362 \hline
360 DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\ 363 DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\
361 状態数[個]& 8 & 50 & 187 & 381\\ 364 DFAの状態数 & 8 & 50 & 187 & 381\\
362 \hline 365 \hline
363 GCC-C [s] & 0.34 & 0.78 & 2.18 & 4.27\\ 366 GCC-C [s] & 0.34 & 0.78 & 2.18 & 4.27\\
364 \hline 367 \hline
365 GCC-CbC[s] & 0.75 & 1.03 & 9.14 & 9.43\\ 368 GCC-CbC[s] & 0.75 & 1.03 & 9.14 & 9.43\\
366 \hline 369 \hline
369 \end{tabular} 372 \end{tabular}
370 \end{table} 373 \end{table}
371 374
372 表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速 375 表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速
373 に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作 376 に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作
374 することで, I/Oやパース等のオーバーヘッドもない. 377 することで, ファイルI/Oやパース等のオーバーヘッドもない.
375 378
376 {\bf マッチング}\\ 379 {\bf マッチング}\\
377 マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実 380 マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実
378 装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ 381 装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ
379 グメント/関数と, switch文によるシンプルな実装であることから, コンパイル 382 グメント/関数と, switch文によるシンプルな実装であることから, コンパイル
435 438
436 \item[complex-regex]複雑な正規表現でのマッチング\\ 439 \item[complex-regex]複雑な正規表現でのマッチング\\
437 パターン :``$(Python|Perl|Pascall|Prolog|\\ 440 パターン :``$(Python|Perl|Pascall|Prolog|\\
438 PHP|Ruby|Haskell|Lisp|Scheme)$''\\ 441 PHP|Ruby|Haskell|Lisp|Scheme)$''\\
439 マッチ行数: 1503行\\ 442 マッチ行数: 1503行\\
440 このパターンは,9個の単語をORで並べたもので,確実に含まれる文字列は存在せ 443 このパターンは,9個の単語を和集合演算 ``$|$''で並べたもので,確実に含まれる文字列は存在せ
441 ず,先の二つに比べてGNU grep は遅い結果となっている. 444 ず,先の二つに比べてGNU grep は遅い結果となっている.
442 445
443 GNU grep 2.5.4 は188秒と, 本実装及びGNU grep 2.6.3に対して非常に遅い結 446 GNU grep 2.5.4 は188秒と, 本実装及びGNU grep 2.6.3に対して非常に遅い結
444 果となっているが, これは後述する mbrtowc(3) によるマルチバイト文字の変換 447 果となっているが, これは後述する mbrtowc(3) によるマルチバイト文字の変換
445 処理によるオーバーヘッドによるものである. 448 処理によるオーバーヘッドによるものである.
446 \end{description} 449 \end{description}
447 450
448 3つのテストケースの結果を見てみると, 本実装はそれぞれ実行時間にあまり差 451 3つのテストケースの結果を見てみると, 本実装はそれぞれ実行時間にあまり差
449 がなく, またコンパイル時間はマッチングにかかる時間と比べて無視できるなっ 452 がなく, またコンパイル時間はマッチングにかかる時間と比べて無視できるほど
450 ている. また, complex-regexのテストケースではGNU grepよりも高速な結果が 453 短い時間である. また, complex-regexのテストケースではGNU grepよりも高速
451 出ており, 本実装は(フィルタリングを用いない)純粋なDFAマッチングにおいて 454 な結果が出ており, 本実装は(フィルタリングを用いない)純粋なDFAマッチング
452 パターンに比べて検索対テキストファイルが十分に大きな場合の検索にコンパイ 455 において, 本実装によって動的に生成されたコードの性能が高いことが分かる.
453 ルの効果が発揮されていることが分かる.
454 456
455 \subsection{特徴} 457 \subsection{特徴}
456 本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ 458 本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
457 みながら説明する. 459 みながら説明する.
458 460
482 いる. 484 いる.
483 2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に 485 2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に
484 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている. 486 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.
485 \begin{figure}[!t] 487 \begin{figure}[!t]
486 \begin{center} 488 \begin{center}
487 \scalebox{0.50}{\includegraphics{fig6.eps}} 489 \scalebox{0.40}{\includegraphics{fig6.eps}}
488 \caption{正規表現``(あ$|$い)*う''に対応するDFA} 490 \caption{正規表現``(あ$|$い)*う''に対応するDFA}
489 \label{figure:multibyte-dfamaple} 491 \label{figure:multibyte-dfamaple}
490 \end{center} 492 \end{center}
491 \end{figure} 493 \end{figure}
492 494