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