123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
- <title>Boost.MultiIndex Documentation - Performance</title>
- <link rel="stylesheet" href="style.css" type="text/css">
- <link rel="start" href="index.html">
- <link rel="prev" href="compiler_specifics.html">
- <link rel="up" href="index.html">
- <link rel="next" href="examples.html">
- </head>
- <body>
- <h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align=
- "middle" width="277" height="86">Boost.MultiIndex Performance</h1>
- <div class="prev_link"><a href="compiler_specifics.html"><img src="prev.gif" alt="compiler specifics" border="0"><br>
- Compiler specifics
- </a></div>
- <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
- Index
- </a></div>
- <div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br>
- Examples
- </a></div><br clear="all" style="clear: all;">
- <hr>
- <h2>Contents</h2>
- <ul>
- <li><a href="#intro">Introduction</a></li>
- <li><a href="#simulation">Manual simulation of a <code>multi_index_container</code></a></li>
- <li><a href="#spatial_efficiency">Spatial efficiency</a></li>
- <li><a href="#time_efficiency">Time efficiency</a></li>
- <li><a href="#tests">Performance tests</a>
- <ul>
- <li><a href="#test_1r">Results for 1 ordered index</a>
- <ul>
- <li><a href="#memory_1r">Memory consumption</a></li>
- <li><a href="#time_1r">Execution time</a></li>
- </ul>
- </li>
- <li><a href="#test_1s">Results for 1 sequenced index</a>
- <ul>
- <li><a href="#memory_1s">Memory consumption</a></li>
- <li><a href="#time_1s">Execution time</a></li>
- </ul>
- </li>
- <li><a href="#test_2r">Results for 2 ordered indices</a>
- <ul>
- <li><a href="#memory_2r">Memory consumption</a></li>
- <li><a href="#time_2r">Execution time</a></li>
- </ul>
- </li>
- <li><a href="#test_1r1s">Results for 1 ordered index + 1 sequenced index</a>
- <ul>
- <li><a href="#memory_1r1s">Memory consumption</a></li>
- <li><a href="#time_1r1s">Execution time</a></li>
- </ul>
- </li>
- <li><a href="#test_3r">Results for 3 ordered indices</a>
- <ul>
- <li><a href="#memory_3r">Memory consumption</a></li>
- <li><a href="#time_3r">Execution time</a></li>
- </ul>
- </li>
- <li><a href="#test_2r1s">Results for 2 ordered indices + 1 sequenced index</a>
- <ul>
- <li><a href="#memory_2r1s">Memory consumption</a></li>
- <li><a href="#time_2r1s">Execution time</a></li>
- </ul>
- </li>
- </ul>
- </li>
- <li><a href="#conclusions">Conclusions</a></li>
- </ul>
- <h2><a name="intro">Introduction</a></h2>
- <p>
- Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome
- compositions of containers when multi-indexing capabilities are needed. Furthermore,
- it does so in an efficient manner, both in terms of space and time consumption. The
- space savings stem from the compact representation of the underlying data structures,
- requiring a single node per element. As for time efficiency, Boost.MultiIndex
- intensively uses metaprogramming techniques producing very tight implementations
- of member functions which take care of the elementary operations for each index:
- for <code>multi_index_container</code>s with two or more indices, the running time
- can be reduced to half as long as with manual simulations involving several
- STL containers.
- </p>
- <h2><a name="simulation">Manual simulation of a <code>multi_index_container</code></a></h2>
- <p>
- The section on <a href="tutorial/techniques.html#emulate_std_containers">emulation
- of standard containers with <code>multi_index_container</code></a> shows the equivalence
- between single-index <code>multi_index_container</code>s and some STL containers. Let us now
- concentrate on the problem of simulating a <code>multi_index_container</code> with two
- or more indices with a suitable combination of standard containers.
- </p>
- <p>
- Consider the following instantiation of <code>multi_index_container</code>:
- </p>
- <blockquote><pre>
- <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <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=special>></span>
- <span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span>
- </pre></blockquote>
- <p>
- <code>indexed_t</code> maintains two internal indices on elements of type
- <code>int</code>. In order to simulate this data structure resorting only to
- standard STL containers, one can use on a first approach the following types:
- </p>
- <blockquote><pre>
- <span class=comment>// dereferencing compare predicate</span>
- <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>
- <span class=keyword>struct</span> <span class=identifier>it_compare</span>
- <span class=special>{</span>
- <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>
- <span class=special>{</span>
- <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>
- <span class=special>}</span>
- <span class=keyword>private</span><span class=special>:</span>
- <span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>;</span>
- <span class=special>};</span>
- <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>
- <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span>
- <span class=keyword>const</span> <span class=keyword>int</span><span class=special>*,</span>
- <span class=identifier>it_compare</span><span class=special><</span>
- <span class=keyword>const</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>
- <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>
- </pre></blockquote>
- <p>
- where <code>manual_t1</code> is the "base" container that holds
- the actual elements, and <code>manual_t2</code> stores pointers to
- elements of <code>manual_t1</code>. This scheme turns out to be quite
- inefficient, though: while insertion into the data structure is simple enough:
- </p>
- <blockquote><pre>
- <span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span>
- <span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span>
- <span class=comment>// insert the element 5</span>
- <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>
- <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>
- </pre></blockquote>
- deletion, on the other hand, necessitates a logarithmic search, whereas
- <code>indexed_t</code> deletes in constant time:
- <blockquote><pre>
- <span class=comment>// remove the element pointed to by it2</span>
- <span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span>
- <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>
- <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>
- </pre></blockquote>
- <p>
- The right approach consists of feeding the second container not with
- raw pointers, but with elements of type <code>manual_t1::iterator</code>:
- </p>
- <blockquote><pre>
- <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>
- <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span>
- <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span>
- <span class=identifier>it_compare</span><span class=special><</span>
- <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</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>
- <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>
- </pre></blockquote>
- <p>
- Now, insertion and deletion can be performed with complexity bounds
- equivalent to those of <code>indexed_t</code>:
- </p>
- <blockquote><pre>
- <span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span>
- <span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span>
- <span class=comment>// insert the element 5</span>
- <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>
- <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>
- <span class=comment>// remove the element pointed to by it2</span>
- <span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span>
- <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>
- <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>
- </pre></blockquote>
- <p>
- The construction can be extended in a straightforward manner to
- handle more than two indices. In what follows, we will compare
- instantiations of <code>multi_index_container</code> against this sort of
- manual simulations.
- </p>
- <h2><a name="spatial_efficiency">Spatial efficiency</a></h2>
- <p>
- The gain in space consumption of <code>multi_index_container</code> with
- respect to its manual simulations is amenable to a very simple
- theoretical analysis. For simplicity, we will ignore alignment
- issues (which in general play in favor of <code>multi_index_container</code>.)
- </p>
- <p>
- Nodes of a <code>multi_index_container</code> with <i>N</i> indices hold the value
- of the element plus <i>N</i> headers containing linking information for
- each index. Thus the node size is
- </p>
- <blockquote>
- <i>S<sub>I</sub></i> = <i>e</i> + <i>h</i><sub>0</sub> + ··· +
- <i>h</i><sub><i>N</i>-1</sub>, where<br>
- <i>e</i> = size of the element,<br>
- <i>h</i><sub><i>i</i></sub> = size of the <i>i</i>-th header.
- </blockquote>
- <p>
- On the other hand, the manual simulation allocates <i>N</i> nodes per
- element, the first holding the elements themselves and the rest
- storing iterators to the "base" container. In practice, an iterator
- merely holds a raw pointer to the node it is associated to, so its size
- is independent of the type of the elements. Summing all contributions,
- the space allocated per element in a manual simulation is
- </p>
- <blockquote>
- <i>S<sub>M</sub></i> = (<i>e</i> + <i>h</i><sub>0</sub>) +
- (<i>p</i> + <i>h</i><sub>1</sub>) + ··· +
- (<i>p</i> + <i>h</i><sub><i>N</i>-1</sub>) =
- <i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i>, where<br>
- <i>p</i> = size of a pointer.<br>
- </blockquote>
- <p>
- The relative amount of memory taken up by <code>multi_index_container</code>
- with respect to its manual simulation is just
- <i>S<sub>I</sub></i> / <i>S<sub>M</sub></i>, which can be expressed
- then as:
- </p>
- <blockquote>
- <i>S<sub>I</sub></i> / <i>S<sub>M</sub></i> =
- <i>S<sub>I</sub></i> / (<i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i>).
- </blockquote>
- <p>
- The formula shows that <code>multi_index_container</code> is more efficient
- with regard to memory consumption as the number of indices grow. An implicit
- assumption has been made that headers of <code>multi_index_container</code>
- index nodes are the same size that their analogues in STL containers; but there
- is a particular case in which this is often not the case: ordered indices use a
- <a href="tutorial/indices.html#ordered_node_compression">spatial optimization
- technique</a> which is not present in many implementations of
- <code>std::set</code>, giving an additional advantage to
- <code>multi_index_container</code>s of one system word per ordered index.
- Taking this fact into account, the former formula can be adjusted to:
- </p>
- <blockquote>
- <i>S<sub>I</sub></i> / <i>S<sub>M</sub></i> =
- <i>S<sub>I</sub></i> / (<i>S<sub>I</sub></i> + (<i>N</i>-1)<i>p</i> + <i>Ow</i>),
- </blockquote>
- <p>
- where <i>O</i> is the number of ordered indices of the container, and <i>w</i>
- is the system word size (typically 4 bytes on 32-bit architectures.)
- </p>
- <p>
- These considerations have overlooked an aspect of the greatest practical
- importance: the fact that <code>multi_index_container</code> allocates a single
- node per element, compared to the many nodes of different sizes
- built by manual simulations, diminishes memory fragmentation, which
- can show up in more usable memory available and better performance.
- </p>
- <h2><a name="time_efficiency">Time efficiency</a></h2>
- <p>
- From the point of view of computational complexity (i.e. big-O
- characterization), <code>multi_index_container</code> and its corresponding manual
- simulations are equivalent: inserting an element into
- a <code>multi_index_container</code> reduces to a simple combination of
- elementary insertion operations on each of the indices, and
- similarly for deletion. Hence, the most we can expect is a reduction
- (or increase) of execution time by a roughly constant factor. As we
- will see later, the reduction can be very significative for
- <code>multi_index_container</code>s with two or more indices.
- </p>
- <p>In the special case of <code>multi_index_container</code>s with only one index,
- resulting performance will roughly match that of the STL equivalent containers:
- tests show that there is at most a negligible degradation with respect to STL,
- and even in some cases a small improvement.
- </p>
- <h2><a name="tests">Performance tests</a></h2>
- <p>
- See <a href="../perf/test_perf.cpp">source code</a> used for measurements.
- <p>
- In order to assess the efficiency of <code>multi_index_container</code>, the following
- basic algorithm
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><...></span> <span class=identifier>c</span><span class=special>;</span>
- <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>
- <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>
- </pre></blockquote>
- <p>
- has been measured for different instantiations of <code>multi_index_container</code>
- at values of <i>n</i> 1,000, 10,000 and 100,000,
- and its execution time compared with that of the equivalent algorithm
- for the corresponding manual simulation of the data structure based on
- STL containers. The table below describes the test environments used.
- </p>
- <p align="center">
- <table cellspacing="0" cellpadding="5">
- <caption><b>Tests environments.</b></caption>
- <tr>
- <th>Compiler</th>
- <th>Settings</th>
- <th>OS and CPU</th>
- </tr>
- <tr>
- <td>GCC 3.4.5 (mingw special)</td>
- <td><code>-O3</code></td>
- <td>Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM</td>
- </tr>
- <tr class="odd_tr">
- <td>Intel C++ 7.1</td>
- <td>default release settings</td>
- <td>Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM</td>
- </tr>
- <tr>
- <td>Microsoft Visual C++ 8.0</td>
- <td>default release settings, <code>_SECURE_SCL=0</code></td>
- <td>Windows XP on P4 Xeon 3.2 GHz, 1 GB RAM</td>
- </tr>
- </table>
- </p>
- <p>
- The relative memory consumption (i.e. the amount of memory allocated
- by a <code>multi_index_container</code> with respect to its manual simulation)
- is determined by dividing the size of a <code>multi_index_container</code> node
- by the sum of node sizes of all the containers integrating the
- simulating data structure.
- </p>
- <h3><a name="test_1r">Results for 1 ordered index</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <p>
- which is functionally equivalent to <code>std::set<int></code>.
- </p>
- <h4><a name="memory_1r">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">80%</td>
- <td align="center">80%</td>
- <td align="center">80%</td>
- </tr>
- </table>
- <b>Table 1: Relative memory consumption of <code>multi_index_container</code> with 1
- ordered index.</b>
- </p>
- <p>
- The reduction in memory usage is accounted for by the optimization technique implemented
- in Boost.MultiIndex ordered indices, as <a href="#spatial_efficiency">explained above</a>.
- </p>
- <h4><a name="time_1r">Execution time</a></h4>
- <p align="center">
- <img src="perf_1o.png" alt="performance of multi_index_container with 1 ordered index"
- width="556" height="372"><br>
- <b>Fig. 1: Performance of <code>multi_index_container</code> with 1 ordered index.</b>
- </p>
- <p>
- Somewhat surprisingly, <code>multi_index_container</code> performs slightly
- better than <code>std::set</code>. A very likely explanation for this behavior
- is that the lower memory consumption of <code>multi_index_container</code>
- results in a higher processor cache hit rate.
- The improvement is smallest for GCC, presumably because the worse quality of
- this compiler's optimizer masks the cache-related benefits.
- </p>
- <h3><a name="test_1s">Results for 1 sequenced index</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <span class=identifier>sequenced</span><span class=special><></span>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <p>
- which is functionally equivalent to <code>std::list<int></code>.
- </p>
- <h4><a name="memory_1s">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">100%</td>
- <td align="center">100%</td>
- <td align="center">100%</td>
- </tr>
- </table>
- <b>Table 2: Relative memory consumption of <code>multi_index_container</code> with 1
- sequenced index.</b>
- </p>
- <p>
- The figures confirm that in this case <code>multi_index_container</code> nodes are the
- same size than those of its <code>std::list</code> counterpart.
- </p>
- <h4><a name="time_1s">Execution time</a></h4>
- <p align="center">
- <img src="perf_1s.png" alt="performance of multi_index_container with 1 sequenced index"
- width="556" height="372"><br>
- <b>Fig. 2: Performance of <code>multi_index_container</code> with 1 sequenced index.</b>
- </p>
- <p>
- <code>multi_index_container</code> does not attain the performance
- of its STL counterpart, although the figures are close. Again, the worst results
- are those of GCC, with a degradation of up to 7%, while ICC and MSVC do not
- exceed a mere 5%.
- </p>
- <h3><a name="test_2r">Results for 2 ordered indices</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <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>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <h4><a name="memory_2r">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">70%</td>
- <td align="center">70%</td>
- <td align="center">70%</td>
- </tr>
- </table>
- <b>Table 3: Relative memory consumption of <code>multi_index_container</code> with 2
- ordered indices.</b>
- </p>
- <p>
- These results coincide with the theoretical formula for
- <i>S<sub>I</sub></i> = 28, <i>N</i> = <i>O</i> = 2 and <i>p</i> = <i>w</i> = 4.
- </p>
- <h4><a name="time_2r">Execution time</a></h4>
- <p align="center">
- <img src="perf_2o.png" alt="performance of multi_index_container with 2 ordered indices"
- width="556" height="372"><br>
- <b>Fig. 3: Performance of <code>multi_index_container</code> with 2 ordered indices.</b>
- </p>
- <p>
- The experimental results confirm our hypothesis that <code>multi_index_container</code>
- provides an improvement on execution time by an approximately constant factor,
- which in this case lies around 60%. There is no obvious explanation for the
- increased advantage of <code>multi_index_container</code> in MSVC for
- <i>n</i>=10<sup>5</sup>.
- </p>
- <h3><a name="test_1r1s">Results for 1 ordered index + 1 sequenced index</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <span class=identifier>sequenced</span><span class=special><></span>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <h4><a name="memory_1r1s">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">75%</td>
- <td align="center">75%</td>
- <td align="center">75%</td>
- </tr>
- </table>
- <b>Table 4: Relative memory consumption of <code>multi_index_container</code> with 1
- ordered index + 1 sequenced index.</b>
- </p>
- <p>
- These results coincide with the theoretical formula for
- <i>S<sub>I</sub></i> = 24, <i>N</i> = 2, <i>O</i> = 1 and <i>p</i> = <i>w</i> = 4.
- </p>
- <h4><a name="time_1r1s">Execution time</a></h4>
- <p align="center">
- <img src="perf_1o1s.png"
- alt="performance of multi_index_container with 1 ordered index + 1 sequenced index"
- width="556" height="372"><br>
- <b>Fig. 4: Performance of <code>multi_index_container</code> with 1 ordered index
- + 1 sequenced index.</b>
- </p>
- <p>
- For <i>n</i>=10<sup>3</sup> and <i>n</i>=10<sup>4</sup>, the results
- are in agreement with our theoretical analysis, showing a constant factor
- improvement of 50-65% with respect to the STL-based manual simulation.
- Curiously enough, this speedup gets even higher when
- <i>n</i>=10<sup>5</sup> for two of the compilers, namely GCC and ICC.
- In order to rule out spurious results, the tests
- have been run many times, yielding similar outcomes. Both test environments
- are deployed on the same machine, which points to some OS-related reason for
- this phenomenon.
- </p>
- <h3><a name="test_3r">Results for 3 ordered indices</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <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>
- <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>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <h4><a name="memory_3r">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">66.7%</td>
- <td align="center">66.7%</td>
- <td align="center">66.7%</td>
- </tr>
- </table>
- <b>Table 5: Relative memory consumption of <code>multi_index_container</code> with 3
- ordered indices.</b>
- </p>
- <p>
- These results coincide with the theoretical formula for
- <i>S<sub>I</sub></i> = 40, <i>N</i> = <i>O</i> = 3 and <i>p</i> = <i>w</i> = 4.
- </p>
- <h4><a name="time_3r">Execution time</a></h4>
- <p align="center">
- <img src="perf_3o.png" alt="performance of multi_index_container with 3 ordered indices"
- width="556" height="372"><br>
- <b>Fig. 5: Performance of <code>multi_index_container</code> with 3 ordered indices.</b>
- </p>
- <p>
- Execution time for this case is between 45% and 55% lower than achieved with
- an STL-based manual simulation of the same data structure.
- </p>
- <h3><a name="test_2r1s">Results for 2 ordered indices + 1 sequenced index</a></h3>
- <p>
- The following instantiation of <code>multi_index_container</code> was tested:
- </p>
- <blockquote><pre>
- <span class=identifier>multi_index_container</span><span class=special><</span>
- <span class=keyword>int</span><span class=special>,</span>
- <span class=identifier>indexed_by</span><span class=special><</span>
- <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>
- <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>
- <span class=identifier>sequenced</span><span class=special><></span>
- <span class=special>></span>
- <span class=special>></span>
- </pre></blockquote>
- <h4><a name="memory_2r1s">Memory consumption</a></h4>
- <p align="center">
- <table cellspacing="0">
- <tr>
- <th width="33%">GCC 3.4.5</th>
- <th width="33%">ICC 7.1</th>
- <th width="33%">MSVC 8.0</th>
- </tr>
- <tr>
- <td align="center">69.2%</td>
- <td align="center">69.2%</td>
- <td align="center">69.2%</td>
- </tr>
- </table>
- <b>Table 6: Relative memory consumption of <code>multi_index_container</code> with 2
- ordered indices + 1 sequenced index.</b>
- </p>
- <p>
- These results coincide with the theoretical formula for
- <i>S<sub>I</sub></i> = 36, <i>N</i> = 3, <i>O</i> = 2 and <i>p</i> = <i>w</i> = 4.
- </p>
- <h4><a name="time_2r1s">Execution time</a></h4>
- <p align="center">
- <img src="perf_2o1s.png"
- alt="performance of multi_index_container with 2 ordered indices + 1 sequenced index"
- width="556" height="372"><br>
- <b>Fig. 6: Performance of <code>multi_index_container</code> with 2 ordered indices
- + 1 sequenced index.</b>
- </p>
- <p>
- In accordance to the expectations, execution time is improved by a fairly constant
- factor, which ranges from 45% to 55%.
- </p>
- <h2><a name="conclusions">Conclusions</a></h2>
- <p>
- We have shown that <code>multi_index_container</code> outperforms, both in space and
- time efficiency, equivalent data structures obtained from the manual
- combination of STL containers. This improvement gets larger when the number
- of indices increase.
- </p>
- <p>
- In the special case of replacing standard containers with single-indexed
- <code>multi_index_container</code>s, the performance of Boost.MultiIndex
- is comparable with that of the tested STL implementations, and can even yield
- some improvements both in space consumption and execution time.
- </p>
- <hr>
- <div class="prev_link"><a href="compiler_specifics.html"><img src="prev.gif" alt="compiler specifics" border="0"><br>
- Compiler specifics
- </a></div>
- <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
- Index
- </a></div>
- <div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br>
- Examples
- </a></div><br clear="all" style="clear: all;">
- <br>
- <p>Revised November 24th 2015</p>
- <p>© Copyright 2003-2015 Joaquín M López Muñoz.
- Distributed under the Boost Software
- License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
- LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
- http://www.boost.org/LICENSE_1_0.txt</a>)
- </p>
- </body>
- </html>
|