projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN"> |
| 2 | ||
| 3 | <html> | |
| 4 | <head> | |
| 5 | <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> | |
| 6 | <title>Boost.MultiIndex Documentation - Performance</title> | |
| 7 | <link rel="stylesheet" href="style.css" type="text/css"> | |
| 8 | <link rel="start" href="index.html"> | |
| 9 | <link rel="prev" href="compiler_specifics.html"> | |
| 10 | <link rel="up" href="index.html"> | |
| 11 | <link rel="next" href="examples.html"> | |
| 12 | </head> | |
| 13 | ||
| 14 | <body> | |
| 15 | <h1><img src="../../../boost.png" alt="boost.png (6897 bytes)" align= | |
| 16 | "middle" width="277" height="86">Boost.MultiIndex Performance</h1> | |
| 17 | ||
| 18 | <div class="prev_link"><a href="compiler_specifics.html"><img src="prev.gif" alt="compiler specifics" border="0"><br> | |
| 19 | Compiler specifics | |
| 20 | </a></div> | |
| 21 | <div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br> | |
| 22 | Index | |
| 23 | </a></div> | |
| 24 | <div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br> | |
| 25 | Examples | |
| 26 | </a></div><br clear="all" style="clear: all;"> | |
| 27 | ||
| 28 | <hr> | |
| 29 | ||
| 30 | <h2>Contents</h2> | |
| 31 | ||
| 32 | <ul> | |
| 33 | <li><a href="#intro">Introduction</a></li> | |
| 34 | <li><a href="#simulation">Manual simulation of a <code>multi_index_container</code></a></li> | |
| 35 | <li><a href="#spatial_efficiency">Spatial efficiency</a></li> | |
| 36 | <li><a href="#time_efficiency">Time efficiency</a></li> | |
| 37 | <li><a href="#tests">Performance tests</a> | |
| 38 | <ul> | |
| 39 | <li><a href="#test_1r">Results for 1 ordered index</a> | |
| 40 | <ul> | |
| 41 | <li><a href="#memory_1r">Memory consumption</a></li> | |
| 42 | <li><a href="#time_1r">Execution time</a></li> | |
| 43 | </ul> | |
| 44 | </li> | |
| 45 | <li><a href="#test_1s">Results for 1 sequenced index</a> | |
| 46 | <ul> | |
| 47 | <li><a href="#memory_1s">Memory consumption</a></li> | |
| 48 | <li><a href="#time_1s">Execution time</a></li> | |
| 49 | </ul> | |
| 50 | </li> | |
| 51 | <li><a href="#test_2r">Results for 2 ordered indices</a> | |
| 52 | <ul> | |
| 53 | <li><a href="#memory_2r">Memory consumption</a></li> | |
| 54 | <li><a href="#time_2r">Execution time</a></li> | |
| 55 | </ul> | |
| 56 | </li> | |
| 57 | <li><a href="#test_1r1s">Results for 1 ordered index + 1 sequenced index</a> | |
| 58 | <ul> | |
| 59 | <li><a href="#memory_1r1s">Memory consumption</a></li> | |
| 60 | <li><a href="#time_1r1s">Execution time</a></li> | |
| 61 | </ul> | |
| 62 | </li> | |
| 63 | <li><a href="#test_3r">Results for 3 ordered indices</a> | |
| 64 | <ul> | |
| 65 | <li><a href="#memory_3r">Memory consumption</a></li> | |
| 66 | <li><a href="#time_3r">Execution time</a></li> | |
| 67 | </ul> | |
| 68 | </li> | |
| 69 | <li><a href="#test_2r1s">Results for 2 ordered indices + 1 sequenced index</a> | |
| 70 | <ul> | |
| 71 | <li><a href="#memory_2r1s">Memory consumption</a></li> | |
| 72 | <li><a href="#time_2r1s">Execution time</a></li> | |
| 73 | </ul> | |
| 74 | </li> | |
| 75 | </ul> | |
| 76 | </li> | |
| 77 | <li><a href="#conclusions">Conclusions</a></li> | |
| 78 | </ul> | |
| 79 | ||
| 80 | <h2><a name="intro">Introduction</a></h2> | |
| 81 | ||
| 82 | <p> | |
| 83 | Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome | |
| 84 | compositions of containers when multi-indexing capabilities are needed. Furthermore, | |
| 85 | it does so in an efficient manner, both in terms of space and time consumption. The | |
| 86 | space savings stem from the compact representation of the underlying data structures, | |
| 87 | requiring a single node per element. As for time efficiency, Boost.MultiIndex | |
| 88 | intensively uses metaprogramming techniques producing very tight implementations | |
| 89 | of member functions which take care of the elementary operations for each index: | |
| 90 | for <code>multi_index_container</code>s with two or more indices, the running time | |
| 91 | can be reduced to half as long as with manual simulations involving several | |
| 92 | STL containers. | |
| 93 | </p> | |
| 94 | ||
| 95 | <h2><a name="simulation">Manual simulation of a <code>multi_index_container</code></a></h2> | |
| 96 | ||
| 97 | <p> | |
| 98 | The section on <a href="tutorial/techniques.html#emulate_std_containers">emulation | |
| 99 | of standard containers with <code>multi_index_container</code></a> shows the equivalence | |
| 100 | between single-index <code>multi_index_container</code>s and some STL containers. Let us now | |
| 101 | concentrate on the problem of simulating a <code>multi_index_container</code> with two | |
| 102 | or more indices with a suitable combination of standard containers. | |
| 103 | </p> | |
| 104 | ||
| 105 | <p> | |
| 106 | Consider the following instantiation of <code>multi_index_container</code>: | |
| 107 | </p> | |
| 108 | ||
| 109 | <blockquote><pre> | |
| 110 | <span class=keyword>typedef</span> <span class=identifier>multi_index_container</span><span class=special><</span> | |
| 111 | <span class=keyword>int</span><span class=special>,</span> | |
| 112 | <span class=identifier>indexed_by</span><span class=special><</span> | |
| 113 | <span class=identifier>ordered_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=special>>,</span> | |
| 114 | <span class=identifier>ordered_non_unique</span><span class=special><</span><span class=identifier>identity</span><span class=special><</span><span class=keyword>int</span><span class=special>>,</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span> <span class=special>>,</span> | |
| 115 | <span class=special>></span> | |
| 116 | <span class=special>></span> <span class=identifier>indexed_t</span><span class=special>;</span> | |
| 117 | </pre></blockquote> | |
| 118 | ||
| 119 | <p> | |
| 120 | <code>indexed_t</code> maintains two internal indices on elements of type | |
| 121 | <code>int</code>. In order to simulate this data structure resorting only to | |
| 122 | standard STL containers, one can use on a first approach the following types: | |
| 123 | </p> | |
| 124 | ||
| 125 | <blockquote><pre> | |
| 126 | <span class=comment>// dereferencing compare predicate</span> | |
| 127 | <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Iterator</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> | |
| 128 | <span class=keyword>struct</span> <span class=identifier>it_compare</span> | |
| 129 | <span class=special>{</span> | |
| 130 | <span class=keyword>bool</span> <span class=keyword>operator</span><span class=special>()(</span><span class=keyword>const</span> <span class=identifier>Iterator</span><span class=special>&</span> <span class=identifier>x</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>Iterator</span><span class=special>&</span> <span class=identifier>y</span><span class=special>)</span><span class=keyword>const</span> | |
| 131 | <span class=special>{</span> | |
| 132 | <span class=keyword>return</span> <span class=identifier>comp</span><span class=special>(*</span><span class=identifier>x</span><span class=special>,*</span><span class=identifier>y</span><span class=special>);</span> | |
| 133 | <span class=special>}</span> | |
| 134 | ||
| 135 | <span class=keyword>private</span><span class=special>:</span> | |
| 136 | <span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>;</span> | |
| 137 | <span class=special>};</span> | |
| 138 | ||
| 139 | <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>set</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=identifier>manual_t1</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #0</span> | |
| 140 | <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span> | |
| 141 | <span class=keyword>const</span> <span class=keyword>int</span><span class=special>*,</span> | |
| 142 | <span class=identifier>it_compare</span><span class=special><</span> | |
| 143 | <span class=keyword>const</span> <span class=keyword>int</span><span class=special>*,</span> | |
| 144 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> | |
| 145 | <span class=special>></span> | |
| 146 | <span class=special>></span> <span class=identifier>manual_t2</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #1</span> | |
| 147 | </pre></blockquote> | |
| 148 | ||
| 149 | <p> | |
| 150 | where <code>manual_t1</code> is the "base" container that holds | |
| 151 | the actual elements, and <code>manual_t2</code> stores pointers to | |
| 152 | elements of <code>manual_t1</code>. This scheme turns out to be quite | |
| 153 | inefficient, though: while insertion into the data structure is simple enough: | |
| 154 | </p> | |
| 155 | ||
| 156 | <blockquote><pre> | |
| 157 | <span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span> | |
| 158 | <span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span> | |
| 159 | ||
| 160 | <span class=comment>// insert the element 5</span> | |
| 161 | <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>c1</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>5</span><span class=special>).</span><span class=identifier>first</span><span class=special>;</span> | |
| 162 | <span class=identifier>c2</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(&*</span><span class=identifier>it1</span><span class=special>);</span> | |
| 163 | </pre></blockquote> | |
| 164 | ||
| 165 | deletion, on the other hand, necessitates a logarithmic search, whereas | |
| 166 | <code>indexed_t</code> deletes in constant time: | |
| 167 | ||
| 168 | <blockquote><pre> | |
| 169 | <span class=comment>// remove the element pointed to by it2</span> | |
| 170 | <span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span> | |
| 171 | <span class=identifier>c1</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(**</span><span class=identifier>it2</span><span class=special>);</span> <span class=comment>// watch out! performs in logarithmic time</span> | |
| 172 | <span class=identifier>c2</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>it2</span><span class=special>);</span> | |
| 173 | </pre></blockquote> | |
| 174 | ||
| 175 | <p> | |
| 176 | The right approach consists of feeding the second container not with | |
| 177 | raw pointers, but with elements of type <code>manual_t1::iterator</code>: | |
| 178 | </p> | |
| 179 | ||
| 180 | <blockquote><pre> | |
| 181 | <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>set</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> <span class=identifier>manual_t1</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #0</span> | |
| 182 | <span class=keyword>typedef</span> <span class=identifier>std</span><span class=special>::</span><span class=identifier>multiset</span><span class=special><</span> | |
| 183 | <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span> | |
| 184 | <span class=identifier>it_compare</span><span class=special><</span> | |
| 185 | <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span><span class=special>,</span> | |
| 186 | <span class=identifier>std</span><span class=special>::</span><span class=identifier>greater</span><span class=special><</span><span class=keyword>int</span><span class=special>></span> | |
| 187 | <span class=special>></span> | |
| 188 | <span class=special>></span> <span class=identifier>manual_t2</span><span class=special>;</span> <span class=comment>// equivalent to indexed_t's index #1</span> | |
| 189 | </pre></blockquote> | |
| 190 | ||
| 191 | <p> | |
| 192 | Now, insertion and deletion can be performed with complexity bounds | |
| 193 | equivalent to those of <code>indexed_t</code>: | |
| 194 | </p> | |
| 195 | ||
| 196 | <blockquote><pre> | |
| 197 | <span class=identifier>manual_t1</span> <span class=identifier>c1</span><span class=special>;</span> | |
| 198 | <span class=identifier>manual_t2</span> <span class=identifier>c2</span><span class=special>;</span> | |
| 199 | ||
| 200 | <span class=comment>// insert the element 5</span> | |
| 201 | <span class=identifier>manual_t1</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it1</span><span class=special>=</span><span class=identifier>c1</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=number>5</span><span class=special>).</span><span class=identifier>first</span><span class=special>;</span> | |
| 202 | <span class=identifier>c2</span><span class=special>.</span><span class=identifier>insert</span><span class=special>(</span><span class=identifier>it1</span><span class=special>);</span> | |
| 203 | ||
| 204 | <span class=comment>// remove the element pointed to by it2</span> | |
| 205 | <span class=identifier>manual_t2</span><span class=special>::</span><span class=identifier>iterator</span> <span class=identifier>it2</span><span class=special>=...;</span> | |
| 206 | <span class=identifier>c1</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(*</span><span class=identifier>it2</span><span class=special>);</span> <span class=comment>// OK: constant time</span> | |
| 207 | <span class=identifier>c2</span><span class=special>.</span><span class=identifier>erase</span><span class=special>(</span><span class=identifier>it2</span><span class=special>);</span> | |
| 208 | </pre></blockquote> | |
| 209 | ||
| 210 | <p> | |
| 211 | The construction can be extended in a straightforward manner to | |
| 212 | handle more than two indices. In what follows, we will compare | |
| 213 | instantiations of <code>multi_index_container</code> against this sort of | |
| 214 | manual simulations. | |
| 215 | </p> | |
| 216 | ||
| 217 | <h2><a name="spatial_efficiency">Spatial efficiency</a></h2> | |
| 218 | ||
| 219 | <p> | |
| 220 | The gain in space consumption of <code>multi_index_container</code> with | |
| 221 | respect to its manual simulations is amenable to a very simple | |
| 222 | theoretical analysis. For simplicity, we will ignore alignment | |
| 223 | issues (which in general play in favor of <code>multi_index_container</code>.) | |
| 224 | </p> | |
| 225 | ||
| 226 | <p> | |
| 227 | Nodes of a <code>multi_index_container</code> with <i>N</i> indices hold the value | |
| 228 | of the element plus <i>N</i> headers containing linking information for | |
| 229 | each index. Thus the node size is | |
| 230 | </p> | |
| 231 | ||
| 232 | <blockquote> | |
| 233 |