473 lines
19 KiB
HTML
473 lines
19 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0.1 Transitional//EN">
|
|
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
|
|
<title>Boost.Flyweight Documentation - Performance</title>
|
|
<link rel="stylesheet" href="style.css" type="text/css">
|
|
<link rel="start" href="index.html">
|
|
<link rel="prev" href="reference/tracking.html">
|
|
<link rel="up" href="index.html">
|
|
<link rel="next" href="examples.html">
|
|
</head>
|
|
|
|
<body>
|
|
<h1><img src="../../../boost.png" alt="Boost logo" align=
|
|
"middle" width="277" height="86">Boost.Flyweight Performance</h1>
|
|
|
|
<div class="prev_link"><a href="reference/tracking.html"><img src="prev.gif" alt="tracking policies" border="0"><br>
|
|
Tracking policies
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
|
|
Index
|
|
</a></div>
|
|
<div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br>
|
|
Examples
|
|
</a></div><br clear="all" style="clear: all;">
|
|
<br clear="all" style="clear: all;">
|
|
|
|
<hr>
|
|
|
|
<h2>Contents</h2>
|
|
|
|
<ul>
|
|
<li><a href="#intro">Introduction</a></li>
|
|
<li><a href="#memory">Memory consumption</a>
|
|
<ul>
|
|
<li><a href="#flyweight_size">Flyweight size</a></li>
|
|
<li><a href="#entry_size">Entry size</a></li>
|
|
<li><a href="#overall_memory">Overall memory consumption</a></li>
|
|
</ul>
|
|
</li>
|
|
<li><a href="#time">Time efficiency</a>
|
|
<ul>
|
|
<li><a href="#initialization">Initialization</a></li>
|
|
<li><a href="#assignment">Assignment</a></li>
|
|
<li><a href="#equality_comparison">Equality comparison</a></li>
|
|
<li><a href="#value_access">Value access</a></li>
|
|
</ul>
|
|
</li>
|
|
<li><a href="#results">Experimental results</a>
|
|
<ul>
|
|
<li><a href="#msvc_80">Microsoft Visual C++ 8.0</a>
|
|
<ul>
|
|
<li><a href="#msvc_80_memory">Memory</a></li>
|
|
<li><a href="#msvc_80_time">Execution time</a></li>
|
|
</ul>
|
|
</li>
|
|
<li><a href="#gcc_344">GCC 3.4.4</a>
|
|
<ul>
|
|
<li><a href="#gcc_344_memory">Memory</a></li>
|
|
<li><a href="#gcc_344_time">Execution time</a></li>
|
|
</ul>
|
|
</li>
|
|
</ul>
|
|
</li>
|
|
<li><a href="#conclusions">Conclusions</a></li>
|
|
</ul>
|
|
|
|
<h2><a name="intro">Introduction</a></h2>
|
|
|
|
<p>
|
|
We show how to estimate the memory reduction obtained by the usage of
|
|
Boost.Flyweight in a particular scenario and study the impact on the execution
|
|
time for the different functional areas of <code>flyweight</code>.
|
|
Some experimental results are provided.
|
|
</p>
|
|
|
|
<h2><a name="memory">Memory consumption</a></h2>
|
|
|
|
<p>
|
|
As we saw in the <a href="tutorial/index.html#rationale">tutorial rationale</a>,
|
|
the flyweight pattern is based on two types of objects:
|
|
<ul>
|
|
<li>The flyweight objects proper, which have very small size, typically
|
|
that of a pointer.
|
|
</li>
|
|
<li>The shared values, which are stored as internal <i>entries</i> into the
|
|
flyweight factory.
|
|
</li>
|
|
</ul>
|
|
The overall memory consumption is then a function of the size of the
|
|
flyweight objects, the size of the entry objects and the degree of
|
|
value redundancy.
|
|
</p>
|
|
|
|
<h3><a name="flyweight_size">Flyweight size</a></h3>
|
|
|
|
<p>
|
|
The only data member of a <code>flyweight</code> object is a so-called
|
|
<i>handle</i>, an opaque object of small size provided by the internal
|
|
flyweight factory to refer to the entries it stores. For the default
|
|
<a href="tutorial/configuration.html#hashed_factory"><code>hashed_factory</code></a>,
|
|
this handle is merely a pointer, so <code>sizeof(flyweight<T>)=sizeof(void*)</code>,
|
|
4 bytes in typical 32-bit architectures.
|
|
For other types of factories, the handle is an iterator to an internal
|
|
container used in the implementation of the factory: again, its size
|
|
is typically that of a pointer.
|
|
</p>
|
|
|
|
<h3><a name="entry_size">Entry size</a></h3>
|
|
|
|
<p>
|
|
The entries stored in the factory associated to <code>flyweight<T,...></code>
|
|
need not only hold a value of <code>T</code>, but also contain additional
|
|
information related to the internal implementation of
|
|
<code>flyweight<T,...></code>:
|
|
</p>
|
|
|
|
<blockquote>
|
|
<i>entry</i> = <code>sizeof(T)</code> + <i>overhead</i>.
|
|
</blockquote>
|
|
|
|
<p>
|
|
For the current implementation of Boost.Flyweight, the following aspects
|
|
contribute to <i>overhead</i>:
|
|
<ul>
|
|
<li>Usage of <a href="tutorial/key_value.html">key-value flyweights</a>.</li>
|
|
<li>Internal overhead of the <a href="tutorial/configuration.html#factories">factory</a>
|
|
container.
|
|
</li>
|
|
<li>Bookkeeping information associated to the
|
|
<a href="tutorial/configuration.html#tracking">tracking mechanism</a>.
|
|
</li>
|
|
</ul>
|
|
The table summarizes the separate contributions to <i>overhead</i> introduced
|
|
by the different components taking part of the definition of
|
|
a <code>flyweight</code> instantiation. Values are given in <i>words</i>,
|
|
i.e. the size of a pointer, which is 4 bytes in a typical 32-bit architecture.
|
|
Alignment may introduce additional overhead.
|
|
</p>
|
|
|
|
<p align="center">
|
|
<table cellspacing="0">
|
|
<caption><b>Entry overhead of the components of Boost.Flyweight.</b></caption>
|
|
<tr>
|
|
<th align="center"colspan="2">component</th>
|
|
<th align="center">overhead (words)</th>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" rowspan="2"> <a href="tutorial/key_value.html#key_value"><code>key_value</code></a> </td>
|
|
<td align="center"> with <a href="tutorial/key_value.html#key_extractor">key extractor</a> </td>
|
|
<td align="center"> 1<sup>(1)</sup> </td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center"> without <a href="tutorial/key_value.html#key_extractor">key extractor</a> </td>
|
|
<td align="center"> 1 + <code>sizeof(Key) </td>
|
|
</tr>
|
|
<tr class="odd_tr">
|
|
<td align="center" rowspan="3"> factory </td>
|
|
<td align="center"> <a href="tutorial/configuration.html#hashed_factory"><code>hashed_factory</code></a> </td>
|
|
<td align="center"> ~2.5 </td>
|
|
</tr>
|
|
<tr class="odd_tr">
|
|
<td align="center"> <a href="tutorial/configuration.html#set_factory"><code>set_factory</code></a> </td>
|
|
<td align="center"> 4<sup>(2)</sup> </td>
|
|
</tr>
|
|
<tr class="odd_tr">
|
|
<td align="center"> <a href="tutorial/configuration.html#assoc_container_factory"><code>assoc_container_factory</code></a> </td>
|
|
<td align="center"> depends on the container used </td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center" rowspan="2"> tracking mechanism </td>
|
|
<td align="center"> <a href="tutorial/configuration.html#refcounted"><code>refcounted</code></a> </td>
|
|
<td align="center"> 2<sup>(3)</sup> </td>
|
|
</tr>
|
|
<tr>
|
|
<td align="center"> <a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a> </td>
|
|
<td align="center"> 0 </td>
|
|
</tr>
|
|
</table>
|
|
<sup>(1)</sup> <small>Assuming that <code>sizeof(Key)<=sizeof(Value)</code>.</small><br>
|
|
<sup>(2)</sup> <small>For some implementations of <code>std::set</code> this overhead reduces to 3.</small><br>
|
|
<sup>(3)</sup> <small>In some platforms this value can be 3.</small>
|
|
</p>
|
|
|
|
<p>
|
|
For instance, for the default configuration parameters of <code>flyweight</code>,
|
|
<i>overhead</i> is typically 2.5(<code>hashed_factory</code>) + 2(<code>refcounted</code>)
|
|
= 4.5 words.
|
|
</p>
|
|
|
|
<h3><a name="overall_memory">Overall memory consumption</a></h3>
|
|
|
|
<p>
|
|
Consider a scenario where there are <i>N</i> different objects of type <code>T</code>
|
|
jointly taking <i>M</i> different values. The objects consume then
|
|
<i>S</i> = <i>N</i>·<i>T</i> bytes, where <i>T</i> is defined as the
|
|
average size of <code>T</code> (<code>sizeof(T)</code> plus dynamic
|
|
memory allocated by <code>T</code> objects).
|
|
If we now replace <code>T</code> by some instantiation
|
|
<code>flyweight<T,...></code>, the resulting memory consumption
|
|
will be
|
|
</p>
|
|
|
|
<blockquote>
|
|
<i>S<sub>F</sub></i> =
|
|
<i>N</i>·<i>P</i> + <i>M</i>·(<i>T</i> + <i>overhead</i>),
|
|
</blockquote>
|
|
|
|
<p>
|
|
where <i>P</i> is <code>sizeof(flyweight<T,...>)</code>, typically
|
|
equal to <code>sizeof(void*)</code>, as seen <a href="#flyweight_size">before</a>.
|
|
The ratio <i>S<sub>F</sub></i> / <i>S</i> is then
|
|
</p>
|
|
|
|
<blockquote>
|
|
<i>S<sub>F</sub></i> / <i>S</i> =
|
|
(<i>P</i> / <i>T</i>)+ (<i>M</i> / <i>N</i>)(1 + <i>overhead</i> / <i>T</i>).
|
|
</blockquote>
|
|
|
|
<p>
|
|
<i>S<sub>F</sub></i> / <i>S</i> tends to its minimum, <i>P</i> / <i>T</i>,
|
|
as <i>M</i> / <i>N</i> tends to 0, i.e. when the degree of value redundancy
|
|
among <code>T</code> objects grows higher. On the other hand, the worst possible case
|
|
<i>S<sub>F</sub></i> / <i>S</i> = 1 + (<i>P</i> + <i>overhead</i>) / <i>T</i>
|
|
happens when <i>M</i> / <i>N</i> = 1, that is, if there is no value redundancy at all; in this situation there is
|
|
no point in applying the flyweight pattern in the first place.
|
|
</p>
|
|
|
|
<p align="center">
|
|
<img src="memory.png" alt="relative memory consumption of Boost.Flyweight as a function of value diversity"
|
|
width="446" height="411"><br>
|
|
<b>Fig. 1: Relative memory consumption of Boost.Flyweight as a function of value diversity.</b>
|
|
</p>
|
|
|
|
<h2>
|
|
<a name="time">Time efficiency</a>
|
|
</h2>
|
|
|
|
<p>
|
|
The introduction of the flyweight pattern involves an extra level of indirection
|
|
that, in general, results in some execution overhead when accessing the values. On
|
|
the other hand, manipulation of flyweight objects is considerably faster than
|
|
moving around the heavy values they stand for. We analyze qualitatively the
|
|
execution overheads or improvements associated to the different usage contexts
|
|
of Boost.Flyweight.
|
|
</p>
|
|
|
|
<h3><a name="initialization">Initialization</a></h3>
|
|
|
|
<p>
|
|
As compared with the initialization an object of type <code>T</code>, constructing
|
|
a <code>flyweight<T></code> performs important extra work like looking
|
|
up the value in the flyweight factory and inserting it if it is not present.
|
|
So, construction of flyweights (other than copy construction, which is
|
|
cheap), is expected to be noticeably slower than the construction of the
|
|
underlying type <code>T</code>. Much of the time spent at constructing
|
|
the associated <code>T</code> value proper can be saved, however, by
|
|
using <a href="tutorial/key_value.html">key-value flyweights</a>.
|
|
</p>
|
|
|
|
<h3><a name="assignment">Assignment</a></h3>
|
|
|
|
<p>
|
|
Assignment of flyweight objects is extremely fast, as it only involves
|
|
assigning an internal handle type used to refer to the shared value. Moreover,
|
|
assignment of <code>flyweight</code> objects never throws. Assignment time
|
|
is influenced by the type of <a href="tutorial/configuration.html#tracking">tracking
|
|
policy</a> used; in this regard,
|
|
<a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>
|
|
is the fastest option.
|
|
</p>
|
|
|
|
<h3><a name="equality_comparison">Equality comparison</a></h3>
|
|
|
|
<p>
|
|
Comparing two <code>flyweight</code> objects for equality reduces to
|
|
checking that the <i>addresses</i> of the values they are associated to
|
|
are equal; in general, this operation is much faster than comparing the
|
|
underlying values. This aspect is of particular relevance when the flyweight
|
|
objects stand for complex values like those arising in the application of
|
|
the <a href="examples.html#example3"><i>composite pattern</i></a>.
|
|
</p>
|
|
|
|
<h3><a name="value_access">Value access</a></h3>
|
|
|
|
<p>
|
|
The conversion from <code>flyweight<T></code> to <code>const T&</code>
|
|
relies on a level of indirection relating the flyweight objects to the
|
|
values they are associated to; so, value access is expected to be slower
|
|
when using Boost.Flyweight as compared to using the associated values
|
|
directly. This overhead, however, can be masked by an indirect improvement
|
|
resulting from locality and cache effects: as the set of different <code>T</code>
|
|
values handled by an instantiation of <code>flyweight<T></code> is
|
|
generally much smaller than the equivalent family of <code>T</code> objects
|
|
when Boost.Flyweight is not used, active values can fit better
|
|
into the processor cache.
|
|
</p>
|
|
|
|
<h2><a name="results">Experimental results</a></h2>
|
|
|
|
<p>
|
|
A <a href="examples.html#example7">profiling program</a> was devised to test
|
|
the space and time efficiency of different instantiations of <code>flyweight</code>
|
|
against a base situation not using Boost.Flyweight. The profiled scenarios are:
|
|
<ol>
|
|
<li><code>std::string</code>.</li>
|
|
<li><code>flyweight<std::string></code> with default configuration aspects
|
|
(<a href="tutorial/configuration.html#hashed_factory"><code>hashed_factory</code></a>,
|
|
<a href="tutorial/configuration.html#refcounted"><code>refcounted</code></a> tracking,
|
|
<a href="tutorial/configuration.html#simple_locking"><code>simple_locking</code></a>).
|
|
</li>
|
|
<li><code>flyweight<std::string,<a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>></code>.</li>
|
|
<li><code>flyweight<std::string,<a href="tutorial/configuration.html#set_factory"><code>set_factory</code></a>></code>.</li>
|
|
<li><code>flyweight<std::string,<a href="tutorial/configuration.html#set_factory"><code>set_factory</code></a>,<a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>></code>.</li>
|
|
</ol>
|
|
</p>
|
|
|
|
<p>
|
|
Actually the types tested are not exactly those listed above, but instrumented
|
|
versions that keep track of the allocated memory for profiling purposes.
|
|
The program parses a text file into an array of words and then perform various
|
|
manipulations involving the different context usages of Boost.Flyweight discussed
|
|
<a href="#time">previously</a>. As our text file we have used the
|
|
<a href="http://www.gutenberg.org/dirs/etext99/2donq10.txt">plain text</a>
|
|
version of Project Gutenberg edition of <a href="http://www.gutenberg.org/etext/2000"><i>Don
|
|
Quijote</i></a> (2.04 MB).
|
|
</p>
|
|
|
|
<h3><a name="msvc_80">Microsoft Visual C++ 8.0</a></h3>
|
|
|
|
<p>
|
|
The program was built with default release settings and <code>_SECURE_SCL=0</code>.
|
|
Tests were run under Windows XP in a machine equipped with an Intel Core 2 Duo T5500
|
|
processor and 1 GB of RAM.
|
|
</p>
|
|
|
|
<h4><a name="msvc_80_memory">Memory</a></h4>
|
|
|
|
<p align="center">
|
|
<img src="memory_msvc_80.png" alt="memory consumption (MB), MSVC++ 8.0"
|
|
width="798" height="323"><br>
|
|
<b>Fig. 2: Memory consumption, MSVC++ 8.0. Values in MB.</b>
|
|
</p>
|
|
|
|
<p>
|
|
The results show the memory consumption figures for the different profiled
|
|
scenarios.
|
|
The standard library implementation of MSVC++ 8.0 features the so-called
|
|
small buffer optimization for strings, by which <code>std::string</code>
|
|
objects hold a small buffer that can be used when the string is short,
|
|
thus avoding dynamic allocations. This results in <code>sizeof(std::string)</code>
|
|
being quite high, 28 bytes. In our particular test strings are almost always
|
|
held in the small buffer, so the minimum <a href="#overall_memory"><i>S<sub>F</sub></i> / <i>S</i></a>
|
|
achievable is 4/28 = 14.3%, which is quite close to the experimental
|
|
results, given that the memory devoted to storage of shared values
|
|
is residual (around 3% of total memory) due to the high word redundancy
|
|
of the text source.
|
|
</p>
|
|
|
|
<h4><a name="msvc_80_time">Execution time</a></h4>
|
|
|
|
<p align="center">
|
|
<img src="time_msvc_80.png" alt="execution time (s), MSVC++ 8.0"
|
|
width="820" height="325"><br>
|
|
<b>Fig. 3: Execution time, MSVC++ 8.0. Values in seconds.</b>
|
|
</p>
|
|
|
|
<p>
|
|
The figure displays execution times for the profiled scenarios in different
|
|
usage contexts. In accordance with our previous
|
|
<a href="#time">qualitative analysis</a>, initialization of <code>flyweight</code>s
|
|
carries an important overhead with respect to the base case scenario (between 20% and 40%
|
|
of additional execution time), while the other usage contexts
|
|
(assignment, equality comparison and value access) have performance gains,
|
|
with speedup factors of more than 10 in some cases. The use of a
|
|
<a href="tutorial/configuration.html#refcounted"><code>refcounted</code></a>
|
|
tracking policy introduces penalties with respect to
|
|
<a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>
|
|
in initialization and assignment, but has no effect in equality comparison
|
|
and value access.
|
|
</p>
|
|
|
|
<h3><a name="gcc_344">GNU GCC 3.4.4</a></h3>
|
|
|
|
<p>
|
|
The Cygwin/MinGW version of the compiler was used, with command options
|
|
<code>-ftemplate-depth-128 -O3 -finline-functions -DNDEBUG</code>.
|
|
Tests were run under a Cygwin terminal in the same machine as <a href="#msvc_80">before</a>.
|
|
</p>
|
|
|
|
<h4><a name="gcc_344_memory">Memory</a></h4>
|
|
|
|
<p align="center">
|
|
<img src="memory_gcc_344.png" alt="memory consumption (MB), GCC 3.4.4"
|
|
width="798" height="323"><br>
|
|
<b>Fig. 4: Memory consumption, GCC 3.4.4. Values in MB.</b>
|
|
</p>
|
|
|
|
<p>
|
|
The standard library used by GCC 3.4.4 implements <code>std::string</code>
|
|
using <a href="http://en.wikipedia.org/wiki/Copy-on-write">copy-on-write</a>
|
|
optimization techniques, which leads to very small value redundancy for
|
|
some usage patterns. This explains why the memory reduction achieved
|
|
by Boost.Flyweight is so poor in this case. Other contexts where assignment
|
|
is much less used than direct construction will favor Boost.Flyweight
|
|
over plain copy-on-write <code>std::string</code>s.
|
|
</p>
|
|
|
|
<h4><a name="gcc_344_time">Execution time</a></h4>
|
|
|
|
<p align="center">
|
|
<img src="time_gcc_344.png" alt="execution time (s), GCC 3.4.4"
|
|
width="820" height="325"><br>
|
|
<b>Fig. 5: Execution time, GCC 3.4.4. Values in seconds.</b>
|
|
</p>
|
|
|
|
<p>
|
|
Relative performance figures are similar to those obtained for
|
|
<a href="#msvc_80_time">MSVC++ 8.0</a>, although some of the
|
|
speedups achieved by Boost.Flyweight are higher here (×25
|
|
in equality comparison and up to ×100 in assignment when
|
|
<a href="tutorial/configuration.html#no_tracking"><code>no_tracking</code></a>
|
|
is in effect).
|
|
</p>
|
|
|
|
<h2><a name="conclusions">Conclusions</a></h2>
|
|
|
|
<p>
|
|
The introduction of Boost.Flyweight in application scenarios with very
|
|
high value redundancy yields important reductions in memory consumption:
|
|
this is especially relevant when data volume approaches the limits of
|
|
physical memory in the machine, since Boost.Flyweight can avoid virtual
|
|
memory thrashing thus making the application viable. We have shown
|
|
how to estimate the achievable reduction in memory consumption from
|
|
some basic value statistics and knowledge of the <code>flyweight</code>
|
|
configuration aspects being used.
|
|
</p>
|
|
|
|
<p>
|
|
Boost.Flyweight can also accelerate execution times in areas other than
|
|
object initialization, due to the fastest manipulation of small
|
|
flyweight objects and to locality and cache effects arising from the
|
|
drastic reduction of the set of allocated values.
|
|
</p>
|
|
|
|
<hr>
|
|
|
|
<div class="prev_link"><a href="reference/tracking.html"><img src="prev.gif" alt="tracking policies" border="0"><br>
|
|
Tracking policies
|
|
</a></div>
|
|
<div class="up_link"><a href="index.html"><img src="up.gif" alt="index" border="0"><br>
|
|
Index
|
|
</a></div>
|
|
<div class="next_link"><a href="examples.html"><img src="next.gif" alt="examples" border="0"><br>
|
|
Examples
|
|
</a></div><br clear="all" style="clear: all;">
|
|
<br clear="all" style="clear: all;">
|
|
|
|
<br>
|
|
|
|
<p>Revised September 1st 2014</p>
|
|
|
|
<p>© Copyright 2006-2014 Joaquín M López Muñoz.
|
|
Distributed under the Boost Software
|
|
License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
|
|
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
|
|
http://www.boost.org/LICENSE_1_0.txt</a>)
|
|
</p>
|
|
|
|
</body>
|
|
</html>
|