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