Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/multi_index/doc/performance.html @ 13

Last change on this file since 13 was 12, checked in by landauf, 18 years ago

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