123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472 |
- <!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>
|