<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Diagnostics</title><meta name="generator" content="DocBook XSL Stylesheets V1.75.2" /><meta name="keywords" content=" C++ , library , profile " /><meta name="keywords" content=" ISO C++ , library " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="profile_mode.html" title="Chapter
32. Profile Mode" /><link rel="prev" href="bk01pt12ch32s06.html" title="Developer Information" /><link rel="next" href="ext_allocators.html" title="Chapter 33. Allocators" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Diagnostics</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt12ch32s06.html">Prev</a> </td><th width="60%" align="center">Chapter 32. Profile Mode</th><td width="20%" align="right"> <a accesskey="n" href="ext_allocators.html">Next</a></td></tr></table><hr /></div><div class="sect1" title="Diagnostics"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.profile_mode.diagnostics"></a>Diagnostics</h2></div></div></div><p>
+<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Diagnostics</title><meta name="generator" content="DocBook XSL Stylesheets V1.75.2" /><meta name="keywords" content=" C++ , library , profile " /><meta name="keywords" content=" ISO C++ , library " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="profile_mode.html" title="Chapter
19. Profile Mode" /><link rel="prev" href="bk01pt03ch19s06.html" title="Developer Information" /><link rel="next" href="ext_allocators.html" title="Chapter 20. Allocators" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Diagnostics</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt03ch19s06.html">Prev</a> </td><th width="60%" align="center">Chapter 19. Profile Mode</th><td width="20%" align="right"> <a accesskey="n" href="ext_allocators.html">Next</a></td></tr></table><hr /></div><div class="sect1" title="Diagnostics"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.profile_mode.diagnostics"></a>Diagnostics</h2></div></div></div><p>
The table below presents all the diagnostics we intend to implement.
Each diagnostic has a corresponding compile time switch
<code class="code">-D_GLIBCXX_PROFILE_<diagnostic></code>.
Groups of related diagnostics can be turned on with a single switch.
For instance, <code class="code">-D_GLIBCXX_PROFILE_LOCALITY</code> is equivalent to
- <code class="code">-D_GLIBCXX_PROFILE_SOFTWARE_PREFETCH
+ <code class="code">-D_GLIBCXX_PROFILE_SOFTWARE_PREFETCH
-D_GLIBCXX_PROFILE_RBTREE_LOCALITY</code>.
</p><p>
The benefit, cost, expected frequency and accuracy of each diagnostic
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.
- </p><div class="table"><a id="id
626153"></a><p class="title"><b>Table 32.2. Diagnostics</b></p><div class="table-contents"><table summary="Diagnostics" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Group</th><th align="left">Flag</th><th align="left">Benefit</th><th align="left">Cost</th><th align="left">Freq.</th><th align="left">Implemented</th></tr></thead><tbody><tr><td align="left"><a class="ulink" href="#manual.ext.profile_mode.analysis.containers" target="_top">
+ </p><div class="table"><a id="id
425023"></a><p class="title"><b>Table 19.2. Profile Diagnostics</b></p><div class="table-contents"><table summary="Profile Diagnostics" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Group</th><th align="left">Flag</th><th align="left">Benefit</th><th align="left">Cost</th><th align="left">Freq.</th><th align="left">Implemented</th><td class="auto-generated"> </td></tr></thead><tbody><tr><td align="left"><a class="ulink" href="#manual.ext.profile_mode.analysis.containers" target="_top">
CONTAINERS</a></td><td align="left"><a class="ulink" href="#manual.ext.profile_mode.analysis.hashtable_too_small" target="_top">
HASHTABLE_TOO_SMALL</a></td><td align="left">10</td><td align="left">1</td><td align="left"> </td><td align="left">10</td><td align="left">yes</td></tr><tr><td align="left"> </td><td align="left"><a class="ulink" href="#manual.ext.profile_mode.analysis.hashtable_too_large" target="_top">
HASHTABLE_TOO_LARGE</a></td><td align="left">5</td><td align="left">1</td><td align="left"> </td><td align="left">10</td><td align="left">yes</td></tr><tr><td align="left"> </td><td align="left"><a class="ulink" href="#manual.ext.profile_mode.analysis.inefficient_hash" target="_top">
<code class="code">_GLIBCXX_PROFILE_CONTAINERS</code>.
</p><div class="sect3" title="Hashtable Too Small"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.hashtable_too_small"></a>Hashtable Too Small</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables with many
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables with many
rehash operations, small construction size and large destruction size.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Rehash is very expensive.
Read content, follow chains within bucket, evaluate hash function, place at
new location in different order.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> 36%.
Code similar to example below.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
Set initial size to N at construction site S.
- </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
+ </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
<code class="code">unordered_set, unordered_map</code> constructor, destructor, rehash.
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
For each dynamic instance of <code class="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.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Number of individual rehash operations * cost per rehash.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Number of individual rehash operations * cost per rehash.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 unordered_set<int> us;
2 for (int k = 0; k < 1000000; ++k) {
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Save memory, which
is good in itself and may also improve memory reference performance through
fewer cache and TLB misses.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> unknown.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
Set initial size to N at construction site S.
- </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
+ </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
<code class="code">unordered_set, unordered_map</code> constructor, destructor, rehash.
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
For each dynamic instance of <code class="code">unordered_[multi]set|map</code>,
record initial size and call context of the constructor, and correlate it
with its size at destruction time.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Number of iteration operations + memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Number of iteration operations + memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 vector<unordered_set<int>> v(100000, unordered_set<int>(100)) ;
2 for (int k = 0; k < 100000; ++k) {
<code class="code">_GLIBCXX_PROFILE_INEFFICIENT_HASH</code>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables with polarized
distribution.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> A non-uniform
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> A non-uniform
distribution may lead to long chains, thus possibly increasing complexity
by a factor up to the number of elements.
</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> factor up
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
Count the exact number of link traversals.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Total number of links traversed.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Total number of links traversed.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
class dumb_hash {
public:
</pre><p>
</p></li></ul></div></div><div class="sect3" title="Vector Too Small"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.vector_too_small"></a>Vector Too Small</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_VECTOR_TOO_SMALL</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span>Detect vectors with many
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span>Detect vectors with many
resize operations, small construction size and large destruction size..
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>Resizing can be expensive.
Copying large amounts of data takes time. Resizing many small vectors may
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
For each dynamic instance of <code class="code">vector</code>,
record initial size and call context of the constructor.
- Record size increase, if any, after each relevant operation such as
+ Record size increase, if any, after each relevant operation such as
<code class="code">push_back</code>. Record the estimated resize cost.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Total number of words copied * time to copy a word.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Total number of words copied * time to copy a word.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="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
+foo.cc:1: advice: Changing initial vector size from 10 to 1000000 saves
copying 4000000 bytes and 20 memory allocations and deallocations.
</pre><p>
</p></li></ul></div></div><div class="sect3" title="Vector Too Large"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.vector_too_large"></a>Vector Too Large</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
For each dynamic instance of <code class="code">vector</code>,
record initial size and call context of the constructor, and correlate it
with its size at destruction time.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Total amount of memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Total amount of memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 vector<vector<int>> v(100000, vector<int>(100)) ;
2 for (int k = 0; k < 100000; ++k) {
</pre><p>
</p></li></ul></div></div><div class="sect3" title="Vector to Hashtable"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.vector_to_hashtable"></a>Vector to Hashtable</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_VECTOR_TO_HASHTABLE</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
<code class="code">vector</code> that can be substituted with <code class="code">unordered_set</code>
to reduce execution time.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
Linear search in a vector is very expensive, whereas searching in a hashtable
is very quick.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>factor up
to container size.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
<code class="code">vector</code> with <code class="code">unordered_set</code> at site S.
</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>
operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
For each dynamic instance of <code class="code">vector</code>,
record call context of the constructor. Issue the advice only if the
- only methods called on this <code class="code">vector</code> are <code class="code">push_back</code>,
+ only methods called on this <code class="code">vector</code> are <code class="code">push_back</code>,
<code class="code">insert</code> and <code class="code">find</code>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
Cost(vector::push_back) + cost(vector::insert) + cost(find, vector) -
</pre><p>
</p></li></ul></div></div><div class="sect3" title="Hashtable to Vector"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.hashtable_to_vector"></a>Hashtable to Vector</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_HASHTABLE_TO_VECTOR</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
<code class="code">unordered_set</code> that can be substituted with <code class="code">vector</code>
to reduce execution time.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
Hashtable iterator is slower than vector iterator.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>95%.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
<code class="code">unordered_set</code> with <code class="code">vector</code> at site S.
</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">unordered_set</code>
operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
For each dynamic instance of <code class="code">unordered_set</code>,
record call context of the constructor. Issue the advice only if the
- number of <code class="code">find</code>, <code class="code">insert</code> and <code class="code">[]</code>
+ number of <code class="code">find</code>, <code class="code">insert</code> and <code class="code">[]</code>
operations on this <code class="code">unordered_set</code> are small relative to the
number of elements, and methods <code class="code">begin</code> or <code class="code">end</code>
are invoked (suggesting iteration).</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
</pre><p>
</p></li></ul></div></div><div class="sect3" title="Vector to List"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.vector_to_list"></a>Vector to List</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_VECTOR_TO_LIST</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
<code class="code">vector</code> could be substituted with <code class="code">list</code> for
better performance.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
- Inserting in the middle of a vector is expensive compared to inserting in a
+ Inserting in the middle of a vector is expensive compared to inserting in a
list.
</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>factor up to
container size.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
(Sum(cost(vector::method)) - Sum(cost(list::method)), for
method in [push_back, insert, erase])
- + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="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
+foo.cc:1: advice: Changing "vector" to "list" will save about 5,000,000
operations.
</pre><p>
</p></li></ul></div></div><div class="sect3" title="List to Vector"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.list_to_vector"></a>List to Vector</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_LIST_TO_VECTOR</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
<code class="code">list</code> could be substituted with <code class="code">vector</code> for
better performance.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
(Sum(cost(vector::method)) - Sum(cost(list::method)), for
method in [push_back, insert, erase])
- + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 list<int> l;
...
</pre><p>
</p></li></ul></div></div><div class="sect3" title="List to Forward List (Slist)"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.list_to_slist"></a>List to Forward List (Slist)</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_LIST_TO_SLIST</code>.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
<code class="code">list</code> could be substituted with <code class="code">forward_list</code> for
better performance.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
Issue the advice if there are no <code class="code">backwards</code> traversals
or insertion before a given node.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
- Always true.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ Always true.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 list<int> l;
...
</p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where ordered
associative containers can be replaced with unordered ones.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
- Insert and search are quicker in a hashtable than in
+ Insert and search are quicker in a hashtable than in
a red-black tree.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>52%.
</p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
Replace set with unordered_set at site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
performance based on actual input. For instance, advise Radix Sort over
Quick Sort for a particular call context.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
- See papers:
+ See papers:
<a class="ulink" href="http://portal.acm.org/citation.cfm?doid=1065944.1065981" target="_top">
- A framework for adaptive algorithm selection in STAPL</a> and
+ A framework for adaptive algorithm selection in STAPL</a> and
<a class="ulink" href="http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4228227" target="_top">
Optimizing Sorting with Machine Learning Algorithms</a>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>60%.
at site S from X Sort to Y Sort.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> <code class="code">sort</code>
algorithm.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
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
+ would do better on this input. Requires us to know what algorithm we
are using in our sort implementation in release mode.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
Runtime(algo) for algo in [radix, quick, merge, ...]</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
Indirect references are hard to predict and are very expensive when they
miss in caches.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>25%.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Insert prefetch
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Insert prefetch
instruction.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Vector iterator and
access operator [].
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
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
+ 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.
</p><p>
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
+ This model could be trained automatically by running a set of synthetic
cases.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
Total distance between pointer values of successive elements in vectors
- of pointers.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ of pointers.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 int zero = 0;
2 vector<int*> v(10000000, &zero);
with respect to their actual traversal patterns.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>Allocation can be tuned
to a specific traversal pattern, to result in better data locality.
- See paper:
+ See paper:
<a class="ulink" href="http://www.springerlink.com/content/8085744l00x72662/" target="_top">
Custom Memory Allocation for Free</a>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>30%.
</p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
High scatter score N for container built at site S.
Consider changing allocation sequence or choosing a structure conscious
- allocator.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Methods of all
+ allocator.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Methods of all
containers using linked structures.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
First, get cache line size and page size from system.
Then record the number of successive elements that are on different line
container member accesses. Issue advice for elements referenced by
multiple threads.
See paper: <a class="ulink" href="http://portal.acm.org/citation.cfm?id=207110.207148" target="_top">
- The LRPD test: speculative run-time parallelization of loops with
+ The LRPD test: speculative run-time parallelization of loops with
privatization and reduction parallelization</a>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
Number of accesses to elements referenced from multiple threads
</p></li></ul></div></div><div class="sect3" title="False Sharing"><div class="titlepage"><div><div><h4 class="title"><a id="manual.ext.profile_mode.analysis.mthread.false_share"></a>False Sharing</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
<code class="code">_GLIBCXX_PROFILE_FALSE_SHARING</code>.
</p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect elements in the
- same container which share a cache line, are written by at least one
+ same container which share a cache line, are written by at least one
thread, and accessed by different threads.
</p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Under these assumptions,
cache protocols require
and iterators.
</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
First, get the cache line size.
- For each shared container, record all the associated iterator dereferences
+ 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. Issue a warning only if the ratio to total references is
- significant. Do the same for iterator dereference values if they are
+ across threads to detect references in two different threads to the same
+ cache line. Issue a warning only if the ratio to total references is
+ significant. Do the same for iterator dereference values if they are
pointers.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
Number of accesses to same cache line from different threads.
- </p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
+ </p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
</p><pre class="programlisting">
1 vector<int> v(2, 0);
2 #pragma omp parallel for shared(v, SIZE) schedule(static, 1)
5 }
OMP_NUM_THREADS=2 ./a.out
-foo.cc:1: advice: Change container structure or padding to avoid false
+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.
</pre><p>
</p></li></ul></div></div></div><div class="sect2" title="Statistics"><div class="titlepage"><div><div><h3 class="title"><a id="manual.ext.profile_mode.analysis.statistics"></a>Statistics</h3></div></div></div><p>
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.
-</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt12ch32s06.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="profile_mode.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ext_allocators.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Developer Information </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 33. Allocators</td></tr></table></div></body></html>
+</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt03ch19s06.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="profile_mode.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ext_allocators.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Developer Information </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 20. Allocators</td></tr></table></div></body></html>
OSDN Git Service
