4.t

早期freebsd实现

.PP
The current compilers available for C do not
do any significant optimization.
Good optimizing compilers are unlikely to be built;
the C language is not well suited to optimization
because of its rampant use of unbound pointers.
Thus, many classical optimizations such as common subexpression
analysis and selection of register variables must be done
by hand using ``exterior'' knowledge of when such optimizations are safe.
.PP
Another optimization usually done by optimizing compilers
is inline expansion of small or frequently used routines.
In past Berkeley systems this has been done by using \fIsed\fP to
run over the assembly language and replace calls to small
routines with the code for the body of the routine, often
a single VAX instruction.
While this optimization eliminated the cost of the subroutine
call and return, 
it did not eliminate the pushing and popping of several arguments
to the routine.
The \fIsed\fP script has been replaced by a more intelligent expander,
\fIinline\fP, that merges the pushes and pops into moves to registers.
For example, if the C code
.DS
if (scanc(map[i], 1, 47, i - 63))
.DE
is compiled into assembly language it generates the code shown
in the left hand column of Table 11.
The \fIsed\fP inline expander changes this code to that
shown in the middle column.
The newer optimizer eliminates most of the stack
operations to generate the code shown in the right hand column.
.KF
.TS
center, box;
c s s s s s
c s | c s | c s
l l | l l | l l.
Alternative C Language Code Optimizations
_
cc	sed	inline
_
subl3	$64,_i,\-(sp)	subl3	$64,_i,\-(sp)	subl3	$64,_i,r5
pushl	$47	pushl	$47	movl	$47,r4
pushl	$1	pushl	$1	pushl	$1
mull2	$16,_i,r3	mull2	$16,_i,r3	mull2	$16,_i,r3
pushl	\-56(fp)[r3]	pushl	\-56(fp)[r3]	movl	\-56(fp)[r3],r2
calls	$4,_scanc	movl	(sp)+,r5	movl	(sp)+,r3
tstl	r0	movl	(sp)+,r4	scanc	r2,(r3),(r4),r5
jeql	L7	movl	(sp)+,r3	tstl	r0
		movl	(sp)+,r2	jeql	L7
		scanc	r2,(r3),(r4),r5
		tstl	r0
		jeql	L7
.TE
.ce
Table 11. Alternative inline code expansions.
.KE
.PP
Another optimization involved reevaluating
existing data structures in the context of the current system.
For example, disk buffer hashing was implemented when the system
typically had thirty to fifty buffers.
Most systems today have 200 to 1000 buffers.
Consequently, most of the hash chains contained
ten to a hundred buffers each!
The running time of the low level buffer management primitives was
dramatically improved simply by enlarging the size of the hash table.
.NH 2
Improvements to Libraries and Utilities
.PP
Intuitively, changes to the kernel would seem to have the greatest 
payoff since they affect all programs that run on the system.
However, the kernel has been tuned many times before, so the
opportunity for significant improvement was small.
By contrast, many of the libraries and utilities had never been tuned.
For example, we found utilities that spent 90% of their
running time doing single character read system calls.
Changing the utility to use the standard I/O library cut the
running time by a factor of five!
Thus, while most of our time has been spent tuning the kernel,
more than half of the speedups are because of improvements in
other parts of the system.
Some of the more dramatic changes are described in the following
subsections.
.NH 3
Hashed Databases
.PP
UNIX provides a set of database management routines, \fIdbm\fP,
that can be used to speed lookups in large data files
with an external hashed index file.
The original version of dbm was designed to work with only one
database at a time.  These routines were generalized to handle
multiple database files, enabling them to be used in rewrites
of the password and host file lookup routines.  The new routines
used to access the password file significantly improve the running
time of many important programs such as the mail subsystem,
the C-shell (in doing tilde expansion), \fIls \-l\fP, etc.
.NH 3
Buffered I/O
.PP
The new filesystem with its larger block sizes allows better
performance, but it is possible to degrade system performance
by performing numerous small transfers rather than using
appropriately-sized buffers.
The standard I/O library
automatically determines the optimal buffer size for each file.
Some C library routines and commonly-used programs use low-level
I/O or their own buffering, however.
Several important utilities that did not use the standard I/O library
and were buffering I/O using the old optimal buffer size,
1Kbytes; the programs were changed to buffer I/O according to the
optimal file system blocksize.
These include the editor, the assembler, loader, remote file copy,
the text formatting programs, and the C compiler.
.PP
The standard error output has traditionally been unbuffered
to prevent delay in presenting the output to the user,
and to prevent it from being lost if buffers are not flushed.
The inordinate expense of sending single-byte packets through
the network led us to impose a buffering scheme on the standard
error stream.
Within a single call to \fIfprintf\fP, all output is buffered temporarily.
Before the call returns, all output is flushed and the stream is again
marked unbuffered.
As before, the normal block or line buffering mechanisms can be used
instead of the default behavior.
.PP
It is possible for programs with good intentions to unintentionally
defeat the standard I/O library's choice of I/O buffer size by using
the \fIsetbuf\fP call to assign an output buffer.
Because of portability requirements, the default buffer size provided
by \fIsetbuf\fP is 1024 bytes; this can lead, once again, to added
overhead.
One such program with this problem was \fIcat\fP;
there are undoubtedly other standard system utilities with similar problems
as the system has changed much since they were originally written.
.NH 3
Mail System
.PP
The problems discussed in section 3.1.1 prompted significant work
on the entire mail system.  The first problem identified was a bug
in the \fIsyslog\fP program.  The mail delivery program, \fIsendmail\fP
logs all mail transactions through this process with the 4.2BSD interprocess
communication facilities.  \fISyslog\fP then records the information in
a log file.  Unfortunately, \fIsyslog\fP was performing a \fIsync\fP 
operation after each message it received, whether it was logged to a file
or not.  This wreaked havoc on the effectiveness of the
buffer cache and explained, to a large
extent, why sending mail to large distribution lists generated such a
heavy load on the system (one syslog message was generated for each
message recipient causing almost a continuous sequence of sync operations).
.PP
The hashed data base files were
installed in all mail programs, resulting in a order of magnitude
speedup on large distribution lists.  The code in \fI/bin/mail\fP
that notifies the \fIcomsat\fP program when mail has been delivered to
a user was changed to cache host table lookups, resulting in a similar
speedup on large distribution lists. 
.PP
Next, the file locking facilities
provided in 4.2BSD, \fIflock\fP\|(2), were used in place of the old
locking mechanism. 
The mail system previously used \fIlink\fP and \fIunlink\fP in
implementing file locking primitives. 
Because these operations usually modify the contents of directories
they require synchronous disk operations and cannot take
advantage of the name cache maintained by the system.
Unlink requires that the entry be found in the directory so that
it can be removed; 
link requires that the directory be scanned to insure that the name
does not already exist.
By contrast the advisory locking facility in 4.2BSD is
efficient because it is all done with in-memory tables.
Thus, the mail system was modified to use the file locking primitives.
This yielded another 10% cut in the basic overhead of delivering mail.
Extensive profiling and tuning of \fIsendmail\fP and
compiling it without debugging code reduced the overhead by another 20%.
.NH 3
Network Servers
.PP
With the introduction of the network facilities in 4.2BSD,
a myriad of services became available, each of which 
required its own daemon process.
Many of these daemons were rarely if ever used,
yet they lay asleep in the process table consuming
system resources and generally slowing down response.
Rather than having many servers started at boot time, a single server,
\fIinetd\fP was substituted.
This process reads a simple configuration file
that specifies the services the system is willing to support
and listens for service requests on each service's Internet port.
When a client requests service the appropriate server is created
and passed a service connection as its standard input.  Servers
that require the identity of their client may use the \fIgetpeername\fP
system call; likewise \fIgetsockname\fP may be used to find out
a server's local address without consulting data base files.
This scheme is attractive for several reasons:
.IP \(bu 3
it eliminates
as many as a dozen processes, easing system overhead and
allowing the file and text tables to be made smaller,
.IP \(bu 3
servers need not contain the code required to handle connection
queueing, simplifying the programs, and
.IP \(bu 3
installing and replacing servers becomes simpler.
.PP
With an increased numbers of networks, both local and external to Berkeley,
we found that the overhead of the routing process was becoming
inordinately high.
Several changes were made in the routing daemon to reduce this load.
Routes to external networks are no longer exchanged by routers
on the internal machines, only a route to a default gateway.
This reduces the amount of network traffic and the time required
to process routing messages.
In addition, the routing daemon was profiled
and functions responsible for large amounts
of time were optimized.
The major changes were a faster hashing scheme,
and inline expansions of the ubiquitous byte-swapping functions.
.PP
Under certain circumstances, when output was blocked,
attempts by the remote login process
to send output to the user were rejected by the system,
although a prior \fIselect\fP call had indicated that data could be sent.
This resulted in continuous attempts to write the data until the remote
user restarted output.
This problem was initially avoided in the remote login handler,
and the original problem in the kernel has since been corrected.
.NH 3
The C Run-time Library
.PP
Several people have found poorly tuned code
in frequently used routines in the C library [Lankford84].
In particular the running time of the string routines can be
cut in half by rewriting them using the VAX string instructions.
The memory allocation routines have been tuned to waste less
memory for memory allocations with sizes that are a power of two.
Certain library routines that did file input in one-character reads
have been corrected.
Other library routines including \fIfread\fP and \fIfwrite\fP
have been rewritten for efficiency.
.NH 3
Csh
.PP
The C-shell was converted to run on 4.2BSD by
writing a set of routines to simulate the old jobs library.
While this provided a functioning C-shell,
it was grossly inefficient, generating up
to twenty system calls per prompt.
The C-shell has been modified to use the new signal
facilities directly,
cutting the number of system calls per prompt in half.
Additional tuning was done with the help of profiling
to cut the cost of frequently used facilities.