Binary file Paper/images/delay.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/images/delay.xbb	Thu Jul 18 17:27:54 2013 +0900
@@ -0,0 +1,8 @@
+%%Title: ./delay.pdf
+%%Creator: extractbb 20120420
+%%BoundingBox: 0 0 360 252
+%%HiResBoundingBox: 0.000000 0.000000 360.000000 252.000000
+%%PDFVersion: 1.4
+%%Pages: 1
+%%CreationDate: Thu Jul 18 16:19:11 2013
+

Binary file Paper/images/para.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/images/para.xbb	Thu Jul 18 17:27:54 2013 +0900
@@ -0,0 +1,8 @@
+%%Title: ./para.pdf
+%%Creator: extractbb 20120420
+%%BoundingBox: 0 0 360 252
+%%HiResBoundingBox: 0.000000 0.000000 360.000000 252.000000
+%%PDFVersion: 1.4
+%%Pages: 1
+%%CreationDate: Thu Jul 18 16:37:16 2013
+

--- a/Paper/jssst.bib	Thu Jul 18 15:11:05 2013 +0900
+++ b/Paper/jssst.bib	Thu Jul 18 17:27:54 2013 +0900
@@ -47,17 +47,6 @@
     title = "Dynamo: Amazon's Highly Avaliable Key-value Store"
 }
 
-@article{seda:1,
-    author = "Matt Welsh",
-    title = "The Staged Event-Driven Architecture for Highly-Concurrent Server Applications"
-}
-
-@article{seda:2,
-    author = "Matt Welsh, David Culler, Eric Brewer",
-    title = "SEDA : An Architecture for Well-Conditioned , Scalable Internet Services",
-    journal = "SOSP"
-}
-
 @misc{warp,
   title = {The warp package},
   howpublished = "\url{http://hackage.haskell.org/package/warp}",

--- a/Paper/jssst.tex	Thu Jul 18 15:11:05 2013 +0900
+++ b/Paper/jssst.tex	Thu Jul 18 17:27:54 2013 +0900
@@ -18,6 +18,8 @@
 % 大会の回数は計算される．
 \taikai{2013}
 
+\pagestyle {empty}
+
 % ここに，使用するパッケージを列挙する．
 \usepackage[dvipdfmx]{graphicx}
 \usepackage{url}
@@ -47,7 +49,7 @@
 %
 % ここにタイトル英訳 (英文の場合は和訳) を書く．
 %
-\ejtitle{Implementation of the CMS using Nondestructive tree structure with Haskell}
+\ejtitle{Implementation of the CMS using Nondestructive Tree Structure and Haskell}
 %
 % ここに著者英文表記 (英文の場合は和文表記) および
 % 所属 (和文および英文) を書く．
@@ -72,8 +74,9 @@
 ウェブサービスではユーザの増加に対応し、容易に拡張できるスケーラビリティが求められる。 
 コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 
 本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。
-非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 
-コンテンツマネージメントシステムの実装にはプログラミング言語 Haskell を用いる。また、Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装およびCassandraとの性能の比較を行う。
+非破壊的木構造では、少ない排他制御で変更を行えるためスケーラビリティを確保できる。 
+コンテンツマネージメントシステムの実装にはプログラミング言語 Haskell を用いた。
+Haskell で書かれた HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存の Java の実装と比較して、短い開発期間やコード行数で同程度の性能を達成できた。
 }
 
 %
@@ -81,6 +84,7 @@
 % \Eabstract{}
 %
 \maketitle
+\thispagestyle {empty}
 
 \section{はじめに}
 ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。
@@ -90,16 +94,16 @@
 本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。
 非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 
 
-コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いる。
+コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いた。
 Haskell は 純粋関数型プログラミング言語である。
-純粋であるため、非破壊な変数代入は許されていない。
+純粋であるため、一度定義した変数の書き換えは許されていない。
+また、生産性が高いことも特徴で、本システムの実装においても開発期間およびコード行数は非常に短くなった。
 
-Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装およびCassandraとの性能の比較を行う。
+Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。
 
 \section{Haskell}
 Haskell は、純粋関数型プログラミング言語である。
 関数型プログラミング言語では、引数に関数を作用させていくことで計算を行う。
-純粋とは、式や関数は副作用を持たないという意味である。
 変数への代入は一度のみで、書き換えることはできない。
 遅延評価や、強い静的型付けも Haskell の特徴である。
 
@@ -117,8 +121,9 @@
 ソースコード \ref{warp_sample}は、URLによって出力する結果を変更するウェブアプリケーションである。
 /hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。
 
+\paragraph*{main 関数}
 HTTP サーバを起動するには、Warp の run 関数を利用する。
-run 関数は、利用する Port 番号 と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。
+run 関数は、利用する Port 番号と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。
 
 関数型言語では、関数を第一級オブジェクトとして扱える。
 また、今回は Haskell のカリー化された関数の特性を利用し、main 内で作成した IORef 型の counter を部分適用させている。
@@ -128,15 +133,18 @@
 IORef 自体が入出力を行うわけではなく、単なる入出力操作の指示にすぎない。
 IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う。
 
+\paragraph*{application 及び routes , findRoute 関数}
 application の実装では、routes という関数を独自に定義して、URL によって出力を変更している。
 application に渡されるリクエストはデータ型で様々な情報が含まれている。
 その中のひとつに pathInfo という、URL から hostname/port と、クエリを取り除いたリストがある。
 この情報を routes という関数に渡すことで、routeSetting というリストから一致する URL がないか調べる。
 routeSetting は、URL のリストとレスポンスを返す関数のタプルのリストである。
 
+\paragraph*{notFound 及び hello 関数}
 レスポンスを返す関数は、いくつか定義されている。
 その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである。
 
+\paragraph*{world 関数}
 world は、インクリメントされる counter を表示するための関数である。
 IORef 内のデータは直接触ることができないため、atomicModifyIORef を利用してデータの更新を行なっている。
 atomicModifyIORef は、データの更新をスレッドセーフに行うことができる。
@@ -150,7 +158,7 @@
 非破壊的木構造とは、編集元の木構造を破壊することなく新しい木構造を構成することで木構造を編集する方法である。
 
 破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能である。
-コピーを複数作成し、アクセスを分散させることで性能を維持することができると考えられる。
+コピーを複数作成し、アクセスを分散させることで性能を維持することができる。
 
 通常の破壊的木構造との違いを説明する。
 
@@ -224,17 +232,17 @@
 
 \section{コンテンツマネージメントシステムの実装}
 コンテンツマネージメントシステムのデータ構造としては木構造を用いると述べた。
-我々が開発している木構造データベース Jungle について説明する。
-\subsection{木構造データベース Jungle}
-Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装も存在する。
+我々が開発している木構造データベース Jungle \cite{shoshi:2011b} について説明する。
+
+Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装が存在する。
 本研究では、Haskell を用いて実装を行った。
 コンテンツマネージメントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。
 
-\subsubsection{利用方法}
+\subsection{利用方法}
 \paragraph*{木の作成}
 はじめに、データベースオブジェクトと木の作成方法について述べる。
 Jungle は複数の木を保持することができる。
-木には名前がついており、名前を利用して作成・編集・削除を行うことができる。
+木には名前がついており、名前を利用して作成・編集・削除を行うことができる。\\
 
 \begin{lstlisting}[label=new_jung, caption=データベースオブジェクトと木の作成]
 jungle = createJungle
@@ -271,7 +279,7 @@
 毎回、新しい変数に代入することで記述が少々煩雑になりやすい。
 State モナドを用いて記述を簡易にしたものもあるが、利用者にどのようなAPIを提供するかは検討中である。
 
-\subsubsection{実装の詳細}
+\subsection{実装の詳細}
 \paragraph*{Treeの取り扱い}
 Jungle の Tree の取り扱いには、Haskell の Map を用いている。
 Mapは、平衡木を使った Haskell の連想リストである。
@@ -380,11 +388,50 @@
 
 Haskell版およびJava版のJungleは、ほぼ同程度の速度が出ていることが分かる。
 また、Cassandraと比較して、僅かながらJungleが速く処理を終えている。
-書き込み速度において、Jungle-Javaが
+% Jungle-Javaのブレについて述べる
+% スレッドスタックのサイズを大きくして計測してみる
+
+\subsection{遅延評価}
+
+Haskell は遅延評価を行うが、書き込みの際に問題が生じる。
+何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。
+その際メモリを消費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる。
+図\ref{fig:write}の結果では、オプションで推奨されるヒープ領域のサイズを変更してある。
+推奨されるヒープ領域のサイズを変更しない場合の実験結果を図\ref{fig:delay}に示す。
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=70mm]{./images/delay.pdf}
+ \end{center}
+ \caption{推奨されるヒープ領域のサイズを変更しない場合の実験結果}
+ \label{fig:delay}
+\end{figure}
 
-遅延評価の問題
+急に実行時間が下がっている点が3箇所あるが、手動で掲示板の表示を挟んだ箇所である。
+数万回以上の書き込みを処理するため、書き込みが積まれている状態ではじめて掲示板を表示する際は数秒かかる。
+書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理されている。
+
+この問題を解決するために、全て遅延評価するのではなく正則評価を挟むことでメモリ効率を向上する必要がある。
+
+\subsection{並列処理}
+
+Haskell 版 Jungle では、並列実行に問題を抱えている。
+並列に動かすことは可能だが、シングルコアで実行した場合と比較して実行結果が遅くなる。
+図\ref{fig:read}や図\ref{fig:write}の結果では、Haskell版はシングルコアで実行している。
 
-並列の問題
+並列に動かした場合の実験結果を図\ref{fig:para}に示す。
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=70mm]{./images/para.pdf}
+ \end{center}
+ \caption{並列に動かした場合の実験結果}
+ \label{fig:para}
+\end{figure}
+
+本研究のウェブアプリケーションとは別に、簡単な例題を並列で動かした場合でも実行速度の向上が見られない。
+並列処理で速度向上をはかることは、今後の課題である。
+
 \section{おわりに}
 実装を行った