1
2%\documentclass[10pt,twoside,twocolumn]{article}
3\documentclass[12pt,twoside]{article}
4\usepackage[bf,small]{caption}
5\usepackage[letterpaper,hmargin=1in,vmargin=1in]{geometry}
6\usepackage{paralist} % comapctitem, compactdesc, compactenum
7\usepackage{titlesec}
8\usepackage{titletoc}
9\usepackage{times}
10\usepackage{hyperref}
11\usepackage{algorithmic}
12\usepackage{graphicx}
13\graphicspath{{./graphics/}}
14\usepackage{xspace}
15\usepackage{verbatim}
16\usepackage{url}
17\usepackage{float}
18\hyphenation{Sub-Bytes Shift-Rows Mix-Col-umns Add-Round-Key}
19
20\setlength{\parskip}{12pt}
21\setlength{\parindent}{0pt}
22
23\newcommand{\hdb}{\emph{hashdb}\xspace}
24
25\begin{document}
26
27\begin{center}
28\Large \hdb v3.0 Timing Analysis
29\end{center}
30
31Timing analysis is shown for importing and scanning under varying conditions
32using a 4-core 3.10GHz Intel processor, 8 GiB or RAM, and Fedora 20.
33
34Timing analyses performed:
35\begin{compactitem}
36\item Random hash: Random hashes are imported and scanned using default parameters.
37\item Same hash, different source offset: The same hash is imported and scanned, with a maximum duplicates count of 100.
38\item Random hash, small hash key space: Random hashes are imported and scanned, where the key space is 9 bits.  With one million hashes, the average bucket size is $1,000,000 / 2^{9} = 1953$.
39\end{compactitem}
40
41\subsubsection* {Random Hash}
42
43\begin{figure}[H]
44  \center
45  \includegraphics[scale=0.52]{temp_add_random_delta}
46  \includegraphics[scale=0.52]{temp_add_random_total}
47  \caption*{Import random hashes.}
48\end{figure}
49
50\begin{figure}[H]
51  \center
52  \includegraphics[scale=0.52]{temp_scan_random_delta}
53  \includegraphics[scale=0.52]{temp_scan_random_total}
54  \caption*{Scan random hashes.}
55\end{figure}
56
57\subsubsection* {Same Hash, Different Source Offset}
58
59\begin{figure}[H]
60  \center
61  \includegraphics[scale=0.52]{temp_add_same_delta}
62  \includegraphics[scale=0.52]{temp_add_same_total}
63  \caption*{Import same hashes, different source offset.}
64\end{figure}
65
66\begin{figure}[H]
67  \center
68  \includegraphics[scale=0.52]{temp_scan_same_delta}
69  \includegraphics[scale=0.52]{temp_scan_same_total}
70  \caption*{Scan same hashes, different source offset.}
71\end{figure}
72
73\subsubsection* {Random Hash, Small Hash Key Space}
74
75\begin{figure}[H]
76  \center
77  \includegraphics[scale=0.52]{temp_add_random_key_delta}
78  \includegraphics[scale=0.52]{temp_add_random_key_total}
79  \caption*{Import same hashes, different source offset.}
80\end{figure}
81
82\begin{figure}[H]
83  \center
84  \includegraphics[scale=0.52]{temp_scan_random_key_delta}
85  \includegraphics[scale=0.52]{temp_scan_random_key_total}
86  \caption*{Scan same hashes, different source offset.}
87\end{figure}
88
89\subsubsection*{Conclusions}
90\begin{compactitem}
91\item For a small database, random hashes import at about 0.55 seconds
92per 100K and scan at about 0.11 seconds per 100K.
93\item Settings must be used to protect performance.
94Specifically, the number of sources per hash and the number of hash suffixes
95must be controlled.
96The effect of various settings is shown here:
97
98\begin{compactitem}
99\item The following table shows performance when varying the maximum number of
100sources stored for hashes.
101This maximum value is set using the \verb+-m+ option when a database is created.
102
103\vspace{4mm}
104\begin{tabular}{|l|l|l|}
105\hline
106max duplicates & Import (Sec/100K) & Scan (Sec/100K) \\
107\hline
10820 & 0.06 & 0.17 \\
109100 & 0.11 & 0.70 \\
110200 & 0.18 & 1.50 \\
111500 & 0.40 & 4.00 \\
1121000 & 0.75 & 8.50 \\
113\hline
114\end{tabular}
115\vspace{4mm}
116
117These results indicate that the max duplicates might be kept below 200.
118
119\item The following table shows performance when varying the density of
120hash suffixes per hash prefix.
121This value is controlled using the \verb+-t+ tuning option
122when a database is created.
123Import times are time to import 100K random hashes
124after importing 900K random hashes.
125Scan times are time to scan 100K random hashes.
126
127\vspace{4mm}
128\begin{tabular}{|l|l|l|}
129\hline
130suffixes per prefix & Import & Scan \\
131\hline
13218:3 (4) & 0.55 & 0.10 \\
13316:3 (15) & 0.51 & 0.09 \\
13414:3 (61) & 0.51 & 0.09 \\
13512:3 (244) & 0.51 & 0.10 \\
13610:3 (976) & 0.62 & 0.17 \\
1379:3 (1953) & 0.75 & 0.26 \\
1388:3 (3906) & 1.00 & 0.45 \\
139\hline
140\end{tabular}
141\vspace{4mm}
142
143These results indicate that the optimum density may be around 50
144suffixes per prefix and that the maximum suffixes per prefix
145should be kept below 250.
146
147\end{compactitem}
148
149\end{compactitem}
150
151\end{document}
152
153