# HG changeset patch # User Daichi TOMA # Date 1392127123 -32400 # Node ID 79d168016df47ca690e362e169312f407e5f7876 # Parent 0644825c43acf37a088dbbaeac925c43d3f21535 add memorize diff -r 0644825c43ac -r 79d168016df4 paper/abstract.tex --- a/paper/abstract.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/abstract.tex Tue Feb 11 22:58:43 2014 +0900 @@ -12,6 +12,6 @@ マルチコアプロセッサの性能を引き出すことができた. また, 実用的な用途で利用できるか示すために, Web 掲示板サービスを開発した. -既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 1.87 倍, 書き込みで 2.3 倍の性能が確認できた. +既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 3.25 倍, 書き込みで 3.78 倍の性能が確認できた. \end{abstract} diff -r 0644825c43ac -r 79d168016df4 paper/abstract_eng.tex --- a/paper/abstract_eng.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/abstract_eng.tex Tue Feb 11 22:58:43 2014 +0900 @@ -11,5 +11,5 @@ We measures the performance for reading and writing of parallel database. We achieve to bring out the performance of the multi-core processor. -Further, in order to indicate the availability of practical applications, we have developed a Web bulletin board service. +Further, in order to indicate the availability of practical applications, we have developed a web bulletin board service. \end{abstract_eng} diff -r 0644825c43ac -r 79d168016df4 paper/benchmark/warp/ghc.dat --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/benchmark/warp/ghc.dat Tue Feb 11 22:58:43 2014 +0900 @@ -0,0 +1,8 @@ +1 31602 +2 69265 +3 97520 +4 133897 +5 161649 +6 83131 +7 63205 +8 31694 diff -r 0644825c43ac -r 79d168016df4 paper/chapter1.tex --- a/paper/chapter1.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/chapter1.tex Tue Feb 11 22:58:43 2014 +0900 @@ -5,6 +5,7 @@ 関数とは, 一つの引数を取り一つの結果を返す変換器のことである. 関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う. +\subsubsection{関数の定義} 既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. 例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. @@ -19,22 +20,24 @@ fib :: Int -$>$ Int は, 関数の型宣言である. この関数は, Int を受け取って Int を返す関数ということを示す. フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. -引数が 0 ならば 2 行目の fib が呼び出される. -引数が 1 ならば 3 行目の fib が呼び出される. -上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛される. +引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる. +引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる. +上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される. フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. 再帰は, 関数型プログラミング言語において必要不可欠な要素である. -手続き型言語では, 配列とループを主に用いてプログラミングを行うが, Haskell ではリスト構造と再帰を用いる. +手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる. +\subsubsection{変数の代入} 純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. 関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. この性質は関数の理解を容易にし, プログラムの証明を可能にする. 正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. +\subsubsection{高階関数} 関数型プログラミング言語は, 関数を変数の値にすることができる. -つまりこれは, 関数を第一級オブジェクトとして扱うことができるということである. +これは, 関数を第一級オブジェクトとして扱うことができるということである. Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. 高階関数の例として Haskell のカリー化が挙げられる. @@ -43,6 +46,9 @@ \begin{lstlisting}[label=src:max, caption=max関数] max :: Int -> Int -> Int +max x y = if x <= y + then y + else x \end{lstlisting} この関数定義に現れる-$>$は左結合である. @@ -56,10 +62,11 @@ カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる（ソースコード\ref{src:partial}）. \begin{lstlisting}[label=src:partial, caption=関数の部分適用] -x = max 3 -x 4 -- max 3 4 の結果として 4 が返される +x = max 3 -- x は Int -> Int の関数 +x 4 -- (max 3) 4 の結果として 4 が返される \end{lstlisting} +\clearpage \section{型} Haskell では, すべての式, すべての関数に型がある. 値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. @@ -67,16 +74,17 @@ 型はプログラムに抽象をもたらす. 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. -例えば, 値の型が文字列ならば, どのように実装されているかという細かいことは気にせず, +例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず, その文字列が他の文字列と同じように振る舞うとみなすことができる. +\subsubsection{型の定義と型検査} Haskell は静的型検査によりエラーを検出することができる. Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. -引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. +例えば, 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. -エラーの検出の例として, Haskell で最もよく使われるデータ構造, リストで確認を行う. -また, リストの定義とあわせてデータ型の定義についても説明する. +エラーの検出の例として Haskell で最もよく使われるデータ構造であるリスト型で確認を行う. +また, リスト型の定義とあわせてデータ型の定義についても説明する. リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. リストはソースコード\ref{src:list}のように定義されている. @@ -86,29 +94,35 @@ \end{lstlisting} data というのは新しい型を定義する際に利用するキーワードである. -[] というのが型名である. +data キーワードのすぐ後にある [] a というのが型名である. -型名の右に a というのがあるが, これは多相型を表すのに使う型変数である. -型変数は様々な型を取ることができる. -リストは, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. -型変数が何の型になるのかという情報は実行時には決まっており, Haskell の型安全を保つ. +a というのは, 型変数と呼ばれるものである. +型変数は任意の型を取ることができる. +リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. +型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない. -= の右側が, 新しい型の定義である. += の右側には, 新しい型の定義として型の値となるものを列挙する. $|$ は, もしくはという意味である. つまりリストは, [] もしくは a : [a] という値になることが分かる. + [] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. 型名はプログラム中では注釈としてしか使われないためである. a : [a] は再帰的なデータ構造である. -何らかの型の値 a を : で繋げて, 再度リストの定義を呼んでいる. +値 a を : で繋げて, 再度リストの定義を呼んでいる. -リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. -[1,2,3]という様にリストを表すが, これは単なるシンタックスシュガーであり, +この定義 [] $|$ a : [a] は, a : a : a : .. : a : [] となり, a が任意個続いた後に, [] が来ることとなる. +つまり, リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. + +Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり, 内部では 1 : 2 : 3 : [] のように表現される. -リストは : を使うことで新しい要素を加えることができるが, 型変数は1つであり, 全ての要素は同じ型の要素である必要がある. +このように定義した型であっても, Haskell は型検査を行う. +リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある. 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. 例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する（ソースコード\ref{src:error}）. +型の定義に型変数を用いても Haskell は, [3,4] が何の型になるのかといった情報を推論する. +そのため文字である 'b' をIntのリスト [3,4] に付け加えることはできない. \begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー] :3:7: @@ -120,7 +134,6 @@ 型検査でも捕まえられないエラーは存在する. 例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. - \subsubsection{型推論} Haskell は型推論を持つ. 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. @@ -157,6 +170,7 @@ Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. +\clearpage \section{モナド} Haskell では, さまざまな目的にモナドを使う. I/O 処理を行うためには IO モナドを使う必要がある. @@ -167,7 +181,7 @@ ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. これは, それらの関数がその型ではどのような意味になるのか定義するということである. -モナドとなる型は, 型変数として具体型をただ１つ取る. +モナドとなる型は, 型変数として具体型をただ 1 つ取る. これにより何かしらのコンテナに包まれた値を実現する. モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する（ソースコード\ref{monad}）. @@ -229,7 +243,7 @@ \end{lstlisting} instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. -その後実装すべき関数である return と $>>$= (bind) を定義していく. +モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく. Maybe モナドの return は, 値をJustで包む. これがコンテナに包む機能という意味である. @@ -250,8 +264,8 @@ \end{lstlisting} 関数 up と down を定義した. -up の場合, 引数として4が渡された場合, 上がれないため失敗, -down の場合, 引数として0が渡された場合, 下がれないため失敗と考える. +up の場合, 引数として4が渡された場合は上がれないため失敗, +down の場合, 引数として0が渡された場合は下がれないため失敗と考える. 3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. @@ -267,23 +281,25 @@ \end{lstlisting} -case 式は, caseとofの間の式を評価し, その値によっ評価を分岐させることができる. -case を受け取る $->$ の左の部分はパターンマッチを行うこともできる. -また, case は式のため, $->$ の右の部分の全ての型は一意である必要がある. -Haskell では分岐によって返ってくる値の型が異なるということはできない. +case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである. +case を受け取る $->$ の左の部分には式の値を書き, その式の値によって評価を分岐させる. +例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である. +Justの場合, 値をplace1という変数に束縛しその後の処理を続ける. -毎回, 失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. -これを文脈を保ったまま, 関数を繋げられる モナドを使えばソースコード\ref{src:upmonad}のように記述できる. +ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. +これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる. \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う] return 3 >>= down >>= down >>= up >>= up \end{lstlisting} -Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を扱うことができる. +Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる. \subsubsection{IO モナド} Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. -IO モナド自体は単なる命令書であり, 命令ではない. +IO モナドは, 処理系が現実世界に対する副作用に変換できるモナドである. + +IO モナド自体は, 「文字を1文字取ってくる」といった命令書である. bind を使って, 小さな命令書を合成して大きな命令書を作成できる. 最終的に, mainという名前をつけることで初めてランタイムにより実行される（ソースコード\ref{src:iomonad}）. @@ -300,10 +316,79 @@ どんな状況においても同じ命令書を返すため, 副作用はない. \clearpage +\section{遅延評価} +Haskell では, 必要となるまで式の評価が遅延される. +Haskell の対話環境である GHCi でどのように評価されるか確認することができる. + +GHCiで評価を強制せずに値を表示する :sprint コマンドを使う. +例えば, x を定義した後に :sprint コマンドを使うとソースコード\ref{src:sprint} のように表示される\footnote{GHCiでは, 関数や変数を定義する際にはletが必要となる.}. + +\begin{lstlisting}[label=src:sprint, caption=sprintコマンドの使用例] +ghci> let x = 1 + 2 +ghci> :sprint x +x = _ +\end{lstlisting} + +\_ は式が未評価であることを示している. +Haskell ではこの未評価の部分を thunk と呼ぶ. + +\begin{lstlisting}[label=src:list_sprint, caption=リストの評価の様子] +ghci> let y = map (+1) [1,2,3] :: [Int] +ghci> :sprint y +y = _ +ghci> length y +3 +ghci> :sprint y +y = [_,_,_] +ghci> head y +2 +ghci> :sprint y +y = [2,_,_] +\end{lstlisting} + +リストを使ってどのように評価されるのか確認する. +ソースコード\ref{src:list_sprint} では, まずmap関数を利用してリストの要素を全て (+1) している. +しかし, この計算は必要となるまで計算されない. +直後にsprintを行うと, ただ\_が表示される. + +リストの長さを表示する関数であるlengthを実行後に sprint を行った場合は, +リストの要素数を確認しているため、要素数分のthunkを持つリストとなる. + +実際に値が必要となる関数を適用する. +head はリストの先頭要素を取得する関数である. +head を適用後に, sprint を行うと先頭要素だけが評価されたリストとなる. + +リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる. + +\subsubsection{引数のメモ化} + +Haskell の遅延評価では引数のメモ化を行う. +ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである. +例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される. +y は未評価のthunkとして同じ x を参照する. +そのため, x が2回評価されることはない. + +\newpage +\begin{lstlisting}[label=memo, caption=メモ化] +Prelude> let x = 1 + 2 :: Int +Prelude> let y = (x,x) +Prelude> :sprint y +y = (_,_) +\end{lstlisting} + +\begin{figure}[!htbp] + \begin{center} + \includegraphics[scale=0.6]{./images/memo.pdf} + \end{center} + \caption{メモ化の様子} + \label{fig:memo} +\end{figure} + +\clearpage \section{並列実行} Haskellはデフォルトではシングルスレッドで走る. 並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する. --N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される. +-N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される（ソースコード\ref{concurrent}）. \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子] $ ghc -O2 par.hs -threaded @@ -342,7 +427,12 @@ Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. 今回は, print (runEval test)が実行される. -\begin{lstlisting}[label=eval, caption=Eval モナド] +並列処理を行いたい箇所には, rpar を使う. +rpar の引数とした関数は並列に実行可能であることを示すことができる. +Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している（ソースコード\ref{eval}）. +rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. + +\begin{lstlisting}[label=eval, caption=Eval モナドの型] data Eval a instance Monad Eval @@ -350,11 +440,6 @@ rpar :: a -> Eval a \end{lstlisting} -並列処理を行いたい箇所には, rpar を使う. -rpar の引数とした関数は並列に実行可能であることを示すことができる. -Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している. -rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. - rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. do 構文を使うことでbindの入れ子構造を簡潔に書ける. @@ -391,7 +476,7 @@ Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない. -rpar で作成した Eval モナドを runEval に渡したあと、値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. +rpar で作成した Eval モナドを runEval に渡したあと, 値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. 例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない. diff -r 0644825c43ac -r 79d168016df4 paper/chapter2.tex --- a/paper/chapter2.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/chapter2.tex Tue Feb 11 22:58:43 2014 +0900 @@ -82,7 +82,7 @@ STM はロックの管理という煩雑な処理から逃れられるだけでなく, 並列性も向上する. どのスレッドもリソースにアクセスするために待つ必要はない. -ルートノードの情報の取得だけならば, 並列に取得できる. +ルートノードの情報の取得は, 並列に行うことが可能である. ルートノードの情報の更新の場合は, 他から変更があれば再度やり直すということが自動的に行われる. 以前の実装では, ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}. diff -r 0644825c43ac -r 79d168016df4 paper/chapter3.tex --- a/paper/chapter3.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/chapter3.tex Tue Feb 11 22:58:43 2014 +0900 @@ -16,7 +16,7 @@ \subsubsection{Jungle が持つデータ型} 非破壊的木構造データベース Jungle が持つのデータ型を表\ref{tab:components}に表す. -また, データ型内部のデータ構造を\ref{tab:components2}に表す. +また, データ型内部のデータ構造を表\ref{tab:components2}に表す. 木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. Node は子と属性を任意の数持てる. @@ -25,7 +25,6 @@ 非破壊的木構造データベース Jungle のデータ型について, ひとつずつ説明する. \begin{table}[!htbp] -\label{tab:components} \begin{center} \begin{tabular}{|c||c|c|} \hline 型名 & 概要 \\ \hline @@ -34,11 +33,12 @@ Node & 基本的なデータ構造, 子と属性を任意の数持てる. \\ \hline \end{tabular} \end{center} +\label{tab:components} \caption{Jungle が持つデータ型} \end{table} -\begin{table}[!htbp] -\label{tab:components2} +\newpage +\begin{table}[htbp] \begin{center} \begin{tabular}{|c||c|} \hline 型名 & データ構造 \\ \hline @@ -47,10 +47,12 @@ Node & Node (Map Int Node) (Map String ByteString) \\ \hline \end{tabular} \end{center} +\label{tab:components2} \caption{データ型のデータ構造} \end{table} -\subsection{Jungle} +\clearpage +\section{Jungle} Jungle は木構造の集まりを表現する. 木には名前がついており, Tree の情報と一緒に保持している（ソースコード\ref{src:jungle}）. @@ -75,9 +77,9 @@ 型名は, Map である. Map は, 連想配列を扱うことのできるデータ構造である. 平衡木を用いて, 挿入や参照が O (log n)で済むように設計されている. -Data.Mapを理解するためにはリストで考えると分かりやすい. +Data.Mapを理解するためにはリストで考えると分かりやすい（ソースコード\ref{src:map_list}）. -\begin{lstlisting}[caption=getJungleMap] +\begin{lstlisting}[label=src:map_list, caption=リストで定義した場合のMap] data Map k a = Map [(k,a)] lookup' :: Eq k => k -> Map k a -> Maybe a @@ -102,7 +104,6 @@ 新たにキーと値のペアを, Mapに追加するには insertを用いる. Haskell では, 受け取った引数を変更することができないため, ペアを追加した新しい Map を返す. - 木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ, スレッド間で共有できるようにしてある. これは, 各スレッドから木構造を新たに作成できるようにするためである. STM は, スレッド間でデータを共有するためのツールである. STM を利用することでロック忘れによる競合状態や, デッドロックといった問題から解放される. @@ -147,7 +148,7 @@ atomically :: STM a -> IO a \end{lstlisting} -atomically の隣にある \$ は関数適用演算子である. +ソースコード\ref{src:createJungle}の atomically の隣にある \$ は関数適用演算子である. \$ 関数は最も低い優先順位を持っており, 右結合である. 括弧を減らすのに使う. \$ を使わない場合はソースコード\ref{src:dollar}の様に記述することになる. @@ -160,7 +161,8 @@ createJungle は, IOを返すため使う際には main に関連付ける必要がある. -\subsection{Tree} +\clearpage +\section{Tree} Jungleが保持する木の情報は, 内部的には Tree というデータ型で保持している. Tree は木の名前と, ルートノードの情報を持っている（ソースコード\ref{src:tree}）. 実際にユーザがJungleを利用する際は, Jungle と木の名前を使ってルートノードを取ってくるため, Tree という構造は見えない. @@ -226,7 +228,7 @@ 例えば, 図\ref{fig:getrootnode}の状態の時は, B というルートノードが取得できる. -getRootNode 関数の定義を示す（\ref{src:getrootnode}）. +getRootNode 関数の定義を示す（ソースコード\ref{src:getrootnode}）. まず, readTVarでJungleが持つmapを参照する. Haskell の where キーワードは, 計算の中間結果に名前をつけるために用いられる. 今回は, root\_node という map を受け取る関数を定義している. @@ -249,7 +251,7 @@ updateRootNode は, データベースと木の名前, 変更して返ってきた木構造の 3 つを渡す. updateRootNodeをした後は, getRootNodeで取得できるルートノードが更新された状態になっている. -updateRootNode 関数の定義を示す（\ref{src:updaterootnode}）. +updateRootNode 関数の定義を示す（ソースコード\ref{src:updaterootnode}）. getRootNodeと同じように, Treeの(TVar Node)を取得し, 最後にwriteTVarを用いて更新している. \begin{lstlisting}[label=src:updaterootnode, caption=ルートノードの更新] @@ -266,7 +268,8 @@ updateRootNodeWithは, ノードを更新する関数とデータベース, 木の名前を渡して利用する. ノードを更新する関数とは, ノードを受け取ってノードを返す関数である. (Node $->$ Node) がそれにあたる. このupdateRootNodeWithを利用することで, getRootNodeをした後に編集しupdateRootNodeを行う一連の操作が分断されずに行われることが保証される. -updateRootNode 関数の定義を示す（\ref{src:updaterootnodewith}）. + +updateRootNodeWith 関数の定義を示す（ソースコード\ref{src:updaterootnodewith}）. updateRootNodeWithでは, 一連の操作を分断せずに行うためにreadTVarからwriteTVarまで同じ STM モナド内で行っている. atomicallyに関数にdo構文で繋げたSTMモナドを渡すことで, このブロックがトランザクションとして実行される. @@ -288,7 +291,8 @@ 並列データベース Jungle では, なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する. ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの, 読み込みに関してはノンブロッキングで高速に読み込める. -\subsection{Node} +\clearpage +\section{Node} Node は木構造を表現するデータ構造である. 再帰的に定義されている. 各ノードは children として子ノードを複数持つことができる（図\ref{fig:node_components}）. @@ -358,6 +362,7 @@ これらの関数は, ほぼ同一の関数で定義できる. addNewChildAtを用いて説明する（ソースコード\ref{src:addNewChildAt}）. +\newpage \begin{lstlisting}[label=src:addNewChildAt, caption=木の編集を行う関数] addNewChildAt :: Node -> Path -> Node addNewChildAt parent [] = addChildAt parent emptyNode @@ -444,10 +449,10 @@ pos = size map \end{lstlisting} -参照関数の基本的な流れは、getNode関数を使って参照したいPathのノードを取ってくることである. -そのノードにはwhereキーワードを利用して、targetという名前をつけている. -targetに対して、子のMapや属性のMapを取得した後、lookup関数などを適用する. -elems, assocs, sizeなどはData.Mapの参照関数で、Jungle ではその関数をそのまま利用している. +参照関数の基本的な流れは, getNode関数を使って参照したいPathのノードを取ってくることである. +そのノードにはwhereキーワードを利用して, targetという名前をつけている. +targetに対して, 子のMapや属性のMapを取得した後, lookup関数などを適用する. +elems, assocs, sizeなどはData.Mapの参照関数で, Jungle ではその関数をそのまま利用している. 参照関数の基本的な機能をまとめて説明する. diff -r 0644825c43ac -r 79d168016df4 paper/chapter4.tex --- a/paper/chapter4.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/chapter4.tex Tue Feb 11 22:58:43 2014 +0900 @@ -35,7 +35,7 @@ Haskell および Java のバージョンを表\ref{tab:compiler}に示す. -\begin{table}[!ht] +\begin{table}[!htbp] \begin{center} \begin{tabular}{|c||c|} \hline 言語 & バージョン \\ \hline \hline @@ -201,7 +201,7 @@ ネットワークのボトルネックがどれぐらいあるのか調査するために, アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する. ネットワークを介さずに性能測定する場合, 性能測定ツール weighttp に 3 スレッド利用するため, Warp で利用するのは 8 スレッドまでとする. weighttpの設定は, リクエストの総数 100 万, 同時に接続するコネクションの数 1,000, 実行時のスレッド数 3, HTTP Keep-Alivesを有効とする. -また, 現在の安定版である 7.6.3 は IO マネージャーに問題があるが, どの程度影響があるか調べるためにGHC 7.6.3 でコンパイルし、ネットワークを介さない状態での測定も行う. +また, 現在の安定版である 7.6.3 は IO マネージャーに問題があるが, どの程度影響があるか調べるためにGHC 7.6.3 でコンパイルし, ネットワークを介さない状態での測定も行う. 結果を表\ref{tab:warp}に示す. \begin{table}[!htbp] diff -r 0644825c43ac -r 79d168016df4 paper/images/deos_proccess.xbb --- a/paper/images/deos_proccess.xbb Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/images/deos_proccess.xbb Tue Feb 11 22:58:43 2014 +0900 @@ -1,8 +1,8 @@ %%Title: ./deos_proccess.pdf %%Creator: extractbb 20130405 -%%BoundingBox: 0 0 712 413 -%%HiResBoundingBox: 0.000000 0.000000 712.000000 413.000000 +%%BoundingBox: 0 0 603 413 +%%HiResBoundingBox: 0.000000 0.000000 603.000000 413.000000 %%PDFVersion: 1.4 %%Pages: 1 -%%CreationDate: Tue Feb 4 18:21:17 2014 +%%CreationDate: Tue Feb 11 20:12:16 2014 diff -r 0644825c43ac -r 79d168016df4 paper/images/memo.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/memo.graffle Tue Feb 11 22:58:43 2014 +0900 @@ -0,0 +1,849 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGrafflePro + 139.17.0.185490 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {559, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2014-02-11 13:14:44 +0000 + Creator + Daichi TOMA + DisplayScale + 1.000 cm = 1.000 m + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{83, 238.5}, {9, 20}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + Ricty-Regular + Size + 18 + + ID + 40 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 Ricty-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 x} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{83, 168}, {9, 20}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + FontInfo + + Font + Ricty-Regular + Size + 18 + + ID + 39 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 Ricty-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 y} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + ID + 38 + Points + + {186, 248} + {99, 248} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + FilledArrow + Width + 2 + + + + + Class + LineGraphic + ID + 36 + Points + + {187, 178} + {100, 178} + + Style + + stroke + + HeadArrow + 0 + Legacy + + TailArrow + FilledArrow + Width + 2 + + + Tail + + ID + 10 + Info + 2 + + + + Class + LineGraphic + ID + 33 + Points + + {284, 247} + {312, 297} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + TailArrow + 0 + Width + 2 + + + + + Class + LineGraphic + ID + 32 + Points + + {249, 246} + {208, 296} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + TailArrow + 0 + Width + 2 + + + + + Class + LineGraphic + ID + 31 + Points + + {288, 179} + {219, 227} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + TailArrow + 0 + Width + 2 + + + + + Class + LineGraphic + ID + 30 + Points + + {248, 179} + {208, 227} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + TailArrow + 0 + Width + 2 + + + + + AllowConnections + NO + Class + TableGroup + Graphics + + + Bounds + {{332, 296}, {40, 40}} + Class + ShapedGraphic + ID + 23 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 2} + + + + Bounds + {{292, 296}, {40, 40}} + Class + ShapedGraphic + ID + 24 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 Int} + + + + GridV + + 24 + 23 + + + ID + 22 + + + AllowConnections + NO + Class + TableGroup + Graphics + + + Bounds + {{227, 296}, {40, 40}} + Class + ShapedGraphic + ID + 19 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 1} + + + + Bounds + {{187, 296}, {40, 40}} + Class + ShapedGraphic + ID + 20 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 Int} + + + + GridV + + 20 + 19 + + + ID + 18 + + + AllowConnections + NO + Class + TableGroup + Graphics + + + Bounds + {{227, 227}, {40, 40}} + Class + ShapedGraphic + ID + 15 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + + + Bounds + {{187, 227}, {40, 40}} + Class + ShapedGraphic + ID + 16 + Magnets + + {1, 0} + {-1, 0} + + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 +} + + + + Bounds + {{267, 227}, {40, 40}} + Class + ShapedGraphic + ID + 17 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + + + GridV + + 16 + 15 + 17 + + + ID + 14 + + + Class + TableGroup + Graphics + + + AllowConnections + NO + Bounds + {{227, 158}, {40, 40}} + Class + ShapedGraphic + ID + 11 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + + + Bounds + {{187, 158}, {40, 40}} + Class + ShapedGraphic + ID + 10 + Magnets + + {1, 0} + {-1, 0} + + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset0 RictyDiscord-Regular;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs36 \cf0 (,)} + + + + AllowConnections + NO + Bounds + {{267, 158}, {40, 40}} + Class + ShapedGraphic + ID + 12 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Width + 2 + + + + + GridV + + 10 + 11 + 12 + + + ID + 9 + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + Layer 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2014-02-11 13:27:55 +0000 + Modifier + Daichi TOMA + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {595, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + Canvas 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + + name + Canvas 1 + + + Frame + {{1316, 212}, {692, 922}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 119 + VisibleRegion + {{0, 0}, {558, 783}} + Zoom + 1 + ZoomValues + + + Canvas 1 + 1 + 1 + + + + + diff -r 0644825c43ac -r 79d168016df4 paper/images/memo.pdf Binary file paper/images/memo.pdf has changed diff -r 0644825c43ac -r 79d168016df4 paper/images/memo.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/memo.xbb Tue Feb 11 22:58:43 2014 +0900 @@ -0,0 +1,8 @@ +%%Title: ./memo.pdf +%%Creator: extractbb 20130405 +%%BoundingBox: 0 0 291 182 +%%HiResBoundingBox: 0.000000 0.000000 291.000000 182.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Tue Feb 11 22:28:55 2014 + diff -r 0644825c43ac -r 79d168016df4 paper/introduciton.tex --- a/paper/introduciton.tex Tue Feb 11 19:45:40 2014 +0900 +++ b/paper/introduciton.tex Tue Feb 11 22:58:43 2014 +0900 @@ -44,4 +44,4 @@ 読み込みに関して 12 コアで実行した場合, 1 コアで実行した場合と比較して, 10.37 倍 という性能向上率が確認でき, マルチコアプロセッサの性能を引き出すことができた. -また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 1.87 倍, 書き込みで 2.3 倍の性能が確認できた. +また, Web 掲示板サービスを開発し, 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない, 読み込みで 3.25 倍, 書き込みで 3.78 倍の性能が確認できた. diff -r 0644825c43ac -r 79d168016df4 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed