<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN">
<html>
<head>
<title>Map Benchmarking (Win32 VS71)</title>
<style type="text/css"><!--
table { width: 95%; }
caption { font-size: larger; font-weight: bold; }
td { text-align: right; }
.explain { text-align: left; }
--></style>
</head>
<body>
<h1>Map Benchmarking (Win32 VS71)</h1>
<div>
<p>The array-based hash map is 150-250% faster than either std::map or stdext::hash_map types for typical <em>by key</em> operations.</p>
<p>The array-based hash map is 3000-5000% faster than either std::map or stdext::hash_map types for atypical <em>by item</em> operations.</p>
</div>
<div>
<p>stdext::hash_map is 7-27% faster than std::map for typical <em>by key</em> operations.</p>
<p>stdext::hash_map is 4-18% faster than std::map for atypical <em>by item</em> operations.</p>
</div>
<table border="2" cellpadding="2" cellspacing="2">
<caption>10000 Dictionary Words</caption>
<tbody>
<tr>
<th>Type</th>
<th>Insert Items<br />by Key (×10)</th>
<th>Find Items<br />by Key (×10)</th>
<th>Erase Items<br />by Key (×10)</th>
<th>I-F-E Cycle<br />by Key (×10)</th>
<th>Clear Items<br />(×10)</th>
<th>Find Keys<br />by Item (×1)</th>
</tr>
<tr>
<th>std::map</th>
<td>0.43</td>
<td>0.25</td>
<td>0.55</td>
<td>1.23</td>
<td>0.10</td>
<td>67.05</td>
</tr>
<tr>
<th>stdext::hash_map</th>
<td>0.51</td>
<td>0.24</td>
<td>0.40</td>
<td>1.15</td>
<td>0.10</td>
<td>56.82</td>
</tr>
<tr>
<th>array hash map</th>
<td>0.20</td>
<td>0.04</td>
<td>0.22</td>
<td>0.46</td>
<td>0.16</td>
<td>1.84</td>
</tr>
</tbody>
</table>
<table border="2" cellpadding="2" cellspacing="2">
<caption>2497 DICOM V3 Tags</caption>
<tbody>
<tr>
<th>Type</th>
<th>Insert Items<br />by Key (×10)</th>
<th>Find Items<br />by Key (×10)</th>
<th>Erase Items<br />by Key (×10)</th>
<th>I-F-E Cycle<br />by Key (×10)</th>
<th>Clear Items<br />(×10)</th>
<th>Find Keys<br />by Item (×1)</th>
</tr>
<tr>
<th>std::map</th>
<td>0.17</td>
<td>0.04</td>
<td>0.17</td>
<td>0.38</td>
<td>0.03</td>
<td>7.58</td>
</tr>
<tr>
<th>stdext::hash_map</th>
<td>0.14</td>
<td>0.05</td>
<td>0.11</td>
<td>0.30</td>
<td>0.06</td>
<td>7.30</td>
</tr>
<tr>
<th>array hash map</th>
<td>0.01</td>
<td>0.00</td>
<td>0.09</td>
<td>0.10</td>
<td>0.10</td>
<td>0.13</td>
</tr>
</tbody>
</table>
<table border="2" cellpadding="2" cellspacing="2">
<caption>Explanations</caption>
<tbody>
<tr>
<th>Test</th>
<th>Description</th>
</tr>
<tr>
<th>Insert Items<br />by Key (×10)</th>
<td class="explain">Time to insert an item into the map associated with each key (10 repetitions).</td>
</tr>
<tr>
<th>Find Items<br />by Key (×10)</th>
<td class="explain">Time to find an item within the map for each associated key (10 repetitions).</td>
</tr>
<tr>
<th>Erase Items<br />by Key (×10)</th>
<td class="explain">Time to erase an item within the map for each associated key (10 repetitions).</td>
</tr>
<tr>
<th>I-F-E Cycle<br />by Key (×10)</th>
<td class="explain">Time to complete an insert, find, and erase cycle (10 repetitions).</td>
</tr>
<tr>
<th>Clear Items<br />(×10)</th>
<td class="explain">Time to erase all items associated with each key at once (10 repetitions).</td>
</tr>
<tr>
<th>Find Keys<br />by Item (×1)</th>
<td class="explain">Time to find an associated key for each item in the map (single repetition).</td>
</tr>
<tr>
<th colspan="2">All times are as reported by vtkTimerLog::GetCPUTime().</th>
</tr>
<tr>
<td colspan="2" class="explain">The <em>"array"</em> hash map is <em>not</em> a chained hash table in which collisions are resolved by the addition of "buckets". Rather, it is represented by an array which grows or shrinks according to the number of elements in the table. Collisions are resolved by rehashing a key until an availible table position is found.</th>
</tr>
</tbody>
</table>
<hr>
<address><a href="mailto:anvil@acm.org">Sean McInerney</a></address>
<!-- Created: Mon Jul 04 14:59:48 Eastern Daylight Time 2005 -->
<!-- hhmts start -->
Last modified: Tue Jul 05 13:54:01 Eastern Daylight Time 2005
<!-- hhmts end -->
</body>
</html>