Merge from vendor branch LIBSTDC++:
[dragonfly.git] / share / doc / papers / kerntune / 3.t
1 .\" Copyright (c) 1984 M. K. McKusick
2 .\" Copyright (c) 1984 The Regents of the University of California.
3 .\" All rights reserved.
4 .\"
5 .\" Redistribution and use in source and binary forms, with or without
6 .\" modification, are permitted provided that the following conditions
7 .\" are met:
8 .\" 1. Redistributions of source code must retain the above copyright
9 .\"    notice, this list of conditions and the following disclaimer.
10 .\" 2. Redistributions in binary form must reproduce the above copyright
11 .\"    notice, this list of conditions and the following disclaimer in the
12 .\"    documentation and/or other materials provided with the distribution.
13 .\" 3. All advertising materials mentioning features or use of this software
14 .\"    must display the following acknowledgement:
15 .\"     This product includes software developed by the University of
16 .\"     California, Berkeley and its contributors.
17 .\" 4. Neither the name of the University nor the names of its contributors
18 .\"    may be used to endorse or promote products derived from this software
19 .\"    without specific prior written permission.
20 .\"
21 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 .\" SUCH DAMAGE.
32 .\"
33 .\"     @(#)3.t 1.2 (Berkeley) 11/8/90
34 .\"
35 .ds RH Techniques for Improving Performance
36 .NH 1 
37 Techniques for Improving Performance
38 .PP
39 This section gives several hints on general optimization techniques.
40 It then proceeds with an example of how they can be
41 applied to the 4.2BSD kernel to improve its performance.
42 .NH 2
43 Using the Profiler
44 .PP
45 The profiler is a useful tool for improving
46 a set of routines that implement an abstraction.
47 It can be helpful in identifying poorly coded routines,
48 and in evaluating the new algorithms and code that replace them.
49 Taking full advantage of the profiler 
50 requires a careful examination of the call graph profile,
51 and a thorough knowledge of the abstractions underlying
52 the kernel.
53 .PP
54 The easiest optimization that can be performed
55 is a small change
56 to a control construct or data structure.
57 An obvious starting point
58 is to expand a small frequently called routine inline.
59 The drawback to inline expansion is that the data abstractions
60 in the kernel may become less parameterized,
61 hence less clearly defined.
62 The profiling will also become less useful since the loss of 
63 routines will make its output more granular.
64 .PP
65 Further potential for optimization lies in routines that
66 implement data abstractions whose total execution
67 time is long.
68 If the data abstraction function cannot easily be speeded up,
69 it may be advantageous to cache its results,
70 and eliminate the need to rerun
71 it for identical inputs.
72 These and other ideas for program improvement are discussed in
73 [Bentley81].
74 .PP
75 This tool is best used in an iterative approach:
76 profiling the kernel,
77 eliminating one bottleneck,
78 then finding some other part of the kernel
79 that begins to dominate execution time.
80 .PP
81 A completely different use of the profiler is to analyze the control
82 flow of an unfamiliar section of the kernel.
83 By running an example that exercises the unfamiliar section of the kernel,
84 and then using \fIgprof\fR, you can get a view of the 
85 control structure of the unfamiliar section.
86 .NH 2
87 An Example of Tuning
88 .PP
89 The first step is to come up with a method for generating
90 profile data.
91 We prefer to run a profiling system for about a one day
92 period on one of our general timesharing machines.
93 While this is not as reproducible as a synthetic workload,
94 it certainly represents a realistic test.
95 We have run one day profiles on several
96 occasions over a three month period.
97 Despite the long period of time that elapsed
98 between the test runs the shape of the profiles,
99 as measured by the number of times each system call
100 entry point was called, were remarkably similar.
101 .PP
102 A second alternative is to write a small benchmark
103 program to repeated exercise a suspected bottleneck.
104 While these benchmarks are not useful as a long term profile
105 they can give quick feedback on whether a hypothesized
106 improvement is really having an effect.
107 It is important to realize that the only real assurance
108 that a change has a beneficial effect is through
109 long term measurements of general timesharing.
110 We have numerous examples where a benchmark program
111 suggests vast improvements while the change
112 in the long term system performance is negligible,
113 and conversely examples in which the benchmark program run more slowly, 
114 but the long term system performance improves significantly.
115 .PP
116 An investigation of our long term profiling showed that
117 the single most expensive function performed by the kernel
118 is path name translation.
119 We find that our general time sharing systems do about
120 500,000 name translations per day.
121 The cost of doing name translation in the original 4.2BSD
122 is 24.2 milliseconds,
123 representing 40% of the time processing system calls,
124 which is 19% of the total cycles in the kernel,
125 or 11% of all cycles executed on the machine.
126 The times are shown in Figure 3.
127 .KF
128 .DS L
129 .TS
130 center box;
131 l r r.
132 part    time    % of kernel
133 _
134 self    14.3 ms/call    11.3%
135 child   9.9 ms/call     7.9%
136 _
137 total   24.2 ms/call    19.2%
138 .TE
139 .ce
140 Figure 3. Call times for \fInamei\fP.
141 .DE
142 .KE
143 .PP
144 The system measurements collected showed the
145 pathname translation routine, \fInamei\fP,
146 was clearly worth optimizing.
147 An inspection of \fInamei\fP shows that
148 it consists of two nested loops.
149 The outer loop is traversed once per pathname component.
150 The inner loop performs a linear search through a directory looking
151 for a particular pathname component.
152 .PP
153 Our first idea was to observe that many programs 
154 step through a directory performing an operation on 
155 each entry in turn.
156 This caused us to modify \fInamei\fP to cache
157 the directory offset of the last pathname
158 component looked up by a process.
159 The cached offset is then used
160 as the point at which a search in the same directory
161 begins.  Changing directories invalidates the cache, as
162 does modifying the directory.
163 For programs that step sequentially through a directory with
164 $N$ files, search time decreases from $O ( N sup 2 )$
165 to $O(N)$.
166 .PP
167 The cost of the cache is about 20 lines of code
168 (about 0.2 kilobytes) 
169 and 16 bytes per process, with the cached data
170 stored in a process's \fIuser\fP vector.
171 .PP
172 As a quick benchmark to verify the effectiveness of the
173 cache we ran ``ls \-l''
174 on a directory containing 600 files.
175 Before the per-process cache this command
176 used 22.3 seconds of system time.
177 After adding the cache the program used the same amount
178 of user time, but the system time dropped to 3.3 seconds.
179 .PP
180 This change prompted our rerunning a profiled system
181 on a machine containing the new \fInamei\fP.
182 The results showed that the time in \fInamei\fP
183 dropped by only 2.6 ms/call and
184 still accounted for 36% of the system call time,
185 18% of the kernel, or about 10% of all the machine cycles.
186 This amounted to a drop in system time from 57% to about 55%.
187 The results are shown in Figure 4.
188 .KF
189 .DS L
190 .TS
191 center box;
192 l r r.
193 part    time    % of kernel
194 _
195 self    11.0 ms/call    9.2%
196 child   10.6 ms/call    8.9%
197 _
198 total   21.6 ms/call    18.1%
199 .TE
200 .ce
201 Figure 4. Call times for \fInamei\fP with per-process cache.
202 .DE
203 .KE
204 .PP
205 The small performance improvement
206 was caused by a low cache hit ratio.
207 Although the cache was 90% effective when hit,
208 it was only usable on about 25% of the names being translated.
209 An additional reason for the small improvement was that
210 although the amount of time spent in \fInamei\fP itself
211 decreased substantially,
212 more time was spent in the routines that it called
213 since each directory had to be accessed twice;
214 once to search from the middle to the end,
215 and once to search from the beginning to the middle.
216 .PP
217 Most missed names were caused by path name components
218 other than the last.
219 Thus Robert Elz introduced a system wide cache of most recent
220 name translations.
221 The cache is keyed on a name and the
222 inode and device number of the directory that contains it.
223 Associated with each entry is a pointer to the corresponding
224 entry in the inode table.
225 This has the effect of short circuiting the outer loop of \fInamei\fP.
226 For each path name component,
227 \fInamei\fP first looks in its cache of recent translations
228 for the needed name.
229 If it exists, the directory search can be completely eliminated.
230 If the name is not recognized,
231 then the per-process cache may still be useful in
232 reducing the directory search time.
233 The two cacheing schemes complement each other well.
234 .PP
235 The cost of the name cache is about 200 lines of code
236 (about 1.2 kilobytes) 
237 and 44 bytes per cache entry.
238 Depending on the size of the system,
239 about 200 to 1000 entries will normally be configured,
240 using 10-44 kilobytes of physical memory.
241 The name cache is resident in memory at all times.
242 .PP
243 After adding the system wide name cache we reran ``ls \-l''
244 on the same directory.
245 The user time remained the same,
246 however the system time rose slightly to 3.7 seconds.
247 This was not surprising as \fInamei\fP
248 now had to maintain the cache,
249 but was never able to make any use of it.
250 .PP
251 Another profiled system was created and measurements
252 were collected over a one day period.  These measurements
253 showed a 6 ms/call decrease in \fInamei\fP, with
254 \fInamei\fP accounting for only 31% of the system call time,
255 16% of the time in the kernel,
256 or about 7% of all the machine cycles.
257 System time dropped from 55% to about 49%.
258 The results are shown in Figure 5.
259 .KF
260 .DS L
261 .TS
262 center box;
263 l r r.
264 part    time    % of kernel
265 _
266 self    9.5 ms/call     9.6%
267 child   6.1 ms/call     6.1%
268 _
269 total   15.6 ms/call    15.7%
270 .TE
271 .ce
272 Figure 5.  Call times for \fInamei\fP with both caches.
273 .DE
274 .KE
275 .PP
276 Statistics on the performance of both caches show
277 the large performance improvement is
278 caused by the high hit ratio.
279 On the profiled system a 60% hit rate was observed in
280 the system wide cache.  This, coupled with the 25%
281 hit rate in the per-process offset cache yielded an
282 effective cache hit rate of 85%.
283 While the system wide cache reduces both the amount of time in
284 the routines that \fInamei\fP calls as well as \fInamei\fP itself
285 (since fewer directories need to be accessed or searched),
286 it is interesting to note that the actual percentage of system
287 time spent in \fInamei\fP itself increases even though the
288 actual time per call decreases.
289 This is because less total time is being spent in the kernel,
290 hence a smaller absolute time becomes a larger total percentage.