2023 lines
77 KiB
HTML
2023 lines
77 KiB
HTML
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|||
|
<html>
|
|||
|
<head>
|
|||
|
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
|||
|
<title>Performance</title>
|
|||
|
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
|
|||
|
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
|
|||
|
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
|
|||
|
<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive">
|
|||
|
<link rel="prev" href="design_notes.html" title="Design Notes">
|
|||
|
<link rel="next" href="release_notes.html" title="Release Notes">
|
|||
|
</head>
|
|||
|
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
|
|||
|
<table cellpadding="2" width="100%"><tr>
|
|||
|
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
|
|||
|
<td align="center"><a href="../../../index.html">Home</a></td>
|
|||
|
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
|
|||
|
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
|
|||
|
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
|
|||
|
<td align="center"><a href="../../../more/index.htm">More</a></td>
|
|||
|
</tr></table>
|
|||
|
<hr>
|
|||
|
<div class="spirit-nav">
|
|||
|
<a accesskey="p" href="design_notes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="release_notes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
|
|||
|
</div>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
|||
|
<a name="intrusive.performance"></a><a class="link" href="performance.html" title="Performance">Performance</a>
|
|||
|
</h2></div></div></div>
|
|||
|
<div class="toc"><dl class="toc">
|
|||
|
<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_push_back">Back
|
|||
|
insertion and destruction</a></span></dt>
|
|||
|
<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_reversing">Reversing</a></span></dt>
|
|||
|
<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_sorting">Sorting</a></span></dt>
|
|||
|
<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_write_access">Write
|
|||
|
access</a></span></dt>
|
|||
|
<dt><span class="section"><a href="performance.html#intrusive.performance.performance_results_conclusions">Conclusions</a></span></dt>
|
|||
|
</dl></div>
|
|||
|
<p>
|
|||
|
<span class="bold"><strong>Boost.Intrusive</strong></span> containers offer speed improvements
|
|||
|
compared to non-intrusive containers primarily because:
|
|||
|
</p>
|
|||
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|||
|
<li class="listitem">
|
|||
|
They minimize memory allocation/deallocation calls.
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
They obtain better memory locality.
|
|||
|
</li>
|
|||
|
</ul></div>
|
|||
|
<p>
|
|||
|
This section will show performance tests comparing some operations on <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">::</span><span class="identifier">list</span></code> and
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code>:
|
|||
|
</p>
|
|||
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|||
|
<li class="listitem">
|
|||
|
Insertions using <code class="computeroutput"><span class="identifier">push_back</span></code>
|
|||
|
and container destruction will show the overhead associated with memory
|
|||
|
allocation/deallocation.
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
The <code class="computeroutput"><span class="identifier">reverse</span></code> member function
|
|||
|
will show the advantages of the compact memory representation that can
|
|||
|
be achieved with intrusive containers.
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
The <code class="computeroutput"><span class="identifier">sort</span></code> and <code class="computeroutput"><span class="identifier">write</span> <span class="identifier">access</span></code>
|
|||
|
tests will show the advantage of intrusive containers minimizing memory
|
|||
|
accesses compared to containers of pointers.
|
|||
|
</li>
|
|||
|
</ul></div>
|
|||
|
<p>
|
|||
|
Given an object of type <code class="computeroutput"><span class="identifier">T</span></code>,
|
|||
|
<code class="computeroutput"><a class="link" href="../boost/intrusive/list.html" title="Class template list">boost::intrusive::list<T></a></code>
|
|||
|
can replace <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">T</span><span class="special">></span></code> to
|
|||
|
avoid memory allocation overhead, or it can replace <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">T</span><span class="special">*></span></code> when
|
|||
|
the user wants containers with polymorphic values or wants to share values
|
|||
|
between several containers. Because of this versatility, the performance tests
|
|||
|
will be executed for 6 different list types:
|
|||
|
</p>
|
|||
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|||
|
<li class="listitem">
|
|||
|
3 intrusive lists holding a class named <code class="computeroutput"><span class="identifier">itest_class</span></code>,
|
|||
|
each one with a different linking policy (<code class="computeroutput"><span class="identifier">normal_link</span></code>,
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code>, <code class="computeroutput"><span class="identifier">auto_unlink</span></code>). The <code class="computeroutput"><span class="identifier">itest_class</span></code>
|
|||
|
objects will be tightly packed in a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">itest_class</span><span class="special">></span></code> object.
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code>,
|
|||
|
where <code class="computeroutput"><span class="identifier">test_class</span></code> is exactly
|
|||
|
the same as <code class="computeroutput"><span class="identifier">itest_class</span></code>,
|
|||
|
but without the intrusive hook.
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">*></span></code>.
|
|||
|
The list will contain pointers to <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
objects tightly packed in a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code> object. We'll call this configuration
|
|||
|
<span class="emphasis"><em>compact pointer list</em></span>
|
|||
|
</li>
|
|||
|
<li class="listitem">
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">*></span></code>.
|
|||
|
The list will contain pointers to <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
objects owned by a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span><span class="special"><</span><span class="identifier">test_class</span><span class="special">></span></code> object. We'll call this configuration
|
|||
|
<span class="emphasis"><em>disperse pointer list</em></span>.
|
|||
|
</li>
|
|||
|
</ul></div>
|
|||
|
<p>
|
|||
|
Both <code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code> are templatized classes that
|
|||
|
can be configured with a boolean to increase the size of the object. This way,
|
|||
|
the tests can be executed with small and big objects. Here is the first part
|
|||
|
of the testing code, which shows the definitions of <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
and <code class="computeroutput"><span class="identifier">itest_class</span></code> classes, and
|
|||
|
some other utilities:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="comment">//Iteration and element count defines</span>
|
|||
|
<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumIter</span> <span class="special">=</span> <span class="number">4</span><span class="special">;</span>
|
|||
|
<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">NumElements</span> <span class="special">=</span> <span class="number">50000</span><span class="special">;</span>
|
|||
|
|
|||
|
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span>
|
|||
|
|
|||
|
<span class="keyword">template</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">></span> <span class="keyword">struct</span> <span class="identifier">filler</span> <span class="special">{</span> <span class="keyword">int</span> <span class="identifier">dummy</span><span class="special">[</span><span class="number">10</span><span class="special">];</span> <span class="special">};</span>
|
|||
|
<span class="keyword">template</span> <span class="special"><></span> <span class="keyword">struct</span> <span class="identifier">filler</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span> <span class="special">{};</span>
|
|||
|
|
|||
|
<span class="keyword">template</span><span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">></span> <span class="comment">//The object for non-intrusive containers</span>
|
|||
|
<span class="keyword">struct</span> <span class="identifier">test_class</span> <span class="special">:</span> <span class="keyword">private</span> <span class="identifier">filler</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">></span>
|
|||
|
<span class="special">{</span>
|
|||
|
<span class="keyword">int</span> <span class="identifier">i_</span><span class="special">;</span>
|
|||
|
<span class="identifier">test_class</span><span class="special">()</span> <span class="special">{}</span>
|
|||
|
<span class="identifier">test_class</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">i_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{}</span>
|
|||
|
<span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special"><(</span><span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">i_</span> <span class="special"><</span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">i_</span><span class="special">;</span> <span class="special">}</span>
|
|||
|
<span class="keyword">friend</span> <span class="keyword">bool</span> <span class="keyword">operator</span> <span class="special">>(</span><span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">l</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">test_class</span> <span class="special">&</span><span class="identifier">r</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">l</span><span class="special">.</span><span class="identifier">i_</span> <span class="special">></span> <span class="identifier">r</span><span class="special">.</span><span class="identifier">i_</span><span class="special">;</span> <span class="special">}</span>
|
|||
|
<span class="special">};</span>
|
|||
|
|
|||
|
<span class="keyword">template</span> <span class="special"><</span><span class="keyword">bool</span> <span class="identifier">BigSize</span><span class="special">,</span> <span class="identifier">link_mode_type</span> <span class="identifier">LinkMode</span><span class="special">></span>
|
|||
|
<span class="keyword">struct</span> <span class="identifier">itest_class</span> <span class="comment">//The object for intrusive containers</span>
|
|||
|
<span class="special">:</span> <span class="keyword">public</span> <span class="identifier">list_base_hook</span><span class="special"><</span><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">LinkMode</span><span class="special">></span> <span class="special">>,</span> <span class="keyword">public</span> <span class="identifier">test_class</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">></span>
|
|||
|
<span class="special">{</span>
|
|||
|
<span class="identifier">itest_class</span><span class="special">()</span> <span class="special">{}</span>
|
|||
|
<span class="identifier">itest_class</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">test_class</span><span class="special"><</span><span class="identifier">BigSize</span><span class="special">>(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{}</span>
|
|||
|
<span class="special">};</span>
|
|||
|
|
|||
|
<span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">FuncObj</span><span class="special">></span> <span class="comment">//Adapts functors taking values to functors taking pointers</span>
|
|||
|
<span class="keyword">struct</span> <span class="identifier">func_ptr_adaptor</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">FuncObj</span>
|
|||
|
<span class="special">{</span>
|
|||
|
<span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">first_argument_type</span><span class="special">*</span> <span class="identifier">first_argument_type</span><span class="special">;</span>
|
|||
|
<span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">second_argument_type</span><span class="special">*</span> <span class="identifier">second_argument_type</span><span class="special">;</span>
|
|||
|
<span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="identifier">result_type</span> <span class="identifier">result_type</span><span class="special">;</span>
|
|||
|
<span class="identifier">result_type</span> <span class="keyword">operator</span><span class="special">()(</span><span class="identifier">first_argument_type</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">second_argument_type</span> <span class="identifier">b</span><span class="special">)</span> <span class="keyword">const</span>
|
|||
|
<span class="special">{</span> <span class="keyword">return</span> <span class="identifier">FuncObj</span><span class="special">::</span><span class="keyword">operator</span><span class="special">()(*</span><span class="identifier">a</span><span class="special">,</span> <span class="special">*</span><span class="identifier">b</span><span class="special">);</span> <span class="special">}</span>
|
|||
|
<span class="special">};</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
As we can see, <code class="computeroutput"><span class="identifier">test_class</span></code> is
|
|||
|
a very simple class holding an <code class="computeroutput"><span class="keyword">int</span></code>.
|
|||
|
<code class="computeroutput"><span class="identifier">itest_class</span></code> is just a class
|
|||
|
that has a base hook (<code class="computeroutput"><a class="link" href="../boost/intrusive/list_base_hook.html" title="Class template list_base_hook">list_base_hook</a></code>)
|
|||
|
and also derives from <code class="computeroutput"><span class="identifier">test_class</span></code>.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">func_ptr_adaptor</span></code> is just a
|
|||
|
functor adaptor to convert function objects taking <code class="computeroutput"><span class="identifier">test_list</span></code>
|
|||
|
objects to function objects taking pointers to them.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
You can find the full test code in the <a href="../../../libs/intrusive/perf/perf_list.cpp" target="_top">perf_list.cpp</a>
|
|||
|
source file.
|
|||
|
</p>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h3 class="title">
|
|||
|
<a name="intrusive.performance.performance_results_push_back"></a><a class="link" href="performance.html#intrusive.performance.performance_results_push_back" title="Back insertion and destruction">Back
|
|||
|
insertion and destruction</a>
|
|||
|
</h3></div></div></div>
|
|||
|
<p>
|
|||
|
The first test will measure the benefits we can obtain with intrusive containers
|
|||
|
avoiding memory allocations and deallocations. All the objects to be inserted
|
|||
|
in intrusive containers are allocated in a single allocation call, whereas
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code> will need to allocate memory for each
|
|||
|
object and deallocate it for every erasure (or container destruction).
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
Let's compare the code to be executed for each container type for different
|
|||
|
insertion tests:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">ilist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="identifier">objects</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">);</span>
|
|||
|
<span class="identifier">ilist</span> <span class="identifier">l</span><span class="special">;</span>
|
|||
|
<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"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">objects</span><span class="special">[</span><span class="identifier">i</span><span class="special">]);</span>
|
|||
|
<span class="comment">//Elements are unlinked in ilist's destructor</span>
|
|||
|
<span class="comment">//Elements are destroyed in vector's destructor</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For intrusive containers, all the values are created in a vector and after
|
|||
|
that inserted in the intrusive list.
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">stdlist</span> <span class="identifier">l</span><span class="special">;</span>
|
|||
|
<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"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
|
|||
|
<span class="comment">//Elements unlinked and destroyed in stdlist's destructor</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For a standard list, elements are pushed back using push_back().
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="identifier">objects</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">);</span>
|
|||
|
<span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span>
|
|||
|
<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"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">[</span><span class="identifier">i</span><span class="special">]);</span>
|
|||
|
<span class="comment">//Pointers to elements unlinked and destroyed in stdptrlist's destructor</span>
|
|||
|
<span class="comment">//Elements destroyed in vector's destructor</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For a standard compact pointer list, elements are created in a vector and
|
|||
|
pushed back in the pointer list using push_back().
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">stdlist</span> <span class="identifier">objects</span><span class="special">;</span> <span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span>
|
|||
|
<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"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
|
|||
|
<span class="identifier">objects</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="keyword">typename</span> <span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">.</span><span class="identifier">back</span><span class="special">());</span>
|
|||
|
<span class="special">}</span>
|
|||
|
<span class="comment">//Pointers to elements unlinked and destroyed in stdptrlist's destructor</span>
|
|||
|
<span class="comment">//Elements unlinked and destroyed in stdlist's destructor</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For a <span class="emphasis"><em>disperse pointer list</em></span>, elements are created in
|
|||
|
a list and pushed back in the pointer list using push_back().
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
These are the times in microseconds for each case, and the normalized time:
|
|||
|
</p>
|
|||
|
<div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_times"></a><p class="title"><b>Table 19.2. Back insertion + destruction times for Visual C++ 7.1 / Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Back insertion + destruction times for Visual C++ 7.1 / Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5000 / 22500
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
7812 / 32187
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.56 / 1.43
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
10156 / 41562
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.03 / 1.84
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
26875 / 97500
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5.37 / 4.33
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
76406 / 86718
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
15.28 / 3.85
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
146562 / 175625
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
29.31 / 7.80
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_time0"></a><p class="title"><b>Table 19.3. Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows
|
|||
|
XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows
|
|||
|
XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4375 / 22187
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
7812 / 32812
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.78 / 1.47
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
10468 / 42031
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.39 / 1.89
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
81250 / 98125
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
18.57 / 4.42
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
83750 / 94218
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
19.14 / 4.24
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
155625 / 175625
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
35.57 / 7.91
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_push_back.back_insertion_destruction_time1"></a><p class="title"><b>Table 19.4. Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18
|
|||
|
(OpenSuse 10.2)</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18
|
|||
|
(OpenSuse 10.2)">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4792 / 20495
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
7709 / 30803
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.60 / 1.5
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
10180 / 41183
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.12 / 2.0
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
17031 / 32586
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3.55 / 1.58
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
27221 / 34823
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5.68 / 1.69
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
102272 / 60056
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
21.34 / 2.93
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><p>
|
|||
|
The results are logical: intrusive lists just need one allocation. The destruction
|
|||
|
time of the <code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
container is trivial (complexity: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="number">1</span><span class="special">)</span></code>),
|
|||
|
whereas <code class="computeroutput"><span class="identifier">safe_link</span></code> and <code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive containers need to
|
|||
|
put the hooks of erased values in the default state (complexity: <code class="computeroutput"><span class="identifier">O</span><span class="special">(</span><span class="identifier">NumElements</span><span class="special">)</span></code>). That's why <code class="computeroutput"><span class="identifier">normal_link</span></code>
|
|||
|
intrusive list shines in this test.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
Non-intrusive containers need to make many more allocations and that's why
|
|||
|
they lag behind. The <code class="computeroutput"><span class="identifier">disperse</span> <span class="identifier">pointer</span> <span class="identifier">list</span></code>
|
|||
|
needs to make <code class="computeroutput"><span class="identifier">NumElements</span><span class="special">*</span><span class="number">2</span></code> allocations,
|
|||
|
so the result is not surprising.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
The Linux test shows that standard containers perform very well against intrusive
|
|||
|
containers with big objects. Nearly the same GCC version in MinGW performs
|
|||
|
worse, so maybe a good memory allocator is the reason for these excellent
|
|||
|
results.
|
|||
|
</p>
|
|||
|
</div>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h3 class="title">
|
|||
|
<a name="intrusive.performance.performance_results_reversing"></a><a class="link" href="performance.html#intrusive.performance.performance_results_reversing" title="Reversing">Reversing</a>
|
|||
|
</h3></div></div></div>
|
|||
|
<p>
|
|||
|
The next test measures the time needed to complete calls to the member function
|
|||
|
<code class="computeroutput"><span class="identifier">reverse</span><span class="special">()</span></code>.
|
|||
|
Values (<code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists are created as explained
|
|||
|
in the previous section.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
Note that for pointer lists, <code class="computeroutput"><span class="identifier">reverse</span></code>
|
|||
|
<span class="bold"><strong>does not need to access <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
values stored in another list or vector</strong></span>, since this function just
|
|||
|
needs to adjust internal pointers, so in theory all tested lists need to
|
|||
|
perform the same operations.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
These are the results:
|
|||
|
</p>
|
|||
|
<div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_reversing.reverse_times_for_visual_c_7_1_w"></a><p class="title"><b>Table 19.5. Reverse times for Visual C++ 7.1 / Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Reverse times for Visual C++ 7.1 / Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2656 / 10625
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1.83
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2812 / 10937
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.05 / 1.89
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2710 / 10781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.02 / 1.86
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5781 / 14531
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.17 / 2.51
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5781 / 5781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.17 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
10781 / 15781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4.05 / 2.72
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_reversing.reverse_times_for_gcc_4_1_1_ming"></a><p class="title"><b>Table 19.6. Reverse times for GCC 4.1.1 / MinGW over Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Reverse times for GCC 4.1.1 / MinGW over Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2656 / 10781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 2.22
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2656 / 10781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 2.22
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2812 / 10781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.02 / 2.22
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4843 / 12500
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.82 / 2.58
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4843 / 4843
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.82 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
9218 / 12968
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3.47 / 2.67
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_reversing.reverse_times_for_gcc_4_1_2_linu"></a><p class="title"><b>Table 19.7. Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2742 / 10847
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 3.41
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2742 / 10847
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 3.41
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2742 / 11027
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 3.47
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3184 / 10942
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.16 / 3.44
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3207 / 3176
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.16 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
5814 / 13381
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.12 / 4.21
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><p>
|
|||
|
For small objects the results show that the compact storage of values in
|
|||
|
intrusive containers improve locality and reversing is faster than with standard
|
|||
|
containers, whose values might be dispersed in memory because each value
|
|||
|
is independently allocated. Note that the dispersed pointer list (a list
|
|||
|
of pointers to values allocated in another list) suffers more because nodes
|
|||
|
of the pointer list might be more dispersed, since allocations from both
|
|||
|
lists are interleaved in the code:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="comment">//Object list (holding `test_class`)</span>
|
|||
|
<span class="identifier">stdlist</span> <span class="identifier">objects</span><span class="special">;</span>
|
|||
|
|
|||
|
<span class="comment">//Pointer list (holding `test_class` pointers)</span>
|
|||
|
<span class="identifier">stdptrlist</span> <span class="identifier">l</span><span class="special">;</span>
|
|||
|
|
|||
|
<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"><</span> <span class="identifier">NumElements</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
|
|||
|
<span class="comment">//Allocation from the object list</span>
|
|||
|
<span class="identifier">objects</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">(</span><span class="identifier">i</span><span class="special">));</span>
|
|||
|
<span class="comment">//Allocation from the pointer list</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(&</span><span class="identifier">objects</span><span class="special">.</span><span class="identifier">back</span><span class="special">());</span>
|
|||
|
<span class="special">}</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For big objects the compact pointer list wins because the reversal test doesn't
|
|||
|
need access to values stored in another container. Since all the allocations
|
|||
|
for nodes of this pointer list are likely to be close (since there is no
|
|||
|
other allocation in the process until the pointer list is created) locality
|
|||
|
is better than with intrusive containers. The dispersed pointer list, as
|
|||
|
with small values, has poor locality.
|
|||
|
</p>
|
|||
|
</div>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h3 class="title">
|
|||
|
<a name="intrusive.performance.performance_results_sorting"></a><a class="link" href="performance.html#intrusive.performance.performance_results_sorting" title="Sorting">Sorting</a>
|
|||
|
</h3></div></div></div>
|
|||
|
<p>
|
|||
|
The next test measures the time needed to complete calls to the member function
|
|||
|
<code class="computeroutput"><span class="identifier">sort</span><span class="special">(</span><span class="identifier">Pred</span> <span class="identifier">pred</span><span class="special">)</span></code>. Values (<code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists
|
|||
|
are created as explained in the first section. The values will be sorted
|
|||
|
in ascending and descending order each iteration. For example, if <span class="emphasis"><em>l</em></span>
|
|||
|
is a list:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><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"><</span> <span class="identifier">NumIter</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
|
|||
|
<span class="keyword">if</span><span class="special">(!(</span><span class="identifier">i</span> <span class="special">%</span> <span class="number">2</span><span class="special">))</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">>());</span>
|
|||
|
<span class="keyword">else</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">>());</span>
|
|||
|
<span class="special">}</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
For a pointer list, the function object will be adapted using <code class="computeroutput"><span class="identifier">func_ptr_adaptor</span></code>:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><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"><</span> <span class="identifier">NumIter</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">){</span>
|
|||
|
<span class="keyword">if</span><span class="special">(!(</span><span class="identifier">i</span> <span class="special">%</span> <span class="number">2</span><span class="special">))</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">func_ptr_adaptor</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="special">>());</span>
|
|||
|
<span class="keyword">else</span>
|
|||
|
<span class="identifier">l</span><span class="special">.</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">func_ptr_adaptor</span><span class="special"><</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">less</span><span class="special"><</span><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">></span> <span class="special">>());</span>
|
|||
|
<span class="special">}</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
Note that for pointer lists, <code class="computeroutput"><span class="identifier">sort</span></code>
|
|||
|
will take a function object that <span class="bold"><strong>will access <code class="computeroutput"><span class="identifier">test_class</span></code> values stored in another list
|
|||
|
or vector</strong></span>, so pointer lists will suffer an extra indirection:
|
|||
|
they will need to access the <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
values stored in another container to compare two elements.
|
|||
|
</p>
|
|||
|
<p>
|
|||
|
These are the results:
|
|||
|
</p>
|
|||
|
<div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_sorting.sort_times_for_visual_c_7_1_wind"></a><p class="title"><b>Table 19.8. Sort times for Visual C++ 7.1 / Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Sort times for Visual C++ 7.1 / Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
16093 / 38906
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
16093 / 39062
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
16093 / 38906
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
32343 / 56406
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.0 / 1.44
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
33593 / 46093
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.08 / 1.18
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
46875 / 68593
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.91 / 1.76
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_sorting.sort_times_for_gcc_4_1_1_mingw_o"></a><p class="title"><b>Table 19.9. Sort times for GCC 4.1.1 / MinGW over Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Sort times for GCC 4.1.1 / MinGW over Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
15000 / 39218
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
15156 / 39531
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.01 / 1.01
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
15156 / 39531
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.01 / 1.01
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
34218 / 56875
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.28 / 1.45
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
35468 / 49218
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.36 / 1.25
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
47656 / 70156
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3.17 / 1.78
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_sorting.sort_times_for_gcc_4_1_2_linux_k"></a><p class="title"><b>Table 19.10. Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
18003 / 40795
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
18003 / 41017
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
18230 / 40941
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.01 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
26273 / 49643
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.45 / 1.21
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
28540 / 43172
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.58 / 1.05
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
35077 / 57638
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.94 / 1.41
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><p>
|
|||
|
The results show that intrusive containers are faster than standard containers.
|
|||
|
We can see that the pointer list holding pointers to values stored in a vector
|
|||
|
is quite fast, so the extra indirection that is needed to access the value
|
|||
|
is minimized because all the values are tightly stored, improving caching.
|
|||
|
The disperse list, on the other hand, is slower because the indirection to
|
|||
|
access values stored in the object list is more expensive than accessing
|
|||
|
values stored in a vector.
|
|||
|
</p>
|
|||
|
</div>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h3 class="title">
|
|||
|
<a name="intrusive.performance.performance_results_write_access"></a><a class="link" href="performance.html#intrusive.performance.performance_results_write_access" title="Write access">Write
|
|||
|
access</a>
|
|||
|
</h3></div></div></div>
|
|||
|
<p>
|
|||
|
The next test measures the time needed to iterate through all the elements
|
|||
|
of a list, and increment the value of the internal <code class="computeroutput"><span class="identifier">i_</span></code>
|
|||
|
member:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">stdlist</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">end</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
|
|||
|
<span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span>
|
|||
|
<span class="special">++(</span><span class="identifier">it</span><span class="special">-></span><span class="identifier">i_</span><span class="special">);</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
Values (<code class="computeroutput"><span class="identifier">test_class</span></code> and <code class="computeroutput"><span class="identifier">itest_class</span></code>) and lists are created as explained
|
|||
|
in the first section. Note that for pointer lists, the iteration will suffer
|
|||
|
an extra indirection: they will need to access the <code class="computeroutput"><span class="identifier">test_class</span></code>
|
|||
|
values stored in another container:
|
|||
|
</p>
|
|||
|
<pre class="programlisting"><span class="identifier">stdptrlist</span><span class="special">::</span><span class="identifier">iterator</span> <span class="identifier">it</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">begin</span><span class="special">()),</span> <span class="identifier">end</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
|
|||
|
<span class="keyword">for</span><span class="special">(;</span> <span class="identifier">it</span> <span class="special">!=</span> <span class="identifier">end</span><span class="special">;</span> <span class="special">++</span><span class="identifier">it</span><span class="special">)</span>
|
|||
|
<span class="special">++((*</span><span class="identifier">it</span><span class="special">)-></span><span class="identifier">i_</span><span class="special">);</span>
|
|||
|
</pre>
|
|||
|
<p>
|
|||
|
These are the results:
|
|||
|
</p>
|
|||
|
<div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_write_access.write_access_times_for_visual_c_"></a><p class="title"><b>Table 19.11. Write access times for Visual C++ 7.1 / Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Write access times for Visual C++ 7.1 / Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2031 / 8125
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2031 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1.01
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2031 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1.01
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4218 / 10000
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.07 / 1.23
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4062 / 8437
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.0 / 1.03
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
8593 / 13125
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4.23 / 1.61
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_write_access.write_access_times_for_gcc_4_1_1"></a><p class="title"><b>Table 19.12. Write access times for GCC 4.1.1 / MinGW over Windows XP</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Write access times for GCC 4.1.1 / MinGW over Windows XP">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2343 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2500 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.06 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2500 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.06 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
4218 / 10781
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.8 / 1.3
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3906 / 8281
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.66 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
8281 / 13750
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3.53 / 1.66
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><div class="table">
|
|||
|
<a name="intrusive.performance.performance_results_write_access.write_access_times_for_gcc_4_1_2"></a><p class="title"><b>Table 19.13. Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)</b></p>
|
|||
|
<div class="table-contents"><table class="table" summary="Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)">
|
|||
|
<colgroup>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
<col>
|
|||
|
</colgroup>
|
|||
|
<thead><tr>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Container
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Time in us/iteration (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
<th>
|
|||
|
<p>
|
|||
|
Normalized time (small object / big object)
|
|||
|
</p>
|
|||
|
</th>
|
|||
|
</tr></thead>
|
|||
|
<tbody>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">normal_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2286 / 8468
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1 / 1.1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">safe_link</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2381 / 8412
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.04 / 1.09
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
<code class="computeroutput"><span class="identifier">auto_unlink</span></code> intrusive
|
|||
|
list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2301 / 8437
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.01 / 1.1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
3044 / 9061
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.33 / 1.18
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard compact pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2755 / 7660
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
1.20 / 1
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
<tr>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
Standard disperse pointer list
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
6118 / 12453
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
<td>
|
|||
|
<p>
|
|||
|
2.67 / 1.62
|
|||
|
</p>
|
|||
|
</td>
|
|||
|
</tr>
|
|||
|
</tbody>
|
|||
|
</table></div>
|
|||
|
</div>
|
|||
|
<br class="table-break"><p>
|
|||
|
As with the read access test, the results show that intrusive containers
|
|||
|
outperform all other containers if the values are tightly packed in a vector.
|
|||
|
The disperse list is again the slowest.
|
|||
|
</p>
|
|||
|
</div>
|
|||
|
<div class="section">
|
|||
|
<div class="titlepage"><div><div><h3 class="title">
|
|||
|
<a name="intrusive.performance.performance_results_conclusions"></a><a class="link" href="performance.html#intrusive.performance.performance_results_conclusions" title="Conclusions">Conclusions</a>
|
|||
|
</h3></div></div></div>
|
|||
|
<p>
|
|||
|
Intrusive containers can offer performance benefits that cannot be achieved
|
|||
|
with equivalent non-intrusive containers. Memory locality improvements are
|
|||
|
noticeable when the objects to be inserted are small. Minimizing memory allocation/deallocation
|
|||
|
calls is also an important factor and intrusive containers make this simple
|
|||
|
if all objects to be inserted in intrusive containers are allocated using
|
|||
|
<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span></code> or <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">deque</span></code>.
|
|||
|
</p>
|
|||
|
</div>
|
|||
|
</div>
|
|||
|
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
|
|||
|
<td align="left"></td>
|
|||
|
<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
|
|||
|
Distributed under the Boost Software License, Version 1.0. (See accompanying
|
|||
|
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
|
|||
|
</p>
|
|||
|
</div></td>
|
|||
|
</tr></table>
|
|||
|
<hr>
|
|||
|
<div class="spirit-nav">
|
|||
|
<a accesskey="p" href="design_notes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="release_notes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
|
|||
|
</div>
|
|||
|
</body>
|
|||
|
</html>
|