ceph/src/boost/libs/multi_index/doc/performance.html

   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>&lt;</span>
 111   <span class=keyword>int</span><span class=special>,</span>
 112   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 113     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 114     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;,</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span> <span class=special>&gt;,</span>
 115   <span class=special>&gt;</span>
 116 <span class=special>&gt;</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>&lt;</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>&gt;</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>&amp;</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>Iterator</span><span class=special>&amp;</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>&lt;</span><span class=keyword>int</span><span class=special>&gt;</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>&lt;</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>&lt;</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>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span>
 145   <span class=special>&gt;</span>
 146 <span class=special>&gt;</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>(&amp;*</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>&lt;</span><span class=keyword>int</span><span class=special>&gt;</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>&lt;</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>&lt;</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>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span>
 187   <span class=special>&gt;</span>
 188 <span class=special>&gt;</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>&nbsp;/&nbsp;<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>&nbsp;/&nbsp;<i>S<sub>M</sub></i> =
 265 <i>S<sub>I</sub></i>&nbsp;/&nbsp;(<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>&nbsp;/&nbsp;<i>S<sub>M</sub></i> =
 283 <i>S<sub>I</sub></i>&nbsp;/&nbsp;(<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>&lt;...&gt;</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>&lt;</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>&lt;</span>
 384   <span class=keyword>int</span><span class=special>,</span>
 385   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 386     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 387   <span class=special>&gt;</span>
 388 <span class=special>&gt;</span>
 389 </pre></blockquote>
 390
 391 <p>
 392 which is functionally equivalent to <code>std::set&lt;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>&lt;</span>
 444   <span class=keyword>int</span><span class=special>,</span>
 445   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 446     <span class=identifier>sequenced</span><span class=special>&lt;&gt;</span>
 447   <span class=special>&gt;</span>
 448 <span class=special>&gt;</span>
 449 </pre></blockquote>
 450
 451 <p>
 452 which is functionally equivalent to <code>std::list&lt;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>&lt;</span>
 502   <span class=keyword>int</span><span class=special>,</span>
 503   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 504     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 505     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 506   <span class=special>&gt;</span>
 507 <span class=special>&gt;</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>&lt;</span>
 558   <span class=keyword>int</span><span class=special>,</span>
 559   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 560     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 561     <span class=identifier>sequenced</span><span class=special>&lt;&gt;</span>
 562   <span class=special>&gt;</span>
 563 <span class=special>&gt;</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>&lt;</span>
 620   <span class=keyword>int</span><span class=special>,</span>
 621   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 622     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 623     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 624     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;</span>
 625   <span class=special>&gt;</span>
 626 <span class=special>&gt;</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>&lt;</span>
 674   <span class=keyword>int</span><span class=special>,</span>
 675   <span class=identifier>indexed_by</span><span class=special>&lt;</span>
 676     <span class=identifier>ordered_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 677     <span class=identifier>ordered_non_unique</span><span class=special>&lt;</span><span class=identifier>identity</span><span class=special>&lt;</span><span class=keyword>int</span><span class=special>&gt;</span> <span class=special>&gt;,</span>
 678     <span class=identifier>sequenced</span><span class=special>&lt;&gt;</span>
 679   <span class=special>&gt;</span>
 680 <span class=special>&gt;</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 November 24th 2015</p>
 753
 754 <p>&copy; Copyright 2003-2015 Joaqu&iacute;n M L&oacute;pez Mu&ntilde;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>