projects / gcc.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
*: Regenerate.
[gcc.git] / libstdc++-v3 / doc / html / manual / bk01pt03ch19s07.html
1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Diagnostics</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
2 C++
3 ,
4 library
5 ,
6 profile
7 "><meta name="keywords" content="
8 ISO C++
9 ,
10 library
11 "><meta name="keywords" content="
12 ISO C++
13 ,
14 runtime
15 ,
16 library
17 "><link rel="home" href="../index.html" title="The GNU C++ Library"><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="mt_allocator.html" title="Chapter 20. The mt_allocator"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><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="mt_allocator.html">Next</a></td></tr></table><hr></div><div class="section" title="Diagnostics"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="manual.ext.profile_mode.diagnostics"></a>Diagnostics</h2></div></div></div><p>
18 The table below presents all the diagnostics we intend to implement.
19 Each diagnostic has a corresponding compile time switch
20 <code class="code">-D_GLIBCXX_PROFILE_&lt;diagnostic&gt;</code>.
21 Groups of related diagnostics can be turned on with a single switch.
22 For instance, <code class="code">-D_GLIBCXX_PROFILE_LOCALITY</code> is equivalent to
23 <code class="code">-D_GLIBCXX_PROFILE_SOFTWARE_PREFETCH
24 -D_GLIBCXX_PROFILE_RBTREE_LOCALITY</code>.
25 </p><p>
26 The benefit, cost, expected frequency and accuracy of each diagnostic
27 was given a grade from 1 to 10, where 10 is highest.
28 A high benefit means that, if the diagnostic is accurate, the expected
29 performance improvement is high.
30 A high cost means that turning this diagnostic on leads to high slowdown.
31 A high frequency means that we expect this to occur relatively often.
32 A high accuracy means that the diagnostic is unlikely to be wrong.
33 These grades are not perfect. They are just meant to guide users with
34 specific needs or time budgets.
35 </p><div class="table"><a name="id635993"></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" class="c1"><col align="left" class="c2"><col align="left" class="c3"><col align="left" class="c4"><col align="left" class="c5"><col align="left" class="c6"><col align="left" class="c7"></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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.containers" title="Containers">
36 CONTAINERS</a></td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_too_small" title="Hashtable Too Small">
37 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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_too_large" title="Hashtable Too Large">
38 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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.inefficient_hash" title="Inefficient Hash">
39 INEFFICIENT_HASH</a></td><td align="left">7</td><td align="left">3</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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_too_small" title="Vector Too Small">
40 VECTOR_TOO_SMALL</a></td><td align="left">8</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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_too_large" title="Vector Too Large">
41 VECTOR_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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_to_hashtable" title="Vector to Hashtable">
42 VECTOR_TO_HASHTABLE</a></td><td align="left">7</td><td align="left">7</td><td align="left"> </td><td align="left">10</td><td align="left">no</td></tr><tr><td align="left"> </td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_to_vector" title="Hashtable to Vector">
43 HASHTABLE_TO_VECTOR</a></td><td align="left">7</td><td align="left">7</td><td align="left"> </td><td align="left">10</td><td align="left">no</td></tr><tr><td align="left"> </td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_to_list" title="Vector to List">
44 VECTOR_TO_LIST</a></td><td align="left">8</td><td align="left">5</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="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.list_to_vector" title="List to Vector">
45 LIST_TO_VECTOR</a></td><td align="left">10</td><td align="left">5</td><td align="left"> </td><td align="left">10</td><td align="left">no</td></tr><tr><td align="left"> </td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.assoc_ord_to_unord" title="Ordered to Unordered Associative Container">
46 ORDERED_TO_UNORDERED</a></td><td align="left">10</td><td align="left">5</td><td align="left"> </td><td align="left">10</td><td align="left">only map/unordered_map</td></tr><tr><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.algorithms" title="Algorithms">
47 ALGORITHMS</a></td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.algorithms.sort" title="Sort Algorithm Performance">
48 SORT</a></td><td align="left">7</td><td align="left">8</td><td align="left"> </td><td align="left">7</td><td align="left">no</td></tr><tr><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality" title="Data Locality">
49 LOCALITY</a></td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality.sw_prefetch" title="Need Software Prefetch">
50 SOFTWARE_PREFETCH</a></td><td align="left">8</td><td align="left">8</td><td align="left"> </td><td align="left">5</td><td align="left">no</td></tr><tr><td align="left"> </td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality.linked" title="Linked Structure Locality">
51 RBTREE_LOCALITY</a></td><td align="left">4</td><td align="left">8</td><td align="left"> </td><td align="left">5</td><td align="left">no</td></tr><tr><td align="left"> </td><td align="left"><a class="link" href="bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.mthread.false_share" title="False Sharing">
52 FALSE_SHARING</a></td><td align="left">8</td><td align="left">10</td><td align="left"> </td><td align="left">10</td><td align="left">no</td></tr></tbody></table></div></div><br class="table-break"><div class="section" title="Diagnostic Template"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.template"></a>Diagnostic Template</h3></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
53 <code class="code">_GLIBCXX_PROFILE_&lt;diagnostic&gt;</code>.
54 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> What problem will it diagnose?
55 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>.
56 What is the fundamental reason why this is a problem</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>
57 Percentage reduction in execution time. When reduction is more than
58 a constant factor, describe the reduction rate formula.
59 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
60 What would the advise look like?</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
61 What stdlibc++ components need to be instrumented?</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
62 How do we decide when to issue the advice?</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
63 How do we measure benefits? Math goes here.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
64 </p><pre class="programlisting">
65 program code
66 ...
67 advice sample
68 </pre><p>
69 </p></li></ul></div></div><div class="section" title="Containers"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.containers"></a>Containers</h3></div></div></div><p>
70 <span class="emphasis"><em>Switch:</em></span>
71 <code class="code">_GLIBCXX_PROFILE_CONTAINERS</code>.
72 </p><div class="section" title="Hashtable Too Small"><div class="titlepage"><div><div><h4 class="title"><a name="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>
73 <code class="code">_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL</code>.
74 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables with many
75 rehash operations, small construction size and large destruction size.
76 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Rehash is very expensive.
77 Read content, follow chains within bucket, evaluate hash function, place at
78 new location in different order.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> 36%.
79 Code similar to example below.
80 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
81 Set initial size to N at construction site S.
82 </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
83 <code class="code">unordered_set, unordered_map</code> constructor, destructor, rehash.
84 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
85 For each dynamic instance of <code class="code">unordered_[multi]set|map</code>,
86 record initial size and call context of the constructor.
87 Record size increase, if any, after each relevant operation such as insert.
88 Record the estimated rehash cost.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
89 Number of individual rehash operations * cost per rehash.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
90 </p><pre class="programlisting">
91 1 unordered_set&lt;int&gt; us;
92 2 for (int k = 0; k &lt; 1000000; ++k) {
93 3 us.insert(k);
94 4 }
95
96 foo.cc:1: advice: Changing initial unordered_set size from 10 to 1000000 saves 1025530 rehash operations.
97 </pre><p>
98 </p></li></ul></div></div><div class="section" title="Hashtable Too Large"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.hashtable_too_large"></a>Hashtable 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>
99 <code class="code">_GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE</code>.
100 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables which are
101 never filled up because fewer elements than reserved are ever
102 inserted.
103 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Save memory, which
104 is good in itself and may also improve memory reference performance through
105 fewer cache and TLB misses.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> unknown.
106 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
107 Set initial size to N at construction site S.
108 </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
109 <code class="code">unordered_set, unordered_map</code> constructor, destructor, rehash.
110 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
111 For each dynamic instance of <code class="code">unordered_[multi]set|map</code>,
112 record initial size and call context of the constructor, and correlate it
113 with its size at destruction time.
114 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
115 Number of iteration operations + memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
116 </p><pre class="programlisting">
117 1 vector&lt;unordered_set&lt;int&gt;&gt; v(100000, unordered_set&lt;int&gt;(100)) ;
118 2 for (int k = 0; k &lt; 100000; ++k) {
119 3 for (int j = 0; j &lt; 10; ++j) {
120 4 v[k].insert(k + j);
121 5 }
122 6 }
123
124 foo.cc:1: advice: Changing initial unordered_set size from 100 to 10 saves N
125 bytes of memory and M iteration steps.
126 </pre><p>
127 </p></li></ul></div></div><div class="section" title="Inefficient Hash"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.inefficient_hash"></a>Inefficient Hash</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
128 <code class="code">_GLIBCXX_PROFILE_INEFFICIENT_HASH</code>.
129 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect hashtables with polarized
130 distribution.
131 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> A non-uniform
132 distribution may lead to long chains, thus possibly increasing complexity
133 by a factor up to the number of elements.
134 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span> factor up
135 to container size.
136 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Change hash function
137 for container built at site S. Distribution score = N. Access score = S.
138 Longest chain = C, in bucket B.
139 </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
140 <code class="code">unordered_set, unordered_map</code> constructor, destructor, [],
141 insert, iterator.
142 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
143 Count the exact number of link traversals.
144 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
145 Total number of links traversed.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
146 </p><pre class="programlisting">
147 class dumb_hash {
148 public:
149 size_t operator() (int i) const { return 0; }
150 };
151 ...
152 unordered_set&lt;int, dumb_hash&gt; hs;
153 ...
154 for (int i = 0; i &lt; COUNT; ++i) {
155 hs.find(i);
156 }
157 </pre><p>
158 </p></li></ul></div></div><div class="section" title="Vector Too Small"><div class="titlepage"><div><div><h4 class="title"><a name="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>
159 <code class="code">_GLIBCXX_PROFILE_VECTOR_TOO_SMALL</code>.
160 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span>Detect vectors with many
161 resize operations, small construction size and large destruction size..
162 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>Resizing can be expensive.
163 Copying large amounts of data takes time. Resizing many small vectors may
164 have allocation overhead and affect locality.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>%.
165 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
166 Set initial size to N at construction site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>.
167 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
168 For each dynamic instance of <code class="code">vector</code>,
169 record initial size and call context of the constructor.
170 Record size increase, if any, after each relevant operation such as
171 <code class="code">push_back</code>. Record the estimated resize cost.
172 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
173 Total number of words copied * time to copy a word.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
174 </p><pre class="programlisting">
175 1 vector&lt;int&gt; v;
176 2 for (int k = 0; k &lt; 1000000; ++k) {
177 3 v.push_back(k);
178 4 }
179
180 foo.cc:1: advice: Changing initial vector size from 10 to 1000000 saves
181 copying 4000000 bytes and 20 memory allocations and deallocations.
182 </pre><p>
183 </p></li></ul></div></div><div class="section" title="Vector Too Large"><div class="titlepage"><div><div><h4 class="title"><a name="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>
184 <code class="code">_GLIBCXX_PROFILE_VECTOR_TOO_LARGE</code>
185 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span>Detect vectors which are
186 never filled up because fewer elements than reserved are ever
187 inserted.
188 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>Save memory, which
189 is good in itself and may also improve memory reference performance through
190 fewer cache and TLB misses.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>%.
191 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
192 Set initial size to N at construction site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>.
193 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
194 For each dynamic instance of <code class="code">vector</code>,
195 record initial size and call context of the constructor, and correlate it
196 with its size at destruction time.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
197 Total amount of memory saved.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
198 </p><pre class="programlisting">
199 1 vector&lt;vector&lt;int&gt;&gt; v(100000, vector&lt;int&gt;(100)) ;
200 2 for (int k = 0; k &lt; 100000; ++k) {
201 3 for (int j = 0; j &lt; 10; ++j) {
202 4 v[k].insert(k + j);
203 5 }
204 6 }
205
206 foo.cc:1: advice: Changing initial vector size from 100 to 10 saves N
207 bytes of memory and may reduce the number of cache and TLB misses.
208 </pre><p>
209 </p></li></ul></div></div><div class="section" title="Vector to Hashtable"><div class="titlepage"><div><div><h4 class="title"><a name="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>
210 <code class="code">_GLIBCXX_PROFILE_VECTOR_TO_HASHTABLE</code>.
211 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
212 <code class="code">vector</code> that can be substituted with <code class="code">unordered_set</code>
213 to reduce execution time.
214 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
215 Linear search in a vector is very expensive, whereas searching in a hashtable
216 is very quick.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>factor up
217 to container size.
218 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
219 <code class="code">vector</code> with <code class="code">unordered_set</code> at site S.
220 </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>
221 operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
222 For each dynamic instance of <code class="code">vector</code>,
223 record call context of the constructor. Issue the advice only if the
224 only methods called on this <code class="code">vector</code> are <code class="code">push_back</code>,
225 <code class="code">insert</code> and <code class="code">find</code>.
226 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
227 Cost(vector::push_back) + cost(vector::insert) + cost(find, vector) -
228 cost(unordered_set::insert) + cost(unordered_set::find).
229 </p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
230 </p><pre class="programlisting">
231 1 vector&lt;int&gt; v;
232 ...
233 2 for (int i = 0; i &lt; 1000; ++i) {
234 3 find(v.begin(), v.end(), i);
235 4 }
236
237 foo.cc:1: advice: Changing "vector" to "unordered_set" will save about 500,000
238 comparisons.
239 </pre><p>
240 </p></li></ul></div></div><div class="section" title="Hashtable to Vector"><div class="titlepage"><div><div><h4 class="title"><a name="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>
241 <code class="code">_GLIBCXX_PROFILE_HASHTABLE_TO_VECTOR</code>.
242 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect uses of
243 <code class="code">unordered_set</code> that can be substituted with <code class="code">vector</code>
244 to reduce execution time.
245 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
246 Hashtable iterator is slower than vector iterator.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>95%.
247 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace
248 <code class="code">unordered_set</code> with <code class="code">vector</code> at site S.
249 </p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">unordered_set</code>
250 operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
251 For each dynamic instance of <code class="code">unordered_set</code>,
252 record call context of the constructor. Issue the advice only if the
253 number of <code class="code">find</code>, <code class="code">insert</code> and <code class="code">[]</code>
254 operations on this <code class="code">unordered_set</code> are small relative to the
255 number of elements, and methods <code class="code">begin</code> or <code class="code">end</code>
256 are invoked (suggesting iteration).</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
257 Number of .</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
258 </p><pre class="programlisting">
259 1 unordered_set&lt;int&gt; us;
260 ...
261 2 int s = 0;
262 3 for (unordered_set&lt;int&gt;::iterator it = us.begin(); it != us.end(); ++it) {
263 4 s += *it;
264 5 }
265
266 foo.cc:1: advice: Changing "unordered_set" to "vector" will save about N
267 indirections and may achieve better data locality.
268 </pre><p>
269 </p></li></ul></div></div><div class="section" title="Vector to List"><div class="titlepage"><div><div><h4 class="title"><a name="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>
270 <code class="code">_GLIBCXX_PROFILE_VECTOR_TO_LIST</code>.
271 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
272 <code class="code">vector</code> could be substituted with <code class="code">list</code> for
273 better performance.
274 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
275 Inserting in the middle of a vector is expensive compared to inserting in a
276 list.
277 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>factor up to
278 container size.
279 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace vector with list
280 at site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>
281 operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
282 For each dynamic instance of <code class="code">vector</code>,
283 record the call context of the constructor. Record the overhead of each
284 <code class="code">insert</code> operation based on current size and insert position.
285 Report instance with high insertion overhead.
286 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
287 (Sum(cost(vector::method)) - Sum(cost(list::method)), for
288 method in [push_back, insert, erase])
289 + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
290 </p><pre class="programlisting">
291 1 vector&lt;int&gt; v;
292 2 for (int i = 0; i &lt; 10000; ++i) {
293 3 v.insert(v.begin(), i);
294 4 }
295
296 foo.cc:1: advice: Changing "vector" to "list" will save about 5,000,000
297 operations.
298 </pre><p>
299 </p></li></ul></div></div><div class="section" title="List to Vector"><div class="titlepage"><div><div><h4 class="title"><a name="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>
300 <code class="code">_GLIBCXX_PROFILE_LIST_TO_VECTOR</code>.
301 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
302 <code class="code">list</code> could be substituted with <code class="code">vector</code> for
303 better performance.
304 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
305 Iterating through a vector is faster than through a list.
306 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>64%.
307 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace list with vector
308 at site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">vector</code>
309 operations and access methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
310 Issue the advice if there are no <code class="code">insert</code> operations.
311 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
312 (Sum(cost(vector::method)) - Sum(cost(list::method)), for
313 method in [push_back, insert, erase])
314 + (Cost(iterate vector) - Cost(iterate list))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
315 </p><pre class="programlisting">
316 1 list&lt;int&gt; l;
317 ...
318 2 int sum = 0;
319 3 for (list&lt;int&gt;::iterator it = l.begin(); it != l.end(); ++it) {
320 4 sum += *it;
321 5 }
322
323 foo.cc:1: advice: Changing "list" to "vector" will save about 1000000 indirect
324 memory references.
325 </pre><p>
326 </p></li></ul></div></div><div class="section" title="List to Forward List (Slist)"><div class="titlepage"><div><div><h4 class="title"><a name="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>
327 <code class="code">_GLIBCXX_PROFILE_LIST_TO_SLIST</code>.
328 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where
329 <code class="code">list</code> could be substituted with <code class="code">forward_list</code> for
330 better performance.
331 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
332 The memory footprint of a forward_list is smaller than that of a list.
333 This has beneficial effects on memory subsystem, e.g., fewer cache misses.
334 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>40%.
335 Note that the reduction is only noticeable if the size of the forward_list
336 node is in fact larger than that of the list node. For memory allocators
337 with size classes, you will only notice an effect when the two node sizes
338 belong to different allocator size classes.
339 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>Replace list with
340 forward_list at site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span><code class="code">list</code>
341 operations and iteration methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
342 Issue the advice if there are no <code class="code">backwards</code> traversals
343 or insertion before a given node.
344 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
345 Always true.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
346 </p><pre class="programlisting">
347 1 list&lt;int&gt; l;
348 ...
349 2 int sum = 0;
350 3 for (list&lt;int&gt;::iterator it = l.begin(); it != l.end(); ++it) {
351 4 sum += *it;
352 5 }
353
354 foo.cc:1: advice: Change "list" to "forward_list".
355 </pre><p>
356 </p></li></ul></div></div><div class="section" title="Ordered to Unordered Associative Container"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.assoc_ord_to_unord"></a>Ordered to Unordered Associative Container</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
357 <code class="code">_GLIBCXX_PROFILE_ORDERED_TO_UNORDERED</code>.
358 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect cases where ordered
359 associative containers can be replaced with unordered ones.
360 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
361 Insert and search are quicker in a hashtable than in
362 a red-black tree.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>52%.
363 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
364 Replace set with unordered_set at site S.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span>
365 <code class="code">set</code>, <code class="code">multiset</code>, <code class="code">map</code>,
366 <code class="code">multimap</code> methods.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
367 Issue the advice only if we are not using operator <code class="code">++</code> on any
368 iterator on a particular <code class="code">[multi]set|map</code>.
369 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
370 (Sum(cost(hashtable::method)) - Sum(cost(rbtree::method)), for
371 method in [insert, erase, find])
372 + (Cost(iterate hashtable) - Cost(iterate rbtree))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
373 </p><pre class="programlisting">
374 1 set&lt;int&gt; s;
375 2 for (int i = 0; i &lt; 100000; ++i) {
376 3 s.insert(i);
377 4 }
378 5 int sum = 0;
379 6 for (int i = 0; i &lt; 100000; ++i) {
380 7 sum += *s.find(i);
381 8 }
382 </pre><p>
383 </p></li></ul></div></div></div><div class="section" title="Algorithms"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.algorithms"></a>Algorithms</h3></div></div></div><p><span class="emphasis"><em>Switch:</em></span>
384 <code class="code">_GLIBCXX_PROFILE_ALGORITHMS</code>.
385 </p><div class="section" title="Sort Algorithm Performance"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.algorithms.sort"></a>Sort Algorithm Performance</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
386 <code class="code">_GLIBCXX_PROFILE_SORT</code>.
387 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Give measure of sort algorithm
388 performance based on actual input. For instance, advise Radix Sort over
389 Quick Sort for a particular call context.
390 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
391 See papers:
392 <a class="link" href="http://portal.acm.org/citation.cfm?doid=1065944.1065981" target="_top">
393 A framework for adaptive algorithm selection in STAPL</a> and
394 <a class="link" href="http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=4228227" target="_top">
395 Optimizing Sorting with Machine Learning Algorithms</a>.
396 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>60%.
397 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Change sort algorithm
398 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>
399 algorithm.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
400 Issue the advice if the cost model tells us that another sort algorithm
401 would do better on this input. Requires us to know what algorithm we
402 are using in our sort implementation in release mode.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
403 Runtime(algo) for algo in [radix, quick, merge, ...]</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
404 </p><pre class="programlisting">
405 </pre><p>
406 </p></li></ul></div></div></div><div class="section" title="Data Locality"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.locality"></a>Data Locality</h3></div></div></div><p><span class="emphasis"><em>Switch:</em></span>
407 <code class="code">_GLIBCXX_PROFILE_LOCALITY</code>.
408 </p><div class="section" title="Need Software Prefetch"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.locality.sw_prefetch"></a>Need Software Prefetch</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
409 <code class="code">_GLIBCXX_PROFILE_SOFTWARE_PREFETCH</code>.
410 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Discover sequences of indirect
411 memory accesses that are not regular, thus cannot be predicted by
412 hardware prefetchers.
413 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
414 Indirect references are hard to predict and are very expensive when they
415 miss in caches.</p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>25%.
416 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Insert prefetch
417 instruction.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Vector iterator and
418 access operator [].
419 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
420 First, get cache line size and page size from system.
421 Then record iterator dereference sequences for which the value is a pointer.
422 For each sequence within a container, issue a warning if successive pointer
423 addresses are not within cache lines and do not form a linear pattern
424 (otherwise they may be prefetched by hardware).
425 If they also step across page boundaries, make the warning stronger.
426 </p><p>The same analysis applies to containers other than vector.
427 However, we cannot give the same advice for linked structures, such as list,
428 as there is no random access to the n-th element. The user may still be
429 able to benefit from this information, for instance by employing frays (user
430 level light weight threads) to hide the latency of chasing pointers.
431 </p><p>
432 This analysis is a little oversimplified. A better cost model could be
433 created by understanding the capability of the hardware prefetcher.
434 This model could be trained automatically by running a set of synthetic
435 cases.
436 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
437 Total distance between pointer values of successive elements in vectors
438 of pointers.</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
439 </p><pre class="programlisting">
440 1 int zero = 0;
441 2 vector&lt;int*&gt; v(10000000, &amp;zero);
442 3 for (int k = 0; k &lt; 10000000; ++k) {
443 4 v[random() % 10000000] = new int(k);
444 5 }
445 6 for (int j = 0; j &lt; 10000000; ++j) {
446 7 count += (*v[j] == 0 ? 0 : 1);
447 8 }
448
449 foo.cc:7: advice: Insert prefetch instruction.
450 </pre><p>
451 </p></li></ul></div></div><div class="section" title="Linked Structure Locality"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.locality.linked"></a>Linked Structure Locality</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
452 <code class="code">_GLIBCXX_PROFILE_RBTREE_LOCALITY</code>.
453 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Give measure of locality of
454 objects stored in linked structures (lists, red-black trees and hashtables)
455 with respect to their actual traversal patterns.
456 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>Allocation can be tuned
457 to a specific traversal pattern, to result in better data locality.
458 See paper:
459 <a class="link" href="http://www.springerlink.com/content/8085744l00x72662/" target="_top">
460 Custom Memory Allocation for Free</a>.
461 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>30%.
462 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span>
463 High scatter score N for container built at site S.
464 Consider changing allocation sequence or choosing a structure conscious
465 allocator.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Methods of all
466 containers using linked structures.</p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
467 First, get cache line size and page size from system.
468 Then record the number of successive elements that are on different line
469 or page, for each traversal method such as <code class="code">find</code>. Give advice
470 only if the ratio between this number and the number of total node hops
471 is above a threshold.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
472 Sum(same_cache_line(this,previous))</p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
473 </p><pre class="programlisting">
474 1 set&lt;int&gt; s;
475 2 for (int i = 0; i &lt; 10000000; ++i) {
476 3 s.insert(i);
477 4 }
478 5 set&lt;int&gt; s1, s2;
479 6 for (int i = 0; i &lt; 10000000; ++i) {
480 7 s1.insert(i);
481 8 s2.insert(i);
482 9 }
483 ...
484 // Fast, better locality.
485 10 for (set&lt;int&gt;::iterator it = s.begin(); it != s.end(); ++it) {
486 11 sum += *it;
487 12 }
488 // Slow, elements are further apart.
489 13 for (set&lt;int&gt;::iterator it = s1.begin(); it != s1.end(); ++it) {
490 14 sum += *it;
491 15 }
492
493 foo.cc:5: advice: High scatter score NNN for set built here. Consider changing
494 the allocation sequence or switching to a structure conscious allocator.
495 </pre><p>
496 </p></li></ul></div></div></div><div class="section" title="Multithreaded Data Access"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.mthread"></a>Multithreaded Data Access</h3></div></div></div><p>
497 The diagnostics in this group are not meant to be implemented short term.
498 They require compiler support to know when container elements are written
499 to. Instrumentation can only tell us when elements are referenced.
500 </p><p><span class="emphasis"><em>Switch:</em></span>
501 <code class="code">_GLIBCXX_PROFILE_MULTITHREADED</code>.
502 </p><div class="section" title="Data Dependence Violations at Container Level"><div class="titlepage"><div><div><h4 class="title"><a name="manual.ext.profile_mode.analysis.mthread.ddtest"></a>Data Dependence Violations at Container Level</h4></div></div></div><div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"><p><span class="emphasis"><em>Switch:</em></span>
503 <code class="code">_GLIBCXX_PROFILE_DDTEST</code>.
504 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect container elements
505 that are referenced from multiple threads in the parallel region or
506 across parallel regions.
507 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span>
508 Sharing data between threads requires communication and perhaps locking,
509 which may be expensive.
510 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>?%.
511 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Change data
512 distribution or parallel algorithm.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Container access methods
513 and iterators.
514 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
515 Keep a shadow for each container. Record iterator dereferences and
516 container member accesses. Issue advice for elements referenced by
517 multiple threads.
518 See paper: <a class="link" href="http://portal.acm.org/citation.cfm?id=207110.207148" target="_top">
519 The LRPD test: speculative run-time parallelization of loops with
520 privatization and reduction parallelization</a>.
521 </p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
522 Number of accesses to elements referenced from multiple threads
523 </p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
524 </p><pre class="programlisting">
525 </pre><p>
526 </p></li></ul></div></div><div class="section" title="False Sharing"><div class="titlepage"><div><div><h4 class="title"><a name="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>
527 <code class="code">_GLIBCXX_PROFILE_FALSE_SHARING</code>.
528 </p></li><li class="listitem"><p><span class="emphasis"><em>Goal:</em></span> Detect elements in the
529 same container which share a cache line, are written by at least one
530 thread, and accessed by different threads.
531 </p></li><li class="listitem"><p><span class="emphasis"><em>Fundamentals:</em></span> Under these assumptions,
532 cache protocols require
533 communication to invalidate lines, which may be expensive.
534 </p></li><li class="listitem"><p><span class="emphasis"><em>Sample runtime reduction:</em></span>68%.
535 </p></li><li class="listitem"><p><span class="emphasis"><em>Recommendation:</em></span> Reorganize container
536 or use padding to avoid false sharing.</p></li><li class="listitem"><p><span class="emphasis"><em>To instrument:</em></span> Container access methods
537 and iterators.
538 </p></li><li class="listitem"><p><span class="emphasis"><em>Analysis:</em></span>
539 First, get the cache line size.
540 For each shared container, record all the associated iterator dereferences
541 and member access methods with the thread id. Compare the address lists
542 across threads to detect references in two different threads to the same
543 cache line. Issue a warning only if the ratio to total references is
544 significant. Do the same for iterator dereference values if they are
545 pointers.</p></li><li class="listitem"><p><span class="emphasis"><em>Cost model:</em></span>
546 Number of accesses to same cache line from different threads.
547 </p></li><li class="listitem"><p><span class="emphasis"><em>Example:</em></span>
548 </p><pre class="programlisting">
549 1 vector&lt;int&gt; v(2, 0);
550 2 #pragma omp parallel for shared(v, SIZE) schedule(static, 1)
551 3 for (i = 0; i &lt; SIZE; ++i) {
552 4 v[i % 2] += i;
553 5 }
554
555 OMP_NUM_THREADS=2 ./a.out
556 foo.cc:1: advice: Change container structure or padding to avoid false
557 sharing in multithreaded access at foo.cc:4. Detected N shared cache lines.
558 </pre><p>
559 </p></li></ul></div></div></div><div class="section" title="Statistics"><div class="titlepage"><div><div><h3 class="title"><a name="manual.ext.profile_mode.analysis.statistics"></a>Statistics</h3></div></div></div><p>
560 <span class="emphasis"><em>Switch:</em></span>
561 <code class="code">_GLIBCXX_PROFILE_STATISTICS</code>.
562 </p><p>
563 In some cases the cost model may not tell us anything because the costs
564 appear to offset the benefits. Consider the choice between a vector and
565 a list. When there are both inserts and iteration, an automatic advice
566 may not be issued. However, the programmer may still be able to make use
567 of this information in a different way.
568 </p><p>
569 This diagnostic will not issue any advice, but it will print statistics for
570 each container construction site. The statistics will contain the cost
571 of each operation actually performed on the container.
572 </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="mt_allocator.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="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 20. The mt_allocator</td></tr></table></div></body></html>