# HG changeset patch # User Daichi TOMA # Date 1391474300 -32400 # Node ID aa6de0f67a0a533688c72c8dc23ee35ac3a15bb8 # Parent ff15fb78a3aed561ba30e482e0e1c714197e2f67 add files diff -r ff15fb78a3ae -r aa6de0f67a0a paper/abstract_eng.tex --- a/paper/abstract_eng.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/abstract_eng.tex Tue Feb 04 09:38:20 2014 +0900 @@ -3,7 +3,7 @@ It provides a modern type system, type-safe and type inference makes it possible to write a program reliable\cite{types}. Haskell has referential transparency that allows the programmer and the compiler to reason about program behavior. -In this study, We implement the parallel database using Haskell and non-destructive tree. +In this study, we implement the parallel database using Haskell and non-destructive tree. We measures the performance for reading and writing of parallel database. We achieve to bring out the performance of the multi-core processor. diff -r ff15fb78a3ae -r aa6de0f67a0a paper/benchmark/readwrite/readwrite.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/benchmark/readwrite/readwrite.txt Tue Feb 04 09:38:20 2014 +0900 @@ -0,0 +1,14 @@ +1 CPU +finished in 141 sec, 406 millisec and 378 microsec, 7071 req/s, 980 kbyte/s + +2CPU +finished in 70 sec, 871 millisec and 294 microsec, 14110 req/s, 1956 kbyte/s + +4 CPU +finished in 54 sec, 326 millisec and 314 microsec, 18407 req/s, 2552 kbyte/s + +8 CPU +finished in 55 sec, 136 millisec and 70 microsec, 18136 req/s, 2515 kbyte/s + +12 CPU +finished in 58 sec, 606 millisec and 103 microsec, 17063 req/s, 2366 kbyte/s diff -r ff15fb78a3ae -r aa6de0f67a0a paper/chapter3.tex --- a/paper/chapter3.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/chapter3.tex Tue Feb 04 09:38:20 2014 +0900 @@ -1,4 +1,4 @@ -\chapter{Haskellによる並列データベースの実装}\label{ch:impl} +\chapter{Haskellによる\\並列データベースの実装}\label{ch:impl} 本章では、並列データベース Jungle の実装について述べる。 \section{木構造データベース Jungle} diff -r ff15fb78a3ae -r aa6de0f67a0a paper/chapter4.tex --- a/paper/chapter4.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/chapter4.tex Tue Feb 04 09:38:20 2014 +0900 @@ -7,7 +7,7 @@ 本研究では、学科が提供するブレードサーバを用いて、計測環境を構築する。 ブレードサーバの仕様を表\ref{tab:server_spec}に示す。 -論理コアは、Intel のハイパースレッディング機能のことであうｒ． +論理コアは、Intel のハイパースレッディング機能のことである。 ハイパースレッディングは、１つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術であり、 同時に演算器などを利用することはできないため性能が２倍になるわけではないが、概ね20 \%程度クロックあたりの性能が向上すると言われている。 @@ -35,10 +35,10 @@ GHC は、Haskell で最も広く使われているコンパイラである\cite{ghc}。 ソフトウェア・トランザクショナル・メモリをサポートするなど、並列プログラミングのためのHaskellの拡張が行われている。 -Haskell および Java のバージョンを表\ref{tab:compiler}に示す。 +Haskell および Java のバージョンを表\ref{compiler}に示す。 \begin{table}[!ht] -\label{tab:compiler} +\label{compiler} \begin{center} \begin{tabular}{|c||c|} \hline 言語 & バージョン \\ \hline \hline @@ -141,7 +141,7 @@ \end{table} 性能向上率のグラフを図\ref{fig:benchmark_write}に示す。 -書き込みは並列化率が低く、性能向上が 4 倍程度で止まっている。 +書き込みは性能向上率が低いことが分かる。 \newpage \begin{figure}[!htbp] @@ -212,9 +212,10 @@ 掲示板の読み込みの計測結果を表\ref{tab:bbs_read}に示す。 並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。 +シングルスレッドで実行した場合と比較して、12 スレッドで 2.14 倍の性能向上が見られる。 これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。 -Warp のボトルネックがどれぐらいあるのか調査するために、アクセスした際に "hello, world" と返すだけのプログラムを作成し測定する。 +Warp のボトルネックがどれぐらいあるのか調査するために、アクセスした際に "hello, world" という文字列を返すだけのプログラムを作成し測定する。 結果を表\ref{tab:warp}に示す。 1 スレッドで実行した場合は、Jungle と組み合わせた掲示板より速い。 しかしながら、スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう。 @@ -264,6 +265,7 @@ 掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す。 並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。 +シングルスレッドで実行した場合と比較して、12 スレッドで 1.65 倍の性能向上が見られる。 読み込みに比べて、書き込みのほうが全体的に遅くなっている。 \begin{table}[!htbp] @@ -304,7 +306,7 @@ \caption{HaskellとJavaの比較} \end{table} -Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能が出ている。 +Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能差が出ている。 書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。 Haskell では書き込みを行う際、完全に評価せず thunk として積み上げていく。 @@ -315,3 +317,25 @@ ハードウェアが効率的に利用できるメモリの範囲内に収まらなければ即時評価より実行時間が遅くなってしまうことがあるので注意が必要である。 本実験では、潤沢にメモリを割り当てているためそういった問題は起きない。 +\subsection{書き込みごとに読み込みを行った場合} +書き込みごとに毎回読み込みを挟むことで、遅延評価ではなく即時評価させる。 +計測結果を表\ref{tab:write_read}に示す。 + +\begin{table}[!htbp] +\label{tab:write_read} +\begin{center} +\begin{tabular}{|c||r|} \hline +CPU数 & 実行時間 \\ \hline +1 & 141.40 s\\ \hline +2 & 70.87 s\\ \hline +4 & 54.32 s\\ \hline +8 & 55.13 s\\ \hline +12 & 58.60 s\\ \hline +\end{tabular} +\end{center} +\caption{書き込みを行うたびに読み込みを挟んだ場合の計測結果} +\end{table} + +結果が明らかに遅くなっている。 +12 スレッドで実行した際、 Java との書き込みの性能差は、1.30 倍である。 +シングルスレッドで実行した場合と比較した場合、12 スレッドで 2.40 倍の性能向上が見られる。 diff -r ff15fb78a3ae -r aa6de0f67a0a paper/conclusion.tex --- a/paper/conclusion.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/conclusion.tex Tue Feb 04 09:38:20 2014 +0900 @@ -8,14 +8,14 @@ 実装において、Haskellの表現力とコンパイル時に多くのエラーを捕まえるという特徴は、開発期間およびコード行数の短縮に繋がった。 また、型安全により実行時に型エラーによってプログラムが終了するといったことがない。 -実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 \%という高い並列化率が確認できた。 -また、掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2 倍の性能を確認することができた。 +読み込みに関して 12 コアで実行した場合、1 コアで実行した場合と比較して、10.77 倍 という性能向上率が確認でき、マルチコアプロセッサの性能を引き出すことができた。 +また、Web 掲示板サービスを開発し、 既存の Java の非破壊的木構造データベースを用いた掲示板実装との比較をおこない、読み込みで 1.87 倍、書き込みで 2.3 倍の性能が確認できた。 \section{今後の課題} 非破壊的木構造データベース Jungle の今後の課題について述べる。 \subsubsection{書き込み処理の並列度の上昇} -データベースへの書き込み処理において 80.8 \%の並列度しか出ていない。 +データベースへの書き込み処理において、12 スレッド時で 3.86 倍の性能向上しか達成できていない。 はじめに、プログラムの変更をせずに、GHC の IO マネージャーの改善によりどの程度並列度が向上するのかを調査する必要がある。 GHC の IO マネージャーの影響度を計測した後、変更処理の改善方法に調査する。 現在ソフトウェア・トランザクショナル・メモリを用いているが、他のスレッドセーフな参照型を用いて性能改善が行えないか確認する。 @@ -23,12 +23,12 @@ ロックが制限的だが、高速なIORef、ロックの使えるMVarなどである。 \subsubsection{分散データベースとしての実装} -並列環境で実行できるが、今後は分散データベースとして実行できるようにしたい。 +現在、並列環境で実行できるが、今後は分散データベースとして実行できるようにしたい。 トポロジーの形成機能や、サーバ間でのデータアクセスの仕組みを実装する必要がある。 サーバ間で木構造の変更を共有するには、木構造を何らかの情報に基づいて、マージする仕組みを導入する必要がある。 \subsubsection{永続性の実装} 非破壊的木構造データベース Jungle は、オンメモリ上で動作するデータベースである。 並列性を損なわない形で、ディスクへの書き出しを実現したい。 -簡単な実装としては、書き出しを担当するスレッドを作成するといったことが考えられる。 +実装としては、書き出しを担当するスレッドを作成するといったことが考えられる。 diff -r ff15fb78a3ae -r aa6de0f67a0a paper/introduciton.tex --- a/paper/introduciton.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/introduciton.tex Tue Feb 04 09:38:20 2014 +0900 @@ -3,7 +3,7 @@ Web サービスの脆弱性狙った攻撃が頻繁に発生している。 脆弱性を悪用されると、Web サービス運営者は賠償など多大な損害を受ける可能性がある。 -純粋型プログラミング言語 Haskell は、バッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを事前の型検査で防ぐことができる。 +純粋関数型プログラミング言語 Haskell は、バッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを事前の型検査で防ぐことができる。 つまり、Haskell を用いることで信頼性の高い Web サービスを開発できると言える。 本研究の目標は、Haskell を用いて信頼性の高い Web サービスおよびデータベースの開発である。 diff -r ff15fb78a3ae -r aa6de0f67a0a paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r ff15fb78a3ae -r aa6de0f67a0a paper/master_paper.tex --- a/paper/master_paper.tex Tue Feb 04 06:35:58 2014 +0900 +++ b/paper/master_paper.tex Tue Feb 04 09:38:20 2014 +0900 @@ -65,7 +65,7 @@ %要旨 \input{abstract.tex} -\input{abstract_eng.tex} +% \input{abstract_eng.tex} %目次 \tableofcontents diff -r ff15fb78a3ae -r aa6de0f67a0a slides/images/get_root_node.png Binary file slides/images/get_root_node.png has changed diff -r ff15fb78a3ae -r aa6de0f67a0a slides/images/read.png Binary file slides/images/read.png has changed diff -r ff15fb78a3ae -r aa6de0f67a0a slides/images/write.png Binary file slides/images/write.png has changed diff -r ff15fb78a3ae -r aa6de0f67a0a slides/master.html --- a/slides/master.html Tue Feb 04 06:35:58 2014 +0900 +++ b/slides/master.html Tue Feb 04 09:38:20 2014 +0900 @@ -53,35 +53,43 @@ 研究概要

- Haskellは純粋関数型プログラミング言語である。 - モダンな型システムを持ち、型推論と型安全により簡潔で信頼性の高いプログラムを書くことが可能である。 + Haskell を用いて並列データベースを実装した。 +

+

+ 読み込みに関して 12 コアで実行した場合、10.77 倍 という性能向上率が確認できた。

- 本研究では、Haskell を用いて並列に読み書き可能なデータベースの実装を行う。 - 並列にデータへアクセスする手法として、非破壊的木構造を用いる。 - 非破壊的木構造は、元となる木構造を書き換えることなく編集を可能にする手法である。 + また、Web 掲示板サービスを開発し、Java より読み込みで 1.87 倍、書き込みで 2.3倍の性能が確認できた。 +

+ +
+

+ 研究背景 +

+

+ Web サービスの脆弱性を悪用されると多大な被害がでる

- 実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 % という高い並列度が確認できた。 - また、簡単な掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2倍の性能を確認することができた。 + Haskell は型検査でバッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを防げる +

+

+ Haskell を用いてデータベースと Web サービスの開発を行う

- Haskell とは + Haskell

- Haskellは純粋関数型プログラミング言語である。 - 関数とは、一つの引数を取り一つの結果を返す変換器のことである。 - 関数型プログラミング言語では、関数を引数に適用させていくことで計算を行う。 + Haskellは純粋関数型プログラミング言語

- 既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 - 例えば、Haskell でフィボナッチ数列を定義するには以下の様に記述する。 + 純粋とは、引数が同じならば関数が必ず同じ値を返す 

+fib :: Int −> Int
 fib 0 = 0
 fib 1 = 1
 fib n = fib (n-2) + fib (n-1)
@@ -90,121 +98,117 @@
 
 			

 				

-          Haskell の特徴
+          実行時型エラーがない
 				

         

-        Haskellの他の言語との大きな違いは、純粋性を持つことと現代的な型システムを備えていることである。
+        Haskellは、評価の際に型に起因するエラーが起きない
+        

+        

+        [1,2,3]のリストに文字'a'を追加することはできない
         

         

-        純粋性を持つとは、引数が同じならば関数は必ず同じ値を返すということを保証しているという意味である。
-        関数が引数のみに依存する場合、関数はどのタイミングで実行してもよいため並列化が行いやすい。
+        コンパイル時にエラーになる
         

+
+abc = 'a' : [1,2,3]
+

+
+
+-- リスト型の定義
+data [] a = [] | a : [a]
+

+			

+
+			

+				

+          型推論
+				

+        

+        Haskell が型を推論してくれる
+        

+
+getChildren node path = elems (children (getNode node path))
+

+        

+        

+
+*Jungle> :type getChildren
+getChildren :: Node -> Path -> [Node]
+

 			

 
 			

 				

-          Haskell の型システム
+          モナド
 				

         

-        Haskell では、すべての式、すべての関数に型がある。
-        Haskell の型システムはプログラマにいくつかの恩恵をもたらす。
+        文脈を保ったまま関数を繋いでいくことができる
         

-        
    
-          
  • エラーの検出
-          
  • 抽象化
-          
  • 安全性
-          
  • ドキュメント化
-        

-        

-        ひとつずつ説明していく
-        

+
+data Maybe a = Nothing | Just a
+

+
+instance Monad Maybe where
+    return x = Just x
+    Nothing >>= f = Nothing
+    Just x >>= f  = f x
+

+
+up 4 = Nothing
+up n = Just (n + 1)
+
+down 0 = Nothing 
+down n = Just (n - 1)
+

+
+return 3 >>= down >>= down >>= up >>= up
+

 			

-      
+
 			

 				

-          Haskell の型システム - エラーの検出
+          モナドを使わないで同じことをする
+				

+
+return 3 >>= down >>= down >>= up >>= up
+

+
+updown :: Maybe Int
+updown = case down 3 of
+            Nothing -> Nothing
+            Just place1 -> case down place1 of
+                    Nothing -> Nothing
+                    Just place2 -> case up place2 of
+                            Nothing -> Nothing
+                            Just place3 -> up place3
+

+			

+
+
+			

+				

+          マルチコアプロセッサ
 				

         

-        Haskell は静的型検査によりエラーを広範囲に検出することができる。
-        プログラムが型検査器（コンパイラ）を通れば「ちゃんと動く」傾向にある。
+        現在、CPU はマルチコア化が進んでいる。
         

         

-        Haskell では、データ構造を独自の型で表現することができる。
-        独自に定義した型も、コンパイラの援助を得ることができる。
+        マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保つ必要性（アムダール則）
         

         

-        また型検査器は保守のためのツールにもなりうる。
-        独自に定義したデータ型を変更した場合、修正が必要な箇所は型の不整合が起こるので、修正が容易である。
+        並列度が 80 % の場合、どんなにコア数を増やしても性能向上は5倍まで
         

 			

 
 			

 				

-          Haskell の型システム - 抽象化
-				

-        

-        型システムは、プログラムに抽象をもたらす。
-        抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。
-        例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、
-        その文字列が他の文字列と同じように振る舞うとみなすことができる。
-        

-        

-        また、Haskell では型クラスを用いて、型の振る舞いを定義できる。
-        言語の基本的な機能である、同値性の検査や数値演算を抽象化することもできる。
-        

-			

-
-			

-				

-          Haskell の型システム - 安全性
-				

-        

-        Haskell の型システムは、自らがもたらす抽象の整合性を保証する。
-        型は不変の条件であり、異なる型として認識されることはない。
-        

-        

-        定義したデータ型は期待通りに動くことが保証される。
-        他のデータ構造の境界を超えてきたデータが書き込まれたりするようなことは起きない。
-        

-			

-
-			

-				

-          Haskell の型システム - ドキュメント化
+          並列データベース
 				

         

-        Haskell の型はプログラムを読む際にも有用である。
-        関数の型は、その関数の振る舞いを理解するヒントになる。
-        

-        

-        例えばリストの先頭要素を取ってくる head という関数がある。
-        この型宣言を見れば、この関数はリストの要素のどれか１つをそのまま返すだけの関数ということが分かる。
-
-head :: [a] -> a
-

+        データベースを線形に性能向上させたければ、各コアからデータに同時にアクセスできるようにし並列度を高める
         

         

-        型はコンパイルが実行されるたびに検査されるので、コメントに埋め込まれた記述と違って古くなることがない。
-        

-			

-
-			

-				

-          Haskell による並列データベース
-				

-        

-        現在、CPU はマルチコア化が進んでいる。
-        マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない（アムダール則）。
-        

-        

-        CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。
-        通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。
-        

-        

-        本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。
-        競合を発生させないためには、既にあるデータを変更しなければよい。
-        非破壊的木構造は、変更元となる木構造を変更しない。
-        そのため、別々の CPU コアから同時にアクセスが可能である。
+        非破壊的木構造という手法を使う
         

 			

 
@@ -213,10 +217,11 @@
           非破壊的木構造
 				
         

-        非破壊的木構造は、元となる木構造を書き換えることなく編集を可能にする手法である。
-        既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。
+        元となる木構造を書き換えずに編集できる
+        

         

-
+        既にあるデータを変更しないので、データの競合状態が発生しない。並列に読み書きできる
+        

         

           
         

@@ -227,10 +232,11 @@
           非破壊的木構造 - ルートノード
 				
         

-        非破壊的木構造では、どの木構造が最新かを表す情報が重要である。
-        最新の木構造を表すノードをルートノードと呼ぶ。
+        どの木構造が最新なのかを表す情報
         

-
+        

+        状態を持つのはここだけで、並列度を高めるにはここの設計が重要
+        

         

           
         

@@ -238,16 +244,35 @@
 
 			

 				

-          非破壊的木構造 - ルートノードの管理
+          データベースの設計 - 並列度を高めるために
 				

         

-        ルートノードの情報はスレッド間で共有する必要がある。
-        ソフトウェア・トランザクショナル・メモリ (STM) を用いて実現する。
-        STM は、排他制御を行わずに共有データを扱うことができる。
+        できるだけルートノードに触る範囲を狭くする
+        

+        

+        ルートノードが必要ない時はさわらない
         

         

-        STM は、他のスレッドによる変更を考慮せずに共有データに対して変更を行う。
-        変更をトランザクションとしてコミットする時に以下のことがひとつだけ起こる。
+        ルートノードを更新する関数と、編集する関数を綺麗に切り分ける
+        

+			

+
+			

+				

+          Haskell でのルートノードの管理
+				

+        

+        ソフトウェア・トランザクショナル・メモリ (STM) を使う
+        

+        

+        STM は、排他制御を行わずに共有データを扱える
+        

+        

+        STM は、他のスレッドによる変更を考慮せずに共有データを変更する
+        

+        

+        変更をトランザクションとしてコミットする時に以下のことがひとつだけ起こる
+        

         
    
           
  • 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる
           
  • そうでなければ、変更を実際に実行せずに破棄し、変更の処理を再度実行する。
@@ -257,83 +282,77 @@
 
 			
    
 				
    
-          非破壊的木構造データベース Jungle
+          Jungle のデータ型
 				
    
         
    
-        Jungle は、複数の非破壊的木構造を扱うことのできるデータベースである。
+        Jungle は、非破壊的木構造を扱う並列データベース
+        
    
+
    +-- Jungle のデータ型
+data Jungle = Jungle (TVar (Map String Tree))
+
+-- Tree のデータ型
+data Tree = Tree (TVar Node) String
+
+-- Node のデータ型
+data Node = Node (Map Int Node) (Map String ByteString)
+
    
+        
    
+        TVarがついてるのはSTMを使ってる変数
         
    
         
    
-        木構造の識別には、名前を利用する。
-        名前を付けて作成し、名前を用いることで参照を行う。
+        Map は連想配列
+        
    
+			
    
+
+			
    
+				
    
+          Jungle の実装
+				
    
+        
    
+        Jungle は Tree と String の連想配列を持っている（状態変数）
         
    
-        
    
-        
    
+        
    
+        Tree は、ルートノードの情報と、木の名前（ルートノードの情報は状態変数）
+        
    
+        
    
+        Node は、子と子の場所の連想配列と、キーと値の連想配列を持ってる。
+        
    
+
+        

    
         
    
-          
+          
         
    
 			
    
 
 			
    
 				
    
-          Jungle - データの取得と更新
+          状態を扱う関数
 				
    
-        
    
-        Jungle では、データの取得や更新のためにルートノードを扱う API がある。
-        ルートノード関連の API は IO 処理となる。
-        
    
 
    --- ルートノードの取得
-node <- getRootNode jungle "your_tree_name_here"
+createJungle :: IO Jungle
+createTree :: Jungle -> String -> IO ()
+getRootNode :: Jungle -> String -> IO Node
+updateRootNode :: Jungle -> String -> Node -> IO ()
+updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO ()
+
    
+        
    
+        すべて IO が返ってくる
+        後回しで性能計測からまとめる
+        
    
+			
    
 
--- ルートノードの更新
-updateRootNode jungle "your_tree_name_here" node
-
--- ノードを編集する関数を渡して、ルートノードの取得から更新までを一貫して行う
-updateRootNodeWith func jungle "your_tree_name_here"
-
-

- Jungle 内部のデータ型 + 性能計測

- Jungle 内部で用いているデータ型を示す。 - これらの型は、Jungle 内部の関数で使われている。 + Jungle がマルチコアプロセッサで性能が出るのか、実用的なWebサービスが提供できるのか確認する

- データ型として定義することで、データ内部の整合性が保たれ、また型検査でエラーがないか検出することができる。 -

- - - - - - - - - - - - - - - - - -
型の名前概要
Jungle複数の木と名前を結びつける辞書
Tree木の名前とルートノードの情報
Node子と属性の2つの辞書
-
- -
-

- ベンチマーク -

-

- 非破壊的木構造データベース Jungle の読み込みと書き込みの性能の計測を行う。 - また、簡単な掲示板ウェブアプリケーションを作成し、Java を用いた非破壊的木構造データベースとの性能比較を行う。 -

-

- 性能の計測に用いるサーバの仕様を示す。 + 性能の計測に用いるサーバの仕様
+ ハイパースレッディングで24コアまで使える

@@ -359,49 +378,322 @@
+
+

+ 性能計測 - 読み込みの計測結果 +

+

+ 木構造の読み込みにかかる時間を計測する +

+

+ 12 スレッドで実行時に 10.77 倍の性能向上 +

+

+ ハイパースレッディングは遅くなったりと安定しない +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
CPU数実行時間
159.77 s
233.36 s
415.63 s
88.10 s
125.55 s
165.65 s
205.23 s
245.77 s
+

+
+

- ベンチマーク - 読み込みの計測方法 + 性能計測 - 読み込みの計測結果 +

+

+ 12 スレッドまでの性能向上率 +

+
+ +
+
+ +
+

+ 性能計測 - 書き込みの計測結果

- 木構造の読み込みにかかる時間を計測する。 + 木構造の書き込みにかかる時間を計測する +

+

+ 2 スレッドで 1.55 倍の性能向上
+ 12 スレッドで実行時に 3.86 倍の性能向上

- Jungleを用いて約 80 万のノードを持つ木構造を作成する。 - 木構造のノードの数を数えるタスクを 1,000 個作成し、並列に実行する。 + ハイパースレッディングは12スレッド以降遅くなっている +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
CPU数実行時間
152.68 s
233.92 s
420.11 s
815.31 s
1213.62 s
1614.92 s
2018.62 s
2416.63 s
+

+
+ +
+

+ 性能計測 - 書き込みの計測結果 +

+

+ 12 スレッドまでの性能向上率 +

+
+ +
+
+ +
+

+ 性能計測 - 読み込みと書き込みの考察 +

+

+ 読み込みと比べて書き込みの性能向上率が低い

- 非破壊的木構造は、木構造に変更を加えても他の読み込みのタスクに影響を与えない。 - そのことを確認するために、木構造は各タスクに渡す前に無作為にノードを追加する。 + 木を登録する際、他のスレッドから登録があった場合、ソフトウェア・トランザクショナル・メモリが処理をやり直すため遅いと考えられる。 +

+

+ 書き込みより読み込みが多用されるシステムに向いている。

- ベンチマーク - 読み込みの計測結果 + 性能計測 - Webサービスに組み込んでの性能評価

- 木構造の読み込みにかかる時間を計測する。 + Haskell の HTTP サーバ Warp と組み合わせて Web掲示板サービスを開発する。 +

+

+ weighttpを用いて掲示板に読み込みと書き込みで負荷をかける。リクエストの総数は100万 +

+

+ Warp は、ハイパースレッディングで明らかに遅くなるので、12コアまでの計測とする。 +

+
+ +
+

+ 性能計測 - Webサービスに組み込んでの性能評価 読み込み +

+

+ 読み込み +

+

+ 12 スレッド時に 2.14 倍

- Jungleを用いて約 80 万のノードを持つ木構造を作成する。 - 木構造のノードの数を数えるタスクを 1,000 個作成し、並列に実行する。 + 性能向上率が低い

-

- 非破壊的木構造は、木構造に変更を加えても他の読み込みのタスクに影響を与えない。 - そのことを確認するために、木構造は各タスクに渡す前に無作為にノードを追加する。 -

-
-
-

- ベンチマーク - 書き込み -

+ + + + + + + + + + + + + + + + + + + + + + + + + +
CPU数実行時間
160.72 s
237.74 s
428.97 s
827.73 s
1228.33 s

- ベンチマーク - Java との比較 + 性能計測 - Webサービスに組み込んでの性能評価 書き込み +

+

+ 書き込み +

+

+ 12 スレッド時に 1.65 倍 +

+

+ 読み込みよりさらに悪い +

+ + + + + + + + + + + + + + + + + + + + + + + + + +
CPU数実行時間
154.16 s
236.71 s
431.74 s
831.58 s
1232.68 s
+
+ +
+

+ Webサービスに組み込んでの性能評価 考察

+

+ Warp がボトルネックとなってしまっている。 + Warp は現状あまり並列化効果がでていない。 +

+

+ アクセスした際に、"hello, world" という文字列を返すだけのプログラムを作成し計測する。 +

+

+ Jungle を組み込んだ時と比較して、読み込みの場合はほとんど差がない。 +

+ + + + + + + + + + + + + + + + + + + + + + + + + +
CPU数実行時間
149.28 s
235.45 s
425.70 s
827.90 s
1229.23 s
+
+ +
+

+ 性能計測 - Java との比較 +

+ + + + + + + + + + + + + + + + + +
測定HaskellJava
読み込み28.33 s53.13 s
書き込み32.68 s76.4 s
+

+ 読み込みで 1.87 倍、書き込みで 2.3 倍の性能差が出ている +

+

+ 書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。 + Haskell では書き込みを行う際、完全に評価せず途中式を積み上げていく。 +