ceph/src/boost/libs/smart_ptr/smarttests.htm

   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 text="#000000" bgcolor="#ffffff" link="#0000ff" vlink="#0000ff">
  11
  12 <h1><img height="86" alt="boost.png (6897 bytes)" src="../../boost.png" width="277" align="middle" border="0">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="http://www.boost.org/people/dave_abrahams.htm">Dave Abrahams</a>,
  25 Gavin Collings,
  26 <a href="http://www.boost.org/people/greg_colvin.htm">Greg Colvin</a> and
  27 <a href="http://www.boost.org/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>&nbsp;</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">&nbsp;</td>
  76     <td>&nbsp;</td>
  77     <td width="20">&nbsp;</td>
  78   </tr>
  79   <tr>
  80     <td width="20">&nbsp; </td>
  81     <td><img src="msvcspeed.gif" width="560" height="355" alt="MSVC speed graph"></td>
  82     <td width="20">&nbsp;</td>
  83   </tr>
  84   <tr>
  85     <td height="20">&nbsp;</td>
  86     <td>&nbsp;</td>
  87     <td>&nbsp;</td>
  88   </tr>
  89   <tr>
  90     <td>&nbsp;</td>
  91     <td><img src="gccspeed.gif" width="560" height="355" alt="GCC speed graph"></td>
  92     <td>&nbsp;</td>
  93   </tr>
  94   <tr>
  95     <td height="20">&nbsp;</td>
  96     <td>&nbsp;</td>
  97     <td>&nbsp;</td>
  98   </tr>
  99 </table>
 100 <p>&nbsp;</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>&nbsp;</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">&nbsp;</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>&nbsp;</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>&nbsp;</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>&nbsp;</p>
 306 <h4 align="center">MSVC</h4>
 307 <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="500">
 308   <tr>
 309     <th>&nbsp;</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>&nbsp;</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 = &quot;outline&quot;</li>
 383 </ul>
 384 <p>&nbsp;</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 &quot;delete 0&quot; 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>&nbsp;</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>&nbsp;</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>$Date$</p>
 537 <p>&copy; Copyright Gavin Collings 2000. Permission to copy, use, modify, sell
 538 and distribute this document is granted provided this copyright notice appears in all
 539 copies. This document is provided &quot;as is&quot; without express or implied warranty,
 540 and with no claim as to its suitability for any purpose.</p>
 541 </body>
 542 </html>