1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN"> 2 3<html> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> 6<title>Boost.MultiIndex Documentation - Performance</title> 7<link rel="stylesheet" href="style.css" type="text/css"> 8<link rel="start" href="index.html"> 9<link rel="prev" href="compiler_specifics.html"> 10<link rel="up" href="index.html"> 11<link rel="next" href="examples.html"> 12</head> 13 14<body> 15<h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align= 16"middle" width="277" height="86">Boost.MultiIndex Performance</h1> 17 18<div class="prev_link"><a href="compiler_specifics.html"><img src="prev.gif" alt="compiler specifics" border="0"><br> 19Compiler specifics 20</a></div> 21<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> 22Index 23</a></div> 24<div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br> 25Examples 26</a></div><br clear="all" style="clear: all;"> 27 28<hr> 29 30<h2>Contents</h2> 31 32<ul> 33 <li><a href="#intro">Introduction</a></li> 34 <li><a href="#simulation">Manual simulation of a <code>multi_index_container</code></a></li> 35 <li><a href="#spatial_efficiency">Spatial efficiency</a></li> 36 <li><a href="#time_efficiency">Time efficiency</a></li> 37 <li><a href="#tests">Performance tests</a> 38 <ul> 39 <li><a href="#test_1r">Results for 1 ordered index</a> 40 <ul> 41 <li><a href="#memory_1r">Memory consumption</a></li> 42 <li><a href="#time_1r">Execution time</a></li> 43 </ul> 44 </li> 45 <li><a href="#test_1s">Results for 1 sequenced index</a> 46 <ul> 47 <li><a href="#memory_1s">Memory consumption</a></li> 48 <li><a href="#time_1s">Execution time</a></li> 49 </ul> 50 </li> 51 <li><a href="#test_2r">Results for 2 ordered indices</a> 52 <ul> 53 <li><a href="#memory_2r">Memory consumption</a></li> 54 <li><a href="#time_2r">Execution time</a></li> 55 </ul> 56 </li> 57 <li><a href="#test_1r1s">Results for 1 ordered index + 1 sequenced index</a> 58 <ul> 59 <li><a href="#memory_1r1s">Memory consumption</a></li> 60 <li><a href="#time_1r1s">Execution time</a></li> 61 </ul> 62 </li> 63 <li><a href="#test_3r">Results for 3 ordered indices</a> 64 <ul> 65 <li><a href="#memory_3r">Memory consumption</a></li> 66 <li><a href="#time_3r">Execution time</a></li> 67 </ul> 68 </li> 69 <li><a href="#test_2r1s">Results for 2 ordered indices + 1 sequenced index</a> 70 <ul> 71 <li><a href="#memory_2r1s">Memory consumption</a></li> 72 <li><a href="#time_2r1s">Execution time</a></li> 73 </ul> 74 </li> 75 </ul> 76 </li> 77 <li><a href="#conclusions">Conclusions</a></li> 78</ul> 79 80<h2><a name="intro">Introduction</a></h2> 81 82<p> 83Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome 84compositions of containers when multi-indexing capabilities are needed. Furthermore, 85it does so in an efficient manner, both in terms of space and time consumption. The 86space savings stem from the compact representation of the underlying data structures, 87requiring a single node per element. As for time efficiency, Boost.MultiIndex 88intensively uses metaprogramming techniques producing very tight implementations 89of member functions which take care of the elementary operations for each index: 90for <code>multi_index_container</code>s with two or more indices, the running time 91can be reduced to half as long as with manual simulations involving several 92STL containers. 93</p> 94 95<h2><a name="simulation">Manual simulation of a <code>multi_index_container</code></a></h2> 96 97<p> 98The section on <a href="tutorial/techniques.html#emulate_std_containers">emulation 99of standard containers with <code>multi_index_container</code></a> shows the equivalence 100between single-index <code>multi_index_container</code>s and some STL containers. Let us now 101concentrate on the problem of simulating a <code>multi_index_container</code> with two 102or more indices with a suitable combination of standard containers. 103</p> 104 105<p> 106Consider the following instantiation of <code>multi_index_container</code>: 107</p> 108 109<blockquote><pre> 110<span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> 111 <span class=keyword>int</span><span class=special>,</span> 112 <span class=identifier>indexed_by</span><span class=special><</span> 113 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 114 <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</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=keyword>int</span><span class=special>></span> <span class=special>>,</span> 115 <span class=special>></span> 116<span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span> 117</pre></blockquote> 118 119<p> 120<code>indexed_t</code> maintains two internal indices on elements of type 121<code>int</code>. In order to simulate this data structure resorting only to 122standard STL containers, one can use on a first approach the following types: 123</p> 124 125<blockquote><pre> 126<span class=comment>// dereferencing compare predicate</span> 127<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Iterator</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> 128<span class=keyword>struct</span> <span class=identifier>it_compare</span> 129<span class=special>{</span> 130 <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>Iterator</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>Iterator</span><span class=special>&</span> <span class=identifier>y</span><span class=special>)</span><span class=keyword>const</span> 131 <span class=special>{</span> 132 <span class=keyword>return</span> <span class=identifier>comp</span><span class=special>(*</span><span class=identifier>x</span><span class=special>,*</span><span class=identifier>y</span><span class=special>);</span> 133 <span class=special>}</span> 134 135<span class=keyword>private</span><span class=special>:</span> 136 <span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>;</span> 137<span class=special>};</span> 138 139<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>set</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=identifier>manual_t1</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #0</span> 140<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span> 141 <span class=keyword>const</span> <span class=keyword>int</span><span class=special>*,</span> 142 <span class=identifier>it_compare</span><span class=special><</span> 143 <span class=keyword>const</span> <span class=keyword>int</span><span class=special>*,</span> 144 <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> 145 <span class=special>></span> 146<span class=special>></span> <span class=identifier>manual_t2</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #1</span> 147</pre></blockquote> 148 149<p> 150where <code>manual_t1</code> is the "base" container that holds 151the actual elements, and <code>manual_t2</code> stores pointers to 152elements of <code>manual_t1</code>. This scheme turns out to be quite 153inefficient, though: while insertion into the data structure is simple enough: 154</p> 155 156<blockquote><pre> 157<span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span> 158<span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span> 159 160<span class=comment>// insert the element 5</span> 161<span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>c1</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>5</span><span class=special>).</span><span class=identifier>first</span><span class=special>;</span> 162<span class=identifier>c2</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(&*</span><span class=identifier>it1</span><span class=special>);</span> 163</pre></blockquote> 164 165deletion, on the other hand, necessitates a logarithmic search, whereas 166<code>indexed_t</code> deletes in constant time: 167 168<blockquote><pre> 169<span class=comment>// remove the element pointed to by it2</span> 170<span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span> 171<span class=identifier>c1</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(**</span><span class=identifier>it2</span><span class=special>);</span> <span class=comment>// watch out! performs in logarithmic time</span> 172<span class=identifier>c2</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>it2</span><span class=special>);</span> 173</pre></blockquote> 174 175<p> 176The right approach consists of feeding the second container not with 177raw pointers, but with elements of type <code>manual_t1::iterator</code>: 178</p> 179 180<blockquote><pre> 181<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>set</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=identifier>manual_t1</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #0</span> 182<span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span> 183 <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span> 184 <span class=identifier>it_compare</span><span class=special><</span> 185 <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span> 186 <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> 187 <span class=special>></span> 188<span class=special>></span> <span class=identifier>manual_t2</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #1</span> 189</pre></blockquote> 190 191<p> 192Now, insertion and deletion can be performed with complexity bounds 193equivalent to those of <code>indexed_t</code>: 194</p> 195 196<blockquote><pre> 197<span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span> 198<span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span> 199 200<span class=comment>// insert the element 5</span> 201<span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>c1</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>5</span><span class=special>).</span><span class=identifier>first</span><span class=special>;</span> 202<span class=identifier>c2</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>it1</span><span class=special>);</span> 203 204<span class=comment>// remove the element pointed to by it2</span> 205<span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span> 206<span class=identifier>c1</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(*</span><span class=identifier>it2</span><span class=special>);</span> <span class=comment>// OK: constant time</span> 207<span class=identifier>c2</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>it2</span><span class=special>);</span> 208</pre></blockquote> 209 210<p> 211The construction can be extended in a straightforward manner to 212handle more than two indices. In what follows, we will compare 213instantiations of <code>multi_index_container</code> against this sort of 214manual simulations. 215</p> 216 217<h2><a name="spatial_efficiency">Spatial efficiency</a></h2> 218 219<p> 220The gain in space consumption of <code>multi_index_container</code> with 221respect to its manual simulations is amenable to a very simple 222theoretical analysis. For simplicity, we will ignore alignment 223issues (which in general play in favor of <code>multi_index_container</code>.) 224</p> 225 226<p> 227Nodes of a <code>multi_index_container</code> with <i>N</i> indices hold the value 228of the element plus <i>N</i> headers containing linking information for 229each index. Thus the node size is 230</p> 231 232<blockquote> 233<i>S<sub>I</sub></i> = <i>e</i> + <i>h</i><sub>0</sub> + ··· + 234<i>h</i><sub><i>N</i>-1</sub>, where<br> 235<i>e</i> = size of the element,<br> 236<i>h</i><sub><i>i</i></sub> = size of the <i>i</i>-th header. 237</blockquote> 238 239<p> 240On the other hand, the manual simulation allocates <i>N</i> nodes per 241element, the first holding the elements themselves and the rest 242storing iterators to the "base" container. In practice, an iterator 243merely holds a raw pointer to the node it is associated to, so its size 244is independent of the type of the elements. Summing all contributions, 245the space allocated per element in a manual simulation is 246</p> 247 248<blockquote> 249<i>S<sub>M</sub></i> = (<i>e</i> + <i>h</i><sub>0</sub>) + 250(<i>p</i> + <i>h</i><sub>1</sub>) + ··· + 251(<i>p</i> + <i>h</i><sub><i>N</i>-1</sub>) = 252<i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i>, where<br> 253<i>p</i> = size of a pointer.<br> 254</blockquote> 255 256<p> 257The relative amount of memory taken up by <code>multi_index_container</code> 258with respect to its manual simulation is just 259<i>S<sub>I</sub></i> / <i>S<sub>M</sub></i>, which can be expressed 260then as: 261</p> 262 263<blockquote> 264<i>S<sub>I</sub></i> / <i>S<sub>M</sub></i> = 265<i>S<sub>I</sub></i> / (<i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i>). 266</blockquote> 267 268<p> 269The formula shows that <code>multi_index_container</code> is more efficient 270with regard to memory consumption as the number of indices grow. An implicit 271assumption has been made that headers of <code>multi_index_container</code> 272index nodes are the same size that their analogues in STL containers; but there 273is a particular case in which this is often not the case: ordered indices use a 274<a href="tutorial/indices.html#ordered_node_compression">spatial optimization 275technique</a> which is not present in many implementations of 276<code>std::set</code>, giving an additional advantage to 277<code>multi_index_container</code>s of one system word per ordered index. 278Taking this fact into account, the former formula can be adjusted to: 279</p> 280 281<blockquote> 282<i>S<sub>I</sub></i> / <i>S<sub>M</sub></i> = 283<i>S<sub>I</sub></i> / (<i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i> + <i>Ow</i>), 284</blockquote> 285 286<p> 287where <i>O</i> is the number of ordered indices of the container, and <i>w</i> 288is the system word size (typically 4 bytes on 32-bit architectures.) 289</p> 290 291<p> 292These considerations have overlooked an aspect of the greatest practical 293importance: the fact that <code>multi_index_container</code> allocates a single 294node per element, compared to the many nodes of different sizes 295built by manual simulations, diminishes memory fragmentation, which 296can show up in more usable memory available and better performance. 297</p> 298 299<h2><a name="time_efficiency">Time efficiency</a></h2> 300 301<p> 302From the point of view of computational complexity (i.e. big-O 303characterization), <code>multi_index_container</code> and its corresponding manual 304simulations are equivalent: inserting an element into 305a <code>multi_index_container</code> reduces to a simple combination of 306elementary insertion operations on each of the indices, and 307similarly for deletion. Hence, the most we can expect is a reduction 308(or increase) of execution time by a roughly constant factor. As we 309will see later, the reduction can be very significative for 310<code>multi_index_container</code>s with two or more indices. 311</p> 312 313<p>In the special case of <code>multi_index_container</code>s with only one index, 314resulting performance will roughly match that of the STL equivalent containers: 315tests show that there is at most a negligible degradation with respect to STL, 316and even in some cases a small improvement. 317</p> 318 319<h2><a name="tests">Performance tests</a></h2> 320 321<p> 322See <a href="../perf/test_perf.cpp">source code</a> used for measurements. 323<p> 324In order to assess the efficiency of <code>multi_index_container</code>, the following 325basic algorithm 326</p> 327 328<blockquote><pre> 329<span class=identifier>multi_index_container</span><span class=special><...></span> <span class=identifier>c</span><span class=special>;</span> 330<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>n</span><span class=special>;++</span><span class=identifier>i</span><span class=special>)</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>i</span><span class=special>);</span> 331<span class=keyword>for</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>it</span><span class=special>=</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>begin</span><span class=special>();</span><span class=identifier>it</span><span class=special>!=</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>end</span><span class=special>();)</span><span class=identifier>c</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>it</span><span class=special>++);</span> 332</pre></blockquote> 333 334<p> 335has been measured for different instantiations of <code>multi_index_container</code> 336at values of <i>n</i> 1,000, 10,000 and 100,000, 337and its execution time compared with that of the equivalent algorithm 338for the corresponding manual simulation of the data structure based on 339STL containers. The table below describes the test environments used. 340</p> 341 342<p align="center"> 343<table cellspacing="0" cellpadding="5"> 344 <caption><b>Tests environments.</b></caption> 345<tr> 346 <th>Compiler</th> 347 <th>Settings</th> 348 <th>OS and CPU</th> 349</tr> 350<tr> 351 <td>GCC 3.4.5 (mingw special)</td> 352 <td><code>-O3</code></td> 353 <td>Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM</td> 354</tr> 355<tr class="odd_tr"> 356 <td>Intel C++ 7.1</td> 357 <td>default release settings</td> 358 <td>Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM</td> 359</tr> 360<tr> 361 <td>Microsoft Visual C++ 8.0</td> 362 <td>default release settings, <code>_SECURE_SCL=0</code></td> 363 <td>Windows XP on P4 Xeon 3.2 GHz, 1 GB RAM</td> 364</tr> 365</table> 366</p> 367 368<p> 369The relative memory consumption (i.e. the amount of memory allocated 370by a <code>multi_index_container</code> with respect to its manual simulation) 371is determined by dividing the size of a <code>multi_index_container</code> node 372by the sum of node sizes of all the containers integrating the 373simulating data structure. 374</p> 375 376<h3><a name="test_1r">Results for 1 ordered index</a></h3> 377 378<p> 379The following instantiation of <code>multi_index_container</code> was tested: 380</p> 381 382<blockquote><pre> 383<span class=identifier>multi_index_container</span><span class=special><</span> 384 <span class=keyword>int</span><span class=special>,</span> 385 <span class=identifier>indexed_by</span><span class=special><</span> 386 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span> 387 <span class=special>></span> 388<span class=special>></span> 389</pre></blockquote> 390 391<p> 392which is functionally equivalent to <code>std::set<int></code>. 393</p> 394 395<h4><a name="memory_1r">Memory consumption</a></h4> 396 397<p align="center"> 398<table cellspacing="0"> 399<tr> 400 <th width="33%">GCC 3.4.5</th> 401 <th width="33%">ICC 7.1</th> 402 <th width="33%">MSVC 8.0</th> 403</tr> 404<tr> 405 <td align="center">80%</td> 406 <td align="center">80%</td> 407 <td align="center">80%</td> 408</tr> 409</table> 410<b>Table 1: Relative memory consumption of <code>multi_index_container</code> with 1 411ordered index.</b> 412</p> 413 414<p> 415The reduction in memory usage is accounted for by the optimization technique implemented 416in Boost.MultiIndex ordered indices, as <a href="#spatial_efficiency">explained above</a>. 417</p> 418 419<h4><a name="time_1r">Execution time</a></h4> 420 421<p align="center"> 422<img src="perf_1o.png" alt="performance of multi_index_container with 1 ordered index" 423width="556" height="372"><br> 424<b>Fig. 1: Performance of <code>multi_index_container</code> with 1 ordered index.</b> 425</p> 426 427<p> 428Somewhat surprisingly, <code>multi_index_container</code> performs slightly 429better than <code>std::set</code>. A very likely explanation for this behavior 430is that the lower memory consumption of <code>multi_index_container</code> 431results in a higher processor cache hit rate. 432The improvement is smallest for GCC, presumably because the worse quality of 433this compiler's optimizer masks the cache-related benefits. 434</p> 435 436<h3><a name="test_1s">Results for 1 sequenced index</a></h3> 437 438<p> 439The following instantiation of <code>multi_index_container</code> was tested: 440</p> 441 442<blockquote><pre> 443<span class=identifier>multi_index_container</span><span class=special><</span> 444 <span class=keyword>int</span><span class=special>,</span> 445 <span class=identifier>indexed_by</span><span class=special><</span> 446 <span class=identifier>sequenced</span><span class=special><></span> 447 <span class=special>></span> 448<span class=special>></span> 449</pre></blockquote> 450 451<p> 452which is functionally equivalent to <code>std::list<int></code>. 453</p> 454 455<h4><a name="memory_1s">Memory consumption</a></h4> 456 457<p align="center"> 458<table cellspacing="0"> 459<tr> 460 <th width="33%">GCC 3.4.5</th> 461 <th width="33%">ICC 7.1</th> 462 <th width="33%">MSVC 8.0</th> 463</tr> 464<tr> 465 <td align="center">100%</td> 466 <td align="center">100%</td> 467 <td align="center">100%</td> 468</tr> 469</table> 470<b>Table 2: Relative memory consumption of <code>multi_index_container</code> with 1 471sequenced index.</b> 472</p> 473 474<p> 475The figures confirm that in this case <code>multi_index_container</code> nodes are the 476same size than those of its <code>std::list</code> counterpart. 477</p> 478 479<h4><a name="time_1s">Execution time</a></h4> 480 481<p align="center"> 482<img src="perf_1s.png" alt="performance of multi_index_container with 1 sequenced index" 483width="556" height="372"><br> 484<b>Fig. 2: Performance of <code>multi_index_container</code> with 1 sequenced index.</b> 485</p> 486 487<p> 488<code>multi_index_container</code> does not attain the performance 489of its STL counterpart, although the figures are close. Again, the worst results 490are those of GCC, with a degradation of up to 7%, while ICC and MSVC do not 491exceed a mere 5%. 492</p> 493 494<h3><a name="test_2r">Results for 2 ordered indices</a></h3> 495 496<p> 497The following instantiation of <code>multi_index_container</code> was tested: 498</p> 499 500<blockquote><pre> 501<span class=identifier>multi_index_container</span><span class=special><</span> 502 <span class=keyword>int</span><span class=special>,</span> 503 <span class=identifier>indexed_by</span><span class=special><</span> 504 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 505 <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span> 506 <span class=special>></span> 507<span class=special>></span> 508</pre></blockquote> 509 510<h4><a name="memory_2r">Memory consumption</a></h4> 511 512<p align="center"> 513<table cellspacing="0"> 514<tr> 515 <th width="33%">GCC 3.4.5</th> 516 <th width="33%">ICC 7.1</th> 517 <th width="33%">MSVC 8.0</th> 518</tr> 519<tr> 520 <td align="center">70%</td> 521 <td align="center">70%</td> 522 <td align="center">70%</td> 523</tr> 524</table> 525<b>Table 3: Relative memory consumption of <code>multi_index_container</code> with 2 526ordered indices.</b> 527</p> 528 529<p> 530These results coincide with the theoretical formula for 531<i>S<sub>I</sub></i> = 28, <i>N</i> = <i>O</i> = 2 and <i>p</i> = <i>w</i> = 4. 532</p> 533 534<h4><a name="time_2r">Execution time</a></h4> 535 536<p align="center"> 537<img src="perf_2o.png" alt="performance of multi_index_container with 2 ordered indices" 538width="556" height="372"><br> 539<b>Fig. 3: Performance of <code>multi_index_container</code> with 2 ordered indices.</b> 540</p> 541 542<p> 543The experimental results confirm our hypothesis that <code>multi_index_container</code> 544provides an improvement on execution time by an approximately constant factor, 545which in this case lies around 60%. There is no obvious explanation for the 546increased advantage of <code>multi_index_container</code> in MSVC for 547<i>n</i>=10<sup>5</sup>. 548</p> 549 550<h3><a name="test_1r1s">Results for 1 ordered index + 1 sequenced index</a></h3> 551 552<p> 553The following instantiation of <code>multi_index_container</code> was tested: 554</p> 555 556<blockquote><pre> 557<span class=identifier>multi_index_container</span><span class=special><</span> 558 <span class=keyword>int</span><span class=special>,</span> 559 <span class=identifier>indexed_by</span><span class=special><</span> 560 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 561 <span class=identifier>sequenced</span><span class=special><></span> 562 <span class=special>></span> 563<span class=special>></span> 564</pre></blockquote> 565 566<h4><a name="memory_1r1s">Memory consumption</a></h4> 567 568<p align="center"> 569<table cellspacing="0"> 570<tr> 571 <th width="33%">GCC 3.4.5</th> 572 <th width="33%">ICC 7.1</th> 573 <th width="33%">MSVC 8.0</th> 574</tr> 575<tr> 576 <td align="center">75%</td> 577 <td align="center">75%</td> 578 <td align="center">75%</td> 579</tr> 580</table> 581<b>Table 4: Relative memory consumption of <code>multi_index_container</code> with 1 582ordered index + 1 sequenced index.</b> 583</p> 584 585<p> 586These results coincide with the theoretical formula for 587<i>S<sub>I</sub></i> = 24, <i>N</i> = 2, <i>O</i> = 1 and <i>p</i> = <i>w</i> = 4. 588</p> 589 590<h4><a name="time_1r1s">Execution time</a></h4> 591 592<p align="center"> 593<img src="perf_1o1s.png" 594alt="performance of multi_index_container with 1 ordered index + 1 sequenced index" 595width="556" height="372"><br> 596<b>Fig. 4: Performance of <code>multi_index_container</code> with 1 ordered index 597+ 1 sequenced index.</b> 598</p> 599 600<p> 601For <i>n</i>=10<sup>3</sup> and <i>n</i>=10<sup>4</sup>, the results 602are in agreement with our theoretical analysis, showing a constant factor 603improvement of 50-65% with respect to the STL-based manual simulation. 604Curiously enough, this speedup gets even higher when 605<i>n</i>=10<sup>5</sup> for two of the compilers, namely GCC and ICC. 606In order to rule out spurious results, the tests 607have been run many times, yielding similar outcomes. Both test environments 608are deployed on the same machine, which points to some OS-related reason for 609this phenomenon. 610</p> 611 612<h3><a name="test_3r">Results for 3 ordered indices</a></h3> 613 614<p> 615The following instantiation of <code>multi_index_container</code> was tested: 616</p> 617 618<blockquote><pre> 619<span class=identifier>multi_index_container</span><span class=special><</span> 620 <span class=keyword>int</span><span class=special>,</span> 621 <span class=identifier>indexed_by</span><span class=special><</span> 622 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 623 <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 624 <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>></span> 625 <span class=special>></span> 626<span class=special>></span> 627</pre></blockquote> 628 629<h4><a name="memory_3r">Memory consumption</a></h4> 630 631<p align="center"> 632<table cellspacing="0"> 633<tr> 634 <th width="33%">GCC 3.4.5</th> 635 <th width="33%">ICC 7.1</th> 636 <th width="33%">MSVC 8.0</th> 637</tr> 638<tr> 639 <td align="center">66.7%</td> 640 <td align="center">66.7%</td> 641 <td align="center">66.7%</td> 642</tr> 643</table> 644<b>Table 5: Relative memory consumption of <code>multi_index_container</code> with 3 645ordered indices.</b> 646</p> 647 648<p> 649These results coincide with the theoretical formula for 650<i>S<sub>I</sub></i> = 40, <i>N</i> = <i>O</i> = 3 and <i>p</i> = <i>w</i> = 4. 651</p> 652 653<h4><a name="time_3r">Execution time</a></h4> 654 655<p align="center"> 656<img src="perf_3o.png" alt="performance of multi_index_container with 3 ordered indices" 657width="556" height="372"><br> 658<b>Fig. 5: Performance of <code>multi_index_container</code> with 3 ordered indices.</b> 659</p> 660 661<p> 662Execution time for this case is between 45% and 55% lower than achieved with 663an STL-based manual simulation of the same data structure. 664</p> 665 666<h3><a name="test_2r1s">Results for 2 ordered indices + 1 sequenced index</a></h3> 667 668<p> 669The following instantiation of <code>multi_index_container</code> was tested: 670</p> 671 672<blockquote><pre> 673<span class=identifier>multi_index_container</span><span class=special><</span> 674 <span class=keyword>int</span><span class=special>,</span> 675 <span class=identifier>indexed_by</span><span class=special><</span> 676 <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 677 <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> 678 <span class=identifier>sequenced</span><span class=special><></span> 679 <span class=special>></span> 680<span class=special>></span> 681</pre></blockquote> 682 683<h4><a name="memory_2r1s">Memory consumption</a></h4> 684 685<p align="center"> 686<table cellspacing="0"> 687<tr> 688 <th width="33%">GCC 3.4.5</th> 689 <th width="33%">ICC 7.1</th> 690 <th width="33%">MSVC 8.0</th> 691</tr> 692<tr> 693 <td align="center">69.2%</td> 694 <td align="center">69.2%</td> 695 <td align="center">69.2%</td> 696</tr> 697</table> 698<b>Table 6: Relative memory consumption of <code>multi_index_container</code> with 2 699ordered indices + 1 sequenced index.</b> 700</p> 701 702<p> 703These results coincide with the theoretical formula for 704<i>S<sub>I</sub></i> = 36, <i>N</i> = 3, <i>O</i> = 2 and <i>p</i> = <i>w</i> = 4. 705</p> 706 707<h4><a name="time_2r1s">Execution time</a></h4> 708 709<p align="center"> 710<img src="perf_2o1s.png" 711alt="performance of multi_index_container with 2 ordered indices + 1 sequenced index" 712width="556" height="372"><br> 713<b>Fig. 6: Performance of <code>multi_index_container</code> with 2 ordered indices 714+ 1 sequenced index.</b> 715</p> 716 717<p> 718In accordance to the expectations, execution time is improved by a fairly constant 719factor, which ranges from 45% to 55%. 720</p> 721 722<h2><a name="conclusions">Conclusions</a></h2> 723 724<p> 725We have shown that <code>multi_index_container</code> outperforms, both in space and 726time efficiency, equivalent data structures obtained from the manual 727combination of STL containers. This improvement gets larger when the number 728of indices increase. 729</p> 730 731<p> 732In the special case of replacing standard containers with single-indexed 733<code>multi_index_container</code>s, the performance of Boost.MultiIndex 734is comparable with that of the tested STL implementations, and can even yield 735some improvements both in space consumption and execution time. 736</p> 737 738<hr> 739 740<div class="prev_link"><a href="compiler_specifics.html"><img src="prev.gif" alt="compiler specifics" border="0"><br> 741Compiler specifics 742</a></div> 743<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> 744Index 745</a></div> 746<div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br> 747Examples 748</a></div><br clear="all" style="clear: all;"> 749 750<br> 751 752<p>Revised April 18th 2020</p> 753 754<p>© Copyright 2003-2020 Joaquín M López Muñoz. 755Distributed under the Boost Software 756License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt"> 757LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> 758http://www.boost.org/LICENSE_1_0.txt</a>) 759</p> 760 761</body> 762</html> 763
