This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[profile-stdlib][patch] design doc
- From: Silvius Rus <rus at google dot com>
- To: patches at gcc dot gnu dot org
- Cc: Benjamin Kosnik <bkoz at redhat dot com>, libstdc++ at gcc dot gnu dot org, paolo dot carlini at oracle dot com, doug dot gregor at gmail dot com
- Date: Wed, 27 Aug 2008 19:52:07 -0700
- Subject: [profile-stdlib][patch] design doc
This email was sent originally on Aug 13 2008. I just noticed it is not
in the archives and it looks like it got rejected by the mailman.
----
This patch contains the design document of the profile mode.
Some bits are unfinished and some diagnostics are completely omitted in
this version.
I decided to send it out as it is since it has grown quite a bit and we
keep coming up with more and more ideas.
Please let me know what you think about the design. Also, please feel
free to suggest other interesting performance diagnostics.
Thank you,
Silvius
Index: libstdc++-v3/doc/xml/manual/profile_mode.xml
===================================================================
--- libstdc++-v3/doc/xml/manual/profile_mode.xml (revision 0)
+++ libstdc++-v3/doc/xml/manual/profile_mode.xml (revision 0)
@@ -0,0 +1,1548 @@
+<?xml version='1.0'?>
+<!DOCTYPE chapter PUBLIC "-//OASIS//DTD DocBook XML V4.5//EN"
+ "http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd";
+[ ]>
+
+<chapter id="manual.ext.profile_mode" xreflabel="Profile Mode">
+<?dbhtml filename="profile_mode.html"?>
+
+<chapterinfo>
+ <keywordset>
+ <keyword>
+ C++
+ </keyword>
+ <keyword>
+ library
+ </keyword>
+ <keyword>
+ profile
+ </keyword>
+ </keywordset>
+</chapterinfo>
+
+<title>Profile Mode</title>
+
+
+
+<sect1 id="manual.ext.profile_mode.intro" xreflabel="Intro">
+ <title>Intro</title>
+ <para>
+ <emphasis>Goal: </emphasis>Give performance improvement advice based on
+ recognition of suboptimal usage patterns of the standard library.
+ </para>
+
+ <para>
+ <emphasis>Method: </emphasis>Wrap the standard library code. Insert
+ calls to an instrumentation library to record the internal state of
+ various components at interesting entry/exit points to/from the standard
+ library. Process trace, recognize suboptimal patterns, give advice.
+ </para>
+ <para>
+ <emphasis>Strengths: </emphasis>
+<itemizedlist>
+ <listitem><para>
+ Unintrusive solution. The application code does not require any
+ modification.
+ </para></listitem>
+ <listitem><para> The advice is call context sensitive, thus capable of
+ identifying precisely interesting dynamic performance behavior.
+ </para></listitem>
+ <listitem><para>
+ The overhead model is pay-per-view. When you turn off a diagnostic class,
+ its overhead disappears.
+ </para></listitem>
+</itemizedlist>
+ </para>
+ <para>
+ <emphasis>Weaknesses: </emphasis>
+<itemizedlist>
+ <listitem><para>
+ You must recompile the application code with custom options.
+ </para></listitem>
+ <listitem><para>You must run the application on representative input.
+ The advice is input dependent.
+ </para></listitem>
+ <listitem><para>
+ The execution time will increase, in some cases by factors.
+ </para></listitem>
+</itemizedlist>
+ </para>
+
+ <para><emphasis>Example:</emphasis>
+<programlisting>
+cat foo.cc
+#include <unordered_set>
+int main() {
+ unordered_set<int> us;
+ for (int k = 0; k < 1000000; ++k) {
+ us.insert(k);
+ }
+ return us.size();
+}
+
+g++ -fprofile-stdlib foo.cc
+
+./a.out
+
+stdlib-advisor -b ./a.out -f ./profile-stdlib.txt
+foo.cc:3: advice: Changing initial unordered_set size from 10 to 1000000 saves N rehash operations.
+</programlisting>
+ </para>
+
+</sect1>
+
+
+
+<sect1 id="manual.ext.profile_mode.using" xreflabel="Using">
+ <title>Using the Profile Mode</title>
+ <para>
+ The profile mode has to be turned on at application build time.
+<itemizedlist>
+ <listitem><para><code>-D_GLIBCXX_PROFILE</code></para></listitem>
+ <listitem><para><code>-lprofc++</code></para></listitem>
+ <listitem><para>The GCC driver will set these compiler and linker flags
+ when invoked with <code>-fprofile-stdlib</code>.</para></listitem>
+ <listitem><para>Profiling can be turned off dynamically by setting
+ <code>GLIBCXX_PROFILE_OFF</code> to <code>true</code>.
+ This is meant to help debugging and will not necessarily reduce the
+ runtime overhead signficantly.</para></listitem>
+ <listitem><para>For expert users,
+ <code>-D[_NO]_GLIBCXX_PROFILE_<diagnostic></code>
+ can enable/disable specific diagnostics or classes of diagnostics.
+ See section Diagnostics for possible values.</para></listitem>
+ <listitem><para>
+ <code>-D_GLIBCXX_PROFILE_LIGHT</code>
+ will enable only diagnostics with little runtime overhead, such as those
+ that instrument only container construction and destruction.
+ <code>-D_GLIBCXX_PROFILE_MEDIUM</code>
+ will disable diagnostics with very high runtime overhead, such as those
+ relying on iterator instrumentation.
+ <code>-D_GLIBCXX_PROFILE_HEAVY</code> will enable all diagnostics.
+ Not all diagnostics are necessarily enabled by default.
+ </para></listitem>
+ <listitem><para>Additionally, for accurate diagnostics it is important
+ to (1) disable inlining and (2) generate debug information.
+ With GCC, use <code>-fno-inline -g</code>.
+ If inlining is enabled, the advice may appear hoisted to the first
+ parent on the call chain that did not get inlined.
+ If debug info is not generated, the advice will not contain line numbers,
+ though it will contain function names, unless the symbol table is stripped.
+ If the symbol table is stripped, the advice may become confusing.
+ We use symbol names to associate the advice with application code, which
+ is defined as the first site on the call stack for which the symbol in
+ outside the <code>std</code> namespace (and other standard library
+ namespaces, if any).
+ </para></listitem>
+ <listitem><para>Our instrumentation makes frequent calls to libc function
+ <code>backtrace</code>, which depends on the presence of frame pointers.
+ With GCC, the user must turn on <code>-fno-omit-frame-pointer</code>
+ with the profile mode, if they need call context accurate information.
+ <code>_GLIBCXX_PROFILE_STACK_DEPTH</code> can be set
+ to 0 if you are willing to give up call context information. Setting
+ it to a small integer may achieve the desired call context accuracy
+ while keeping the run time overhead low.
+ </para></listitem>
+ <listitem><para>As in the release mode, access to <code>unordered_*</code>
+ containers requires <code>-std=c++0x</code>.</para></listitem>
+</itemizedlist>
+ </para>
+
+Trace generation and interpretation.
+<itemizedlist>
+ <listitem><para>
+ After being built in profile mode, the program
+ must be run to produce an execution trace.
+ </para></listitem>
+ <listitem><para>
+ The trace path is by default <code>./profile-stdlib.txt</code>.
+ It can be overriden by setting environment variable
+ <code>GLIBCXX_PROFILE_TRACE_PATH</code> to a parameterized path,
+ e.g., <code>"$HOME/tmp/%v/%p.profile-stdlib.txt"</code>.
+ In addition to environment variable expansion, <code>%v</code> expands
+ to <code>argv[0]</code> and <code>%p</code> expands to the process id.
+ </para></listitem>
+ <listitem><para>
+ The trace file size can be limited by setting environment variable
+ <code>GLIBCXX_PROFILE_TRACE_SIZE</code> to a number of bytes.
+ If trace size is very important, accuracy can be sacrificed by setting
+ <code>_GLIBCXX_PROFILE_STACK_DEPTH</code> to 0. This means that the trace
+ size will be a constant factor of the number of diagnostics.
+ </para></listitem>
+ <listitem><para>
+ The trace contains partially processed information. To generate advice,
+ you need to run <code>stdlib-advisor</code>, which can be downloaded from
+ http://TODO as a Python script.
+ </para></listitem>
+</itemizedlist>
+</sect1>
+
+
+
+<sect1 id="manual.ext.profile_mode.design" xreflabel="Design">
+ <title>Design</title>
+
+<table frame='all'>
+<title>Code Location</title>
+<tgroup cols='2' align='left' colsep='1' rowsep='1'>
+<colspec colname='c1'></colspec>
+<colspec colname='c2'></colspec>
+
+<thead>
+ <row>
+ <entry>Code Location</entry>
+ <entry>Use</entry>
+ </row>
+</thead>
+<tbody>
+ <row>
+ <entry><code>gcc/gcc.c</code></entry>
+ <entry>Added handles for <code>-fprofile-stdlib</code>.</entry>
+ </row>
+ <row>
+ <entry><code>libstdc++-v3/include/std/*</code></entry>
+ <entry>Added hooks to include instrumented headers when
+ <code>_GLIBCXX_PROFILE</code> is defined.</entry>
+ </row>
+ <row>
+ <entry><code>libstdc++-v3/include/profile/*</code></entry>
+ <entry>New instrumented headers. They get included from the hooks under
+ <code>include/std/</code> when <code>_GLIBCXX_PROFILE</code> is defined.
+ </entry>
+ </row>
+ <row>
+ <entry><code>libstdc++-v3/include/profile/config.h</code></entry>
+ <entry>Compile time switches for instrumentation hooks.</entry>
+ </row>
+ <row>
+ <entry><code>libstdc++-v3/libprofc++/*</code></entry>
+ <entry>New run time library.</entry>
+ </row>
+ <row>
+ <entry><code>stdlib-advisor</code></entry>
+ <entry>New Python script for the final advice phase.
+ Not included in distribution yet.</entry>
+ </row>
+</tbody>
+</tgroup>
+</table>
+
+
+<sect2 id="manual.ext.profile_mode.design.driver"
+ xreflabel="Compiler Driver">
+<title>Compiler Driver</title>
+ <para>
+ <emphasis>Profile collection:</emphasis>
+ The compiler driver translates <code>-fprofile-stdlib</code> into
+ <code>-D_GLIBCXX_PROFILE</code> when invoking the compiler.
+ Fine tuning options
+ <code>-D[_NO]_GLIBCXX_PROFILE_<diagnostic></code>
+ are passed to the compiler to enable specific diagnostics or classes
+ of diagnostics. See section Diagnostics for possible values.
+ The driver also passes <code>-lprofc++</code> to the linker.
+ </para>
+ <para>
+ <emphasis>Profile driven compiler optimization:</emphasis>
+ We hope to be able to use the profiles not only to give advice, but to
+ provide feedback to the compiler. We reserve compiler option
+ <code>-fprofile-stdlib-use</code> for this purpose.
+ </para>
+
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.wrapper"
+ xreflabel="Wrapper">
+<title>Wrapper Model</title>
+ <para>
+ In order to get our instrumented library version included instead of the
+ release one,
+ we use the same wrapper model as the debug mode.
+ We subclass entities from the release version. Wherever
+ <code>_GLIBCXX_PROFILE</code> is defined, the release namespace is
+ <code>std::__norm</code>, whereas the profile namespace is
+ <code>std::__profile</code>. Using plain <code>std</code> translates
+ into <code>std::__profile</code>.
+ </para>
+ <para>
+ Whenever possible, we try to wrap at the public interface level, e.g.,
+ in <code>unordered_set</code> rather than in <code>hashtable</code>,
+ in order not to depend on implementation.
+ </para>
+ <para>
+ Mixing object files built with and without the profile mode must
+ not affect the program execution. However, there are no guarantees to
+ the accuracy of diagnostics when using even a single object not built with
+ <code>-fprofile-stdlib</code>.
+ Similarly, we give no guarantees about mixing profile mode with
+ debug, parallel and other extensions.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.instrumentation"
+ xreflabel="Instrumentation">
+<title>Instrumentation</title>
+ <para>
+ We considered instrumenting every public entry and exit point.
+ Instead, we chose to add instrumentation on demand, as needed
+ by individual diagonistics.
+ The main reason is that some diagnostics require us to extract bits of
+ internal state that are particular only to that diagnostic.
+ We plan to formalize this later, after we learn more about the requirements
+ of several diagnostics.
+ </para>
+ <para>
+ All the instrumentation points can be switched on and off using
+ <code>-D[_NO]_GLIBCXX_PROFILE_<diagnostic></code> options.
+ With all the instrumentation calls off, there should be negligible
+ overhead over the release version. This property is needed to support
+ diagnostics based on timing of internal operations. For such diagnostics,
+ we anticipate turning most of the instrumentation off in order to prevent
+ profiling overhead from polluting time measurements, and thus diagnostics.
+ </para>
+ <para>
+ All the instrumentation on/off compile time switches live in
+ <code>include/profile/config.h</code>.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.rtlib"
+ xreflabel="Run Time Library">
+<title>Run Time Library</title>
+ <para>
+ For practical reasons, the instrumentation library processes the trace
+ partially
+ rather than dumping it to disk in raw form. Each event is processed when
+ it occurs. It is usually attached a cost and it is aggregated into
+ the database of a specific diagnostic class. The cost model
+ is based largely on the standard performance guarantees, but in some
+ cases we use knowledge about GCC's standard library implementation.
+ </para>
+ <para>
+ Information is indexed by (1) call stack and (2) instance id or address
+ to be able to understand and summarize precise creation-use-destruction
+ dynamic chains. Although the analysis is sensitive to dynamic instances,
+ the reports are only sensitive to call context. Whenever a dynamic instance
+ is destroyed, we accumulate its effect to the corresponding entry for the
+ call stack of its constructor location.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.analysis"
+ xreflabel="Analysis and Diagnostics">
+<title>Analysis and Diagnostics</title>
+ <para>
+ Final analysis takes place offline, and it is based entirely on the
+ generated trace and debugging info in the application binary.
+ See section Diagnostics for a list of analysis types that we plan to support.
+ </para>
+ <para>
+ The input to the analysis is a table indexed by profile type and call stack.
+ The data type for each entry depends on the profile type.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.cost-model"
+ xreflabel="Cost Model">
+<title>Cost Model</title>
+ <para>
+ While it is likely that cost models become complex as we get into
+ more sophisticated analysis, we will try to follow a simple set of rules
+ at the beginning.
+ </para>
+<itemizedlist>
+ <listitem><para><emphasis>Relative benefit estimation:</emphasis>
+ The idea is to estimate or measure the cost of all operations
+ in the original scenario versus the scenario we advise to switch to.
+ For instance, when advising to change a vector to a list, an occurrence
+ of the <code>insert</code> method will generally count as a benefit.
+ Its magnitude depends on (1) the number of elements that get shifted
+ and (2) whether it triggers a reallocation.
+ </para></listitem>
+ <listitem><para><emphasis>Synthetic measurements:</emphasis>
+ We will measure the relative difference between similar operations on
+ different containers. We plan to write a battery of small tests that
+ compare the times of the executions of similar methods on different
+ containers. The idea is to run these tests on the target machine.
+ If this training phase is very quick, we may decide to perform it at
+ library initialization time. The results can be cached on disk and reused
+ across runs.
+ </para></listitem>
+ <listitem><para><emphasis>Timers:</emphasis>
+ We plan to use timers for operations of larger granularity, such as sort.
+ For instance, we can switch between different sort methods on the fly
+ and report the one that performs best for each call context.
+ </para></listitem>
+ <listitem><para><emphasis>Show stoppers:</emphasis>
+ We may decide that the presence of an operation nullifies the advice.
+ For instance, when considering switching from <code>set</code> to
+ <code>unordered_set</code>, if we detect use of operator <code>++</code>,
+ we will simply not issue the advice, since this could signal that the use
+ care require a sorted container.</para></listitem>
+</itemizedlist>
+
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.reports"
+ xreflabel="Reports">
+<title>Reports</title>
+ <para>
+There are two types of reports. First, if we recognize a pattern for which
+we have a substitute that is likely to give better performance, we print
+the advice and estimated performance gain. The advice is usually associated
+to a code position and possibly a call stack.
+<programlisting>
+foo.cc:1: advice: Changing initial unordered_set size from 10 to 1000000 saves 1025530 rehash operations.
+</programlisting>
+ </para>
+ <para>
+Second, we report performance characteristics for which we do not have
+a clear solution for improvement. For instance, we can point to the user
+the top 10 <code>set</code> construction locations
+which have the worst data locality in actual traversals, of all the sites
+that create sets in the program. Although this does not offer a solution,
+it helps the user focus on the key problems and ignore the uninteresting ones.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.design.testing"
+ xreflabel="Testing">
+<title>Testing</title>
+ <para>
+ First, we want to make sure we preserve the behavior of the release mode.
+ You can just type <code>make check-profile</code>, which
+ builds and runs the whole test suite in profile mode.
+ </para>
+ <para>
+ Second, we want to test the correctness of each diagnostic.
+ We created a <code>profile</code> directory in the test suite.
+ Each diagnostic must come with at least two tests, one for false positives
+ and one for false negatives.
+ </para>
+</sect2>
+
+</sect1>
+
+
+
+<sect1 id="manual.ext.profile_mode.implementation"
+ xreflabel="Implementation">
+<title>Implementation Issues</title>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.stack"
+ xreflabel="Stack Traces">
+<title>Stack Traces</title>
+ <para>
+ Accurate stack traces are needed during profiling since we group events by
+ call context and dynamic instance. Without accurate traces, diagnostics
+ may be hard to interpret. For instance, when giving advice to the user
+ it is imperative to reference application code, not library code.
+ </para>
+ <para>
+ Currently we are using the libc <code>backtrace</code> routine to get
+ stack traces.
+ <code>_GLIBCXX_PROFILE_STACK_DEPTH</code> can be set
+ to 0 if you are willing to give up call context information, or to a small
+ positive value to reduce run time overhead.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.symbols"
+ xreflabel="Symbolization">
+<title>Symbolization of Instruction Addresses</title>
+ <para>
+ The profiling and analysis phases use only instruction addresses.
+ We translate them into symbols and code location (file:line) just before
+ printing the diagnostic.
+ </para>
+ <para>
+ We are currently using <code>addr2line</code> to get symbol and location
+ information.
+ Symbolization requires access to the unstripped binary, which currently
+ is expected to be available as <code>./a.out</code>. The current
+ interface does not allow passing another binary path to the compiler.
+ However, <code>stdlib-advisor</code> can be passed another path using
+ <code>-b <path></code>.
+ For accurate diagnostics,
+ the code must have been compiled with <code>-g -fno-inline</code>.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.concurrency"
+ xreflabel="Concurrency">
+<title>Concurrency</title>
+ <para>
+ Our current model is simplistic, but precise.
+ We cannot afford to approximate because some of our diagnostics require
+ precise matching of operations to container instance and call context.
+ During profiling, we keep a shared
+ database in which we insert new nodes. All operations are currently
+ guarded by a master lock. As we add more complex analysis methods,
+ we will design private storage and locks of
+ appropriate granularity.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.stdlib-in-proflib"
+ xreflabel="Using the Standard Library in the Runtime Library">
+<title>Using the Standard Library in the Runtime Library</title>
+ <para>
+ As much as we would like to avoid uses of stdlibc++ within our
+ instrumentation library, containers such as unordered_map are very
+ appealing. We plan to use them as long as they are named properly
+ to avoid ambiguity. The library will be built with
+ <code>-D_GNUCXX_PROFILE</code>. The inner standard library code is
+ referenced under the <code>std::__norm</code> namespace.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.malloc-hooks"
+ xreflabel="Malloc Hooks">
+<title>Malloc Hooks</title>
+ <para>
+ Some applications and libraries provide malloc hooks.
+ This can be a show stopper to the profile mode, showing
+ as infinite recursion or
+ deadlock when the malloc hook uses stdlibc++ internally. A reasonable
+ such case is instrumenting malloc to collect use statistics.
+ The statistic collection may use standard library algorithms.
+ The problem comes from the fact that our instrumentation library
+ uses malloc to allocate its internal state, which may result in an
+ infinite loop.
+ </para>
+ <para>
+ For now, the workaround is to ask users to disable any malloc instrumentation
+ that may use the standard library internally.
+ For the future, we plan to provide a simple pool allocator and make all
+ our internal memory allocation go through it.
+ Unfortunately, its implementation cannot use malloc, thus it
+ will be system dependent. This alternate allocator will be used only when
+ environment variable <code>_GCLIBCXX_PROFILE_ALLOC</code> is set to
+ <code>internal</code> in the environment where the application runs.
+ </para>
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.implementation.construction-destruction"
+ xreflabel="Construction and Destruction of Global Objects">
+<title>Construction and Destruction of Global Objects</title>
+ <para>
+ The profiling library state is initialized at the first call to a profiling
+ method. This allows us to record the construction of all global objects.
+ However, we cannot do the same at destruction time. The trace is written
+ by a function registered by <code>atexit</code>, thus invoked by
+ <code>exit</code>. This function will be called before any global
+ destructors. Before writing the trace, we invoke, for each object
+ for which we have recorded construction but not destruction, the
+ instrumentation method of its destructor. This way we not only capture the
+ state of global objects but also of those leaked by dynamic memory
+ allocation.
+ </para>
+</sect2>
+
+
+</sect1>
+
+
+
+<sect1 id="manual.ext.profile_mode.diagnostics"
+ xreflabel="Diagnostics">
+<title>Diagnostics</title>
+
+ <para>
+ The table below presents all the diagnostics we intend to implement.
+ Each diagnostic has a corresponding compile time switch
+ <code>-D_GLIBCXX_PROFILE_<diagnostic></code>.
+ Groups of related diagnostics can be turned on with a single switch.
+ For instance, <code>-D_GLIBCXX_PROFILE_LOCALITY</code> is equivalent to
+ <code>-D_GLIBCXX_PROFILE_SOFTWARE_PREFETCH
+ -D_GLIBCXX_PROFILE_RBTREE_LOCALITY</code>.
+ </para>
+
+ <para>
+ The benefit, cost, expected frequency and accuracy of each diagnostic
+ was given a grade from 1 to 10, where 10 is highest.
+ A high benefit means that, if the diagnostic is accurate, the expected
+ performance improvement is high.
+ A high cost means that turning this diagnostic on leads to high slowdown.
+ A high frequency means that we expect this to occur relatively often.
+ A high accuracy means that the diagnostic is unlikely to be wrong.
+ These grades are not perfect. They are just meant to guide users with
+ specific needs or time budgets.
+ </para>
+
+<table frame='all'>
+<title>Diagnostics</title>
+<tgroup cols='6' align='left' colsep='1' rowsep='1'>
+<colspec colname='c1'></colspec>
+<colspec colname='c2'></colspec>
+<colspec colname='c3'></colspec>
+<colspec colname='c4'></colspec>
+<colspec colname='c5'></colspec>
+<colspec colname='c6'></colspec>
+
+<thead>
+ <row>
+ <entry>Group Flag</entry>
+ <entry>Individual Flag</entry>
+ <entry>Benefit</entry>
+ <entry>Cost</entry>
+ <entry>Freq.</entry>
+ <entry>Accuracy</entry>
+ </row>
+</thead>
+<tbody>
+ <row>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.containers">
+ CONTAINERS</ulink></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.hashtable_too_small">
+ HASHTABLE_TOO_SMALL</ulink></entry>
+ <entry>10</entry>
+ <entry>1</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.hashtable_too_large">
+ HASHTABLE_TOO_LARGE</ulink></entry>
+ <entry>5</entry>
+ <entry>1</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.inefficient_hash">
+ INEFFICIENT_HASH</ulink></entry>
+ <entry>7</entry>
+ <entry>3</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.vector_too_small">
+ VECTOR_TOO_SMALL</ulink></entry>
+ <entry>8</entry>
+ <entry>1</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.vector_too_large">
+ VECTOR_TOO_LARGE</ulink></entry>
+ <entry>5</entry>
+ <entry>1</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.vector_to_hashtable">
+ VECTOR_TO_HASHTABLE</ulink></entry>
+ <entry>7</entry>
+ <entry>7</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.hashtable_to_vector">
+ HASHTABLE_TO_VECTOR</ulink></entry>
+ <entry>7</entry>
+ <entry>7</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.vector_to_list">
+ VECTOR_TO_LIST</ulink></entry>
+ <entry>8</entry>
+ <entry>5</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.list_to_vector">
+ LIST_TO_VECTOR</ulink></entry>
+ <entry>10</entry>
+ <entry>5</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.assoc_ord_to_unord">
+ ORDERED_TO_UNORDERED</ulink></entry>
+ <entry>10</entry>
+ <entry>5</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.algorithms">
+ ALGORITHMS</ulink></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.algorithms.sort">
+ SORT</ulink></entry>
+ <entry>7</entry>
+ <entry>8</entry>
+ <entry></entry>
+ <entry>7</entry>
+ </row>
+ <row>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.locality">
+ LOCALITY</ulink></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.locality.sw_prefetch">
+ SOFTWARE_PREFETCH</ulink></entry>
+ <entry>8</entry>
+ <entry>8</entry>
+ <entry></entry>
+ <entry>5</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.locality.linked">
+ RBTREE_LOCALITY</ulink></entry>
+ <entry>4</entry>
+ <entry>8</entry>
+ <entry></entry>
+ <entry>5</entry>
+ </row>
+ <row>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.mthread">
+ MULTITHREADED</ulink></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.mthread.ddtest">
+ DDTEST</ulink></entry>
+ <entry>8</entry>
+ <entry>10</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+ <row>
+ <entry></entry>
+ <entry><ulink url="#manual.ext.profile_mode.analysis.mthread.false_share">
+ FALSE_SHARING</ulink></entry>
+ <entry>8</entry>
+ <entry>10</entry>
+ <entry></entry>
+ <entry>10</entry>
+ </row>
+</tbody>
+</tgroup>
+</table>
+
+<sect3 id="manual.ext.profile_mode.analysis.template"
+ xreflabel="Template">
+<title>Diagnostic Template</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_<diagnostic></code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> What problem will it diagnose?
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>.
+ What is the fundamental reason why this is a problem</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>
+ Percentage reduction in execution time. When reduction is more than
+ a constant factor, describe the reduction rate formula.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ What would the advise look like?</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis>
+ What stdlibc++ components need to be instrumented?</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ How do we decide when to issue the advice?</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+program code
+...
+advice sample
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+
+<sect2 id="manual.ext.profile_mode.analysis.containers"
+ xreflabel="Containers">
+<title>Containers</title>
+
+<para>
+<emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_CONTAINERS</code>.
+</para>
+
+<sect3 id="manual.ext.profile_mode.analysis.hashtable_too_small"
+ xreflabel="Hashtable Too Small">
+<title>Hashtable Too Small</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect hashtables with many
+ rehash operations, small construction size and large destruction size.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis> Rehash is very expensive.
+ Read content, follow chains within bucket, evaluate hash function, place at
+ new location in different order.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis> 36%.
+ Code similar to example below.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ Set initial size to N at construction site S.
+ </para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis>
+ <code>unordered_set, unordered_map</code> constructor, destructor, rehash.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>unordered_[multi]set|map</code>,
+ record initial size and call context of the constructor.
+ Record size increase, if any, after each relevant operation such as insert.
+ Record the estimated rehash cost.</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 unordered_set<int> us;
+2 for (int k = 0; k < 1000000; ++k) {
+3 us.insert(k);
+4 }
+
+foo.cc:1: advice: Changing initial unordered_set size from 10 to 1000000 saves 1025530 rehash operations.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+
+<sect3 id="manual.ext.profile_mode.analysis.hashtable_too_large"
+ xreflabel="Hashtable Too Large">
+<title>Hashtable Too Large</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect hashtables which are
+ never filled up because fewer elements than reserved are ever
+ inserted.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis> Save memory, which
+ is good in itself and may also improve memory reference performance through
+ fewer cache and TLB misses.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis> unknown.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ Set initial size to N at construction site S.
+ </para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis>
+ <code>unordered_set, unordered_map</code> constructor, destructor, rehash.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>unordered_[multi]set|map</code>,
+ record initial size and call context of the constructor, and correlate it
+ with its size at destruction time.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<unordered_set<int>> v(100000, unordered_set<int>(100)) ;
+2 for (int k = 0; k < 100000; ++k) {
+3 for (int j = 0; j < 10; ++j) {
+4 v[k].insert(k + j);
+5 }
+6 }
+
+foo.cc:1: advice: Changing initial unordered_set size from 100 to 10 saves N
+bytes of memory and may reduce the number of cache and TLB misses.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.inefficient_hash"
+ xreflabel="Inefficient Hash">
+<title>Inefficient Hash</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_INEFFICIENT_HASH</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect hashtables with polarized
+ distribution.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis> A non-uniform
+ distribution may lead to long chains, thus possibly increasing complexity
+ by a factor up to the number of elements.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis> factor up
+ to container size.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis> Change hash function
+ for container built at site S. Distribution score = N. Access score = S.
+ Longest chain = C, in bucket B.
+ </para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis>
+ <code>unordered_set, unordered_map</code> constructor, destructor, [],
+ insert, iterator.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ Compute correlation of actual distribution per bucket to uniform
+ distribution, at destruction time. Report if over a threshold.
+ We could also count the exact number of link traversals, to avoid false
+ positives when longer chains are rarely followed. This would make the
+ analysis more expensive though, for a not-so-likely benefit.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+class dumb_hash {
+ public:
+ size_t operator() (int i) const { return 0; }
+};
+...
+ unordered_set<int, dumb_hash> hs;
+ ...
+ for (int i = 0; i < COUNT; ++i) {
+ hs.find(i);
+ }
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.vector_too_small"
+ xreflabel="Vector Too Small">
+<title>Vector Too Small</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_VECTOR_TOO_SMALL</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis>Detect vectors with many
+ resize operations, small construction size and large destruction size..
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>Resizing can be expensive.
+ Copying large amounts of data takes time. Resizing many small vectors may
+ have allocation overhead and affect locality.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ Set initial size to N at construction site S.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>vector</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>vector</code>,
+ record initial size and call context of the constructor.
+ Record size increase, if any, after each relevant operation such as
+ <code>push_back</code>. Record the estimated resize cost.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<int> v;
+2 for (int k = 0; k < 1000000; ++k) {
+3 v.push_back(k);
+4 }
+
+foo.cc:1: advice: Changing initial vector size from 10 to 1000000 saves
+copying 4000000 bytes and 20 memory allocations and deallocations.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.vector_too_large"
+ xreflabel="Vector Too Large">
+<title>Vector Too Large</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_VECTOR_TOO_LARGE</code>
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis>Detect vectors which are
+ never filled up because fewer elements than reserved are ever
+ inserted.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>Save memory, which
+ is good in itself and may also improve memory reference performance through
+ fewer cache and TLB misses.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ Set initial size to N at construction site S.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>vector</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>vector</code>,
+ record initial size and call context of the constructor, and correlate it
+ with its size at destruction time.</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<vector<int>> v(100000, vector<int>(100)) ;
+2 for (int k = 0; k < 100000; ++k) {
+3 for (int j = 0; j < 10; ++j) {
+4 v[k].insert(k + j);
+5 }
+6 }
+
+foo.cc:1: advice: Changing initial vector size from 100 to 10 saves N
+bytes of memory and may reduce the number of cache and TLB misses.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.vector_to_hashtable"
+ xreflabel="Vector to Hashtable">
+<title>Vector to Hashtable</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_VECTOR_TO_HASHTABLE</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect uses of
+ <code>vector</code> that can be substituted with <code>unordered_set</code>
+ to reduce execution time.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Linear search in a vector is very expensive, whereas searching in a hashtable
+ is very quick.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>factor up
+ to container size.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>Replace
+ <code>vector</code> with <code>unordered_set</code> at site S.
+ </para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>vector</code>
+ operations and access methods.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>vector</code>,
+ record call context of the constructor. Issue the advice only if the
+ only methods called on this <code>vector</code> are <code>push_back</code>,
+ <code>insert</code> and <code>find</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<int> v;
+...
+2 for (int i = 0; i < 1000; ++i) {
+3 find(v.begin(), v.end(), i);
+4 }
+
+foo.cc:1: advice: Changing "vector" to "unordered_set" will save about 500,000
+comparisons.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.hashtable_to_vector"
+ xreflabel="Hashtable to Vector">
+<title>Hashtable to Vector</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_HASHTABLE_TO_VECTOR</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect uses of
+ <code>unordered_set</code> that can be substituted with <code>vector</code>
+ to reduce execution time.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Hashtable iterator is slower than vector iterator.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>95%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>Replace
+ <code>unordered_set</code> with <code>vector</code> at site S.
+ </para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>unordered_set</code>
+ operations and access methods.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>unordered_set</code>,
+ record call context of the constructor. Issue the advice only if the
+ number of <code>find</code>, <code>insert</code> and <code>[]</code>
+ operations on this <code>unordered_set</code> are small relative to the
+ number of elements, and methods <code>begin</code> or <code>end</code>
+ are invoked (suggesting iteration).</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 unordered_set<int> us;
+...
+2 int s = 0;
+3 for (unordered_set<int>::iterator it = us.begin(); it != us.end(); ++it) {
+4 s += *it;
+5 }
+
+foo.cc:1: advice: Changing "unordered_set" to "vector" will save about N
+indirections and may achieve better data locality.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.vector_to_list"
+ xreflabel="Vector to List">
+<title>Vector to List</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_VECTOR_TO_LIST</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect cases where
+ <code>vector</code> could be substituted with <code>list</code> for
+ better performance.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Inserting in the middle of a vector is expensive compared to inserting in a
+ list.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>factor up to
+ container size.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>Replace vector with list
+ at site S.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>vector</code>
+ operations and access methods.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ For each dynamic instance of <code>vector</code>,
+ record the call context of the constructor. Record the overhead of each
+ <code>insert</code> operation based on current size and insert position.
+ Report instance with high insertion overhead.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<int> v;
+2 for (int i = 0; i < 10000; ++i) {
+3 v.insert(v.begin(), i);
+4 }
+
+foo.cc:1: advice: Changing "vector" to "list" will save about 5,000,000
+operations.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.list_to_vector"
+ xreflabel="List to Vector">
+<title>List to Vector</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_LIST_TO_VECTOR</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect cases where
+ <code>list</code> could be substituted with <code>vector</code> for
+ better performance.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Iterating through a vector is faster than through a list.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>64%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>Replace list with vector
+ at site S.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis><code>vector</code>
+ operations and access methods.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ Issue the advice if there are no <code>insert</code> operations.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 list<int> l;
+...
+2 int sum = 0;
+3 for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
+4 sum += *it;
+5 }
+
+foo.cc:1: advice: Changing "list" to "vector" will save about 1000000 indirect
+memory references.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.assoc_ord_to_unord"
+ xreflabel="Ordered to Unordered Associative Container">
+<title>Ordered to Unordered Associative Container</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_ORDERED_TO_UNORDERED</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect cases where ordered
+ associative containers can be replaced with unordered ones.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Insert and search are quicker in a hashtable than in
+ a red-black tree.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>52%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ Replace set with unordered_set at site S.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis>
+ <code>set</code>, <code>multiset</code>, <code>map</code>,
+ <code>multimap</code> methods.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ Issue the advice only if we are not using operator <code>++</code> on any
+ iterator on a particular <code>[multi]set|map</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 set<int> s;
+2 for (int i = 0; i < 100000; ++i) {
+3 s.insert(i);
+4 }
+5 int sum = 0;
+6 for (int i = 0; i < 100000; ++i) {
+7 sum += *s.find(i);
+8 }
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+</sect2>
+
+
+
+<sect2 id="manual.ext.profile_mode.analysis.algorithms"
+ xreflabel="Algorithms">
+<title>Algorithms</title>
+
+ <para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_ALGORITHMS</code>.
+ </para>
+
+<sect3 id="manual.ext.profile_mode.analysis.algorithms.sort"
+ xreflabel="Sorting">
+<title>Sort Algorithm Performance</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_SORT</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Give measure of sort algorithm
+ performance based on actual input. For instance, advise Radix Sort over
+ Quick Sort for a particular call context.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ See papers:
+ <ulink url="http://portal.acm.org/citation.cfm?doid=1065944.1065981";>
+ A framework for adaptive algorithm selection in STAPL</ulink> and
+ <ulink url="http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4228227";>
+ Optimizing Sorting with Machine Learning Algorithms</ulink>.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>60%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis> Change sort algorithm
+ at site S from X Sort to Y Sort.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis> <code>sort</code>
+ algorithm.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ Issue the advice if the cost model tells us that another sort algorithm
+ would do better on this input. Requires us to know what algorithm we
+ are using in our sort implementation in release mode.</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.analysis.locality"
+ xreflabel="Data Locality">
+<title>Data Locality</title>
+
+ <para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_LOCALITY</code>.
+ </para>
+
+<sect3 id="manual.ext.profile_mode.analysis.locality.sw_prefetch"
+ xreflabel="Need Software Prefetch">
+<title>Need Software Prefetch</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_SOFTWARE_PREFETCH</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Discover sequences of indirect
+ memory accesses that are not regular, thus cannot be predicted by
+ hardware prefetchers.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Indirect references are hard to predict and are very expensive when they
+ miss in caches.</para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>25%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis> Insert prefetch
+ instruction.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis> Vector iterator and
+ access operator [].
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ First, get cache line size and page size from system.
+ Then record iterator dereference sequences for which the value is a pointer.
+ For each sequence within a container, issue a warning if successive pointer
+ addresses are not within cache lines and do not form a linear pattern
+ (otherwise they may be prefetched by hardware).
+ If they also step across page boundaries, make the warning stronger.
+ </para>
+ <para>The same analysis applies to containers other than vector.
+ However, we cannot give the same advice for linked structures, such as list,
+ as there is no random access to the n-th element. The user may still be
+ able to benefit from this information, for instance by employing frays (user
+ level light weight threads) to hide the latency of chasing pointers.
+ </para>
+ <para>
+ This analysis is a little oversimplified. A better cost model could be
+ created by understanding the capability of the hardware prefetcher.
+ This model could be trained automatically by running a set of synthetic
+ cases.
+ </para>
+ </listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 int zero = 0;
+2 vector<int*> v(10000000, &zero);
+3 for (int k = 0; k < 10000000; ++k) {
+4 v[random() % 10000000] = new int(k);
+5 }
+6 for (int j = 0; j < 10000000; ++j) {
+7 count += (*v[j] == 0 ? 0 : 1);
+8 }
+
+foo.cc:7: advice: Insert prefetch instruction.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.locality.linked"
+ xreflabel="Linked Structure Locality">
+<title>Linked Structure Locality</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_RBTREE_LOCALITY</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Give measure of locality of
+ objects stored in linked structures (lists, red-black trees and hashtables)
+ with respect to their actual traversal patterns.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>Allocation can be tuned
+ to a specific traversal pattern, to result in better data locality.
+ See paper:
+ <ulink url="http://www.springerlink.com/content/8085744l00x72662/";>
+ Custom Memory Allocation for Free</ulink>.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>30%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis>
+ High scatter score N for container built at site S.
+ Consider changing allocation sequence or choosing a structure conscious
+ allocator.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis> Methods of all
+ containers using linked structures.</para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ First, get cache line size and page size from system.
+ Then record the number of successive elements that are on different line
+ or page, for each traversal method such as <code>find</code>. Give advice
+ only if the ratio between this number and the number of total node hops
+ is above a threshold.</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+ 1 set<int> s;
+ 2 for (int i = 0; i < 10000000; ++i) {
+ 3 s.insert(i);
+ 4 }
+ 5 set<int> s1, s2;
+ 6 for (int i = 0; i < 10000000; ++i) {
+ 7 s1.insert(i);
+ 8 s2.insert(i);
+ 9 }
+...
+ // Fast, better locality.
+10 for (set<int>::iterator it = s.begin(); it != s.end(); ++it) {
+11 sum += *it;
+12 }
+ // Slow, elements are further apart.
+13 for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) {
+14 sum += *it;
+15 }
+
+foo.cc:5: advice: High scatter score NNN for set built here. Consider changing
+the allocation sequence or switching to a structure conscious allocator.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.analysis.mthread"
+ xreflabel="Multithreaded Data Access">
+<title>Multithreaded Data Access</title>
+
+ <para>
+ The diagnostics in this group are not meant to be implemented short term.
+ They require compiler support to know when container elements are written
+ to. Instrumentation can only tell us when elements are referenced.
+ </para>
+
+ <para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_MULTITHREADED</code>.
+ </para>
+
+<sect3 id="manual.ext.profile_mode.analysis.mthread.ddtest"
+ xreflabel="Dependence Violations at Container Level">
+<title>Data Dependence Violations at Container Level</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_DDTEST</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect container elements
+ that are referenced from multiple threads in the parallel region or
+ across parallel regions.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis>
+ Sharing data between threads requires communication and perhaps locking,
+ which may be expensive.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>?%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis> Change data
+ distribution or parallel algorithm.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis> Container access methods
+ and iterators.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ Keep a shadow for each container. Record iterator dereferences and
+ container member accesses. Issue advice for elements referenced by
+ multiple threads. Need compiler support to tell which are writes.
+ See paper: <ulink url="http://portal.acm.org/citation.cfm?id=207110.207148";>
+ The LRPD test: speculative run-time parallelization of loops with
+ privatization and reduction parallelization</ulink>.
+ </para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+<sect3 id="manual.ext.profile_mode.analysis.mthread.false_share"
+ xreflabel="False Sharing">
+<title>False Sharing</title>
+<itemizedlist>
+ <listitem><para><emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_FALSE_SHARING</code>.
+ </para></listitem>
+ <listitem><para><emphasis>Goal:</emphasis> Detect elements in the
+ same container which share a cache line, are written by at least one
+ thread, and accessed by different threads.
+ </para></listitem>
+ <listitem><para><emphasis>Fundamentals:</emphasis> Under these assumptions,
+ cache protocols require
+ communication to invalidate lines, which may be expensive.
+ </para></listitem>
+ <listitem><para><emphasis>Sample runtime reduction:</emphasis>68%.
+ </para></listitem>
+ <listitem><para><emphasis>Recommendation:</emphasis> Reorganize container
+ or use padding to avoid false sharing.</para></listitem>
+ <listitem><para><emphasis>To instrument:</emphasis> Container access methods
+ and iterators.
+ </para></listitem>
+ <listitem><para><emphasis>Analysis:</emphasis>
+ First, get the cache line size.
+ For each shared container, record all the associated iterator dereferences
+ and member access methods with the thread id. Compare the address lists
+ across threads to detect references in two different threads to the same
+ cache line. Need compiler support to verify that at least one of them
+ is a write. Issue a warning only if the ratio to total references is
+ significant. Do the same for iterator dereference values if they are
+ pointers.</para></listitem>
+ <listitem><para><emphasis>Cost model:</emphasis>
+ How do we measure benefits? Math goes here.</para></listitem>
+ <listitem><para><emphasis>Example:</emphasis>
+<programlisting>
+1 vector<int> v(2, 0);
+2 #pragma omp parallel for shared(v, SIZE) schedule(static, 1)
+3 for (i = 0; i < SIZE; ++i) {
+4 v[i % 2] += i;
+5 }
+
+OMP_NUM_THREADS=2 ./a.out
+foo.cc:1: advice: Change container structure or padding to avoid false
+sharing in multithreaded access at foo.cc:4. Detected N shared cache lines.
+</programlisting>
+</para></listitem>
+</itemizedlist>
+</sect3>
+
+</sect2>
+
+
+<sect2 id="manual.ext.profile_mode.analysis.statistics"
+ xreflabel="Statistics">
+<title>Statistics</title>
+
+<para>
+<emphasis>Switch:</emphasis>
+ <code>_GLIBCXX_PROFILE_STATISTICS</code>.
+</para>
+
+<para>
+ In some cases the cost model may not tell us anything because the costs
+ appear to offset the benefits. Consider the choice between a vector and
+ a list. When there are both inserts and iteration, an automatic advice
+ may not be issued. However, the programmer may still be able to make use
+ of this information in a different way.
+</para>
+<para>
+ This diagnostic will not issue any advice, but it will print statistics for
+ each container construction site. The statistics will contain the cost
+ of each operation actually performed on the container.
+</para>
+
+</sect2>
+
+
+</sect1>
+
+
+
+</chapter>
Index: libstdc++-v3/doc/xml/manual/debug.xml
===================================================================
--- libstdc++-v3/doc/xml/manual/debug.xml (revision 138063)
+++ libstdc++-v3/doc/xml/manual/debug.xml (working copy)
@@ -242,4 +242,12 @@
</para>
</sect2>
-</sect1>
\ No newline at end of file
+<sect2 id="debug.profile_mode" xreflabel="debug.profile_mode">
+<title>Profile-based Performance Analysis</title>
+ <para> The <link linkend="manual.ext.profile_mode">Profile-based
+ Performance Analysis</link> Extension has performance checks for many
+ algorithms.
+ </para>
+</sect2>
+
+</sect1>
Index: libstdc++-v3/doc/xml/manual/extensions.xml
===================================================================
--- libstdc++-v3/doc/xml/manual/extensions.xml (revision 138063)
+++ libstdc++-v3/doc/xml/manual/extensions.xml (working copy)
@@ -110,6 +110,12 @@
parse="xml" href="parallel_mode.xml">
</xi:include>
+<!-- Chapter XX : Profile Mode -->
+<xi:include xmlns:xi="http://www.w3.org/2001/XInclude";
+ parse="xml" href="profile_mode.xml">
+</xi:include>
+
+
<!-- Chapter 04 : Allocators -->
<chapter id="manual.ext.allocator" xreflabel="Allocators">
<title>Allocators</title>
Index: libstdc++-v3/doc/Makefile.in
===================================================================
--- libstdc++-v3/doc/Makefile.in (revision 138063)
+++ libstdc++-v3/doc/Makefile.in (working copy)
@@ -325,6 +325,7 @@
${xml_srcdir}/manual/mt_allocator.xml \
${xml_srcdir}/manual/numerics.xml \
${xml_srcdir}/manual/parallel_mode.xml \
+ ${xml_srcdir}/manual/profile_mode.xml \
${xml_srcdir}/manual/internals.xml \
${xml_srcdir}/manual/shared_ptr.xml \
${xml_srcdir}/manual/spine.xml \
Index: libstdc++-v3/doc/Makefile.am
===================================================================
--- libstdc++-v3/doc/Makefile.am (revision 138063)
+++ libstdc++-v3/doc/Makefile.am (working copy)
@@ -101,6 +101,7 @@
${xml_srcdir}/manual/mt_allocator.xml \
${xml_srcdir}/manual/numerics.xml \
${xml_srcdir}/manual/parallel_mode.xml \
+ ${xml_srcdir}/manual/profile_mode.xml \
${xml_srcdir}/manual/internals.xml \
${xml_srcdir}/manual/shared_ptr.xml \
${xml_srcdir}/manual/spine.xml \