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> 19 Compiler specifics 20 </a></div> 21 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> 22 Index 23 </a></div> 24 <div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br> 25 Examples 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> 83 Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome 84 compositions of containers when multi-indexing capabilities are needed. Furthermore, 85 it does so in an efficient manner, both in terms of space and time consumption. The 86 space savings stem from the compact representation of the underlying data structures, 87 requiring a single node per element. As for time efficiency, Boost.MultiIndex 88 intensively uses metaprogramming techniques producing very tight implementations 89 of member functions which take care of the elementary operations for each index: 90 for <code>multi_index_container</code>s with two or more indices, the running time 91 can be reduced to half as long as with manual simulations involving several 92 STL containers. 93 </p> 94 95 <h2><a name="simulation">Manual simulation of a <code>multi_index_container</code></a></h2> 96 97 <p> 98 The section on <a href="tutorial/techniques.html#emulate_std_containers">emulation 99 of standard containers with <code>multi_index_container</code></a> shows the equivalence 100 between single-index <code>multi_index_container</code>s and some STL containers. Let us now 101 concentrate on the problem of simulating a <code>multi_index_container</code> with two 102 or more indices with a suitable combination of standard containers. 103 </p> 104 105 <p> 106 Consider 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 122 standard 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> 150 where <code>manual_t1</code> is the "base" container that holds 151 the actual elements, and <code>manual_t2</code> stores pointers to 152 elements of <code>manual_t1</code>. This scheme turns out to be quite 153 inefficient, 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 165 deletion, 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> 176 The right approach consists of feeding the second container not with 177 raw 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> 192 Now, insertion and deletion can be performed with complexity bounds 193 equivalent 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> 211 The construction can be extended in a straightforward manner to 212 handle more than two indices. In what follows, we will compare 213 instantiations of <code>multi_index_container</code> against this sort of 214 manual simulations. 215 </p> 216 217 <h2><a name="spatial_efficiency">Spatial efficiency</a></h2> 218 219 <p> 220 The gain in space consumption of <code>multi_index_container</code> with 221 respect to its manual simulations is amenable to a very simple 222 theoretical analysis. For simplicity, we will ignore alignment 223 issues (which in general play in favor of <code>multi_index_container</code>.) 224 </p> 225 226 <p> 227 Nodes of a <code>multi_index_container</code> with <i>N</i> indices hold the value 228 of the element plus <i>N</i> headers containing linking information for 229 each 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> 240 On the other hand, the manual simulation allocates <i>N</i> nodes per 241 element, the first holding the elements themselves and the rest 242 storing iterators to the "base" container. In practice, an iterator 243 merely holds a raw pointer to the node it is associated to, so its size 244 is independent of the type of the elements. Summing all contributions, 245 the 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> 257 The relative amount of memory taken up by <code>multi_index_container</code> 258 with respect to its manual simulation is just 259 <i>S<sub>I</sub></i> / <i>S<sub>M</sub></i>, which can be expressed 260 then 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> 269 The formula shows that <code>multi_index_container</code> is more efficient 270 with regard to memory consumption as the number of indices grow. An implicit 271 assumption has been made that headers of <code>multi_index_container</code> 272 index nodes are the same size that their analogues in STL containers; but there 273 is 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 275 technique</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. 278 Taking 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> 287 where <i>O</i> is the number of ordered indices of the container, and <i>w</i> 288 is the system word size (typically 4 bytes on 32-bit architectures.) 289 </p> 290 291 <p> 292 These considerations have overlooked an aspect of the greatest practical 293 importance: the fact that <code>multi_index_container</code> allocates a single 294 node per element, compared to the many nodes of different sizes 295 built by manual simulations, diminishes memory fragmentation, which 296 can 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> 302 From the point of view of computational complexity (i.e. big-O 303 characterization), <code>multi_index_container</code> and its corresponding manual 304 simulations are equivalent: inserting an element into 305 a <code>multi_index_container</code> reduces to a simple combination of 306 elementary insertion operations on each of the indices, and 307 similarly for deletion. Hence, the most we can expect is a reduction 308 (or increase) of execution time by a roughly constant factor. As we 309 will 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, 314 resulting performance will roughly match that of the STL equivalent containers: 315 tests show that there is at most a negligible degradation with respect to STL, 316 and even in some cases a small improvement. 317 </p> 318 319 <h2><a name="tests">Performance tests</a></h2> 320 321 <p> 322 See <a href="../perf/test_perf.cpp">source code</a> used for measurements. 323 <p> 324 In order to assess the efficiency of <code>multi_index_container</code>, the following 325 basic 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> 335 has been measured for different instantiations of <code>multi_index_container</code> 336 at values of <i>n</i> 1,000, 10,000 and 100,000, 337 and its execution time compared with that of the equivalent algorithm 338 for the corresponding manual simulation of the data structure based on 339 STL 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> 369 The relative memory consumption (i.e. the amount of memory allocated 370 by a <code>multi_index_container</code> with respect to its manual simulation) 371 is determined by dividing the size of a <code>multi_index_container</code> node 372 by the sum of node sizes of all the containers integrating the 373 simulating data structure. 374 </p> 375 376 <h3><a name="test_1r">Results for 1 ordered index</a></h3> 377 378 <p> 379 The 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> 392 which 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 411 ordered index.</b> 412 </p> 413 414 <p> 415 The reduction in memory usage is accounted for by the optimization technique implemented 416 in 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" 423 width="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> 428 Somewhat surprisingly, <code>multi_index_container</code> performs slightly 429 better than <code>std::set</code>. A very likely explanation for this behavior 430 is that the lower memory consumption of <code>multi_index_container</code> 431 results in a higher processor cache hit rate. 432 The improvement is smallest for GCC, presumably because the worse quality of 433 this 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> 439 The 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> 452 which 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 471 sequenced index.</b> 472 </p> 473 474 <p> 475 The figures confirm that in this case <code>multi_index_container</code> nodes are the 476 same 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" 483 width="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 489 of its STL counterpart, although the figures are close. Again, the worst results 490 are those of GCC, with a degradation of up to 7%, while ICC and MSVC do not 491 exceed a mere 5%. 492 </p> 493 494 <h3><a name="test_2r">Results for 2 ordered indices</a></h3> 495 496 <p> 497 The 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 526 ordered indices.</b> 527 </p> 528 529 <p> 530 These 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" 538 width="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> 543 The experimental results confirm our hypothesis that <code>multi_index_container</code> 544 provides an improvement on execution time by an approximately constant factor, 545 which in this case lies around 60%. There is no obvious explanation for the 546 increased 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> 553 The 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 582 ordered index + 1 sequenced index.</b> 583 </p> 584 585 <p> 586 These 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" 594 alt="performance of multi_index_container with 1 ordered index + 1 sequenced index" 595 width="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> 601 For <i>n</i>=10<sup>3</sup> and <i>n</i>=10<sup>4</sup>, the results 602 are in agreement with our theoretical analysis, showing a constant factor 603 improvement of 50-65% with respect to the STL-based manual simulation. 604 Curiously enough, this speedup gets even higher when 605 <i>n</i>=10<sup>5</sup> for two of the compilers, namely GCC and ICC. 606 In order to rule out spurious results, the tests 607 have been run many times, yielding similar outcomes. Both test environments 608 are deployed on the same machine, which points to some OS-related reason for 609 this phenomenon. 610 </p> 611 612 <h3><a name="test_3r">Results for 3 ordered indices</a></h3> 613 614 <p> 615 The 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 645 ordered indices.</b> 646 </p> 647 648 <p> 649 These 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" 657 width="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> 662 Execution time for this case is between 45% and 55% lower than achieved with 663 an 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> 669 The 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 699 ordered indices + 1 sequenced index.</b> 700 </p> 701 702 <p> 703 These 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" 711 alt="performance of multi_index_container with 2 ordered indices + 1 sequenced index" 712 width="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> 718 In accordance to the expectations, execution time is improved by a fairly constant 719 factor, which ranges from 45% to 55%. 720 </p> 721 722 <h2><a name="conclusions">Conclusions</a></h2> 723 724 <p> 725 We have shown that <code>multi_index_container</code> outperforms, both in space and 726 time efficiency, equivalent data structures obtained from the manual 727 combination of STL containers. This improvement gets larger when the number 728 of indices increase. 729 </p> 730 731 <p> 732 In the special case of replacing standard containers with single-indexed 733 <code>multi_index_container</code>s, the performance of Boost.MultiIndex 734 is comparable with that of the tested STL implementations, and can even yield 735 some 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> 741 Compiler specifics 742 </a></div> 743 <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> 744 Index 745 </a></div> 746 <div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br> 747 Examples 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. 755 Distributed under the Boost Software 756 License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt"> 757 LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt"> 758 http://www.boost.org/LICENSE_1_0.txt</a>) 759 </p> 760 761 </body> 762 </html> 763
