| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| |
| <html> |
| |
| <head> |
| <title>Smart Pointer Timings</title> |
| <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
| </head> |
| |
| <body bgcolor="#FFFFFF"> |
| |
| <h1><img src="../../boost.png" alt="boost.png (6897 bytes)" align="middle" WIDTH="277" HEIGHT="86">Smart Pointer Timings</h1> |
| |
| <p>In late January 2000, Mark Borgerding put forward a suggestion to boost for |
| a new design of smart pointer whereby an intrusive doubly linked list is used |
| to join together all instances of smart pointers sharing a given raw pointer. |
| This allowed avoidance of the costly heap allocation of a reference count that |
| occurred in the initial construction of the then current version of boost::shared_ptr. |
| Of course, nothing is for free and the benefit here was gained at the expense |
| of increased size and more costly copy operations. A debate ensued on the boost |
| mailing list and the tests which this page describes were performed to provide |
| a guide for current and future investigations into smart pointer implementation |
| strategies.</p> |
| <p>Thanks are due to <a href="http://www.boost.org/people/dave_abrahams.htm">Dave Abrahams</a>, |
| Gavin Collings, |
| <a href="http://www.boost.org/people/greg_colvin.htm">Greg Colvin</a> and |
| <a href="http://www.boost.org/people/beman_dawes.html">Beman Dawes</a> |
| for test code and trial implementations, the final version of which can be found |
| in .zip format <a href="smarttest.zip">here</a>.</p> |
| <h2>Description</h2> |
| <p>Two tests were run: the first aimed to obtain timings for two basic individual |
| operations:</p> |
| <ol type="i"> |
| <li> Initial construction from raw pointer.</li> |
| <li> An amortized copy operation consisting of half an assignment and half a |
| copy construction - designed to reflect average usage.</li> |
| </ol> |
| <p>The second attempted to gain more insight into normal usage by timing the fill |
| and sort algorithms for vectors and lists filled with the various smart pointers.</p> |
| <p>Five smart pointer implementation strategies were tested:</p> |
| <ol type="i"> |
| <li>Counted pointer using a heap allocated reference count, this is referred |
| to as <b>simple counted</b>.</li> |
| <li>Counted pointer using a special purpose allocator for the reference count |
| - <b>special counted</b>.</li> |
| <li>Counted pointer using an intrusive reference count - <b>intrusive</b>.</li> |
| <li>Linked pointer as described above - <b>linked</b>.</li> |
| <li>Cyclic pointer, a counted implementation using a std::deque for allocation |
| with provision for weak pointers and garbage collection of cycles of pointers |
| - <b>cyclic</b>.</li> |
| </ol> |
| <p>on two compilers:</p> |
| <ol type="i"> |
| <li>MSVC 6.0 service pack 3, using default release optimization mode (/O2 - |
| optimized for speed, no inlining of functions defined outside a class body |
| unless specified as inline).</li> |
| <li>gcc 2.95.2 using full optimization (-O3 -DNDEBUG).</li> |
| </ol> |
| <p>Additionally, generated pointer sizes (taking into account struct alignment) |
| were compared, as were generated code sizes for MSVC mainly by manual inspection |
| of generated assembly code - a necessity due to function inlining.</p> |
| <p>All tests were run on a PII-200 running Windows NT version 4.0</p> |
| <h2> </h2> |
| <h2>Operation Timing Test Results</h2> |
| <p>The following graphs show the overall time in nanoseconds to acquire a pointer |
| (default construction) perform n amortized copy operations on it and finally |
| release it. The initial allocation time for the contained pointer is not included, |
| although the time for it's deallocation is. The contained pointer pointed to |
| a trivial class, but for the inclusion of an intrusive reference count for the |
| benefit of the intrusive counted shared pointer. A dumb pointer (i.e. a smart |
| pointer that simply acquires and releases its contained pointer with no extra |
| overhead) and a raw pointer were also included for comparison.</p> |
| <table border="0" align="center"> |
| <tr> |
| <td width="20" height="20"> </td> |
| <td> </td> |
| <td width="20"> </td> |
| </tr> |
| <tr> |
| <td width="20"> </td> |
| <td><img src="msvcspeed.gif" width="560" height="355" alt="MSVC speed graph"></td> |
| <td width="20"> </td> |
| </tr> |
| <tr> |
| <td height="20"> </td> |
| <td> </td> |
| <td> </td> |
| </tr> |
| <tr> |
| <td> </td> |
| <td><img src="gccspeed.gif" width="560" height="355" alt="GCC speed graph"></td> |
| <td> </td> |
| </tr> |
| <tr> |
| <td height="20"> </td> |
| <td> </td> |
| <td> </td> |
| </tr> |
| </table> |
| <p> </p> |
| <p>Fitting straight lines to the above plots gives the following figures for initialization |
| and amortized copy operation for the two compilers (times in nanoseconds, errors |
| at two standard deviations) : -</p> |
| <p> </p> |
| <h4 align="center">MSVC</h4> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="400"> |
| <tr> |
| <th width="120"> |
| <div align="right"></div> |
| </th> |
| <th class="codetabletop" width="120"> |
| <div align="center">initialization</div> |
| </th> |
| <th class="codetabletop" width="120">copy operation</th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell" align="center">3000 +/- 170</td> |
| <td class="codetablecell" align="center">104 +/- 31</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell" align="center">1330 +/- 50</td> |
| <td class="codetablecell" align="center">85 +/- 9</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell" align="center">1000 +/- 20</td> |
| <td class="codetablecell" align="center">71 +/- 3</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">linked</th> |
| <td class="codetablecell" align="center">970 +/- 60</td> |
| <td class="codetablecell" align="center">136 +/- 10</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">cyclic</th> |
| <td class="codetablecell" align="center">1290 +/- 70</td> |
| <td class="codetablecell" align="center">112 +/- 12</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">dumb</th> |
| <td class="codetablecell" align="center">1020 +/- 20</td> |
| <td class="codetablecell" align="center">10 +/- 4</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">raw</div> |
| </th> |
| <td class="codetablecell" align="center">1038 +/- 30</td> |
| <td class="codetablecell" align="center">10 +/- 5</td> |
| </tr> |
| </table> |
| <h4 align="center"> </h4> |
| <h4 align="center">GCC</h4> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="400"> |
| <tr> |
| <th width="120"> |
| <div align="right"></div> |
| </th> |
| <th class="codetabletop" width="120"> |
| <div align="center">initialization</div> |
| </th> |
| <th class="codetabletop" width="120">copy operation</th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell" align="center">4620 +/- 150</td> |
| <td class="codetablecell" align="center">301 +/- 28</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell" align="center">1990 +/- 40</td> |
| <td class="codetablecell" align="center">264 +/- 7</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell" align="center">1590 +/- 70</td> |
| <td class="codetablecell" align="center">181 +/- 12</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">linked</th> |
| <td class="codetablecell" align="center">1470 +/- 140</td> |
| <td class="codetablecell" align="center">345 +/- 26</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">cyclic</th> |
| <td class="codetablecell" align="center">2180 +/- 100</td> |
| <td class="codetablecell" align="center">330 +/- 18</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">dumb</th> |
| <td class="codetablecell" align="center">1590 +/- 70</td> |
| <td class="codetablecell" align="center">74 +/- 12</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right"> |
| <div align="right">raw</div> |
| </th> |
| <td class="codetablecell" align="center">1430 +/- 60</td> |
| <td class="codetablecell" align="center">27 +/- 11</td> |
| </tr> |
| </table> |
| <p>Note that the above times include a certain amount of loop overhead etc. for |
| each operation. An estimate of the pure smart pointer operation time 'overhead' |
| can be obtained by subtracting the dumb or raw figure from the smart pointer |
| time of interest.</p> |
| <h3>Detail</h3> |
| <p>The test involved iterating a loop which creates raw pointers. These were then |
| shared among a varying number (set size) of smart pointers. A range of set sizes |
| was used and then a line fitted to get a linear relation with number of initializations |
| and copy-operations. A spreadsheet was used for the line fit, and to produce |
| the performance graphs above.</p> |
| <h2> </h2> |
| <h2>Container Test Results</h2> |
| <p>To gain some insight in to operation within real life programs, this test was |
| devised. Smart pointers were used to fill standard containers which were then |
| sorted.</p> |
| <p>In this case, the contained pointer pointed to a class which initializes a |
| private data member to a random value in its default constructor. This value |
| is used subsequently for the sort comparison test. The class also contains an |
| intrusive reference count for the benefit of the intrusive counted pointer.</p> |
| <p> All times are in seconds for 300,000 contained pointers.</p> |
| <h4 align="center">GCC</h4> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="500"> |
| <tr> |
| <th> </th> |
| <th class="codetabletop" colspan="2">vector</th> |
| <th class="codetabletop" colspan="2">list</th> |
| </tr> |
| <tr> |
| <th width="120"> |
| <div align="right"></div> |
| </th> |
| <th class="codetabletop2" width="80"> |
| <div align="center">fill</div> |
| </th> |
| <th class="codetabletop2" width="80">sort</th> |
| <th class="codetabletop2" width="80">fill</th> |
| <th class="codetabletop2" width="80">sort</th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell" align="center">46.54</td> |
| <td class="codetablecell" align="center">2.44</td> |
| <td class="codetablecell" align="center">47.09</td> |
| <td class="codetablecell" align="center">3.22</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell" align="center">14.02</td> |
| <td class="codetablecell" align="center">2.83</td> |
| <td class="codetablecell" align="center">7.28</td> |
| <td class="codetablecell" align="center">3.21</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell" align="center">12.15</td> |
| <td class="codetablecell" align="center">1.91</td> |
| <td class="codetablecell" align="center">7.99</td> |
| <td class="codetablecell" align="center">3.08</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">linked</th> |
| <td class="codetablecell" align="center">12.46</td> |
| <td class="codetablecell" align="center">2.32</td> |
| <td class="codetablecell" align="center">8.14</td> |
| <td class="codetablecell" align="center">3.27</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">cyclic</th> |
| <td class="codetablecell" align="center">22.60</td> |
| <td class="codetablecell" align="center">3.19</td> |
| <td class="codetablecell" align="center">1.63</td> |
| <td class="codetablecell" align="center">3.18</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right"> |
| <div align="right">raw</div> |
| </th> |
| <td class="codetablecell" align="center">11.81</td> |
| <td class="codetablecell" align="center">0.24</td> |
| <td class="codetablecell" align="center">27.51</td> |
| <td class="codetablecell" align="center">0.77</td> |
| </tr> |
| </table> |
| <p> </p> |
| <h4 align="center">MSVC</h4> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="500"> |
| <tr> |
| <th> </th> |
| <th class="codetabletop" colspan="2">vector</th> |
| <th class="codetabletop" colspan="2">list</th> |
| </tr> |
| <tr> |
| <th width="120"> |
| <div align="right"></div> |
| </th> |
| <th class="codetabletop2" width="80"> |
| <div align="center">fill</div> |
| </th> |
| <th class="codetabletop2" width="80">sort</th> |
| <th class="codetabletop2" width="80">fill</th> |
| <th class="codetabletop2" width="80">sort</th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell" align="center">1.83</td> |
| <td class="codetablecell" align="center">2.37</td> |
| <td class="codetablecell" align="center">1.86</td> |
| <td class="codetablecell" align="center">4.85</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell" align="center">1.04</td> |
| <td class="codetablecell" align="center">2.35</td> |
| <td class="codetablecell" align="center">1.38</td> |
| <td class="codetablecell" align="center">4.58</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell" align="center">1.04</td> |
| <td class="codetablecell" align="center">1.84</td> |
| <td class="codetablecell" align="center">1.16</td> |
| <td class="codetablecell" align="center">4.29</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">linked</th> |
| <td class="codetablecell" align="center">1.08</td> |
| <td class="codetablecell" align="center">2.00</td> |
| <td class="codetablecell" align="center">1.21</td> |
| <td class="codetablecell" align="center">4.33</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right">cyclic</th> |
| <td class="codetablecell" align="center">1.38</td> |
| <td class="codetablecell" align="center">2.84</td> |
| <td class="codetablecell" align="center">1.47</td> |
| <td class="codetablecell" align="center">4.73</td> |
| </tr> |
| <tr> |
| <th class="codetableleft" align="right"> |
| <div align="right">raw</div> |
| </th> |
| <td class="codetablecell" align="center">0.67</td> |
| <td class="codetablecell" align="center">0.28</td> |
| <td class="codetablecell" align="center">1.24</td> |
| <td class="codetablecell" align="center">1.81</td> |
| </tr> |
| </table> |
| <p> </p> |
| <h2>Code Size</h2> |
| <p>The following code sizes were determined by inspection of generated code for |
| MSVC only. Sizes are given in the form N / M / I where:</p> |
| <ul type="circle"> |
| <li> N is the instruction count of the operation</li> |
| <li>M is the size of the code in bytes</li> |
| <li>I determines whether generated code was inlined or not I = inline, O = "outline"</li> |
| </ul> |
| <p> </p> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="570"> |
| <tr> |
| <th height="28" width="140"> |
| <div align="right"></div> |
| </th> |
| <th height="28" class="codetabletop" width="80"> |
| <div align="center">ptr()</div> |
| </th> |
| <th height="28" class="codetabletop" width="80">ptr(p)</th> |
| <th height="28" class="codetabletop" width="80">ptr(ptr)</th> |
| <th height="28" class="codetabletop" width="80">op=()</th> |
| <th height="28" class="codetabletop" width="80"> |
| <div align="center">~ptr()</div> |
| </th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell" align="center">38/110/O</td> |
| <td class="codetablecell" align="center">38/110/O</td> |
| <td class="codetablecell" align="center">9/23/I</td> |
| <td class="codetablecell" align="center">22/57/I</td> |
| <td class="codetablecell" align="center">17/40/I</td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell" align="center"><font size="-1">50/141/O</font></td> |
| <td class="codetablecell" align="center"><font size="-1">50/141/O</font></td> |
| <td class="codetablecell" align="center"><font size="-1">9/23/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">23/64/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">13/38/I</font></td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell" align="center"><font size="-1">1/2/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">3/6/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">3/6/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">6/11/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">6/11/I</font></td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">linked</div> |
| </th> |
| <td class="codetablecell" align="center"><font size="-1">5/19/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">5/15/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">10/30/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">27/59/I</font></td> |
| <td class="codetablecell" align="center"><font size="-1">14/38/I</font></td> |
| </tr> |
| </table> |
| <p>During the code inspection, a couple of minor points were noticed: -</p> |
| <ul> |
| <li>Function inlining was critical to performance.</li> |
| <li>For MSVC, at least, a "delete 0" caused execution of 11 assembly |
| instructions, including a function call. So in cases where performance is |
| at an absolute premium it can be worth inserting the extra manual test.</li> |
| </ul> |
| <h2> </h2> |
| <h2>Data Size</h2> |
| <p>The following smart pointer sizes were obtained in bytes</p> |
| <table align="center" cellpadding="5" cellspacing="0" class="codetable" width="270"> |
| <tr> |
| <th height="28" width="150"> |
| <div align="right"></div> |
| </th> |
| <th height="28" class="codetabletop" width="60"> |
| <div align="center">MSVC</div> |
| </th> |
| <th height="28" class="codetabletop" width="60"> |
| <div align="center">GCC</div> |
| </th> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">simple counted</div> |
| </th> |
| <td class="codetablecell"> |
| <div align="center">8</div> |
| </td> |
| <td class="codetablecell"> |
| <div align="center">8</div> |
| </td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">special counted</div> |
| </th> |
| <td class="codetablecell"> |
| <div align="center">8</div> |
| </td> |
| <td class="codetablecell"> |
| <div align="center">12</div> |
| </td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">intrusive</div> |
| </th> |
| <td class="codetablecell"> |
| <div align="center">4</div> |
| </td> |
| <td class="codetablecell"> |
| <div align="center">4</div> |
| </td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">linked</div> |
| </th> |
| <td class="codetablecell"> |
| <div align="center">12</div> |
| </td> |
| <td class="codetablecell"> |
| <div align="center">12</div> |
| </td> |
| </tr> |
| <tr> |
| <th class="codetableleft"> |
| <div align="right">cyclic</div> |
| </th> |
| <td class="codetablecell"> |
| <div align="center">8</div> |
| </td> |
| <td class="codetablecell"> |
| <div align="center">8</div> |
| </td> |
| </tr> |
| </table> |
| <h2> </h2> |
| <h2>Summary</h2> |
| <p>The timing results mainly speak for themselves: clearly an intrusive pointer |
| outperforms all others and a simple heap based counted pointer has poor performance |
| relative to other implementations. The selection of an optimal non-intrusive |
| smart pointer implementation is more application dependent, however. Where small |
| numbers of copies are expected, it is likely that the linked implementation |
| will be favoured. Conversely, for larger numbers of copies a counted pointer |
| with some type of special purpose allocator looks like a win. Other factors |
| to bear in mind are: -</p> |
| <ul> |
| <li>Deterministic individual, as opposed to amortized, operation time. This |
| weighs against any implementation depending on an allocator.</li> |
| <li>Multithreaded synchronization. This weighs against an implementation which |
| spreads its information as in the case of linked pointer.</li> |
| </ul> |
| <hr> |
| <p>Revised <!--webbot bot="Timestamp" S-Type="EDITED" S-Format="%d %B %Y" startspan -->19 August 2001<!--webbot bot="Timestamp" endspan i-checksum="14767" --> |
| </p> |
| <p>© Copyright Gavin Collings 2000. Permission to copy, use, modify, sell |
| and distribute this document is granted provided this copyright notice appears in all |
| copies. This document is provided "as is" without express or implied warranty, |
| and with no claim as to its suitability for any purpose.</p> |
| </body> |
| </html> |
