1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Performance</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive"> 10<link rel="prev" href="design_notes.html" title="Design Notes"> 11<link rel="next" href="release_notes.html" title="Release Notes"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<a accesskey="p" href="design_notes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="release_notes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="intrusive.performance"></a><a class="link" href="performance.html" title="Performance">Performance</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_push_back">Back 32 insertion and destruction</a></span></dt> 33<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_reversing">Reversing</a></span></dt> 34<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_sorting">Sorting</a></span></dt> 35<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_write_access">Write 36 access</a></span></dt> 37<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_conclusions">Conclusions</a></span></dt> 38</dl></div> 39<p> 40 <span class="bold"><strong>Boost.Intrusive</strong></span> containers offer speed improvements 41 compared to non-intrusive containers primarily because: 42 </p> 43<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 44<li class="listitem"> 45 They minimize memory allocation/deallocation calls. 46 </li> 47<li class="listitem"> 48 They obtain better memory locality. 49 </li> 50</ul></div> 51<p> 52 This section will show performance tests comparing some operations on <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">list</span></code> and 53 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code>: 54 </p> 55<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 56<li class="listitem"> 57 Insertions using <code class="computeroutput"><span class="identifier">push_back</span></code> 58 and container destruction will show the overhead associated with memory 59 allocation/deallocation. 60 </li> 61<li class="listitem"> 62 The <code class="computeroutput"><span class="identifier">reverse</span></code> member function 63 will show the advantages of the compact memory representation that can 64 be achieved with intrusive containers. 65 </li> 66<li class="listitem"> 67 The <code class="computeroutput"><span class="identifier">sort</span></code> and <code class="computeroutput"><span class="identifier">write</span> <span class="identifier">access</span></code> 68 tests will show the advantage of intrusive containers minimizing memory 69 accesses compared to containers of pointers. 70 </li> 71</ul></div> 72<p> 73 Given an object of type <code class="computeroutput"><span class="identifier">T</span></code>, 74 <code class="computeroutput"><a class="link" href="../boost/intrusive/list.html" title="Class template list">boost::intrusive::list<T></a></code> 75 can replace <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> to 76 avoid memory allocation overhead, or it can replace <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">T</span><span class="special">*></span></code> when 77 the user wants containers with polymorphic values or wants to share values 78 between several containers. Because of this versatility, the performance tests 79 will be executed for 6 different list types: 80 </p> 81<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 82<li class="listitem"> 83 3 intrusive lists holding a class named <code class="computeroutput"><span class="identifier">itest_class</span></code>, 84 each one with a different linking policy (<code class="computeroutput"><span class="identifier">normal_link</span></code>, 85 <code class="computeroutput"><span class="identifier">safe_link</span></code>, <code class="computeroutput"><span class="identifier">auto_unlink</span></code>). The <code class="computeroutput"><span class="identifier">itest_class</span></code> 86 objects will be tightly packed in a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">itest_class</span><span class="special">></span></code> object. 87 </li> 88<li class="listitem"> 89 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code>, 90 where <code class="computeroutput"><span class="identifier">test_class</span></code> is exactly 91 the same as <code class="computeroutput"><span class="identifier">itest_class</span></code>, 92 but without the intrusive hook. 93 </li> 94<li class="listitem"> 95 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">*></span></code>. 96 The list will contain pointers to <code class="computeroutput"><span class="identifier">test_class</span></code> 97 objects tightly packed in a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code> object. We'll call this configuration 98 <span class="emphasis"><em>compact pointer list</em></span> 99 </li> 100<li class="listitem"> 101 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">*></span></code>. 102 The list will contain pointers to <code class="computeroutput"><span class="identifier">test_class</span></code> 103 objects owned by a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code> object. We'll call this configuration 104 <span class="emphasis"><em>disperse pointer list</em></span>. 105 </li> 106</ul></div> 107<p> 108 Both <code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code> are templatized classes that 109 can be configured with a boolean to increase the size of the object. This way, 110 the tests can be executed with small and big objects. Here is the first part 111 of the testing code, which shows the definitions of <code class="computeroutput"><span class="identifier">test_class</span></code> 112 and <code class="computeroutput"><span class="identifier">itest_class</span></code> classes, and 113 some other utilities: 114 </p> 115<pre class="programlisting"><span class="comment">//Iteration and element count defines</span> 116<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumIter</span> <span class="special">=</span> <span class="number">4</span><span class="special">;</span> 117<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumElements</span> <span class="special">=</span> <span class="number">50000</span><span class="special">;</span> 118 119<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span> 120 121<span class="keyword">template</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">></span> <span class="keyword">struct</span> <span class="identifier">filler</span> <span class="special">{</span> <span class="keyword">int</span> <span class="identifier">dummy</span><span class="special">[</span><span class="number">10</span><span class="special">];</span> <span class="special">};</span> 122<span class="keyword">template</span> <span class="special"><></span> <span class="keyword">struct</span> <span class="identifier">filler</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span> <span class="special">{};</span> 123 124<span class="keyword">template</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">></span> <span class="comment">//The object for non-intrusive containers</span> 125<span class="keyword">struct</span> <span class="identifier">test_class</span> <span class="special">:</span> <span class="keyword">private</span> <span class="identifier">filler</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">></span> 126<span class="special">{</span> 127 <span class="keyword">int</span> <span class="identifier">i_</span><span class="special">;</span> 128 <span class="identifier">test_class</span><span class="special">()</span> <span class="special">{}</span> 129 <span class="identifier">test_class</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">i_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{}</span> 130 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special"><(</span><span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">i_</span> <span class="special"><</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">i_</span><span class="special">;</span> <span class="special">}</span> 131 <span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special">>(</span><span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">i_</span> <span class="special">></span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">i_</span><span class="special">;</span> <span class="special">}</span> 132<span class="special">};</span> 133 134<span class="keyword">template</span> <span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">,</span> <span class="identifier">link_mode_type</span> <span class="identifier">LinkMode</span><span class="special">></span> 135<span class="keyword">struct</span> <span class="identifier">itest_class</span> <span class="comment">//The object for intrusive containers</span> 136 <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">list_base_hook</span><span class="special"><</span><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">LinkMode</span><span class="special">></span> <span class="special">>,</span> <span class="keyword">public</span> <span class="identifier">test_class</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">></span> 137<span class="special">{</span> 138 <span class="identifier">itest_class</span><span class="special">()</span> <span class="special">{}</span> 139 <span class="identifier">itest_class</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">test_class</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">>(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{}</span> 140<span class="special">};</span> 141 142<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">FuncObj</span><span class="special">></span> <span class="comment">//Adapts functors taking values to functors taking pointers</span> 143<span class="keyword">struct</span> <span class="identifier">func_ptr_adaptor</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">FuncObj</span> 144<span class="special">{</span> 145 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">first_argument_type</span><span class="special">*</span> <span class="identifier">first_argument_type</span><span class="special">;</span> 146 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">second_argument_type</span><span class="special">*</span> <span class="identifier">second_argument_type</span><span class="special">;</span> 147 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">result_type</span><span class="special">;</span> 148 <span class="identifier">result_type</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">first_argument_type</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">second_argument_type</span> <span class="identifier">b</span><span class="special">)</span> <span class="keyword">const</span> 149 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="keyword">operator</span><span class="special">()(*</span><span class="identifier">a</span><span class="special">,</span> <span class="special">*</span><span class="identifier">b</span><span class="special">);</span> <span class="special">}</span> 150<span class="special">};</span> 151</pre> 152<p> 153 As we can see, <code class="computeroutput"><span class="identifier">test_class</span></code> is 154 a very simple class holding an <code class="computeroutput"><span class="keyword">int</span></code>. 155 <code class="computeroutput"><span class="identifier">itest_class</span></code> is just a class 156 that has a base hook (<code class="computeroutput"><a class="link" href="../boost/intrusive/list_base_hook.html" title="Class template list_base_hook">list_base_hook</a></code>) 157 and also derives from <code class="computeroutput"><span class="identifier">test_class</span></code>. 158 </p> 159<p> 160 <code class="computeroutput"><span class="identifier">func_ptr_adaptor</span></code> is just a 161 functor adaptor to convert function objects taking <code class="computeroutput"><span class="identifier">test_list</span></code> 162 objects to function objects taking pointers to them. 163 </p> 164<p> 165 You can find the full test code in the <a href="../../../libs/intrusive/perf/perf_list.cpp" target="_top">perf_list.cpp</a> 166 source file. 167 </p> 168<div class="section"> 169<div class="titlepage"><div><div><h3 class="title"> 170<a name="intrusive.performance.performance_results_push_back"></a><a class="link" href="performance.html#intrusive.performance.performance_results_push_back" title="Back insertion and destruction">Back 171 insertion and destruction</a> 172</h3></div></div></div> 173<p> 174 The first test will measure the benefits we can obtain with intrusive containers 175 avoiding memory allocations and deallocations. All the objects to be inserted 176 in intrusive containers are allocated in a single allocation call, whereas 177 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code> will need to allocate memory for each 178 object and deallocate it for every erasure (or container destruction). 179 </p> 180<p> 181 Let's compare the code to be executed for each container type for different 182 insertion tests: 183 </p> 184<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">ilist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="identifier">objects</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">);</span> 185<span class="identifier">ilist</span> <span class="identifier">l</span><span class="special">;</span> 186<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> 187 <span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">objects</span><span class="special">[</span><span class="identifier">i</span><span class="special">]);</span> 188<span class="comment">//Elements are unlinked in ilist's destructor</span> 189<span class="comment">//Elements are destroyed in vector's destructor</span> 190</pre> 191<p> 192 For intrusive containers, all the values are created in a vector and after 193 that inserted in the intrusive list. 194 </p> 195<pre class="programlisting"><span class="identifier">stdlist</span> <span class="identifier">l</span><span class="special">;</span> 196<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> 197 <span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 198<span class="comment">//Elements unlinked and destroyed in stdlist's destructor</span> 199</pre> 200<p> 201 For a standard list, elements are pushed back using push_back(). 202 </p> 203<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="identifier">objects</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">);</span> 204<span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span> 205<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> 206 <span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">[</span><span class="identifier">i</span><span class="special">]);</span> 207<span class="comment">//Pointers to elements unlinked and destroyed in stdptrlist's destructor</span> 208<span class="comment">//Elements destroyed in vector's destructor</span> 209</pre> 210<p> 211 For a standard compact pointer list, elements are created in a vector and 212 pushed back in the pointer list using push_back(). 213 </p> 214<pre class="programlisting"><span class="identifier">stdlist</span> <span class="identifier">objects</span><span class="special">;</span> <span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span> 215<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span> 216 <span class="identifier">objects</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 217 <span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">.</span><span class="identifier">back</span><span class="special">());</span> 218<span class="special">}</span> 219<span class="comment">//Pointers to elements unlinked and destroyed in stdptrlist's destructor</span> 220<span class="comment">//Elements unlinked and destroyed in stdlist's destructor</span> 221</pre> 222<p> 223 For a <span class="emphasis"><em>disperse pointer list</em></span>, elements are created in 224 a list and pushed back in the pointer list using push_back(). 225 </p> 226<p> 227 These are the times in microseconds for each case, and the normalized time: 228 </p> 229<div class="table"> 230<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_times"></a><p class="title"><b>Table 19.2. Back insertion + destruction times for Visual C++ 7.1 / Windows XP</b></p> 231<div class="table-contents"><table class="table" summary="Back insertion + destruction times for Visual C++ 7.1 / Windows XP"> 232<colgroup> 233<col> 234<col> 235<col> 236</colgroup> 237<thead><tr> 238<th> 239 <p> 240 Container 241 </p> 242 </th> 243<th> 244 <p> 245 Time in us/iteration (small object / big object) 246 </p> 247 </th> 248<th> 249 <p> 250 Normalized time (small object / big object) 251 </p> 252 </th> 253</tr></thead> 254<tbody> 255<tr> 256<td> 257 <p> 258 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 259 list 260 </p> 261 </td> 262<td> 263 <p> 264 5000 / 22500 265 </p> 266 </td> 267<td> 268 <p> 269 1 / 1 270 </p> 271 </td> 272</tr> 273<tr> 274<td> 275 <p> 276 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 277 list 278 </p> 279 </td> 280<td> 281 <p> 282 7812 / 32187 283 </p> 284 </td> 285<td> 286 <p> 287 1.56 / 1.43 288 </p> 289 </td> 290</tr> 291<tr> 292<td> 293 <p> 294 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 295 list 296 </p> 297 </td> 298<td> 299 <p> 300 10156 / 41562 301 </p> 302 </td> 303<td> 304 <p> 305 2.03 / 1.84 306 </p> 307 </td> 308</tr> 309<tr> 310<td> 311 <p> 312 Standard list 313 </p> 314 </td> 315<td> 316 <p> 317 26875 / 97500 318 </p> 319 </td> 320<td> 321 <p> 322 5.37 / 4.33 323 </p> 324 </td> 325</tr> 326<tr> 327<td> 328 <p> 329 Standard compact pointer list 330 </p> 331 </td> 332<td> 333 <p> 334 76406 / 86718 335 </p> 336 </td> 337<td> 338 <p> 339 15.28 / 3.85 340 </p> 341 </td> 342</tr> 343<tr> 344<td> 345 <p> 346 Standard disperse pointer list 347 </p> 348 </td> 349<td> 350 <p> 351 146562 / 175625 352 </p> 353 </td> 354<td> 355 <p> 356 29.31 / 7.80 357 </p> 358 </td> 359</tr> 360</tbody> 361</table></div> 362</div> 363<br class="table-break"><div class="table"> 364<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_time0"></a><p class="title"><b>Table 19.3. Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows 365 XP</b></p> 366<div class="table-contents"><table class="table" summary="Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows 367 XP"> 368<colgroup> 369<col> 370<col> 371<col> 372</colgroup> 373<thead><tr> 374<th> 375 <p> 376 Container 377 </p> 378 </th> 379<th> 380 <p> 381 Time in us/iteration (small object / big object) 382 </p> 383 </th> 384<th> 385 <p> 386 Normalized time (small object / big object) 387 </p> 388 </th> 389</tr></thead> 390<tbody> 391<tr> 392<td> 393 <p> 394 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 395 list 396 </p> 397 </td> 398<td> 399 <p> 400 4375 / 22187 401 </p> 402 </td> 403<td> 404 <p> 405 1 / 1 406 </p> 407 </td> 408</tr> 409<tr> 410<td> 411 <p> 412 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 413 list 414 </p> 415 </td> 416<td> 417 <p> 418 7812 / 32812 419 </p> 420 </td> 421<td> 422 <p> 423 1.78 / 1.47 424 </p> 425 </td> 426</tr> 427<tr> 428<td> 429 <p> 430 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 431 list 432 </p> 433 </td> 434<td> 435 <p> 436 10468 / 42031 437 </p> 438 </td> 439<td> 440 <p> 441 2.39 / 1.89 442 </p> 443 </td> 444</tr> 445<tr> 446<td> 447 <p> 448 Standard list 449 </p> 450 </td> 451<td> 452 <p> 453 81250 / 98125 454 </p> 455 </td> 456<td> 457 <p> 458 18.57 / 4.42 459 </p> 460 </td> 461</tr> 462<tr> 463<td> 464 <p> 465 Standard compact pointer list 466 </p> 467 </td> 468<td> 469 <p> 470 83750 / 94218 471 </p> 472 </td> 473<td> 474 <p> 475 19.14 / 4.24 476 </p> 477 </td> 478</tr> 479<tr> 480<td> 481 <p> 482 Standard disperse pointer list 483 </p> 484 </td> 485<td> 486 <p> 487 155625 / 175625 488 </p> 489 </td> 490<td> 491 <p> 492 35.57 / 7.91 493 </p> 494 </td> 495</tr> 496</tbody> 497</table></div> 498</div> 499<br class="table-break"><div class="table"> 500<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_time1"></a><p class="title"><b>Table 19.4. Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18 501 (OpenSuse 10.2)</b></p> 502<div class="table-contents"><table class="table" summary="Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18 503 (OpenSuse 10.2)"> 504<colgroup> 505<col> 506<col> 507<col> 508</colgroup> 509<thead><tr> 510<th> 511 <p> 512 Container 513 </p> 514 </th> 515<th> 516 <p> 517 Time in us/iteration (small object / big object) 518 </p> 519 </th> 520<th> 521 <p> 522 Normalized time (small object / big object) 523 </p> 524 </th> 525</tr></thead> 526<tbody> 527<tr> 528<td> 529 <p> 530 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 531 list 532 </p> 533 </td> 534<td> 535 <p> 536 4792 / 20495 537 </p> 538 </td> 539<td> 540 <p> 541 1 / 1 542 </p> 543 </td> 544</tr> 545<tr> 546<td> 547 <p> 548 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 549 list 550 </p> 551 </td> 552<td> 553 <p> 554 7709 / 30803 555 </p> 556 </td> 557<td> 558 <p> 559 1.60 / 1.5 560 </p> 561 </td> 562</tr> 563<tr> 564<td> 565 <p> 566 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 567 list 568 </p> 569 </td> 570<td> 571 <p> 572 10180 / 41183 573 </p> 574 </td> 575<td> 576 <p> 577 2.12 / 2.0 578 </p> 579 </td> 580</tr> 581<tr> 582<td> 583 <p> 584 Standard list 585 </p> 586 </td> 587<td> 588 <p> 589 17031 / 32586 590 </p> 591 </td> 592<td> 593 <p> 594 3.55 / 1.58 595 </p> 596 </td> 597</tr> 598<tr> 599<td> 600 <p> 601 Standard compact pointer list 602 </p> 603 </td> 604<td> 605 <p> 606 27221 / 34823 607 </p> 608 </td> 609<td> 610 <p> 611 5.68 / 1.69 612 </p> 613 </td> 614</tr> 615<tr> 616<td> 617 <p> 618 Standard disperse pointer list 619 </p> 620 </td> 621<td> 622 <p> 623 102272 / 60056 624 </p> 625 </td> 626<td> 627 <p> 628 21.34 / 2.93 629 </p> 630 </td> 631</tr> 632</tbody> 633</table></div> 634</div> 635<br class="table-break"><p> 636 The results are logical: intrusive lists just need one allocation. The destruction 637 time of the <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 638 container is trivial (complexity: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="number">1</span><span class="special">)</span></code>), 639 whereas <code class="computeroutput"><span class="identifier">safe_link</span></code> and <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive containers need to 640 put the hooks of erased values in the default state (complexity: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">)</span></code>). That's why <code class="computeroutput"><span class="identifier">normal_link</span></code> 641 intrusive list shines in this test. 642 </p> 643<p> 644 Non-intrusive containers need to make many more allocations and that's why 645 they lag behind. The <code class="computeroutput"><span class="identifier">disperse</span> <span class="identifier">pointer</span> <span class="identifier">list</span></code> 646 needs to make <code class="computeroutput"><span class="identifier">NumElements</span><span class="special">*</span><span class="number">2</span></code> allocations, 647 so the result is not surprising. 648 </p> 649<p> 650 The Linux test shows that standard containers perform very well against intrusive 651 containers with big objects. Nearly the same GCC version in MinGW performs 652 worse, so maybe a good memory allocator is the reason for these excellent 653 results. 654 </p> 655</div> 656<div class="section"> 657<div class="titlepage"><div><div><h3 class="title"> 658<a name="intrusive.performance.performance_results_reversing"></a><a class="link" href="performance.html#intrusive.performance.performance_results_reversing" title="Reversing">Reversing</a> 659</h3></div></div></div> 660<p> 661 The next test measures the time needed to complete calls to the member function 662 <code class="computeroutput"><span class="identifier">reverse</span><span class="special">()</span></code>. 663 Values (<code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists are created as explained 664 in the previous section. 665 </p> 666<p> 667 Note that for pointer lists, <code class="computeroutput"><span class="identifier">reverse</span></code> 668 <span class="bold"><strong>does not need to access <code class="computeroutput"><span class="identifier">test_class</span></code> 669 values stored in another list or vector</strong></span>, since this function just 670 needs to adjust internal pointers, so in theory all tested lists need to 671 perform the same operations. 672 </p> 673<p> 674 These are the results: 675 </p> 676<div class="table"> 677<a name="intrusive.performance.performance_results_reversing.reverse_times_for_visual_c_7_1_w"></a><p class="title"><b>Table 19.5. Reverse times for Visual C++ 7.1 / Windows XP</b></p> 678<div class="table-contents"><table class="table" summary="Reverse times for Visual C++ 7.1 / Windows XP"> 679<colgroup> 680<col> 681<col> 682<col> 683</colgroup> 684<thead><tr> 685<th> 686 <p> 687 Container 688 </p> 689 </th> 690<th> 691 <p> 692 Time in us/iteration (small object / big object) 693 </p> 694 </th> 695<th> 696 <p> 697 Normalized time (small object / big object) 698 </p> 699 </th> 700</tr></thead> 701<tbody> 702<tr> 703<td> 704 <p> 705 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 706 list 707 </p> 708 </td> 709<td> 710 <p> 711 2656 / 10625 712 </p> 713 </td> 714<td> 715 <p> 716 1 / 1.83 717 </p> 718 </td> 719</tr> 720<tr> 721<td> 722 <p> 723 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 724 list 725 </p> 726 </td> 727<td> 728 <p> 729 2812 / 10937 730 </p> 731 </td> 732<td> 733 <p> 734 1.05 / 1.89 735 </p> 736 </td> 737</tr> 738<tr> 739<td> 740 <p> 741 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 742 list 743 </p> 744 </td> 745<td> 746 <p> 747 2710 / 10781 748 </p> 749 </td> 750<td> 751 <p> 752 1.02 / 1.86 753 </p> 754 </td> 755</tr> 756<tr> 757<td> 758 <p> 759 Standard list 760 </p> 761 </td> 762<td> 763 <p> 764 5781 / 14531 765 </p> 766 </td> 767<td> 768 <p> 769 2.17 / 2.51 770 </p> 771 </td> 772</tr> 773<tr> 774<td> 775 <p> 776 Standard compact pointer list 777 </p> 778 </td> 779<td> 780 <p> 781 5781 / 5781 782 </p> 783 </td> 784<td> 785 <p> 786 2.17 / 1 787 </p> 788 </td> 789</tr> 790<tr> 791<td> 792 <p> 793 Standard disperse pointer list 794 </p> 795 </td> 796<td> 797 <p> 798 10781 / 15781 799 </p> 800 </td> 801<td> 802 <p> 803 4.05 / 2.72 804 </p> 805 </td> 806</tr> 807</tbody> 808</table></div> 809</div> 810<br class="table-break"><div class="table"> 811<a name="intrusive.performance.performance_results_reversing.reverse_times_for_gcc_4_1_1_ming"></a><p class="title"><b>Table 19.6. Reverse times for GCC 4.1.1 / MinGW over Windows XP</b></p> 812<div class="table-contents"><table class="table" summary="Reverse times for GCC 4.1.1 / MinGW over Windows XP"> 813<colgroup> 814<col> 815<col> 816<col> 817</colgroup> 818<thead><tr> 819<th> 820 <p> 821 Container 822 </p> 823 </th> 824<th> 825 <p> 826 Time in us/iteration (small object / big object) 827 </p> 828 </th> 829<th> 830 <p> 831 Normalized time (small object / big object) 832 </p> 833 </th> 834</tr></thead> 835<tbody> 836<tr> 837<td> 838 <p> 839 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 840 list 841 </p> 842 </td> 843<td> 844 <p> 845 2656 / 10781 846 </p> 847 </td> 848<td> 849 <p> 850 1 / 2.22 851 </p> 852 </td> 853</tr> 854<tr> 855<td> 856 <p> 857 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 858 list 859 </p> 860 </td> 861<td> 862 <p> 863 2656 / 10781 864 </p> 865 </td> 866<td> 867 <p> 868 1 / 2.22 869 </p> 870 </td> 871</tr> 872<tr> 873<td> 874 <p> 875 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 876 list 877 </p> 878 </td> 879<td> 880 <p> 881 2812 / 10781 882 </p> 883 </td> 884<td> 885 <p> 886 1.02 / 2.22 887 </p> 888 </td> 889</tr> 890<tr> 891<td> 892 <p> 893 Standard list 894 </p> 895 </td> 896<td> 897 <p> 898 4843 / 12500 899 </p> 900 </td> 901<td> 902 <p> 903 1.82 / 2.58 904 </p> 905 </td> 906</tr> 907<tr> 908<td> 909 <p> 910 Standard compact pointer list 911 </p> 912 </td> 913<td> 914 <p> 915 4843 / 4843 916 </p> 917 </td> 918<td> 919 <p> 920 1.82 / 1 921 </p> 922 </td> 923</tr> 924<tr> 925<td> 926 <p> 927 Standard disperse pointer list 928 </p> 929 </td> 930<td> 931 <p> 932 9218 / 12968 933 </p> 934 </td> 935<td> 936 <p> 937 3.47 / 2.67 938 </p> 939 </td> 940</tr> 941</tbody> 942</table></div> 943</div> 944<br class="table-break"><div class="table"> 945<a name="intrusive.performance.performance_results_reversing.reverse_times_for_gcc_4_1_2_linu"></a><p class="title"><b>Table 19.7. Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p> 946<div class="table-contents"><table class="table" summary="Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)"> 947<colgroup> 948<col> 949<col> 950<col> 951</colgroup> 952<thead><tr> 953<th> 954 <p> 955 Container 956 </p> 957 </th> 958<th> 959 <p> 960 Time in us/iteration (small object / big object) 961 </p> 962 </th> 963<th> 964 <p> 965 Normalized time (small object / big object) 966 </p> 967 </th> 968</tr></thead> 969<tbody> 970<tr> 971<td> 972 <p> 973 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 974 list 975 </p> 976 </td> 977<td> 978 <p> 979 2742 / 10847 980 </p> 981 </td> 982<td> 983 <p> 984 1 / 3.41 985 </p> 986 </td> 987</tr> 988<tr> 989<td> 990 <p> 991 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 992 list 993 </p> 994 </td> 995<td> 996 <p> 997 2742 / 10847 998 </p> 999 </td> 1000<td> 1001 <p> 1002 1 / 3.41 1003 </p> 1004 </td> 1005</tr> 1006<tr> 1007<td> 1008 <p> 1009 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1010 list 1011 </p> 1012 </td> 1013<td> 1014 <p> 1015 2742 / 11027 1016 </p> 1017 </td> 1018<td> 1019 <p> 1020 1 / 3.47 1021 </p> 1022 </td> 1023</tr> 1024<tr> 1025<td> 1026 <p> 1027 Standard list 1028 </p> 1029 </td> 1030<td> 1031 <p> 1032 3184 / 10942 1033 </p> 1034 </td> 1035<td> 1036 <p> 1037 1.16 / 3.44 1038 </p> 1039 </td> 1040</tr> 1041<tr> 1042<td> 1043 <p> 1044 Standard compact pointer list 1045 </p> 1046 </td> 1047<td> 1048 <p> 1049 3207 / 3176 1050 </p> 1051 </td> 1052<td> 1053 <p> 1054 1.16 / 1 1055 </p> 1056 </td> 1057</tr> 1058<tr> 1059<td> 1060 <p> 1061 Standard disperse pointer list 1062 </p> 1063 </td> 1064<td> 1065 <p> 1066 5814 / 13381 1067 </p> 1068 </td> 1069<td> 1070 <p> 1071 2.12 / 4.21 1072 </p> 1073 </td> 1074</tr> 1075</tbody> 1076</table></div> 1077</div> 1078<br class="table-break"><p> 1079 For small objects the results show that the compact storage of values in 1080 intrusive containers improve locality and reversing is faster than with standard 1081 containers, whose values might be dispersed in memory because each value 1082 is independently allocated. Note that the dispersed pointer list (a list 1083 of pointers to values allocated in another list) suffers more because nodes 1084 of the pointer list might be more dispersed, since allocations from both 1085 lists are interleaved in the code: 1086 </p> 1087<pre class="programlisting"><span class="comment">//Object list (holding `test_class`)</span> 1088<span class="identifier">stdlist</span> <span class="identifier">objects</span><span class="special">;</span> 1089 1090<span class="comment">//Pointer list (holding `test_class` pointers)</span> 1091<span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span> 1092 1093<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span> 1094 <span class="comment">//Allocation from the object list</span> 1095 <span class="identifier">objects</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span> 1096 <span class="comment">//Allocation from the pointer list</span> 1097 <span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">.</span><span class="identifier">back</span><span class="special">());</span> 1098<span class="special">}</span> 1099</pre> 1100<p> 1101 For big objects the compact pointer list wins because the reversal test doesn't 1102 need access to values stored in another container. Since all the allocations 1103 for nodes of this pointer list are likely to be close (since there is no 1104 other allocation in the process until the pointer list is created) locality 1105 is better than with intrusive containers. The dispersed pointer list, as 1106 with small values, has poor locality. 1107 </p> 1108</div> 1109<div class="section"> 1110<div class="titlepage"><div><div><h3 class="title"> 1111<a name="intrusive.performance.performance_results_sorting"></a><a class="link" href="performance.html#intrusive.performance.performance_results_sorting" title="Sorting">Sorting</a> 1112</h3></div></div></div> 1113<p> 1114 The next test measures the time needed to complete calls to the member function 1115 <code class="computeroutput"><span class="identifier">sort</span><span class="special">(</span><span class="identifier">Pred</span> <span class="identifier">pred</span><span class="special">)</span></code>. Values (<code class="computeroutput"><span class="identifier">test_class</span></code> 1116 and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists 1117 are created as explained in the first section. The values will be sorted 1118 in ascending and descending order each iteration. For example, if <span class="emphasis"><em>l</em></span> 1119 is a list: 1120 </p> 1121<pre class="programlisting"><span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumIter</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span> 1122 <span class="keyword">if</span><span class="special">(!(</span><span class="identifier">i</span> <span class="special">%</span> <span class="number">2</span><span class="special">))</span> 1123 <span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">>());</span> 1124 <span class="keyword">else</span> 1125 <span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">>());</span> 1126<span class="special">}</span> 1127</pre> 1128<p> 1129 For a pointer list, the function object will be adapted using <code class="computeroutput"><span class="identifier">func_ptr_adaptor</span></code>: 1130 </p> 1131<pre class="programlisting"><span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special"><</span> <span class="identifier">NumIter</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span> 1132 <span class="keyword">if</span><span class="special">(!(</span><span class="identifier">i</span> <span class="special">%</span> <span class="number">2</span><span class="special">))</span> 1133 <span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">func_ptr_adaptor</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="special">>());</span> 1134 <span class="keyword">else</span> 1135 <span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">func_ptr_adaptor</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="special">>());</span> 1136<span class="special">}</span> 1137</pre> 1138<p> 1139 Note that for pointer lists, <code class="computeroutput"><span class="identifier">sort</span></code> 1140 will take a function object that <span class="bold"><strong>will access <code class="computeroutput"><span class="identifier">test_class</span></code> values stored in another list 1141 or vector</strong></span>, so pointer lists will suffer an extra indirection: 1142 they will need to access the <code class="computeroutput"><span class="identifier">test_class</span></code> 1143 values stored in another container to compare two elements. 1144 </p> 1145<p> 1146 These are the results: 1147 </p> 1148<div class="table"> 1149<a name="intrusive.performance.performance_results_sorting.sort_times_for_visual_c_7_1_wind"></a><p class="title"><b>Table 19.8. Sort times for Visual C++ 7.1 / Windows XP</b></p> 1150<div class="table-contents"><table class="table" summary="Sort times for Visual C++ 7.1 / Windows XP"> 1151<colgroup> 1152<col> 1153<col> 1154<col> 1155</colgroup> 1156<thead><tr> 1157<th> 1158 <p> 1159 Container 1160 </p> 1161 </th> 1162<th> 1163 <p> 1164 Time in us/iteration (small object / big object) 1165 </p> 1166 </th> 1167<th> 1168 <p> 1169 Normalized time (small object / big object) 1170 </p> 1171 </th> 1172</tr></thead> 1173<tbody> 1174<tr> 1175<td> 1176 <p> 1177 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1178 list 1179 </p> 1180 </td> 1181<td> 1182 <p> 1183 16093 / 38906 1184 </p> 1185 </td> 1186<td> 1187 <p> 1188 1 / 1 1189 </p> 1190 </td> 1191</tr> 1192<tr> 1193<td> 1194 <p> 1195 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1196 list 1197 </p> 1198 </td> 1199<td> 1200 <p> 1201 16093 / 39062 1202 </p> 1203 </td> 1204<td> 1205 <p> 1206 1 / 1 1207 </p> 1208 </td> 1209</tr> 1210<tr> 1211<td> 1212 <p> 1213 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1214 list 1215 </p> 1216 </td> 1217<td> 1218 <p> 1219 16093 / 38906 1220 </p> 1221 </td> 1222<td> 1223 <p> 1224 1 / 1 1225 </p> 1226 </td> 1227</tr> 1228<tr> 1229<td> 1230 <p> 1231 Standard list 1232 </p> 1233 </td> 1234<td> 1235 <p> 1236 32343 / 56406 1237 </p> 1238 </td> 1239<td> 1240 <p> 1241 2.0 / 1.44 1242 </p> 1243 </td> 1244</tr> 1245<tr> 1246<td> 1247 <p> 1248 Standard compact pointer list 1249 </p> 1250 </td> 1251<td> 1252 <p> 1253 33593 / 46093 1254 </p> 1255 </td> 1256<td> 1257 <p> 1258 2.08 / 1.18 1259 </p> 1260 </td> 1261</tr> 1262<tr> 1263<td> 1264 <p> 1265 Standard disperse pointer list 1266 </p> 1267 </td> 1268<td> 1269 <p> 1270 46875 / 68593 1271 </p> 1272 </td> 1273<td> 1274 <p> 1275 2.91 / 1.76 1276 </p> 1277 </td> 1278</tr> 1279</tbody> 1280</table></div> 1281</div> 1282<br class="table-break"><div class="table"> 1283<a name="intrusive.performance.performance_results_sorting.sort_times_for_gcc_4_1_1_mingw_o"></a><p class="title"><b>Table 19.9. Sort times for GCC 4.1.1 / MinGW over Windows XP</b></p> 1284<div class="table-contents"><table class="table" summary="Sort times for GCC 4.1.1 / MinGW over Windows XP"> 1285<colgroup> 1286<col> 1287<col> 1288<col> 1289</colgroup> 1290<thead><tr> 1291<th> 1292 <p> 1293 Container 1294 </p> 1295 </th> 1296<th> 1297 <p> 1298 Time in us/iteration (small object / big object) 1299 </p> 1300 </th> 1301<th> 1302 <p> 1303 Normalized time (small object / big object) 1304 </p> 1305 </th> 1306</tr></thead> 1307<tbody> 1308<tr> 1309<td> 1310 <p> 1311 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1312 list 1313 </p> 1314 </td> 1315<td> 1316 <p> 1317 15000 / 39218 1318 </p> 1319 </td> 1320<td> 1321 <p> 1322 1 / 1 1323 </p> 1324 </td> 1325</tr> 1326<tr> 1327<td> 1328 <p> 1329 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1330 list 1331 </p> 1332 </td> 1333<td> 1334 <p> 1335 15156 / 39531 1336 </p> 1337 </td> 1338<td> 1339 <p> 1340 1.01 / 1.01 1341 </p> 1342 </td> 1343</tr> 1344<tr> 1345<td> 1346 <p> 1347 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1348 list 1349 </p> 1350 </td> 1351<td> 1352 <p> 1353 15156 / 39531 1354 </p> 1355 </td> 1356<td> 1357 <p> 1358 1.01 / 1.01 1359 </p> 1360 </td> 1361</tr> 1362<tr> 1363<td> 1364 <p> 1365 Standard list 1366 </p> 1367 </td> 1368<td> 1369 <p> 1370 34218 / 56875 1371 </p> 1372 </td> 1373<td> 1374 <p> 1375 2.28 / 1.45 1376 </p> 1377 </td> 1378</tr> 1379<tr> 1380<td> 1381 <p> 1382 Standard compact pointer list 1383 </p> 1384 </td> 1385<td> 1386 <p> 1387 35468 / 49218 1388 </p> 1389 </td> 1390<td> 1391 <p> 1392 2.36 / 1.25 1393 </p> 1394 </td> 1395</tr> 1396<tr> 1397<td> 1398 <p> 1399 Standard disperse pointer list 1400 </p> 1401 </td> 1402<td> 1403 <p> 1404 47656 / 70156 1405 </p> 1406 </td> 1407<td> 1408 <p> 1409 3.17 / 1.78 1410 </p> 1411 </td> 1412</tr> 1413</tbody> 1414</table></div> 1415</div> 1416<br class="table-break"><div class="table"> 1417<a name="intrusive.performance.performance_results_sorting.sort_times_for_gcc_4_1_2_linux_k"></a><p class="title"><b>Table 19.10. Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p> 1418<div class="table-contents"><table class="table" summary="Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)"> 1419<colgroup> 1420<col> 1421<col> 1422<col> 1423</colgroup> 1424<thead><tr> 1425<th> 1426 <p> 1427 Container 1428 </p> 1429 </th> 1430<th> 1431 <p> 1432 Time in us/iteration (small object / big object) 1433 </p> 1434 </th> 1435<th> 1436 <p> 1437 Normalized time (small object / big object) 1438 </p> 1439 </th> 1440</tr></thead> 1441<tbody> 1442<tr> 1443<td> 1444 <p> 1445 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1446 list 1447 </p> 1448 </td> 1449<td> 1450 <p> 1451 18003 / 40795 1452 </p> 1453 </td> 1454<td> 1455 <p> 1456 1 / 1 1457 </p> 1458 </td> 1459</tr> 1460<tr> 1461<td> 1462 <p> 1463 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1464 list 1465 </p> 1466 </td> 1467<td> 1468 <p> 1469 18003 / 41017 1470 </p> 1471 </td> 1472<td> 1473 <p> 1474 1 / 1 1475 </p> 1476 </td> 1477</tr> 1478<tr> 1479<td> 1480 <p> 1481 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1482 list 1483 </p> 1484 </td> 1485<td> 1486 <p> 1487 18230 / 40941 1488 </p> 1489 </td> 1490<td> 1491 <p> 1492 1.01 / 1 1493 </p> 1494 </td> 1495</tr> 1496<tr> 1497<td> 1498 <p> 1499 Standard list 1500 </p> 1501 </td> 1502<td> 1503 <p> 1504 26273 / 49643 1505 </p> 1506 </td> 1507<td> 1508 <p> 1509 1.45 / 1.21 1510 </p> 1511 </td> 1512</tr> 1513<tr> 1514<td> 1515 <p> 1516 Standard compact pointer list 1517 </p> 1518 </td> 1519<td> 1520 <p> 1521 28540 / 43172 1522 </p> 1523 </td> 1524<td> 1525 <p> 1526 1.58 / 1.05 1527 </p> 1528 </td> 1529</tr> 1530<tr> 1531<td> 1532 <p> 1533 Standard disperse pointer list 1534 </p> 1535 </td> 1536<td> 1537 <p> 1538 35077 / 57638 1539 </p> 1540 </td> 1541<td> 1542 <p> 1543 1.94 / 1.41 1544 </p> 1545 </td> 1546</tr> 1547</tbody> 1548</table></div> 1549</div> 1550<br class="table-break"><p> 1551 The results show that intrusive containers are faster than standard containers. 1552 We can see that the pointer list holding pointers to values stored in a vector 1553 is quite fast, so the extra indirection that is needed to access the value 1554 is minimized because all the values are tightly stored, improving caching. 1555 The disperse list, on the other hand, is slower because the indirection to 1556 access values stored in the object list is more expensive than accessing 1557 values stored in a vector. 1558 </p> 1559</div> 1560<div class="section"> 1561<div class="titlepage"><div><div><h3 class="title"> 1562<a name="intrusive.performance.performance_results_write_access"></a><a class="link" href="performance.html#intrusive.performance.performance_results_write_access" title="Write access">Write 1563 access</a> 1564</h3></div></div></div> 1565<p> 1566 The next test measures the time needed to iterate through all the elements 1567 of a list, and increment the value of the internal <code class="computeroutput"><span class="identifier">i_</span></code> 1568 member: 1569 </p> 1570<pre class="programlisting"><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">end</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 1571<span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 1572 <span class="special">++(</span><span class="identifier">it</span><span class="special">-></span><span class="identifier">i_</span><span class="special">);</span> 1573</pre> 1574<p> 1575 Values (<code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists are created as explained 1576 in the first section. Note that for pointer lists, the iteration will suffer 1577 an extra indirection: they will need to access the <code class="computeroutput"><span class="identifier">test_class</span></code> 1578 values stored in another container: 1579 </p> 1580<pre class="programlisting"><span class="identifier">stdptrlist</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">end</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> 1581<span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span> 1582 <span class="special">++((*</span><span class="identifier">it</span><span class="special">)-></span><span class="identifier">i_</span><span class="special">);</span> 1583</pre> 1584<p> 1585 These are the results: 1586 </p> 1587<div class="table"> 1588<a name="intrusive.performance.performance_results_write_access.write_access_times_for_visual_c_"></a><p class="title"><b>Table 19.11. Write access times for Visual C++ 7.1 / Windows XP</b></p> 1589<div class="table-contents"><table class="table" summary="Write access times for Visual C++ 7.1 / Windows XP"> 1590<colgroup> 1591<col> 1592<col> 1593<col> 1594</colgroup> 1595<thead><tr> 1596<th> 1597 <p> 1598 Container 1599 </p> 1600 </th> 1601<th> 1602 <p> 1603 Time in us/iteration (small object / big object) 1604 </p> 1605 </th> 1606<th> 1607 <p> 1608 Normalized time (small object / big object) 1609 </p> 1610 </th> 1611</tr></thead> 1612<tbody> 1613<tr> 1614<td> 1615 <p> 1616 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1617 list 1618 </p> 1619 </td> 1620<td> 1621 <p> 1622 2031 / 8125 1623 </p> 1624 </td> 1625<td> 1626 <p> 1627 1 / 1 1628 </p> 1629 </td> 1630</tr> 1631<tr> 1632<td> 1633 <p> 1634 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1635 list 1636 </p> 1637 </td> 1638<td> 1639 <p> 1640 2031 / 8281 1641 </p> 1642 </td> 1643<td> 1644 <p> 1645 1 / 1.01 1646 </p> 1647 </td> 1648</tr> 1649<tr> 1650<td> 1651 <p> 1652 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1653 list 1654 </p> 1655 </td> 1656<td> 1657 <p> 1658 2031 / 8281 1659 </p> 1660 </td> 1661<td> 1662 <p> 1663 1 / 1.01 1664 </p> 1665 </td> 1666</tr> 1667<tr> 1668<td> 1669 <p> 1670 Standard list 1671 </p> 1672 </td> 1673<td> 1674 <p> 1675 4218 / 10000 1676 </p> 1677 </td> 1678<td> 1679 <p> 1680 2.07 / 1.23 1681 </p> 1682 </td> 1683</tr> 1684<tr> 1685<td> 1686 <p> 1687 Standard compact pointer list 1688 </p> 1689 </td> 1690<td> 1691 <p> 1692 4062 / 8437 1693 </p> 1694 </td> 1695<td> 1696 <p> 1697 2.0 / 1.03 1698 </p> 1699 </td> 1700</tr> 1701<tr> 1702<td> 1703 <p> 1704 Standard disperse pointer list 1705 </p> 1706 </td> 1707<td> 1708 <p> 1709 8593 / 13125 1710 </p> 1711 </td> 1712<td> 1713 <p> 1714 4.23 / 1.61 1715 </p> 1716 </td> 1717</tr> 1718</tbody> 1719</table></div> 1720</div> 1721<br class="table-break"><div class="table"> 1722<a name="intrusive.performance.performance_results_write_access.write_access_times_for_gcc_4_1_1"></a><p class="title"><b>Table 19.12. Write access times for GCC 4.1.1 / MinGW over Windows XP</b></p> 1723<div class="table-contents"><table class="table" summary="Write access times for GCC 4.1.1 / MinGW over Windows XP"> 1724<colgroup> 1725<col> 1726<col> 1727<col> 1728</colgroup> 1729<thead><tr> 1730<th> 1731 <p> 1732 Container 1733 </p> 1734 </th> 1735<th> 1736 <p> 1737 Time in us/iteration (small object / big object) 1738 </p> 1739 </th> 1740<th> 1741 <p> 1742 Normalized time (small object / big object) 1743 </p> 1744 </th> 1745</tr></thead> 1746<tbody> 1747<tr> 1748<td> 1749 <p> 1750 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1751 list 1752 </p> 1753 </td> 1754<td> 1755 <p> 1756 2343 / 8281 1757 </p> 1758 </td> 1759<td> 1760 <p> 1761 1 / 1 1762 </p> 1763 </td> 1764</tr> 1765<tr> 1766<td> 1767 <p> 1768 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1769 list 1770 </p> 1771 </td> 1772<td> 1773 <p> 1774 2500 / 8281 1775 </p> 1776 </td> 1777<td> 1778 <p> 1779 1.06 / 1 1780 </p> 1781 </td> 1782</tr> 1783<tr> 1784<td> 1785 <p> 1786 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1787 list 1788 </p> 1789 </td> 1790<td> 1791 <p> 1792 2500 / 8281 1793 </p> 1794 </td> 1795<td> 1796 <p> 1797 1.06 / 1 1798 </p> 1799 </td> 1800</tr> 1801<tr> 1802<td> 1803 <p> 1804 Standard list 1805 </p> 1806 </td> 1807<td> 1808 <p> 1809 4218 / 10781 1810 </p> 1811 </td> 1812<td> 1813 <p> 1814 1.8 / 1.3 1815 </p> 1816 </td> 1817</tr> 1818<tr> 1819<td> 1820 <p> 1821 Standard compact pointer list 1822 </p> 1823 </td> 1824<td> 1825 <p> 1826 3906 / 8281 1827 </p> 1828 </td> 1829<td> 1830 <p> 1831 1.66 / 1 1832 </p> 1833 </td> 1834</tr> 1835<tr> 1836<td> 1837 <p> 1838 Standard disperse pointer list 1839 </p> 1840 </td> 1841<td> 1842 <p> 1843 8281 / 13750 1844 </p> 1845 </td> 1846<td> 1847 <p> 1848 3.53 / 1.66 1849 </p> 1850 </td> 1851</tr> 1852</tbody> 1853</table></div> 1854</div> 1855<br class="table-break"><div class="table"> 1856<a name="intrusive.performance.performance_results_write_access.write_access_times_for_gcc_4_1_2"></a><p class="title"><b>Table 19.13. Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p> 1857<div class="table-contents"><table class="table" summary="Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)"> 1858<colgroup> 1859<col> 1860<col> 1861<col> 1862</colgroup> 1863<thead><tr> 1864<th> 1865 <p> 1866 Container 1867 </p> 1868 </th> 1869<th> 1870 <p> 1871 Time in us/iteration (small object / big object) 1872 </p> 1873 </th> 1874<th> 1875 <p> 1876 Normalized time (small object / big object) 1877 </p> 1878 </th> 1879</tr></thead> 1880<tbody> 1881<tr> 1882<td> 1883 <p> 1884 <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive 1885 list 1886 </p> 1887 </td> 1888<td> 1889 <p> 1890 2286 / 8468 1891 </p> 1892 </td> 1893<td> 1894 <p> 1895 1 / 1.1 1896 </p> 1897 </td> 1898</tr> 1899<tr> 1900<td> 1901 <p> 1902 <code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive 1903 list 1904 </p> 1905 </td> 1906<td> 1907 <p> 1908 2381 / 8412 1909 </p> 1910 </td> 1911<td> 1912 <p> 1913 1.04 / 1.09 1914 </p> 1915 </td> 1916</tr> 1917<tr> 1918<td> 1919 <p> 1920 <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive 1921 list 1922 </p> 1923 </td> 1924<td> 1925 <p> 1926 2301 / 8437 1927 </p> 1928 </td> 1929<td> 1930 <p> 1931 1.01 / 1.1 1932 </p> 1933 </td> 1934</tr> 1935<tr> 1936<td> 1937 <p> 1938 Standard list 1939 </p> 1940 </td> 1941<td> 1942 <p> 1943 3044 / 9061 1944 </p> 1945 </td> 1946<td> 1947 <p> 1948 1.33 / 1.18 1949 </p> 1950 </td> 1951</tr> 1952<tr> 1953<td> 1954 <p> 1955 Standard compact pointer list 1956 </p> 1957 </td> 1958<td> 1959 <p> 1960 2755 / 7660 1961 </p> 1962 </td> 1963<td> 1964 <p> 1965 1.20 / 1 1966 </p> 1967 </td> 1968</tr> 1969<tr> 1970<td> 1971 <p> 1972 Standard disperse pointer list 1973 </p> 1974 </td> 1975<td> 1976 <p> 1977 6118 / 12453 1978 </p> 1979 </td> 1980<td> 1981 <p> 1982 2.67 / 1.62 1983 </p> 1984 </td> 1985</tr> 1986</tbody> 1987</table></div> 1988</div> 1989<br class="table-break"><p> 1990 As with the read access test, the results show that intrusive containers 1991 outperform all other containers if the values are tightly packed in a vector. 1992 The disperse list is again the slowest. 1993 </p> 1994</div> 1995<div class="section"> 1996<div class="titlepage"><div><div><h3 class="title"> 1997<a name="intrusive.performance.performance_results_conclusions"></a><a class="link" href="performance.html#intrusive.performance.performance_results_conclusions" title="Conclusions">Conclusions</a> 1998</h3></div></div></div> 1999<p> 2000 Intrusive containers can offer performance benefits that cannot be achieved 2001 with equivalent non-intrusive containers. Memory locality improvements are 2002 noticeable when the objects to be inserted are small. Minimizing memory allocation/deallocation 2003 calls is also an important factor and intrusive containers make this simple 2004 if all objects to be inserted in intrusive containers are allocated using 2005 <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code> or <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">deque</span></code>. 2006 </p> 2007</div> 2008</div> 2009<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 2010<td align="left"></td> 2011<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 2012 Distributed under the Boost Software License, Version 1.0. (See accompanying 2013 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 2014 </p> 2015</div></td> 2016</tr></table> 2017<hr> 2018<div class="spirit-nav"> 2019<a accesskey="p" href="design_notes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="release_notes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 2020</div> 2021</body> 2022</html> 2023
