|
17
|
1 \chapter{性能測定}
|
|
|
2
|
|
|
3 前章までに、Jungle へ行った改善点・開発したアプリケーションについて述べた。
|
|
|
4 本章では、実装した新機能の性能測定を行う。
|
|
|
5
|
|
|
6
|
|
|
7 \section{測定環境}
|
|
|
8 表\ref{environment}に、測定を行ったマシンの環境を記述する。
|
|
|
9
|
|
|
10 \begin{table}[htb]
|
|
|
11 \begin{center}
|
|
|
12 \caption{実験環境}
|
|
|
13 \begin{tabular}{|p{15em}|p{24em}|} \hline
|
|
|
14 OS & MacOS Sierra 10.12.3 \\ \hline
|
|
|
15 Memory & 16 GB 1600 MHz DDR3 \\ \hline
|
|
|
16 CPU & 2.5 GHz Intel Core i7\\ \hline
|
|
|
17 Java & 1.8.0.111 \\ \hline
|
|
|
18 mongoDB & 3.4.1\\ \hline
|
|
|
19 PostgreSQL & 9.6.1 \\ \hline
|
|
|
20 \end{tabular}
|
|
|
21 \label{environment}
|
|
|
22 \end{center}
|
|
|
23 \end{table}
|
|
|
24
|
|
|
25
|
|
|
26
|
|
|
27 \newpage
|
|
|
28
|
|
|
29 \section{TreeMapの測定}
|
|
|
30 5章で実装した TreeMap の性能測定を行う。
|
|
18
|
31 比較対象には、 TreeMap 実装前に Jungle で使用していた Functional Java の TreeMap を使用する。
|
|
17
|
32
|
|
18
|
33 図\ref{find}は、 TreeMap に1000回の Get を行った際のベンチマークである。
|
|
17
|
34 X 軸は Get を行う TreeMap のノード数。
|
|
18
|
35 Y 軸は Get にかかった時間を表す
|
|
17
|
36
|
|
|
37 \begin{figure}[htpb]
|
|
|
38 \begin{center}
|
|
|
39 \includegraphics[scale=0.6,angle=-90]{result/treemap/find.pdf}
|
|
|
40 \caption{TreeMap への Get}
|
|
|
41 \end{center}
|
|
|
42 \label{find}
|
|
|
43 \end{figure}
|
|
|
44
|
|
|
45 \ref{find}より、Functional Java の TreeMap と比較して、 Jungle の TreeMap の方が非常に高速に動いている。
|
|
|
46 理由として、Jungle の TreeMap は、検索対象の値を持つノードを、二分探索木の探索アルゴリズムに則り探索するのに対し、
|
|
18
|
47 Functional Java の TreeMap は、検索対象のノードがルートになる木を構築し、ルートを返す。といったアルゴリズムを採用していため、
|
|
17
|
48 探索アルゴリズムの差が図\ref{find}の結果に出た。
|
|
|
49 その他の処理についても、Jungleの TreeMap の方が高速に動作していた。
|
|
|
50
|
|
|
51 \newpage
|
|
|
52 \section{Index の差分 Update の測定}
|
|
|
53 6章で実装した、Index の差分 Update の測定を行う。
|
|
|
54 図\ref{index}は、Index の差分 Update と FullUpdate の両方で木のCommitを行った際のグラフである。
|
|
|
55 測定は、木にノードを追加、Commit を1セットの変更として行う。
|
|
|
56 X 軸は、木に行った変更のセット数。
|
|
|
57 Y 軸は、Commit にかかった時間を表す。
|
|
|
58
|
|
|
59 \begin{figure}[htpb]
|
|
|
60 \begin{center}
|
|
|
61 \includegraphics[scale=0.6]{result/createIndex.pdf}
|
|
|
62 \caption{IndexのUpdate}
|
|
|
63 \label{index}
|
|
|
64 \end{center}
|
|
|
65 \end{figure}
|
|
|
66
|
|
|
67 図\ref{index}より、Index の Full Update は、グラフがO(n\verb|^|2)なのに対し、 差分 Update は、O(n)で行えている。
|
|
|
68
|
|
|
69 しかし、Jungleでは木に変更を加える際、毎回 Commit を行うわけでなく、 基本的に複数回変更を行った後、一気にCommit を行う。
|
|
|
70 差分 Update は、変更を加えたノードを記憶し、 Commit 時に Index の更新を行う。
|
|
|
71 一方、Full Update では、 Commit を行うまでに木に加えた変更の数に関係なく、新しい Index を構築する。
|
|
18
|
72 よって、 Commit を行うまでに行う木の編集回数が増えた場合、 Index の Full Update と 差分 Update では、差分 Update の方が、Index に対して多くの変更を行うことになる。
|
|
17
|
73 そのため、Commit を行うまでの 木に対する変更回数によっては、 Full Update の方が高速に Index の構築を行える可能性がある。
|
|
|
74
|
|
|
75 そこで、図\ref{index2}に、Commit を行うまでに行った木の編集回数と、 Index の Update 速度の測定結果を記述する。
|
|
|
76 X軸は、1回の Commit を行うまでに木に行った変更のセット回数。
|
|
|
77 Y軸は、Commit にかかった時間を表す。
|
|
|
78 また、構築する木のノード数は1000ノードとする。
|
|
|
79 \begin{figure}[htpb]
|
|
|
80 \begin{center}
|
|
|
81 \includegraphics[scale=0.6,angle = -90]{result/createIndex2.pdf}
|
|
|
82 \caption{Commit を行うまでに木に加えた変更回数と、 Index の構築時間}
|
|
|
83 \label{index2}
|
|
|
84 \end{center}
|
|
|
85 \end{figure}
|
|
|
86
|
|
|
87 図\ref{index2} より、Commit の前に行った木の編集回数に関係なく、基本的に Index の更新は差分 Update の方が早いことがわかった。
|
|
|
88
|
|
|
89
|
|
|
90 \newpage
|
|
18
|
91 \section{正順の線形木の構築時間の測定}
|
|
17
|
92 7章で実装した、 Differential Jungle Tree の性能測定を行う。
|
|
|
93 比較対象は、Default Jungle Tree を用いる。
|
|
|
94 図\ref{dfTree}は、正順の木を構築するまでにかかった時間のベンチマークである。
|
|
|
95 X 軸は、構築した木のノード数。
|
|
|
96 Y 軸は、構築にかかった時間を表す。
|
|
18
|
97 また、木のみを構築する時間を測定するため、Index は作っていない。
|
|
17
|
98
|
|
|
99 \begin{figure}[htpb]
|
|
|
100 \begin{center}
|
|
|
101 \includegraphics[scale=0.6]{result/createListTree.pdf}
|
|
|
102 \caption{Differential Tree と Default Jungle Tree}
|
|
|
103 \label{dfTree}
|
|
|
104 \end{center}
|
|
|
105 \end{figure}
|
|
|
106
|
|
|
107 図\ref{dfTree}より、Default Jungle Tree より、Differential Jungle Tree の方が高速に木の構築している。
|
|
18
|
108 これは、Default Jungle Tree が、木を構築する際に複製を行うのに対し、Differential Jungle Tree は複製を行っていないからである。
|
|
|
109 期待通りの結果が出たといえる。
|
|
|
110
|
|
17
|
111
|
|
|
112 \section{Red Black Jungle Tree の測定}
|
|
|
113 8章で実装した、Red Black Jungle Tree の性能測定を行う。
|
|
|
114 比較対象は、Default Jungle Tree を用いる。
|
|
|
115 図\ref{redblack}は、正順の木を構築するまでにかかった時間のベンチマークである。
|
|
|
116 X 軸は、構築した木のノード数。
|
|
|
117 Y 軸は、構築にかかった時間を表す。
|
|
|
118
|
|
|
119 \begin{figure}[htpb]
|
|
|
120 \begin{center}
|
|
|
121 \includegraphics[scale=0.6]{result/createRedBlackTreeAndDefaultTreeTime.pdf}
|
|
|
122 \caption{Red Black Jungle Tree と Default Jungle Tree}
|
|
|
123 \label{redblack}
|
|
|
124 \end{center}
|
|
|
125 \end{figure}
|
|
|
126
|
|
|
127 図\ref{redblack}より、Default Jungle Tree より、 Red Black Jungle Tree の方が高速に木を構築している。
|
|
|
128 これは、Default Jungle Tree が、木を構築する際に Index を生成しているのに対し、 Red Black Jungle Tree は、自身の木構造が Index と同等の働きを持つため、Index を構築する必要がない。
|
|
|
129 その差が出たためである。
|
|
|
130
|
|
|
131 \section{既存のデータベースとの比較}
|
|
|
132 Jungle と既存のデータベースとの比較を行う。
|
|
|
133 比較対象は PostgreSql と mongoDB を選択した。
|
|
|
134 検索対象のデータは10000件。
|
|
|
135 データの検索の速度を比較した。
|
|
|
136 図\ref{compareDB}に結果のグラフを記述する。
|
|
|
137
|
|
|
138 \begin{figure}[htpb]
|
|
|
139 \begin{center}
|
|
|
140 \includegraphics[scale=0.6,angle=-90]{result/findTime.pdf}
|
|
|
141 \caption{既存の DB との比較}
|
|
|
142 \label{compareDB}
|
|
|
143 \end{center}
|
|
|
144 \end{figure}
|
|
|
145
|
|
|
146 図\ref{compareDB}より、Jungle は PostgreSql と mongDB と比較して、非常に高速な検索を行えている。
|
|
|
147 理由として、PostgreSql と mongoDB は、通信を介してデータにアクセスするのに対し、Jungle は、アプリケーション内にデータがあるため、通信を介さないためだと考えられる。
|
