[29] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
---|
| 2 | |
---|
| 3 | <html> |
---|
| 4 | |
---|
| 5 | <head> |
---|
| 6 | <title>Smart Pointer Timings</title> |
---|
| 7 | <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
---|
| 8 | </head> |
---|
| 9 | |
---|
| 10 | <body bgcolor="#FFFFFF"> |
---|
| 11 | |
---|
| 12 | <h1><img src="../../boost.png" alt="boost.png (6897 bytes)" align="middle" WIDTH="277" HEIGHT="86">Smart Pointer Timings</h1> |
---|
| 13 | |
---|
| 14 | <p>In late January 2000, Mark Borgerding put forward a suggestion to boost for |
---|
| 15 | a new design of smart pointer whereby an intrusive doubly linked list is used |
---|
| 16 | to join together all instances of smart pointers sharing a given raw pointer. |
---|
| 17 | This allowed avoidance of the costly heap allocation of a reference count that |
---|
| 18 | occurred in the initial construction of the then current version of boost::shared_ptr. |
---|
| 19 | Of course, nothing is for free and the benefit here was gained at the expense |
---|
| 20 | of increased size and more costly copy operations. A debate ensued on the boost |
---|
| 21 | mailing list and the tests which this page describes were performed to provide |
---|
| 22 | a guide for current and future investigations into smart pointer implementation |
---|
| 23 | strategies.</p> |
---|
| 24 | <p>Thanks are due to <a href="../../people/dave_abrahams.htm">Dave Abrahams</a>, |
---|
| 25 | Gavin Collings, |
---|
| 26 | <a href="../../people/greg_colvin.htm">Greg Colvin</a> and |
---|
| 27 | <a href="../../people/beman_dawes.html">Beman Dawes</a> |
---|
| 28 | for test code and trial implementations, the final version of which can be found |
---|
| 29 | in .zip format <a href="smarttest.zip">here</a>.</p> |
---|
| 30 | <h2>Description</h2> |
---|
| 31 | <p>Two tests were run: the first aimed to obtain timings for two basic individual |
---|
| 32 | operations:</p> |
---|
| 33 | <ol type="i"> |
---|
| 34 | <li> Initial construction from raw pointer.</li> |
---|
| 35 | <li> An amortized copy operation consisting of half an assignment and half a |
---|
| 36 | copy construction - designed to reflect average usage.</li> |
---|
| 37 | </ol> |
---|
| 38 | <p>The second attempted to gain more insight into normal usage by timing the fill |
---|
| 39 | and sort algorithms for vectors and lists filled with the various smart pointers.</p> |
---|
| 40 | <p>Five smart pointer implementation strategies were tested:</p> |
---|
| 41 | <ol type="i"> |
---|
| 42 | <li>Counted pointer using a heap allocated reference count, this is referred |
---|
| 43 | to as <b>simple counted</b>.</li> |
---|
| 44 | <li>Counted pointer using a special purpose allocator for the reference count |
---|
| 45 | - <b>special counted</b>.</li> |
---|
| 46 | <li>Counted pointer using an intrusive reference count - <b>intrusive</b>.</li> |
---|
| 47 | <li>Linked pointer as described above - <b>linked</b>.</li> |
---|
| 48 | <li>Cyclic pointer, a counted implementation using a std::deque for allocation |
---|
| 49 | with provision for weak pointers and garbage collection of cycles of pointers |
---|
| 50 | - <b>cyclic</b>.</li> |
---|
| 51 | </ol> |
---|
| 52 | <p>on two compilers:</p> |
---|
| 53 | <ol type="i"> |
---|
| 54 | <li>MSVC 6.0 service pack 3, using default release optimization mode (/O2 - |
---|
| 55 | optimized for speed, no inlining of functions defined outside a class body |
---|
| 56 | unless specified as inline).</li> |
---|
| 57 | <li>gcc 2.95.2 using full optimization (-O3 -DNDEBUG).</li> |
---|
| 58 | </ol> |
---|
| 59 | <p>Additionally, generated pointer sizes (taking into account struct alignment) |
---|
| 60 | were compared, as were generated code sizes for MSVC mainly by manual inspection |
---|
| 61 | of generated assembly code - a necessity due to function inlining.</p> |
---|
| 62 | <p>All tests were run on a PII-200 running Windows NT version 4.0</p> |
---|
| 63 | <h2> </h2> |
---|
| 64 | <h2>Operation Timing Test Results</h2> |
---|
| 65 | <p>The following graphs show the overall time in nanoseconds to acquire a pointer |
---|
| 66 | (default construction) perform n amortized copy operations on it and finally |
---|
| 67 | release it. The initial allocation time for the contained pointer is not included, |
---|
| 68 | although the time for it's deallocation is. The contained pointer pointed to |
---|
| 69 | a trivial class, but for the inclusion of an intrusive reference count for the |
---|
| 70 | benefit of the intrusive counted shared pointer. A dumb pointer (i.e. a smart |
---|
| 71 | pointer that simply acquires and releases its contained pointer with no extra |
---|
| 72 | overhead) and a raw pointer were also included for comparison.</p> |
---|
| 73 | <table border="0" align="center"> |
---|
| 74 | <tr> |
---|
| 75 | <td width="20" height="20"> </td> |
---|
| 76 | <td> </td> |
---|
| 77 | <td width="20"> </td> |
---|
| 78 | </tr> |
---|
| 79 | <tr> |
---|
| 80 | <td width="20"> </td> |
---|
| 81 | <td><img src="msvcspeed.gif" width="560" height="355" alt="MSVC speed graph"></td> |
---|
| 82 | <td width="20"> </td> |
---|
| 83 | </tr> |
---|
| 84 | <tr> |
---|
| 85 | <td height="20"> </td> |
---|
| 86 | <td> </td> |
---|
| 87 | <td> </td> |
---|
| 88 | </tr> |
---|
| 89 | <tr> |
---|
| 90 | <td> </td> |
---|
| 91 | <td><img src="gccspeed.gif" width="560" height="355" alt="GCC speed graph"></td> |
---|
| 92 | <td> </td> |
---|
| 93 | </tr> |
---|
| 94 | <tr> |
---|
| 95 | <td height="20"> </td> |
---|
| 96 | <td> </td> |
---|
| 97 | <td> </td> |
---|
| 98 | </tr> |
---|
| 99 | </table> |
---|
| 100 | <p> </p> |
---|
| 101 | <p>Fitting straight lines to the above plots gives the following figures for initialization |
---|
| 102 | and amortized copy operation for the two compilers (times in nanoseconds, errors |
---|
| 103 | at two standard deviations) : -</p> |
---|
| 104 | <p> </p> |
---|
| 105 | <h4 align="center">MSVC</h4> |
---|
| 106 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="400"> |
---|
| 107 | <tr> |
---|
| 108 | <th width="120"> |
---|
| 109 | <div align="right"></div> |
---|
| 110 | </th> |
---|
| 111 | <th class="codetabletop" width="120"> |
---|
| 112 | <div align="center">initialization</div> |
---|
| 113 | </th> |
---|
| 114 | <th class="codetabletop" width="120">copy operation</th> |
---|
| 115 | </tr> |
---|
| 116 | <tr> |
---|
| 117 | <th class="codetableleft"> |
---|
| 118 | <div align="right">simple counted</div> |
---|
| 119 | </th> |
---|
| 120 | <td class="codetablecell" align="center">3000 +/- 170</td> |
---|
| 121 | <td class="codetablecell" align="center">104 +/- 31</td> |
---|
| 122 | </tr> |
---|
| 123 | <tr> |
---|
| 124 | <th class="codetableleft"> |
---|
| 125 | <div align="right">special counted</div> |
---|
| 126 | </th> |
---|
| 127 | <td class="codetablecell" align="center">1330 +/- 50</td> |
---|
| 128 | <td class="codetablecell" align="center">85 +/- 9</td> |
---|
| 129 | </tr> |
---|
| 130 | <tr> |
---|
| 131 | <th class="codetableleft"> |
---|
| 132 | <div align="right">intrusive</div> |
---|
| 133 | </th> |
---|
| 134 | <td class="codetablecell" align="center">1000 +/- 20</td> |
---|
| 135 | <td class="codetablecell" align="center">71 +/- 3</td> |
---|
| 136 | </tr> |
---|
| 137 | <tr> |
---|
| 138 | <th class="codetableleft" align="right">linked</th> |
---|
| 139 | <td class="codetablecell" align="center">970 +/- 60</td> |
---|
| 140 | <td class="codetablecell" align="center">136 +/- 10</td> |
---|
| 141 | </tr> |
---|
| 142 | <tr> |
---|
| 143 | <th class="codetableleft" align="right">cyclic</th> |
---|
| 144 | <td class="codetablecell" align="center">1290 +/- 70</td> |
---|
| 145 | <td class="codetablecell" align="center">112 +/- 12</td> |
---|
| 146 | </tr> |
---|
| 147 | <tr> |
---|
| 148 | <th class="codetableleft" align="right">dumb</th> |
---|
| 149 | <td class="codetablecell" align="center">1020 +/- 20</td> |
---|
| 150 | <td class="codetablecell" align="center">10 +/- 4</td> |
---|
| 151 | </tr> |
---|
| 152 | <tr> |
---|
| 153 | <th class="codetableleft"> |
---|
| 154 | <div align="right">raw</div> |
---|
| 155 | </th> |
---|
| 156 | <td class="codetablecell" align="center">1038 +/- 30</td> |
---|
| 157 | <td class="codetablecell" align="center">10 +/- 5</td> |
---|
| 158 | </tr> |
---|
| 159 | </table> |
---|
| 160 | <h4 align="center"> </h4> |
---|
| 161 | <h4 align="center">GCC</h4> |
---|
| 162 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="400"> |
---|
| 163 | <tr> |
---|
| 164 | <th width="120"> |
---|
| 165 | <div align="right"></div> |
---|
| 166 | </th> |
---|
| 167 | <th class="codetabletop" width="120"> |
---|
| 168 | <div align="center">initialization</div> |
---|
| 169 | </th> |
---|
| 170 | <th class="codetabletop" width="120">copy operation</th> |
---|
| 171 | </tr> |
---|
| 172 | <tr> |
---|
| 173 | <th class="codetableleft"> |
---|
| 174 | <div align="right">simple counted</div> |
---|
| 175 | </th> |
---|
| 176 | <td class="codetablecell" align="center">4620 +/- 150</td> |
---|
| 177 | <td class="codetablecell" align="center">301 +/- 28</td> |
---|
| 178 | </tr> |
---|
| 179 | <tr> |
---|
| 180 | <th class="codetableleft"> |
---|
| 181 | <div align="right">special counted</div> |
---|
| 182 | </th> |
---|
| 183 | <td class="codetablecell" align="center">1990 +/- 40</td> |
---|
| 184 | <td class="codetablecell" align="center">264 +/- 7</td> |
---|
| 185 | </tr> |
---|
| 186 | <tr> |
---|
| 187 | <th class="codetableleft"> |
---|
| 188 | <div align="right">intrusive</div> |
---|
| 189 | </th> |
---|
| 190 | <td class="codetablecell" align="center">1590 +/- 70</td> |
---|
| 191 | <td class="codetablecell" align="center">181 +/- 12</td> |
---|
| 192 | </tr> |
---|
| 193 | <tr> |
---|
| 194 | <th class="codetableleft" align="right">linked</th> |
---|
| 195 | <td class="codetablecell" align="center">1470 +/- 140</td> |
---|
| 196 | <td class="codetablecell" align="center">345 +/- 26</td> |
---|
| 197 | </tr> |
---|
| 198 | <tr> |
---|
| 199 | <th class="codetableleft" align="right">cyclic</th> |
---|
| 200 | <td class="codetablecell" align="center">2180 +/- 100</td> |
---|
| 201 | <td class="codetablecell" align="center">330 +/- 18</td> |
---|
| 202 | </tr> |
---|
| 203 | <tr> |
---|
| 204 | <th class="codetableleft" align="right">dumb</th> |
---|
| 205 | <td class="codetablecell" align="center">1590 +/- 70</td> |
---|
| 206 | <td class="codetablecell" align="center">74 +/- 12</td> |
---|
| 207 | </tr> |
---|
| 208 | <tr> |
---|
| 209 | <th class="codetableleft" align="right"> |
---|
| 210 | <div align="right">raw</div> |
---|
| 211 | </th> |
---|
| 212 | <td class="codetablecell" align="center">1430 +/- 60</td> |
---|
| 213 | <td class="codetablecell" align="center">27 +/- 11</td> |
---|
| 214 | </tr> |
---|
| 215 | </table> |
---|
| 216 | <p>Note that the above times include a certain amount of loop overhead etc. for |
---|
| 217 | each operation. An estimate of the pure smart pointer operation time 'overhead' |
---|
| 218 | can be obtained by subtracting the dumb or raw figure from the smart pointer |
---|
| 219 | time of interest.</p> |
---|
| 220 | <h3>Detail</h3> |
---|
| 221 | <p>The test involved iterating a loop which creates raw pointers. These were then |
---|
| 222 | shared among a varying number (set size) of smart pointers. A range of set sizes |
---|
| 223 | was used and then a line fitted to get a linear relation with number of initializations |
---|
| 224 | and copy-operations. A spreadsheet was used for the line fit, and to produce |
---|
| 225 | the performance graphs above.</p> |
---|
| 226 | <h2> </h2> |
---|
| 227 | <h2>Container Test Results</h2> |
---|
| 228 | <p>To gain some insight in to operation within real life programs, this test was |
---|
| 229 | devised. Smart pointers were used to fill standard containers which were then |
---|
| 230 | sorted.</p> |
---|
| 231 | <p>In this case, the contained pointer pointed to a class which initializes a |
---|
| 232 | private data member to a random value in its default constructor. This value |
---|
| 233 | is used subsequently for the sort comparison test. The class also contains an |
---|
| 234 | intrusive reference count for the benefit of the intrusive counted pointer.</p> |
---|
| 235 | <p> All times are in seconds for 300,000 contained pointers.</p> |
---|
| 236 | <h4 align="center">GCC</h4> |
---|
| 237 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="500"> |
---|
| 238 | <tr> |
---|
| 239 | <th> </th> |
---|
| 240 | <th class="codetabletop" colspan="2">vector</th> |
---|
| 241 | <th class="codetabletop" colspan="2">list</th> |
---|
| 242 | </tr> |
---|
| 243 | <tr> |
---|
| 244 | <th width="120"> |
---|
| 245 | <div align="right"></div> |
---|
| 246 | </th> |
---|
| 247 | <th class="codetabletop2" width="80"> |
---|
| 248 | <div align="center">fill</div> |
---|
| 249 | </th> |
---|
| 250 | <th class="codetabletop2" width="80">sort</th> |
---|
| 251 | <th class="codetabletop2" width="80">fill</th> |
---|
| 252 | <th class="codetabletop2" width="80">sort</th> |
---|
| 253 | </tr> |
---|
| 254 | <tr> |
---|
| 255 | <th class="codetableleft"> |
---|
| 256 | <div align="right">simple counted</div> |
---|
| 257 | </th> |
---|
| 258 | <td class="codetablecell" align="center">46.54</td> |
---|
| 259 | <td class="codetablecell" align="center">2.44</td> |
---|
| 260 | <td class="codetablecell" align="center">47.09</td> |
---|
| 261 | <td class="codetablecell" align="center">3.22</td> |
---|
| 262 | </tr> |
---|
| 263 | <tr> |
---|
| 264 | <th class="codetableleft"> |
---|
| 265 | <div align="right">special counted</div> |
---|
| 266 | </th> |
---|
| 267 | <td class="codetablecell" align="center">14.02</td> |
---|
| 268 | <td class="codetablecell" align="center">2.83</td> |
---|
| 269 | <td class="codetablecell" align="center">7.28</td> |
---|
| 270 | <td class="codetablecell" align="center">3.21</td> |
---|
| 271 | </tr> |
---|
| 272 | <tr> |
---|
| 273 | <th class="codetableleft"> |
---|
| 274 | <div align="right">intrusive</div> |
---|
| 275 | </th> |
---|
| 276 | <td class="codetablecell" align="center">12.15</td> |
---|
| 277 | <td class="codetablecell" align="center">1.91</td> |
---|
| 278 | <td class="codetablecell" align="center">7.99</td> |
---|
| 279 | <td class="codetablecell" align="center">3.08</td> |
---|
| 280 | </tr> |
---|
| 281 | <tr> |
---|
| 282 | <th class="codetableleft" align="right">linked</th> |
---|
| 283 | <td class="codetablecell" align="center">12.46</td> |
---|
| 284 | <td class="codetablecell" align="center">2.32</td> |
---|
| 285 | <td class="codetablecell" align="center">8.14</td> |
---|
| 286 | <td class="codetablecell" align="center">3.27</td> |
---|
| 287 | </tr> |
---|
| 288 | <tr> |
---|
| 289 | <th class="codetableleft" align="right">cyclic</th> |
---|
| 290 | <td class="codetablecell" align="center">22.60</td> |
---|
| 291 | <td class="codetablecell" align="center">3.19</td> |
---|
| 292 | <td class="codetablecell" align="center">1.63</td> |
---|
| 293 | <td class="codetablecell" align="center">3.18</td> |
---|
| 294 | </tr> |
---|
| 295 | <tr> |
---|
| 296 | <th class="codetableleft" align="right"> |
---|
| 297 | <div align="right">raw</div> |
---|
| 298 | </th> |
---|
| 299 | <td class="codetablecell" align="center">11.81</td> |
---|
| 300 | <td class="codetablecell" align="center">0.24</td> |
---|
| 301 | <td class="codetablecell" align="center">27.51</td> |
---|
| 302 | <td class="codetablecell" align="center">0.77</td> |
---|
| 303 | </tr> |
---|
| 304 | </table> |
---|
| 305 | <p> </p> |
---|
| 306 | <h4 align="center">MSVC</h4> |
---|
| 307 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="500"> |
---|
| 308 | <tr> |
---|
| 309 | <th> </th> |
---|
| 310 | <th class="codetabletop" colspan="2">vector</th> |
---|
| 311 | <th class="codetabletop" colspan="2">list</th> |
---|
| 312 | </tr> |
---|
| 313 | <tr> |
---|
| 314 | <th width="120"> |
---|
| 315 | <div align="right"></div> |
---|
| 316 | </th> |
---|
| 317 | <th class="codetabletop2" width="80"> |
---|
| 318 | <div align="center">fill</div> |
---|
| 319 | </th> |
---|
| 320 | <th class="codetabletop2" width="80">sort</th> |
---|
| 321 | <th class="codetabletop2" width="80">fill</th> |
---|
| 322 | <th class="codetabletop2" width="80">sort</th> |
---|
| 323 | </tr> |
---|
| 324 | <tr> |
---|
| 325 | <th class="codetableleft"> |
---|
| 326 | <div align="right">simple counted</div> |
---|
| 327 | </th> |
---|
| 328 | <td class="codetablecell" align="center">1.83</td> |
---|
| 329 | <td class="codetablecell" align="center">2.37</td> |
---|
| 330 | <td class="codetablecell" align="center">1.86</td> |
---|
| 331 | <td class="codetablecell" align="center">4.85</td> |
---|
| 332 | </tr> |
---|
| 333 | <tr> |
---|
| 334 | <th class="codetableleft"> |
---|
| 335 | <div align="right">special counted</div> |
---|
| 336 | </th> |
---|
| 337 | <td class="codetablecell" align="center">1.04</td> |
---|
| 338 | <td class="codetablecell" align="center">2.35</td> |
---|
| 339 | <td class="codetablecell" align="center">1.38</td> |
---|
| 340 | <td class="codetablecell" align="center">4.58</td> |
---|
| 341 | </tr> |
---|
| 342 | <tr> |
---|
| 343 | <th class="codetableleft"> |
---|
| 344 | <div align="right">intrusive</div> |
---|
| 345 | </th> |
---|
| 346 | <td class="codetablecell" align="center">1.04</td> |
---|
| 347 | <td class="codetablecell" align="center">1.84</td> |
---|
| 348 | <td class="codetablecell" align="center">1.16</td> |
---|
| 349 | <td class="codetablecell" align="center">4.29</td> |
---|
| 350 | </tr> |
---|
| 351 | <tr> |
---|
| 352 | <th class="codetableleft" align="right">linked</th> |
---|
| 353 | <td class="codetablecell" align="center">1.08</td> |
---|
| 354 | <td class="codetablecell" align="center">2.00</td> |
---|
| 355 | <td class="codetablecell" align="center">1.21</td> |
---|
| 356 | <td class="codetablecell" align="center">4.33</td> |
---|
| 357 | </tr> |
---|
| 358 | <tr> |
---|
| 359 | <th class="codetableleft" align="right">cyclic</th> |
---|
| 360 | <td class="codetablecell" align="center">1.38</td> |
---|
| 361 | <td class="codetablecell" align="center">2.84</td> |
---|
| 362 | <td class="codetablecell" align="center">1.47</td> |
---|
| 363 | <td class="codetablecell" align="center">4.73</td> |
---|
| 364 | </tr> |
---|
| 365 | <tr> |
---|
| 366 | <th class="codetableleft" align="right"> |
---|
| 367 | <div align="right">raw</div> |
---|
| 368 | </th> |
---|
| 369 | <td class="codetablecell" align="center">0.67</td> |
---|
| 370 | <td class="codetablecell" align="center">0.28</td> |
---|
| 371 | <td class="codetablecell" align="center">1.24</td> |
---|
| 372 | <td class="codetablecell" align="center">1.81</td> |
---|
| 373 | </tr> |
---|
| 374 | </table> |
---|
| 375 | <p> </p> |
---|
| 376 | <h2>Code Size</h2> |
---|
| 377 | <p>The following code sizes were determined by inspection of generated code for |
---|
| 378 | MSVC only. Sizes are given in the form N / M / I where:</p> |
---|
| 379 | <ul type="circle"> |
---|
| 380 | <li> N is the instruction count of the operation</li> |
---|
| 381 | <li>M is the size of the code in bytes</li> |
---|
| 382 | <li>I determines whether generated code was inlined or not I = inline, O = "outline"</li> |
---|
| 383 | </ul> |
---|
| 384 | <p> </p> |
---|
| 385 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="570"> |
---|
| 386 | <tr> |
---|
| 387 | <th height="28" width="140"> |
---|
| 388 | <div align="right"></div> |
---|
| 389 | </th> |
---|
| 390 | <th height="28" class="codetabletop" width="80"> |
---|
| 391 | <div align="center">ptr()</div> |
---|
| 392 | </th> |
---|
| 393 | <th height="28" class="codetabletop" width="80">ptr(p)</th> |
---|
| 394 | <th height="28" class="codetabletop" width="80">ptr(ptr)</th> |
---|
| 395 | <th height="28" class="codetabletop" width="80">op=()</th> |
---|
| 396 | <th height="28" class="codetabletop" width="80"> |
---|
| 397 | <div align="center">~ptr()</div> |
---|
| 398 | </th> |
---|
| 399 | </tr> |
---|
| 400 | <tr> |
---|
| 401 | <th class="codetableleft"> |
---|
| 402 | <div align="right">simple counted</div> |
---|
| 403 | </th> |
---|
| 404 | <td class="codetablecell" align="center">38/110/O</td> |
---|
| 405 | <td class="codetablecell" align="center">38/110/O</td> |
---|
| 406 | <td class="codetablecell" align="center">9/23/I</td> |
---|
| 407 | <td class="codetablecell" align="center">22/57/I</td> |
---|
| 408 | <td class="codetablecell" align="center">17/40/I</td> |
---|
| 409 | </tr> |
---|
| 410 | <tr> |
---|
| 411 | <th class="codetableleft"> |
---|
| 412 | <div align="right">special counted</div> |
---|
| 413 | </th> |
---|
| 414 | <td class="codetablecell" align="center"><font size="-1">50/141/O</font></td> |
---|
| 415 | <td class="codetablecell" align="center"><font size="-1">50/141/O</font></td> |
---|
| 416 | <td class="codetablecell" align="center"><font size="-1">9/23/I</font></td> |
---|
| 417 | <td class="codetablecell" align="center"><font size="-1">23/64/I</font></td> |
---|
| 418 | <td class="codetablecell" align="center"><font size="-1">13/38/I</font></td> |
---|
| 419 | </tr> |
---|
| 420 | <tr> |
---|
| 421 | <th class="codetableleft"> |
---|
| 422 | <div align="right">intrusive</div> |
---|
| 423 | </th> |
---|
| 424 | <td class="codetablecell" align="center"><font size="-1">1/2/I</font></td> |
---|
| 425 | <td class="codetablecell" align="center"><font size="-1">3/6/I</font></td> |
---|
| 426 | <td class="codetablecell" align="center"><font size="-1">3/6/I</font></td> |
---|
| 427 | <td class="codetablecell" align="center"><font size="-1">6/11/I</font></td> |
---|
| 428 | <td class="codetablecell" align="center"><font size="-1">6/11/I</font></td> |
---|
| 429 | </tr> |
---|
| 430 | <tr> |
---|
| 431 | <th class="codetableleft"> |
---|
| 432 | <div align="right">linked</div> |
---|
| 433 | </th> |
---|
| 434 | <td class="codetablecell" align="center"><font size="-1">5/19/I</font></td> |
---|
| 435 | <td class="codetablecell" align="center"><font size="-1">5/15/I</font></td> |
---|
| 436 | <td class="codetablecell" align="center"><font size="-1">10/30/I</font></td> |
---|
| 437 | <td class="codetablecell" align="center"><font size="-1">27/59/I</font></td> |
---|
| 438 | <td class="codetablecell" align="center"><font size="-1">14/38/I</font></td> |
---|
| 439 | </tr> |
---|
| 440 | </table> |
---|
| 441 | <p>During the code inspection, a couple of minor points were noticed: -</p> |
---|
| 442 | <ul> |
---|
| 443 | <li>Function inlining was critical to performance.</li> |
---|
| 444 | <li>For MSVC, at least, a "delete 0" caused execution of 11 assembly |
---|
| 445 | instructions, including a function call. So in cases where performance is |
---|
| 446 | at an absolute premium it can be worth inserting the extra manual test.</li> |
---|
| 447 | </ul> |
---|
| 448 | <h2> </h2> |
---|
| 449 | <h2>Data Size</h2> |
---|
| 450 | <p>The following smart pointer sizes were obtained in bytes</p> |
---|
| 451 | <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="270"> |
---|
| 452 | <tr> |
---|
| 453 | <th height="28" width="150"> |
---|
| 454 | <div align="right"></div> |
---|
| 455 | </th> |
---|
| 456 | <th height="28" class="codetabletop" width="60"> |
---|
| 457 | <div align="center">MSVC</div> |
---|
| 458 | </th> |
---|
| 459 | <th height="28" class="codetabletop" width="60"> |
---|
| 460 | <div align="center">GCC</div> |
---|
| 461 | </th> |
---|
| 462 | </tr> |
---|
| 463 | <tr> |
---|
| 464 | <th class="codetableleft"> |
---|
| 465 | <div align="right">simple counted</div> |
---|
| 466 | </th> |
---|
| 467 | <td class="codetablecell"> |
---|
| 468 | <div align="center">8</div> |
---|
| 469 | </td> |
---|
| 470 | <td class="codetablecell"> |
---|
| 471 | <div align="center">8</div> |
---|
| 472 | </td> |
---|
| 473 | </tr> |
---|
| 474 | <tr> |
---|
| 475 | <th class="codetableleft"> |
---|
| 476 | <div align="right">special counted</div> |
---|
| 477 | </th> |
---|
| 478 | <td class="codetablecell"> |
---|
| 479 | <div align="center">8</div> |
---|
| 480 | </td> |
---|
| 481 | <td class="codetablecell"> |
---|
| 482 | <div align="center">12</div> |
---|
| 483 | </td> |
---|
| 484 | </tr> |
---|
| 485 | <tr> |
---|
| 486 | <th class="codetableleft"> |
---|
| 487 | <div align="right">intrusive</div> |
---|
| 488 | </th> |
---|
| 489 | <td class="codetablecell"> |
---|
| 490 | <div align="center">4</div> |
---|
| 491 | </td> |
---|
| 492 | <td class="codetablecell"> |
---|
| 493 | <div align="center">4</div> |
---|
| 494 | </td> |
---|
| 495 | </tr> |
---|
| 496 | <tr> |
---|
| 497 | <th class="codetableleft"> |
---|
| 498 | <div align="right">linked</div> |
---|
| 499 | </th> |
---|
| 500 | <td class="codetablecell"> |
---|
| 501 | <div align="center">12</div> |
---|
| 502 | </td> |
---|
| 503 | <td class="codetablecell"> |
---|
| 504 | <div align="center">12</div> |
---|
| 505 | </td> |
---|
| 506 | </tr> |
---|
| 507 | <tr> |
---|
| 508 | <th class="codetableleft"> |
---|
| 509 | <div align="right">cyclic</div> |
---|
| 510 | </th> |
---|
| 511 | <td class="codetablecell"> |
---|
| 512 | <div align="center">8</div> |
---|
| 513 | </td> |
---|
| 514 | <td class="codetablecell"> |
---|
| 515 | <div align="center">8</div> |
---|
| 516 | </td> |
---|
| 517 | </tr> |
---|
| 518 | </table> |
---|
| 519 | <h2> </h2> |
---|
| 520 | <h2>Summary</h2> |
---|
| 521 | <p>The timing results mainly speak for themselves: clearly an intrusive pointer |
---|
| 522 | outperforms all others and a simple heap based counted pointer has poor performance |
---|
| 523 | relative to other implementations. The selection of an optimal non-intrusive |
---|
| 524 | smart pointer implementation is more application dependent, however. Where small |
---|
| 525 | numbers of copies are expected, it is likely that the linked implementation |
---|
| 526 | will be favoured. Conversely, for larger numbers of copies a counted pointer |
---|
| 527 | with some type of special purpose allocator looks like a win. Other factors |
---|
| 528 | to bear in mind are: -</p> |
---|
| 529 | <ul> |
---|
| 530 | <li>Deterministic individual, as opposed to amortized, operation time. This |
---|
| 531 | weighs against any implementation depending on an allocator.</li> |
---|
| 532 | <li>Multithreaded synchronization. This weighs against an implementation which |
---|
| 533 | spreads its information as in the case of linked pointer.</li> |
---|
| 534 | </ul> |
---|
| 535 | <hr> |
---|
| 536 | <p>Revised <!--webbot bot="Timestamp" S-Type="EDITED" S-Format="%d %B %Y" startspan -->19 August 2001<!--webbot bot="Timestamp" endspan i-checksum="14767" --> |
---|
| 537 | </p> |
---|
| 538 | <p>© Copyright Gavin Collings 2000. Permission to copy, use, modify, sell |
---|
| 539 | and distribute this document is granted provided this copyright notice appears in all |
---|
| 540 | copies. This document is provided "as is" without express or implied warranty, |
---|
| 541 | and with no claim as to its suitability for any purpose.</p> |
---|
| 542 | </body> |
---|
| 543 | </html> |
---|