Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/multi_index/doc/performance.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

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