Chapter 5 |
Advanced Compiler Use and Efficiency Hints |
|
by Robert MacLachlan
5.1 |
Advanced Compiler Introduction |
|
In CMUCL, as with any language on any computer, the path to efficient
code starts with good algorithms and sensible programming techniques,
but to avoid inefficiency pitfalls, you need to know some of this
implementation's quirks and features. This chapter is mostly a fairly
long and detailed overview of what optimizations Python does.
Although there are the usual negative suggestions of inefficient
features to avoid, the main emphasis is on describing the things that
programmers can count on being efficient.
The optimizations described here can have the effect of speeding up
existing programs written in conventional styles, but the potential
for new programming styles that are clearer and less error-prone is at
least as significant. For this reason, several sections end with a
discussion of the implications of these optimizations for programming
style.
Python's support for types is unusual in three major ways:
- Precise type checking encourages the specific use of type
declarations as a form of run-time consistency checking. This
speeds development by localizing type errors and giving more
meaningful error messages. See section 4.5.2. Python
produces completely safe code; optimized type checking maintains
reasonable efficiency on conventional hardware
(see section 5.3.6.)
- Comprehensive support for the Common Lisp type system makes complex
type specifiers useful. Using type specifiers such as or and
member has both efficiency and robustness advantages.
See section 5.2.
- Type inference eliminates the need for some declarations, and
also aids compile-time detection of type errors. Given detailed
type declarations, type inference can often eliminate type checks
and enable more efficient object representations and code sequences.
Checking all types results in fewer type checks. See sections
5.3 and 5.11.2.
The main barrier to efficient Lisp programs is not that there is no
efficient way to code the program in Lisp, but that it is difficult to
arrive at that efficient coding. Common Lisp is a highly complex
language, and usually has many semantically equivalent ``reasonable''
ways to code a given problem. It is desirable to make all of these
equivalent solutions have comparable efficiency so that programmers
don't have to waste time discovering the most efficient solution.
Source level optimization increases the number of efficient ways to
solve a problem. This effect is much larger than the increase in the
efficiency of the ``best'' solution. Source level optimization
transforms the original program into a more efficient (but equivalent)
program. Although the optimizer isn't doing anything the programmer
couldn't have done, this high-level optimization is important because:
-
The programmer can code simply and directly, rather than
obfuscating code to please the compiler.
- When presented with a choice of similar coding alternatives, the
programmer can chose whichever happens to be most convenient,
instead of worrying about which is most efficient.
Source level optimization eliminates the need for macros to optimize
their expansion, and also increases the effectiveness of inline
expansion. See sections 5.4 and
5.8.
Efficient support for a safer programming style is the biggest
advantage of source level optimization. Existing tuned programs
typically won't benefit much from source optimization, since their
source has already been optimized by hand. However, even tuned
programs tend to run faster under Python because:
-
Low level optimization and register allocation provides modest
speedups in any program.
- Block compilation and inline expansion can reduce function call
overhead, but may require some program restructuring. See sections
5.8, 5.6 and
5.7.
- Efficiency notes will point out important type declarations that
are often missed even in highly tuned programs.
See section 5.13.
- Existing programs can be compiled safely without prohibitive
speed penalty, although they would be faster and safer with added
declarations. See section 5.3.6.
- The context declaration mechanism allows both space and runtime
of large systems to be reduced without sacrificing robustness by
semi-automatically varying compilation policy without addition any
optimize declarations to the source.
See section 5.7.5.
- Byte compilation can be used to dramatically reduce the size of
code that is not speed-critical. See section 5.9
The sort of symbolic programs generally written in Common Lisp often
favor recursion over iteration, or have inner loops so complex that
they involve multiple function calls. Such programs spend a larger
fraction of their time doing function calls than is the norm in other
languages; for this reason Common Lisp implementations strive to make the
general (or full) function call as inexpensive as possible. Python
goes beyond this by providing two good alternatives to full call:
-
Local call resolves function references at compile time,
allowing better calling sequences and optimization across function
calls. See section 5.6.
- Inline expansion totally eliminates call overhead and allows
many context dependent optimizations. This provides a safe and
efficient implementation of operations with function semantics,
eliminating the need for error-prone macro definitions or manual
case analysis. Although most Common Lisp implementations support
inline expansion, it becomes a more powerful tool with Python's
source level optimization. See sections 5.4
and 5.8.
Generally, Python provides simple implementations for simple uses
of function call, rather than having only a single calling convention.
These features allow a more natural programming style:
-
Proper tail recursion. See section 5.5
- Relatively efficient closures.
- A funcall that is as efficient as normal named call.
- Calls to local functions such as from labels are
optimized:
- Control transfer is a direct jump.
- The closure environment is passed in registers rather than heap
allocated.
- Keyword arguments and multiple values are implemented more
efficiently.
See section 5.6.
5.1.4 |
Representation of Objects |
|
Sometimes traditional Common Lisp implementation techniques compare so
poorly to the techniques used in other languages that Common Lisp can
become an impractical language choice. Terrible inefficiencies appear
in number-crunching programs, since Common Lisp numeric operations often
involve number-consing and generic arithmetic. Python supports
efficient natural representations for numbers (and some other types),
and allows these efficient representations to be used in more
contexts. Python also provides good efficiency notes that warn
when a crucial declaration is missing.
See section 5.11.2 for more about object representations and
numeric types. Also see section 5.13 about efficiency notes.
5.1.5 |
Writing Efficient Code |
|
Writing efficient code that works is a complex and prolonged process.
It is important not to get so involved in the pursuit of efficiency
that you lose sight of what the original problem demands. Remember
that:
- The program should be correct---it doesn't matter how
quickly you get the wrong answer.
- Both the programmer and the user will make errors, so the
program must be robust---it must detect errors in a way that
allows easy correction.
- A small portion of the program will consume most of the
resources, with the bulk of the code being virtually irrelevant to
efficiency considerations. Even experienced programmers familiar
with the problem area cannot reliably predict where these ``hot
spots'' will be.
The best way to get efficient code that is still worth using, is to separate
coding from tuning. During coding, you should:
- Use a coding style that aids correctness and robustness without
being incompatible with efficiency.
- Choose appropriate data structures that allow efficient
algorithms and object representations
(see section 5.10). Try to make interfaces abstract
enough so that you can change to a different representation if
profiling reveals a need.
- Whenever you make an assumption about a function argument or
global data structure, add consistency assertions, either with type
declarations or explicit uses of assert, ecase, etc.
During tuning, you should:
- Identify the hot spots in the program through profiling (section
5.14.)
- Identify inefficient constructs in the hot spot with efficiency
notes, more profiling, or manual inspection of the source. See
sections 5.12 and 5.13.
- Add declarations and consider the application of optimizations.
See sections 5.6, 5.8 and
5.11.2.
- If all else fails, consider algorithm or data structure changes.
If you did a good job coding, changes will be easy to introduce.
5.2 |
More About Types in Python |
|
This section goes into more detail describing what types and declarations are
recognized by Python. The area where Python differs most radically from
previous Common Lisp compilers is in its support for types:
- Precise type checking helps to find bugs at run time.
- Compile-time type checking helps to find bugs at compile time.
- Type inference minimizes the need for generic operations, and
also increases the efficiency of run time type checking and the
effectiveness of compile time type checking.
- Support for detailed types provides a wealth of opportunity for
operation-specific type inference and optimization.
5.2.1 |
More Types Meaningful |
|
Common Lisp has a very powerful type system, but conventional Common Lisp
implementations typically only recognize the small set of types
special in that implementation. In these systems, there is an
unfortunate paradox: a declaration for a relatively general type like
fixnum will be recognized by the compiler, but a highly
specific declaration such as (integer 3 17) is totally
ignored.
This is obviously a problem, since the user has to know how to specify
the type of an object in the way the compiler wants it. A very
minimal (but rarely satisfied) criterion for type system support is
that it be no worse to make a specific declaration than to make a
general one. Python goes beyond this by exploiting a number of
advantages obtained from detailed type information.
Using more restrictive types in declarations allows the compiler to do
better type inference and more compile-time type checking. Also, when
type declarations are considered to be consistency assertions that
should be verified (conditional on policy), then complex types are
useful for making more detailed assertions.
Python ``understands'' the list-style or, member,
function, array and number type specifiers. Understanding
means that:
- If the type contains more information than is used in a
particular context, then the extra information is simply ignored,
rather than derailing type inference.
- In many contexts, the extra information from these type
specifier is used to good effect. In particular, type checking in
Python is precise, so these complex types can be used
in declarations to make interesting assertions about functions and
data structures (see section 4.5.2.) More specific
declarations also aid type inference and reduce the cost for type
checking.
For related information, see section 5.11 for numeric types, and
section 5.10.3 for array types.
When given a type specifier, Python will often rewrite it into a
different (but equivalent) type. This is the mechanism that Python
uses for detecting type equivalence. For example, in Python's
canonical representation, these types are equivalent:
(or list (member :end)) <==> (or cons (member nil :end))
This has two implications for the user:
- The standard symbol type specifiers for atom,
null, fixnum, etc., are in no way magical. The
null type is actually defined to be (member
nil), list is (or cons null), and
fixnum is (signed-byte 30).
- When the compiler prints out a type, it may not look like the
type specifier that originally appeared in the program. This is
generally not a problem, but it must be taken into consideration
when reading compiler error messages.
The member type specifier can be used to represent
``symbolic'' values, analogous to the enumerated types of Pascal. For
example, the second value of find-symbol has this type:
(member :internal :external :inherited nil)
Member types are very useful for expressing consistency constraints on data
structures, for example:
(defstruct ice-cream
(flavor :vanilla :type (member :vanilla :chocolate :strawberry)))
Member types are also useful in type inference, as the number of members can
sometimes be pared down to one, in which case the value is a known constant.
The or (union) type specifier is understood, and is
meaningfully applied in many contexts. The use of or allows
assertions to be made about types in dynamically typed programs. For
example:
(defstruct box
(next nil :type (or box null))
(top :removed :type (or box-top (member :removed))))
The type assertion on the top slot ensures that an error will be signaled
when there is an attempt to store an illegal value (such as :rmoved.)
Although somewhat weak, these union type assertions provide a useful input into
type inference, allowing the cost of type checking to be reduced. For example,
this loop is safely compiled with no type checks:
(defun find-box-with-top (box)
(declare (type (or box null) box))
(do ((current box (box-next current)))
((null current))
(unless (eq (box-top current) :removed)
(return current))))
Union types are also useful in type inference for representing types that are
partially constrained. For example, the result of this expression:
(if foo
(logior x y)
(list x y))
can be expressed as (or integer cons).
The type nil is also called the empty type, since no object is of
type nil. The union of no types, (or), is also empty.
Python's interpretation of an expression whose type is nil is
that the expression never yields any value, but rather fails to
terminate, or is thrown out of. For example, the type of a call to
error or a use of return is nil. When the type of
an expression is empty, compile-time type warnings about its value are
suppressed; presumably somebody else is signaling an error. If a
function is declared to have return type nil, but does in fact
return, then (in safe compilation policies) a ``NIL Function
returned'' error will be signaled. See also the function
required-argument.
function types are understood in the restrictive sense, specifying:
- The argument syntax that the function must be called with. This
is information about what argument counts are acceptable, and which
keyword arguments are recognized. In Python, warnings about
argument syntax are a consequence of function type checking.
- The types of the argument values that the caller must pass. If
the compiler can prove that some argument to a call is of a type
disallowed by the called function's type, then it will give a
compile-time type warning. In addition to being used for
compile-time type checking, these type assertions are also used as
output type assertions in code generation. For example, if
foo is declared to have a fixnum argument, then the
1+ in (foo (1+ x)) is compiled with knowledge that
the result must be a fixnum.
- The types the values that will be bound to argument variables in
the function's definition. Declaring a function's type with
ftype implicitly declares the types of the arguments in the
definition. Python checks for consistency between the definition
and the ftype declaration. Because of precise type checking,
an error will be signaled when a function is called with an
argument of the wrong type.
- The type of return value(s) that the caller can expect. This
information is a useful input to type inference. For example, if a
function is declared to return a fixnum, then when a call to
that function appears in an expression, the expression will be
compiled with knowledge that the call will return a fixnum.
- The type of return value(s) that the definition must return.
The result type in an ftype declaration is treated like an
implicit the wrapped around the body of the definition. If
the definition returns a value of the wrong type, an error will be
signaled. If the compiler can prove that the function returns the
wrong type, then it will give a compile-time warning.
This is consistent with the new interpretation of function types and
the ftype declaration in the proposed X3J13
``function-type-argument-type-semantics'' cleanup. Note also, that if
you don't explicitly declare the type of a function using a global
ftype declaration, then Python will compute a function type
from the definition, providing a degree of inter-routine type
inference, see section 5.3.3.
5.2.7 |
The Values Declaration |
|
CMUCL supports the values declaration as an extension to
Common Lisp. The syntax of the declaration is
(values type1 type2...typen). This
declaration is semantically equivalent to a the form wrapped
around the body of the special form in which the values
declaration appears. The advantage of values over
the is purely syntactic---it doesn't introduce more
indentation. For example:
(defun foo (x)
(declare (values single-float))
(ecase x
(:this ...)
(:that ...)
(:the-other ...)))
is equivalent to:
(defun foo (x)
(the single-float
(ecase x
(:this ...)
(:that ...)
(:the-other ...))))
and
(defun floor (number &optional (divisor 1))
(declare (values integer real))
...)
is equivalent to:
(defun floor (number &optional (divisor 1))
(the (values integer real)
...))
In addition to being recognized by lambda (and hence by
defun), the values declaration is recognized by all the
other special forms with bodies and declarations: let,
let*, labels and flet. Macros with declarations
usually splice the declarations into one of the above forms, so they
will accept this declaration too, but the exact effect of a
values declaration will depend on the macro.
If you declare the types of all arguments to a function, and also
declare the return value types with values, you have described
the type of the function. Python will use this argument and result
type information to derive a function type that will then be applied
to calls of the function (see section 5.2.6.) This provides a
way to declare the types of functions that is much less syntactically
awkward than using the ftype declaration with a function
type specifier.
Although the values declaration is non-standard, it is
relatively harmless to use it in otherwise portable code, since any
warning in non-CMU implementations can be suppressed with the standard
declaration proclamation.
Because of precise type checking, structure types are much better
supported by Python than by conventional compilers:
-
The structure argument to structure accessors is precisely
checked---if you call foo-a on a bar, an error
will be signaled.
- The types of slot values are precisely checked---if you pass
the wrong type argument to a constructor or a slot setter, then an
error will be signaled.
This error checking is tremendously useful for detecting bugs in
programs that manipulate complex data structures.
An additional advantage of checking structure types and enforcing slot
types is that the compiler can safely believe slot type declarations.
Python effectively moves the type checking from the slot access to
the slot setter or constructor call. This is more efficient since
caller of the setter or constructor often knows the type of the value,
entirely eliminating the need to check the value's type. Consider
this example:
(defstruct coordinate
(x nil :type single-float)
(y nil :type single-float))
(defun make-it ()
(make-coordinate :x 1.0 :y 1.0))
(defun use-it (it)
(declare (type coordinate it))
(sqrt (expt (coordinate-x it) 2) (expt (coordinate-y it) 2)))
make-it and use-it are compiled with no checking on the
types of the float slots, yet use-it can use
single-float arithmetic with perfect safety. Note that
make-coordinate must still check the values of x and
y unless the call is block compiled or inline expanded
(see section 5.6.) But even without this advantage, it is almost
always more efficient to check slot values on structure
initialization, since slots are usually written once and read many
times.
5.2.9 |
The Freeze-Type Declaration |
|
The extensions:freeze-type declaration is a CMUCL extension that
enables more efficient compilation of user-defined types by asserting
that the definition is not going to change. This declaration may only
be used globally (with declaim or proclaim). Currently
freeze-type only affects structure type testing done by
typep, typecase, etc. Here is an example:
(declaim (freeze-type foo bar))
This asserts that the types foo and bar and their
subtypes are not going to change. This allows more efficient type
testing, since the compiler can open-code a test for all possible
subtypes, rather than having to examine the type hierarchy at
run-time.
Avoid use of the and, not and satisfies types in
declarations, since type inference has problems with them. When these
types do appear in a declaration, they are still checked precisely,
but the type information is of limited use to the compiler.
and types are effective as long as the intersection can be
canonicalized to a type that doesn't use and. For example:
(and fixnum unsigned-byte)
is fine, since it is the same as:
(integer 0 most-positive-fixnum)
but this type:
(and symbol (not (member :end)))
will not be fully understood by type interference since the and
can't be removed by canonicalization.
Using any of these type specifiers in a type test with typep or
typecase is fine, since as tests, these types can be translated
into the and macro, the not function or a call to the
satisfies predicate.
5.2.11 |
Type Style Recommendations |
|
Python provides good support for some currently unconventional ways of
using the Common Lisp type system. With Python, it is desirable to make
declarations as precise as possible, but type inference also makes
some declarations unnecessary. Here are some general guidelines for
maximum robustness and efficiency:
- Declare the types of all function arguments and structure slots
as precisely as possible (while avoiding not, and and
satisfies). Put these declarations in during initial coding
so that type assertions can find bugs for you during debugging.
- Use the member type specifier where there are a small
number of possible symbol values, for example: (member :red
:blue :green).
- Use the or type specifier in situations where the
type is not certain, but there are only a few possibilities, for
example: (or list vector).
- Declare integer types with the tightest bounds that you can,
such as (integer 3 7).
- Define deftype or defstruct types before
they are used. Definition after use is legal (producing no
``undefined type'' warnings), but type tests and structure
operations will be compiled much less efficiently.
- Use the extensions:freeze-type declaration to speed up
type testing for structure types which won't have new subtypes added
later. See section 5.2.9
- In addition to declaring the array element type and simpleness,
also declare the dimensions if they are fixed, for example:
(simple-array single-float (1024 1024))
This bounds information allows array indexing for multi-dimensional
arrays to be compiled much more efficiently, and may also allow
array bounds checking to be done at compile time.
See section 5.10.3.
- Avoid use of the the declaration within expressions.
Not only does it clutter the code, but it is also almost worthless
under safe policies. If the need for an output type assertion is
revealed by efficiency notes during tuning, then you can consider
the, but it is preferable to constrain the argument types
more, allowing the compiler to prove the desired result type.
- Don't bother declaring the type of let or other
non-argument variables unless the type is non-obvious. If you
declare function return types and structure slot types, then the
type of a variable is often obvious both to the programmer and to
the compiler. An important case where the type isn't obvious, and a
declaration is appropriate, is when the value for a variable is
pulled out of untyped structure (e.g., the result of car), or
comes from some weakly typed function, such as read.
- Declarations are sometimes necessary for integer loop variables,
since the compiler can't always prove that the value is of a good
integer type. These declarations are best added during tuning, when
an efficiency note indicates the need.
Type inference is the process by which the compiler tries to figure
out the types of expressions and variables, given an inevitable lack
of complete type information. Although Python does much more type
inference than most Common Lisp compilers, remember that the more precise
and comprehensive type declarations are, the more type inference will
be able to do.
5.3.1 |
Variable Type Inference |
|
The type of a variable is the union of the types of all the
definitions. In the degenerate case of a let, the type of the
variable is the type of the initial value. This inferred type is
intersected with any declared type, and is then propagated to all the
variable's references. The types of multiple-value-bind
variables are similarly inferred from the types of the individual
values of the values form.
If multiple type declarations apply to a single variable, then all the
declarations must be correct; it is as though all the types were intersected
producing a single and type specifier. In this example:
(defmacro my-dotimes ((var count) &body body)
`(do ((,var 0 (1+ ,var)))
((>= ,var ,count))
(declare (type (integer 0 *) ,var))
,@body))
(my-dotimes (i ...)
(declare (fixnum i))
...)
the two declarations for i are intersected, so i is
known to be a non-negative fixnum.
In practice, this type inference is limited to lets and local
functions, since the compiler can't analyze all the calls to a global
function. But type inference works well enough on local variables so
that it is often unnecessary to declare the type of local variables.
This is especially likely when function result types and structure
slot types are declared. The main areas where type inference breaks
down are:
- When the initial value of a variable is a untyped expression,
such as (car x), and
- When the type of one of the variable's definitions is a function
of the variable's current value, as in: (setq x (1+ x))
5.3.2 |
Local Function Type Inference |
|
The types of arguments to local functions are inferred in the same was
as any other local variable; the type is the union of the argument
types across all the calls to the function, intersected with the
declared type. If there are any assignments to the argument
variables, the type of the assigned value is unioned in as well.
The result type of a local function is computed in a special way that
takes tail recursion (see section 5.5) into consideration.
The result type is the union of all possible return values that aren't
tail-recursive calls. For example, Python will infer that the
result type of this function is integer:
(defun ! (n res)
(declare (integer n res))
(if (zerop n)
res
(! (1- n) (* n res))))
Although this is a rather obvious result, it becomes somewhat less
trivial in the presence of mutual tail recursion of multiple
functions. Local function result type inference interacts with the
mechanisms for ensuring proper tail recursion mentioned in section
5.6.5.
5.3.3 |
Global Function Type Inference |
|
As described in section 5.2.6, a global function type
(ftype) declaration places implicit type assertions on the
call arguments, and also guarantees the type of the return value. So
wherever a call to a declared function appears, there is no doubt as
to the types of the arguments and return value. Furthermore,
Python will infer a function type from the function's definition if
there is no ftype declaration. Any type declarations on the
argument variables are used as the argument types in the derived
function type, and the compiler's best guess for the result type of
the function is used as the result type in the derived function type.
This method of deriving function types from the definition implicitly assumes
that functions won't be redefined at run-time. Consider this example:
(defun foo-p (x)
(let ((res (and (consp x) (eq (car x) 'foo))))
(format t "It is ~:[not ~;~]foo." res)))
(defun frob (it)
(if (foo-p it)
(setf (cadr it) 'yow!)
(1+ it)))
Presumably, the programmer really meant to return res from
foo-p, but he seems to have forgotten. When he tries to call
do (frob (list 'foo nil)), frob will flame out when
it tries to add to a cons. Realizing his error, he fixes
foo-p and recompiles it. But when he retries his test case, he
is baffled because the error is still there. What happened in this
example is that Python proved that the result of foo-p is
null, and then proceeded to optimize away the setf in
frob.
Fortunately, in this example, the error is detected at compile time
due to notes about unreachable code (see section 5.4.5.)
Still, some users may not want to worry about this sort of problem
during incremental development, so there is a variable to control
deriving function types.
[Variable]
extensions:*derive-function-types*
If true (the default), argument and result type information derived
from compilation of defuns is used when compiling calls to
that function. If false, only information from ftype
proclamations will be used.
5.3.4 |
Operation Specific Type Inference |
|
Many of the standard Common Lisp functions have special type inference
procedures that determine the result type as a function of the
argument types. For example, the result type of aref is the
array element type. Here are some other examples of type inferences:
(logand x #xFF) ==> (unsigned-byte 8)
(+ (the (integer 0 12) x) (the (integer 0 1) y)) ==> (integer 0 13)
(ash (the (unsigned-byte 16) x) -8) ==> (unsigned-byte 8)
5.3.5 |
Dynamic Type Inference |
|
Python uses flow analysis to infer types in dynamically typed
programs. For example:
(ecase x
(list (length x))
...)
Here, the compiler knows the argument to length is a list,
because the call to length is only done when x is a
list. The most significant efficiency effect of inference from
assertions is usually in type check optimization.
Dynamic type inference has two inputs: explicit conditionals and
implicit or explicit type assertions. Flow analysis propagates these
constraints on variable type to any code that can be executed only
after passing though the constraint. Explicit type constraints come
from ifs where the test is either a lexical variable or a
function of lexical variables and constants, where the function is
either a type predicate, a numeric comparison or eq.
If there is an eq (or eql) test, then the compiler will
actually substitute one argument for the other in the true branch.
For example:
(when (eq x :yow!) (return x))
becomes:
(when (eq x :yow!) (return :yow!))
This substitution is done when one argument is a constant, or one
argument has better type information than the other. This
transformation reveals opportunities for constant folding or
type-specific optimizations. If the test is against a constant, then
the compiler can prove that the variable is not that constant value in
the false branch, or (not (member :yow!)) in the example
above. This can eliminate redundant tests, for example:
(if (eq x nil)
...
(if x a b))
is transformed to this:
(if (eq x nil)
...
a)
Variables appearing as if tests are interpreted as
(not (eq var nil)) tests. The compiler also converts
= into eql where possible. It is difficult to do
inference directly on = since it does implicit coercions.
When there is an explicit or test on numeric
variables, the compiler makes inferences about the ranges the
variables can assume in the true and false branches. This is mainly
useful when it proves that the values are small enough in magnitude to
allow open-coding of arithmetic operations. For example, in many uses
of dotimes with a fixnum repeat count, the compiler
proves that fixnum arithmetic can be used.
Implicit type assertions are quite common, especially if you declare
function argument types. Dynamic inference from implicit type
assertions sometimes helps to disambiguate programs to a useful
degree, but is most noticeable when it detects a dynamic type error.
For example:
(defun foo (x)
(+ (car x) x))
results in this warning:
In: DEFUN FOO
(+ (CAR X) X)
==>
X
Warning: Result is a LIST, not a NUMBER.
Note that Common Lisp's dynamic type checking semantics make dynamic type
inference useful even in programs that aren't really dynamically
typed, for example:
(+ (car x) (length x))
Here, x presumably always holds a list, but in the absence of a
declaration the compiler cannot assume x is a list simply
because list-specific operations are sometimes done on it. The
compiler must consider the program to be dynamically typed until it
proves otherwise. Dynamic type inference proves that the argument to
length is always a list because the call to length is
only done after the list-specific car operation.
5.3.6 |
Type Check Optimization |
|
Python backs up its support for precise type checking by minimizing
the cost of run-time type checking. This is done both through type
inference and though optimizations of type checking itself.
Type inference often allows the compiler to prove that a value is of
the correct type, and thus no type check is necessary. For example:
(defstruct foo a b c)
(defstruct link
(foo (required-argument) :type foo)
(next nil :type (or link null)))
(foo-a (link-foo x))
Here, there is no need to check that the result of link-foo is
a foo, since it always is. Even when some type checks are
necessary, type inference can often reduce the number:
(defun test (x)
(let ((a (foo-a x))
(b (foo-b x))
(c (foo-c x)))
...))
In this example, only one (foo-p x) check is needed. This
applies to a lesser degree in list operations, such as:
(if (eql (car x) 3) (cdr x) y)
Here, we only have to check that x is a list once.
Since Python recognizes explicit type tests, code that explicitly
protects itself against type errors has little introduced overhead due
to implicit type checking. For example, this loop compiles with no
implicit checks checks for car and cdr:
(defun memq (e l)
(do ((current l (cdr current)))
((atom current) nil)
(when (eq (car current) e) (return current))))
Python reduces the cost of checks that must be done through an
optimization called complementing. A complemented check for
type is simply a check that the value is not of the type
(not type). This is only interesting when something
is known about the actual type, in which case we can test for the
complement of (and known-type (not type)), or
the difference between the known type and the assertion. An example:
(link-foo (link-next x))
Here, we change the type check for link-foo from a test for
foo to a test for:
(not (and (or foo null) (not foo)))
or more simply (not null). This is probably the most
important use of complementing, since the situation is fairly common,
and a null test is much cheaper than a structure type test.
Here is a more complicated example that illustrates the combination of
complementing with dynamic type inference:
(defun find-a (a x)
(declare (type (or link null) x))
(do ((current x (link-next current)))
((null current) nil)
(let ((foo (link-foo current)))
(when (eq (foo-a foo) a) (return foo)))))
This loop can be compiled with no type checks. The link test
for link-foo and link-next is complemented to
(not null), and then deleted because of the explicit
null test. As before, no check is necessary for foo-a,
since the link-foo is always a foo. This sort of
situation shows how precise type checking combined with precise
declarations can actually result in reduced type checking.
This section describes source-level transformations that Python does on
programs in an attempt to make them more efficient. Although source-level
optimizations can make existing programs more efficient, the biggest advantage
of this sort of optimization is that it makes it easier to write efficient
programs. If a clean, straightforward implementation is can be transformed
into an efficient one, then there is no need for tricky and dangerous hand
optimization.
The primary optimization of let variables is to delete them when they
are unnecessary. Whenever the value of a let variable is a constant,
a constant variable or a constant (local or non-notinline) function,
the variable is deleted, and references to the variable are replaced
with references to the constant expression. This is useful primarily
in the expansion of macros or inline functions, where argument values
are often constant in any given call, but are in general non-constant
expressions that must be bound to preserve order of evaluation. Let
variable optimization eliminates the need for macros to carefully
avoid spurious bindings, and also makes inline functions just as
efficient as macros.
A particularly interesting class of constant is a local function.
Substituting for lexical variables that are bound to a function can
substantially improve the efficiency of functional programming styles,
for example:
(let ((a #'(lambda (x) (zow x))))
(funcall a 3))
effectively transforms to:
(zow 3)
This transformation is done even when the function is a closure, as in:
(let ((a (let ((y (zug)))
#'(lambda (x) (zow x y)))))
(funcall a 3))
becoming:
(zow 3 (zug))
A constant variable is a lexical variable that is never assigned to,
always keeping its initial value. Whenever possible, avoid setting
lexical variables---instead bind a new variable to the new value.
Except for loop variables, it is almost always possible to avoid
setting lexical variables. This form:
(let ((x (f x)))
...)
is more efficient than this form:
(setq x (f x))
...
Setting variables makes the program more difficult to understand, both
to the compiler and to the programmer. Python compiles assignments
at least as efficiently as any other Common Lisp compiler, but most let
optimizations are only done on constant variables.
Constant variables with only a single use are also optimized away,
even when the initial value is not constant.1 For example, this expansion of
incf:
(let ((#:g3 (+ x 1)))
(setq x #:G3))
becomes:
(setq x (+ x 1))
The type semantics of this transformation are more important than the
elimination of the variable itself. Consider what happens when
x is declared to be a fixnum; after the transformation,
the compiler can compile the addition knowing that the result is a
fixnum, whereas before the transformation the addition would
have to allow for fixnum overflow.
Another variable optimization deletes any variable that is never read.
This causes the initial value and any assigned values to be unused,
allowing those expressions to be deleted if they have no side-effects.
Note that a let is actually a degenerate case of local call
(see section 5.6.2), and that let optimization can be done on calls
that weren't created by a let. Also, local call allows an applicative
style of iteration that is totally assignment free.
Constant folding is an optimization that replaces a call of constant
arguments with the constant result of that call. Constant folding is
done on all standard functions for which it is legal. Inline
expansion allows folding of any constant parts of the definition, and
can be done even on functions that have side-effects.
It is convenient to rely on constant folding when programming, as in this
example:
(defconstant limit 42)
(defun foo ()
(... (1- limit) ...))
Constant folding is also helpful when writing macros or inline
functions, since it usually eliminates the need to write a macro that
special-cases constant arguments.
Constant folding of a user
defined function is enabled by the extensions:constant-function
proclamation. In this example:
(declaim (ext:constant-function myfun))
(defun myexp (x y)
(declare (single-float x y))
(exp (* (log x) y)))
... (myexp 3.0 1.3) ...
The call to myexp is constant-folded to 4.1711674.
5.4.3 |
Unused Expression Elimination |
|
If the value of any expression is not used, and the expression has no
side-effects, then it is deleted. As with constant folding, this
optimization applies most often when cleaning up after inline
expansion and other optimizations. Any function declared an
extensions:constant-function is also subject to unused
expression elimination.
Note that Python will eliminate parts of unused expressions known
to be side-effect free, even if there are other unknown parts. For
example:
(let ((a (list (foo) (bar))))
(if t
(zow)
(raz a)))
becomes:
(progn (foo) (bar))
(zow)
5.4.4 |
Control Optimization |
|
The most important optimization of control is recognizing when an
if test is known at compile time, then deleting the
if, the test expression, and the unreachable branch of the
if. This can be considered a special case of constant folding,
although the test doesn't have to be truly constant as long as it is
definitely not nil. Note also, that type inference propagates the
result of an if test to the true and false branches,
see section 5.3.5.
A related if optimization is this transformation:2
(if (if a b c) x y)
into:
(if a
(if b x y)
(if c x y))
The opportunity for this sort of optimization usually results from a
conditional macro. For example:
(if (not a) x y)
is actually implemented as this:
(if (if a nil t) x y)
which is transformed to this:
(if a
(if nil x y)
(if t x y))
which is then optimized to this:
(if a y x)
Note that due to Python's internal representations, the
if---if situation will be recognized even if other
forms are wrapped around the inner if, like:
(if (let ((g ...))
(loop
...
(return (not g))
...))
x y)
In Python, all the Common Lisp macros really are macros, written in
terms of if, block and tagbody, so user-defined
control macros can be just as efficient as the standard ones.
Python emits basic blocks using a heuristic that minimizes the
number of unconditional branches. The code in a tagbody will
not be emitted in the order it appeared in the source, so there is no
point in arranging the code to make control drop through to the
target.
5.4.5 |
Unreachable Code Deletion |
|
Python will delete code whenever it can prove that the code can never be
executed. Code becomes unreachable when:
-
An if is optimized away, or
- There is an explicit unconditional control transfer such as go or
return-from, or
- The last reference to a local function is deleted (or there never was any
reference.)
When code that appeared in the original source is deleted, the compiler prints
a note to indicate a possible problem (or at least unnecessary code.) For
example:
(defun foo ()
(if t
(write-line "True.")
(write-line "False.")))
will result in this note:
In: DEFUN FOO
(WRITE-LINE "False.")
Note: Deleting unreachable code.
It is important to pay attention to unreachable code notes, since they often
indicate a subtle type error. For example:
(defstruct foo a b)
(defun lose (x)
(let ((a (foo-a x))
(b (if x (foo-b x) :none)))
...))
results in this note:
In: DEFUN LOSE
(IF X (FOO-B X) :NONE)
==>
:NONE
Note: Deleting unreachable code.
The :none is unreachable, because type inference knows that the argument
to foo-a must be a foo, and thus can't be nil. Presumably the
programmer forgot that x could be nil when he wrote the binding for
a.
Here is an example with an incorrect declaration:
(defun count-a (string)
(do ((pos 0 (position #\a string :start (1+ pos)))
(count 0 (1+ count)))
((null pos) count)
(declare (fixnum pos))))
This time our note is:
In: DEFUN COUNT-A
(DO ((POS 0 #) (COUNT 0 #))
((NULL POS) COUNT)
(DECLARE (FIXNUM POS)))
--> BLOCK LET TAGBODY RETURN-FROM PROGN
==>
COUNT
Note: Deleting unreachable code.
The problem here is that pos can never be null since it is declared a
fixnum.
It takes some experience with unreachable code notes to be able to
tell what they are trying to say. In non-obvious cases, the best
thing to do is to call the function in a way that should cause the
unreachable code to be executed. Either you will get a type error, or
you will find that there truly is no way for the code to be executed.
Not all unreachable code results in a note:
-
A note is only given when the unreachable code textually appears
in the original source. This prevents spurious notes due to the
optimization of macros and inline functions, but sometimes also
foregoes a note that would have been useful.
- Since accurate source information is not available for non-list
forms, there is an element of heuristic in determining whether or
not to give a note about an atom. Spurious notes may be given when
a macro or inline function defines a variable that is also present
in the calling function. Notes about nil and t are never
given, since it is too easy to confuse these constants in expanded
code with ones in the original source.
- Notes are only given about code unreachable due to control flow.
There is no note when an expression is deleted because its value is
unused, since this is a common consequence of other optimizations.
Somewhat spurious unreachable code notes can also result when a macro
inserts multiple copies of its arguments in different contexts, for
example:
(defmacro t-and-f (var form)
`(if ,var ,form ,form))
(defun foo (x)
(t-and-f x (if x "True." "False.")))
results in these notes:
In: DEFUN FOO
(IF X "True." "False.")
==>
"False."
Note: Deleting unreachable code.
==>
"True."
Note: Deleting unreachable code.
It seems like it has deleted both branches of the if, but it has really
deleted one branch in one copy, and the other branch in the other copy. Note
that these messages are only spurious in not satisfying the intent of the rule
that notes are only given when the deleted code appears in the original source;
there is always some code being deleted when a unreachable code note is
printed.
5.4.6 |
Multiple Values Optimization |
|
Within a function, Python implements uses of multiple values
particularly efficiently. Multiple values can be kept in arbitrary
registers, so using multiple values doesn't imply stack manipulation
and representation conversion. For example, this code:
(let ((a (if x (foo x) u))
(b (if x (bar x) v)))
...)
is actually more efficient written this way:
(multiple-value-bind
(a b)
(if x
(values (foo x) (bar x))
(values u v))
...)
Also, see section 5.6.5 for information on how local call
provides efficient support for multiple function return values.
5.4.7 |
Source to Source Transformation |
|
The compiler implements a number of operation-specific optimizations as
source-to-source transformations. You will often see unfamiliar code in error
messages, for example:
(defun my-zerop () (zerop x))
gives this warning:
In: DEFUN MY-ZEROP
(ZEROP X)
==>
(= X 0)
Warning: Undefined variable: X
The original zerop has been transformed into a call to
=. This transformation is indicated with the same ==>
used to mark macro and function inline expansion. Although it can be
confusing, display of the transformed source is important, since
warnings are given with respect to the transformed source. This a
more obscure example:
(defun foo (x) (logand 1 x))
gives this efficiency note:
In: DEFUN FOO
(LOGAND 1 X)
==>
(LOGAND C::Y C::X)
Note: Forced to do static-function Two-arg-and (cost 53).
Unable to do inline fixnum arithmetic (cost 1) because:
The first argument is a INTEGER, not a FIXNUM.
etc.
Here, the compiler commuted the call to logand, introducing
temporaries. The note complains that the first argument is not
a fixnum, when in the original call, it was the second
argument. To make things more confusing, the compiler introduced
temporaries called c::x and c::y that are bound to
y and 1, respectively.
You will also notice source-to-source optimizations when efficiency
notes are enabled (see section 5.13.) When the compiler is
unable to do a transformation that might be possible if there was more
information, then an efficiency note is printed. For example,
my-zerop above will also give this efficiency note:
In: DEFUN FOO
(ZEROP X)
==>
(= X 0)
Note: Unable to optimize because:
Operands might not be the same type, so can't open code.
5.4.8 |
Style Recommendations |
|
Source level optimization makes possible a clearer and more relaxed programming
style:
- Don't use macros purely to avoid function call. If you want an
inline function, write it as a function and declare it inline. It's
clearer, less error-prone, and works just as well.
- Don't write macros that try to ``optimize'' their expansion in
trivial ways such as avoiding binding variables for simple
expressions. The compiler does these optimizations too, and is less
likely to make a mistake.
- Make use of local functions (i.e., labels or flet)
and tail-recursion in places where it is clearer. Local function
call is faster than full call.
- Avoid setting local variables when possible. Binding a new
let variable is at least as efficient as setting an existing
variable, and is easier to understand, both for the compiler and the
programmer.
- Instead of writing similar code over and over again so that it
can be hand customized for each use, define a macro or inline
function, and let the compiler do the work.
A call is tail-recursive if nothing has to be done after the the call
returns, i.e. when the call returns, the returned value is immediately
returned from the calling function. In this example, the recursive
call to myfun is tail-recursive:
(defun myfun (x)
(if (oddp (random x))
(isqrt x)
(myfun (1- x))))
Tail recursion is interesting because it is form of recursion that can be
implemented much more efficiently than general recursion. In general, a
recursive call requires the compiler to allocate storage on the stack at
run-time for every call that has not yet returned. This memory consumption
makes recursion unacceptably inefficient for representing repetitive algorithms
having large or unbounded size. Tail recursion is the special case of
recursion that is semantically equivalent to the iteration constructs normally
used to represent repetition in programs. Because tail recursion is equivalent
to iteration, tail-recursive programs can be compiled as efficiently as
iterative programs.
So why would you want to write a program recursively when you can write it
using a loop? Well, the main answer is that recursion is a more general
mechanism, so it can express some solutions simply that are awkward to write as
a loop. Some programmers also feel that recursion is a stylistically
preferable way to write loops because it avoids assigning variables.
For example, instead of writing:
(defun fun1 (x)
something-that-uses-x)
(defun fun2 (y)
something-that-uses-y)
(do ((x something (fun2 (fun1 x))))
(nil))
You can write:
(defun fun1 (x)
(fun2 something-that-uses-x))
(defun fun2 (y)
(fun1 something-that-uses-y))
(fun1 something)
The tail-recursive definition is actually more efficient, in addition to being
(arguably) clearer. As the number of functions and the complexity of their
call graph increases, the simplicity of using recursion becomes compelling.
Consider the advantages of writing a large finite-state machine with separate
tail-recursive functions instead of using a single huge prog.
It helps to understand how to use tail recursion if you think of a
tail-recursive call as a psetq that assigns the argument values to the
called function's variables, followed by a go to the start of the called
function. This makes clear an inherent efficiency advantage of tail-recursive
call: in addition to not having to allocate a stack frame, there is no need to
prepare for the call to return (e.g., by computing a return PC.)
Is there any disadvantage to tail recursion? Other than an increase
in efficiency, the only way you can tell that a call has been compiled
tail-recursively is if you use the debugger. Since a tail-recursive
call has no stack frame, there is no way the debugger can print out
the stack frame representing the call. The effect is that backtrace
will not show some calls that would have been displayed in a
non-tail-recursive implementation. In practice, this is not as bad as
it sounds---in fact it isn't really clearly worse, just different.
See section 3.3.5 for information about the debugger
implications of tail recursion, and how to turn it off for the sake of
more conservative backtrace information.
In order to ensure that tail-recursion is preserved in arbitrarily
complex calling patterns across separately compiled functions, the
compiler must compile any call in a tail-recursive position as a
tail-recursive call. This is done regardless of whether the program
actually exhibits any sort of recursive calling pattern. In this
example, the call to fun2 will always be compiled as a
tail-recursive call:
(defun fun1 (x)
(fun2 x))
So tail recursion doesn't necessarily have anything to do with recursion
as it is normally thought of. See section 5.6.4 for more
discussion of using tail recursion to implement loops.
5.5.1 |
Tail Recursion Exceptions |
|
Although Python is claimed to be ``properly'' tail-recursive, some
might dispute this, since there are situations where tail recursion is
inhibited:
- When the call is enclosed by a special binding, or
- When the call is enclosed by a catch or
unwind-protect, or
- When the call is enclosed by a block or tagbody
and the block name or go tag has been closed over.
These dynamic extent binding forms inhibit tail recursion because they
allocate stack space to represent the binding. Shallow-binding
implementations of dynamic scoping also require cleanup code to be
evaluated when the scope is exited.
In addition, optimization of tail-recursive calls is inhibited when
the debug optimization quality is greater than 2
(see section 3.6.)
Python supports two kinds of function call: full call and local call.
Full call is the standard calling convention; its late binding and
generality make Common Lisp what it is, but create unavoidable overheads.
When the compiler can compile the calling function and the called
function simultaneously, it can use local call to avoid some of the
overhead of full call. Local call is really a collection of
compilation strategies. If some aspect of call overhead is not needed
in a particular local call, then it can be omitted. In some cases,
local call can be totally free. Local call provides two main
advantages to the user:
- Local call makes the use of the lexical function binding forms
flet and labels much more efficient. A local
call is always faster than a full call, and in many cases is much
faster.
- Local call is a natural approach to block compilation, a
compilation technique that resolves function references at compile
time. Block compilation speeds function call, but increases
compilation times and prevents function redefinition.
5.6.1 |
Self-Recursive Calls |
|
Local call is used when a function defined by defun calls itself. For
example:
(defun fact (n)
(if (zerop n)
1
(* n (fact (1- n)))))
This use of local call speeds recursion, but can also complicate
debugging, since trace will only show the first call to
fact, and not the recursive calls. This is because the
recursive calls directly jump to the start of the function, and don't
indirect through the symbol-function. Self-recursive local
call is inhibited when the :block-compile argument to
compile-file is nil (see section 5.7.3.)
Because local call avoids unnecessary call overheads, the compiler
internally uses local call to implement some macros and special forms
that are not normally thought of as involving a function call. For
example, this let:
(let ((a (foo))
(b (bar)))
...)
is internally represented as though it was macroexpanded into:
(funcall #'(lambda (a b)
...)
(foo)
(bar))
This implementation is acceptable because the simple cases of local
call (equivalent to a let) result in good code. This doesn't
make let any more efficient, but does make local calls that are
semantically the same as let much more efficient than full
calls. For example, these definitions are all the same as far as the
compiler is concerned:
(defun foo ()
...some other stuff...
(let ((a something))
...some stuff...))
(defun foo ()
(flet ((localfun (a)
...some stuff...))
...some other stuff...
(localfun something)))
(defun foo ()
(let ((funvar #'(lambda (a)
...some stuff...)))
...some other stuff...
(funcall funvar something)))
Although local call is most efficient when the function is called only
once, a call doesn't have to be equivalent to a let to be more
efficient than full call. All local calls avoid the overhead of
argument count checking and keyword argument parsing, and there are a
number of other advantages that apply in many common situations.
See section 5.4.1 for a discussion of the optimizations done on
let calls.
Local call allows for much more efficient use of closures, since the
closure environment doesn't need to be allocated on the heap, or even
stored in memory at all. In this example, there is no penalty for
localfun referencing a and b:
(defun foo (a b)
(flet ((localfun (x)
(1+ (* a b x))))
(if (= a b)
(localfun (- x))
(localfun x))))
In local call, the compiler effectively passes closed-over values as
extra arguments, so there is no need for you to ``optimize'' local
function use by explicitly passing in lexically visible values.
Closures may also be subject to let optimization
(see section 5.4.1.)
Note: indirect value cells are currently always allocated on the heap
when a variable is both assigned to (with setq or setf)
and closed over, regardless of whether the closure is a local function
or not. This is another reason to avoid setting variables when you
don't have to.
5.6.4 |
Local Tail Recursion |
|
Tail-recursive local calls are particularly efficient, since they are
in effect an assignment plus a control transfer. Scheme programmers
write loops with tail-recursive local calls, instead of using the
imperative go and setq. This has not caught on in the
Common Lisp community, since conventional Common Lisp compilers don't
implement local call. In Python, users can choose to write loops
such as:
(defun ! (n)
(labels ((loop (n total)
(if (zerop n)
total
(loop (1- n) (* n total)))))
(loop n 1)))
[Macro]
extensions:iterate name ({(var initial-value)}*)
{declaration}* {form}*
This macro provides syntactic sugar for using labels to
do iteration. It creates a local function name with the
specified vars as its arguments and the declarations and
forms as its body. This function is then called with the
initial-values, and the result of the call is return from the
macro.
Here is our factorial example rewritten using iterate:
(defun ! (n)
(iterate loop
((n n)
(total 1))
(if (zerop n)
total
(loop (1- n) (* n total)))))
The main advantage of using iterate over do is that
iterate naturally allows stepping to be done differently
depending on conditionals in the body of the loop. iterate
can also be used to implement algorithms that aren't really
iterative by simply doing a non-tail call. For example, the
standard recursive definition of factorial can be written like this:
(iterate fact
((n n))
(if (zerop n)
1
(* n (fact (1- n)))))
One of the more subtle costs of full call comes from allowing
arbitrary numbers of return values. This overhead can be avoided in
local calls to functions that always return the same number of values.
For efficiency reasons (as well as stylistic ones), you should write
functions so that they always return the same number of values. This
may require passing extra nil arguments to values in some
cases, but the result is more efficient, not less so.
When efficiency notes are enabled (see section 5.13), and the
compiler wants to use known values return, but can't prove that the
function always returns the same number of values, then it will print
a note like this:
In: DEFUN GRUE
(DEFUN GRUE (X) (DECLARE (FIXNUM X)) (COND (# #) (# NIL) (T #)))
Note: Return type not fixed values, so can't use known return convention:
(VALUES (OR (INTEGER -536870912 -1) NULL) &REST T)
In order to implement proper tail recursion in the presence of known
values return (see section 5.5), the compiler sometimes must
prove that multiple functions all return the same number of values.
When this can't be proven, the compiler will print a note like this:
In: DEFUN BLUE
(DEFUN BLUE (X) (DECLARE (FIXNUM X)) (COND (# #) (# #) (# #) (T #)))
Note: Return value count mismatch prevents known return from
these functions:
BLUE
SNOO
See section 5.11.10 for the interaction between local call
and the representation of numeric types.
Block compilation allows calls to global functions defined by
defun to be compiled as local calls. The function call
can be in a different top-level form than the defun, or even in a
different file.
In addition, block compilation allows the declaration of the entry points
to the block compiled portion. An entry point is any function that may be
called from outside of the block compilation. If a function is not an entry
point, then it can be compiled more efficiently, since all calls are known at
compile time. In particular, if a function is only called in one place, then
it will be let converted. This effectively inline expands the function, but
without the code duplication that results from defining the function normally
and then declaring it inline.
The main advantage of block compilation is that it it preserves efficiency in
programs even when (for readability and syntactic convenience) they are broken
up into many small functions. There is absolutely no overhead for calling a
non-entry point function that is defined purely for modularity (i.e. called
only in one place.)
Block compilation also allows the use of non-descriptor arguments and return
values in non-trivial programs (see section 5.11.10).
5.7.1 |
Block Compilation Semantics |
|
The effect of block compilation can be envisioned as the compiler turning all
the defuns in the block compilation into a single labels form:
(declaim (start-block fun1 fun3))
(defun fun1 ()
...)
(defun fun2 ()
...
(fun1)
...)
(defun fun3 (x)
(if x
(fun1)
(fun2)))
(declaim (end-block))
becomes:
(labels ((fun1 ()
...)
(fun2 ()
...
(fun1)
...)
(fun3 (x)
(if x
(fun1)
(fun2))))
(setf (fdefinition 'fun1) #'fun1)
(setf (fdefinition 'fun3) #'fun3))
Calls between the block compiled functions are local calls, so changing the
global definition of fun1 will have no effect on what fun2 does;
fun2 will keep calling the old fun1.
The entry points fun1 and fun3 are still installed in
the symbol-function as the global definitions of the functions,
so a full call to an entry point works just as before. However,
fun2 is not an entry point, so it is not globally defined. In
addition, fun2 is only called in one place, so it will be let
converted.
5.7.2 |
Block Compilation Declarations |
|
The extensions:start-block and extensions:end-block
declarations allow fine-grained control of block compilation. These
declarations are only legal as a global declarations (declaim
or proclaim).
The start-block declaration has this syntax:
(start-block {entry-point-name}*)
When processed by the compiler, this declaration marks the start of
block compilation, and specifies the entry points to that block. If
no entry points are specified, then all functions are made into
entry points. If already block compiling, then the compiler ends the
current block and starts a new one.
The end-block declaration has no arguments:
(end-block)
The end-block declaration ends a block compilation unit without
starting a new one. This is useful mainly when only a portion of a file
is worth block compiling.
The :block-compile and :entry-points arguments to
extensions:compile-from-stream and compile-file provide overall
control of block compilation, and allow block compilation without requiring
modification of the program source.
There are three possible values of the :block-compile argument:
- nil
- Do no compile-time resolution of global function
names, not even for self-recursive calls. This inhibits any
start-block declarations appearing in the file, allowing all
functions to be incrementally redefined.
- t
- Start compiling in block compilation mode. This is
mainly useful for block compiling small files that contain no
start-block declarations. See also the :entry-points
argument.
- :specified
- Start compiling in form-at-a-time mode, but
exploit any start-block declarations and compile
self-recursive calls as local calls. Normally :specified is
the default for this argument (see *block-compile-default*.)
The :entry-points argument can be used in conjunction with
:block-compile t to specify the entry-points to a
block-compiled file. If not specified or nil, all global functions
will be compiled as entry points. When :block-compile is not
t, this argument is ignored.
[Variable]
*block-compile-default*
This variable determines the default value for the
:block-compile argument to compile-file and
compile-from-stream. The initial value of this variable is
:specified, but nil is sometimes useful for totally
inhibiting block compilation.
5.7.4 |
Practical Difficulties |
|
The main problem with block compilation is that the compiler uses
large amounts of memory when it is block compiling. This places an
upper limit on the amount of code that can be block compiled as a
unit. To make best use of block compilation, it is necessary to
locate the parts of the program containing many internal calls, and
then add the appropriate start-block declarations. When writing
new code, it is a good idea to put in block compilation declarations
from the very beginning, since writing block declarations correctly
requires accurate knowledge of the program's function call structure.
If you want to initially develop code with full incremental
redefinition, you can compile with *block-compile-default* set to
nil.
Note if a defun appears in a non-null lexical environment, then
calls to it cannot be block compiled.
Unless files are very small, it is probably impractical to block compile
multiple files as a unit by specifying a list of files to compile-file.
Semi-inline expansion (see section 5.8.2) provides another way to
extend block compilation across file boundaries.
5.7.5 |
Context Declarations |
|
CMUCL has a context-sensitive declaration mechanism which is useful
because it allows flexible control of the compilation policy in large
systems without requiring changes to the source files. The primary
use of this feature is to allow the exported interfaces of a system to
be compiled more safely than the system internals. The context used
is the name being defined and the kind of definition (function, macro,
etc.)
The :context-declarations option to with-compilation-unit has
dynamic scope, affecting all compilation done during the evaluation of the
body. The argument to this option should evaluate to a list of lists of the
form:
(context-spec {declare-form}+)
In the indicated context, the specified declare forms are inserted at
the head of each definition. The declare forms for all contexts that
match are appended together, with earlier declarations getting
precedence over later ones. A simple example:
:context-declarations
'((:external (declare (optimize (safety 2)))))
This will cause all functions that are named by external symbols to be
compiled with safety 2.
The full syntax of context specs is:
- :internal, :external
- True if the symbol is internal
(external) in its home package.
- :uninterned
- True if the symbol has no home package.
- (:package {package-name}*)
- True if the
symbol's home package is in any of the named packages (false if
uninterned.)
- :anonymous
- True if the function doesn't have any
interesting name (not defmacro, defun, labels
or flet).
- :macro, :function
- :macro is a global
(defmacro) macro. :function is anything else.
- :local, :global
- :local is a labels or
flet. :global is anything else.
- (:or {context-spec}*)
- True when any
supplied context-spec is true.
- (:and {context-spec}*)
- True only when all
supplied context-specs are true.
- (:not {context-spec}*)
- True when
context-spec is false.
- (:member {name}*)
- True when the defined
name is one of these names (equal test.)
- (:match {pattern}*)
- True when any of the
patterns is a substring of the name. The name is wrapped with
$'s, so ``$FOO'' matches names beginning with
``FOO'', etc.
5.7.6 |
Context Declaration Example |
|
Here is a more complex example of with-compilation-unit options:
:optimize '(optimize (speed 2) (space 2) (inhibit-warnings 2)
(debug 1) (safety 0))
:optimize-interface '(optimize-interface (safety 1) (debug 1))
:context-declarations
'(((:or :external (:and (:match "%") (:match "SET")))
(declare (optimize-interface (safety 2))))
((:or (:and :external :macro)
(:match "$PARSE-"))
(declare (optimize (safety 2)))))
The optimize and extensions:optimize-interface
declarations (see section 4.7.1) set up the global
compilation policy. The bodies of functions are to be compiled
completely unsafe (safety 0), but argument count and weakened
argument type checking is to be done when a function is called
(speed 2 safety 1).
The first declaration specifies that all functions that are external
or whose names contain both ``%'' and ``SET'' are to be
compiled compiled with completely safe interfaces (safety 2).
The reason for this particular :match rule is that setf
inverse functions in this system tend to have both strings in their
name somewhere. We want setf inverses to be safe because they
are implicitly called by users even though their name is not exported.
The second declaration makes external macros or functions whose names
start with ``PARSE-'' have safe bodies (as well as interfaces).
This is desirable because a syntax error in a macro may cause a type
error inside the body. The :match rule is used because macros
often have auxiliary functions whose names begin with this string.
This particular example is used to build part of the standard CMUCL
system. Note however, that context declarations must be set up
according to the needs and coding conventions of a particular system;
different parts of CMUCL are compiled with different context
declarations, and your system will probably need its own declarations.
In particular, any use of the :match option depends on naming
conventions used in coding.
Python can expand almost any function inline, including functions
with keyword arguments. The only restrictions are that keyword
argument keywords in the call must be constant, and that global
function definitions (defun) must be done in a null lexical
environment (not nested in a let or other binding form.) Local
functions (flet) can be inline expanded in any environment.
Combined with Python's source-level optimization, inline expansion
can be used for things that formerly required macros for efficient
implementation. In Python, macros don't have any efficiency
advantage, so they need only be used where a macro's syntactic
flexibility is required.
Inline expansion is a compiler optimization technique that reduces
the overhead of a function call by simply not doing the call:
instead, the compiler effectively rewrites the program to appear as
though the definition of the called function was inserted at each
call site. In Common Lisp, this is straightforwardly expressed by
inserting the lambda corresponding to the original definition:
(proclaim '(inline my-1+))
(defun my-1+ (x) (+ x 1))
(my-1+ someval) ==> ((lambda (x) (+ x 1)) someval)
When the function expanded inline is large, the program after inline
expansion may be substantially larger than the original program. If
the program becomes too large, inline expansion hurts speed rather
than helping it, since hardware resources such as physical memory and
cache will be exhausted. Inline expansion is called for:
- When profiling has shown that a relatively simple function is
called so often that a large amount of time is being wasted in the
calling of that function (as opposed to running in that function.)
If a function is complex, it will take a long time to run relative
the time spent in call, so the speed advantage of inline expansion
is diminished at the same time the space cost of inline expansion is
increased. Of course, if a function is rarely called, then the
overhead of calling it is also insignificant.
- With functions so simple that they take less space to inline
expand than would be taken to call the function (such as
my-1+ above.) It would require intimate knowledge of the
compiler to be certain when inline expansion would reduce space, but
it is generally safe to inline expand functions whose definition is
a single function call, or a few calls to simple Common Lisp functions.
In addition to this speed/space tradeoff from inline expansion's
avoidance of the call, inline expansion can also reveal opportunities
for optimization. Python's extensive source-level optimization can
make use of context information from the caller to tremendously
simplify the code resulting from the inline expansion of a function.
The main form of caller context is local information about the actual
argument values: what the argument types are and whether the arguments
are constant. Knowledge about argument types can eliminate run-time
type tests (e.g., for generic arithmetic.) Constant arguments in a
call provide opportunities for constant folding optimization after
inline expansion.
A hidden way that constant arguments are often supplied to functions
is through the defaulting of unsupplied optional or keyword arguments.
There can be a huge efficiency advantage to inline expanding functions
that have complex keyword-based interfaces, such as this definition of
the member function:
(proclaim '(inline member))
(defun member (item list &key
(key #'identity)
(test #'eql testp)
(test-not nil notp))
(do ((list list (cdr list)))
((null list) nil)
(let ((car (car list)))
(if (cond (testp
(funcall test item (funcall key car)))
(notp
(not (funcall test-not item (funcall key car))))
(t
(funcall test item (funcall key car))))
(return list)))))
After inline expansion, this call is simplified to the obvious code:
(member a l :key #'foo-a :test #'char=) ==>
(do ((list list (cdr list)))
((null list) nil)
(let ((car (car list)))
(if (char= item (foo-a car))
(return list))))
In this example, there could easily be more than an order of magnitude
improvement in speed. In addition to eliminating the original call to
member, inline expansion also allows the calls to char=
and foo-a to be open-coded. We go from a loop with three tests
and two calls to a loop with one test and no calls.
See section 5.4 for more discussion of source level
optimization.
5.8.1 |
Inline Expansion Recording |
|
Inline expansion requires that the source for the inline expanded function to
be available when calls to the function are compiled. The compiler doesn't
remember the inline expansion for every function, since that would take an
excessive about of space. Instead, the programmer must tell the compiler to
record the inline expansion before the definition of the inline expanded
function is compiled. This is done by globally declaring the function inline
before the function is defined, by using the inline and
extensions:maybe-inline (see section 5.8.3)
declarations.
In addition to recording the inline expansion of inline functions at the time
the function is compiled, compile-file also puts the inline expansion in
the output file. When the output file is loaded, the inline expansion is made
available for subsequent compilations; there is no need to compile the
definition again to record the inline expansion.
If a function is declared inline, but no expansion is recorded, then the
compiler will give an efficiency note like:
Note: MYFUN is declared inline, but has no expansion.
When you get this note, check that the inline declaration and the
definition appear before the calls that are to be inline expanded. This note
will also be given if the inline expansion for a defun could not be
recorded because the defun was in a non-null lexical environment.
5.8.2 |
Semi-Inline Expansion |
|
Python supports semi-inline functions. Semi-inline expansion
shares a single copy of a function across all the calls in a component
by converting the inline expansion into a local function
(see section 5.6.) This takes up less space when there are
multiple calls, but also provides less opportunity for context
dependent optimization. When there is only one call, the result is
identical to normal inline expansion. Semi-inline expansion is done
when the space optimization quality is 0, and the
function has been declared extensions:maybe-inline.
This mechanism of inline expansion combined with local call also
allows recursive functions to be inline expanded. If a recursive
function is declared inline, calls will actually be compiled
semi-inline. Although recursive functions are often so complex that
there is little advantage to semi-inline expansion, it can still be
useful in the same sort of cases where normal inline expansion is
especially advantageous, i.e. functions where the calling context can
help a lot.
5.8.3 |
The Maybe-Inline Declaration |
|
The extensions:maybe-inline declaration is a CMUCL
extension. It is similar to inline, but indicates that inline
expansion may sometimes be desirable, rather than saying that inline
expansion should almost always be done. When used in a global
declaration, extensions:maybe-inline causes the expansion for
the named functions to be recorded, but the functions aren't actually
inline expanded unless space is 0 or the function is
eventually (perhaps locally) declared inline.
Use of the extensions:maybe-inline declaration followed by the
defun is preferable to the standard idiom of:
(proclaim '(inline myfun))
(defun myfun () ...)
(proclaim '(notinline myfun))
;;; Any calls to myfun here are not inline expanded.
(defun somefun ()
(declare (inline myfun))
;;
;; Calls to myfun here are inline expanded.
...)
The problem with using notinline in this way is that in
Common Lisp it does more than just suppress inline expansion, it also
forbids the compiler to use any knowledge of myfun until a
later inline declaration overrides the notinline. This
prevents compiler warnings about incorrect calls to the function, and
also prevents block compilation.
The extensions:maybe-inline declaration is used like this:
(proclaim '(extensions:maybe-inline myfun))
(defun myfun () ...)
;;; Any calls to myfun here are not inline expanded.
(defun somefun ()
(declare (inline myfun))
;;
;; Calls to myfun here are inline expanded.
...)
(defun someotherfun ()
(declare (optimize (space 0)))
;;
;; Calls to myfun here are expanded semi-inline.
...)
In this example, the use of extensions:maybe-inline causes the
expansion to be recorded when the defun for somefun is
compiled, and doesn't waste space through doing inline expansion by
default. Unlike notinline, this declaration still allows the
compiler to assume that the known definition really is the one that
will be called when giving compiler warnings, and also allows the
compiler to do semi-inline expansion when the policy is appropriate.
When the goal is merely to control whether inline expansion is done by
default, it is preferable to use extensions:maybe-inline rather
than notinline. The notinline declaration should be
reserved for those special occasions when a function may be redefined
at run-time, so the compiler must be told that the obvious definition
of a function is not necessarily the one that will be in effect at the
time of the call.
5.9 |
Byte Coded Compilation |
|
Python supports byte compilation to reduce the size of Lisp
programs by allowing functions to be compiled more compactly. Byte
compilation provides an extreme speed/space tradeoff: byte code is
typically six times more compact than native code, but runs fifty
times (or more) slower. This is about ten times faster than the
standard interpreter, which is itself considered fast in comparison to
other Common Lisp interpreters.
Large Lisp systems (such as CMUCL itself) often have large amounts
of user-interface code, compile-time (macro) code, debugging code, or
rarely executed special-case code. This code is a good target for
byte compilation: very little time is spent running in it, but it can
take up quite a bit of space. Straight-line code with many function
calls is much more suitable than inner loops.
When byte-compiling, the compiler compiles about twice as fast, and
can produce a hardware independent object file (.bytef type.)
This file can be loaded like a normal fasl file on any implementation
of CMUCL with the same byte-ordering.
The decision to byte compile or native compile can be done on a
per-file or per-code-object basis. The :byte-compile argument to
compile-file has these possible values:
-
nil
- Don't byte compile anything in this file.
- t
- Byte compile everything in this file and produce a
processor-independent .bytef file.
- :maybe
- Produce a normal fasl file, but byte compile any
functions for which the speed optimization quality is
0 and the debug quality is not greater than 1.
[Variable]
extensions:*byte-compile-top-level*
If this variable is true (the default) and the :byte-compile
argument to compile-file is :maybe, then byte compile
top-level code (code outside of any defun, defmethod,
etc.)
[Variable]
extensions:*byte-compile-default*
This variable determines the default value for the
:byte-compile argument to compile-file, initially
:maybe.
5.10 |
Object Representation |
|
A somewhat subtle aspect of writing efficient Common Lisp programs is
choosing the correct data structures so that the underlying objects
can be implemented efficiently. This is partly because of the need
for multiple representations for a given value
(see section 5.11.2), but is also due to the sheer number of
object types that Common Lisp has built in. The number of possible
representations complicates the choice of a good representation
because semantically similar objects may vary in their efficiency
depending on how the program operates on them.
5.10.1 |
Think Before You Use a List |
|
Although Lisp's creator seemed to think that it was for LISt
Processing, the astute observer may have noticed that the chapter on
list manipulation makes up less that three percent of Common Lisp: The Language II. The
language has grown since Lisp 1.5---new data types supersede lists
for many purposes.
5.10.2 |
Structure Representation |
|
One of the best ways of
building complex data structures is to define appropriate structure
types using defstruct. In Python, access of structure
slots is always at least as fast as list or vector access, and is
usually faster. In comparison to a list representation of a tuple,
structures also have a space advantage.
Even if structures weren't more efficient than other representations, structure
use would still be attractive because programs that use structures in
appropriate ways are much more maintainable and robust than programs written
using only lists. For example:
(rplaca (caddr (cadddr x)) (caddr y))
could have been written using structures in this way:
(setf (beverage-flavor (astronaut-beverage x)) (beverage-flavor y))
The second version is more maintainable because it is easier to
understand what it is doing. It is more robust because structures
accesses are type checked. An astronaut will never be confused
with a beverage, and the result of beverage-flavor is
always a flavor. See sections 5.2.8 and
5.2.9 for more information about structure types.
See section 5.3 for a number of examples that make clear the
advantages of structure typing.
Note that the structure definition should be compiled before any uses
of its accessors or type predicate so that these function calls can be
efficiently open-coded.
Arrays are often the most efficient representation for collections of objects
because:
- Array representations are often the most compact. An array is
always more compact than a list containing the same number of
elements.
- Arrays allow fast constant-time access.
- Arrays are easily destructively modified, which can reduce
consing.
- Array element types can be specialized, which reduces both
overall size and consing (see section 5.11.8.)
Access of arrays that are not of type simple-array is less
efficient, so declarations are appropriate when an array is of a
simple type like simple-string or simple-bit-vector.
Arrays are almost always simple, but the compiler may not be able to
prove simpleness at every use. The only way to get a non-simple array
is to use the :displaced-to, :fill-pointer or
adjustable arguments to make-array. If you don't use
these hairy options, then arrays can always be declared to be simple.
Because of the many specialized array types and the possibility of
non-simple arrays, array access is much like generic arithmetic
(see section 5.11.4). In order for array accesses to be
efficiently compiled, the element type and simpleness of the array
must be known at compile time. If there is inadequate information,
the compiler is forced to call a generic array access routine. You
can detect inefficient array accesses by enabling efficiency notes,
see section 5.13.
Vectors (one dimensional arrays) are particularly useful, since in
addition to their obvious array-like applications, they are also well
suited to representing sequences. In comparison to a list
representation, vectors are faster to access and take up between two
and sixty-four times less space (depending on the element type.) As
with arbitrary arrays, the compiler needs to know that vectors are not
complex, so you should use simple-string in preference to
string, etc.
The only advantage that lists have over vectors for representing
sequences is that it is easy to change the length of a list, add to it
and remove items from it. Likely signs of archaic, slow lisp code are
nth and nthcdr. If you are using these functions you
should probably be using a vector.
Another thing that lists have been used for is set manipulation. In
applications where there is a known, reasonably small universe of
items bit-vectors can be used to improve performance. This is much
less convenient than using lists, because instead of symbols, each
element in the universe must be assigned a numeric index into the bit
vector. Using a bit-vector will nearly always be faster, and can be
tremendously faster if the number of elements in the set is not small.
The logical operations on simple-bit-vectors are efficient,
since they operate on a word at a time.
Hashtables are an efficient and general mechanism for maintaining associations
such as the association between an object and its name. Although hashtables
are usually the best way to maintain associations, efficiency and style
considerations sometimes favor the use of an association list (a-list).
assoc is fairly fast when the test argument is eq
or eql and there are only a few elements, but the time goes up
in proportion with the number of elements. In contrast, the
hash-table lookup has a somewhat higher overhead, but the speed is
largely unaffected by the number of entries in the table. For an
equal hash-table or alist, hash-tables have an even greater
advantage, since the test is more expensive. Whatever you do, be sure
to use the most restrictive test function possible.
The style argument observes that although hash-tables and alists
overlap in function, they do not do all things equally well.
- Alists are good for maintaining scoped environments. They were
originally invented to implement scoping in the Lisp interpreter,
and are still used for this in Python. With an alist one can
non-destructively change an association simply by consing a new
element on the front. This is something that cannot be done with
hash-tables.
- Hashtables are good for maintaining a global association. The
value associated with an entry can easily be changed with
setf. With an alist, one has to go through contortions,
either rplacd'ing the cons if the entry exists, or pushing a
new one if it doesn't. The side-effecting nature of hash-table
operations is an advantage here.
Historically, symbol property lists were often used for global name
associations. Property lists provide an awkward and error-prone
combination of name association and record structure. If you must use
the property list, please store all the related values in a single
structure under a single property, rather than using many properties.
This makes access more efficient, and also adds a modicum of typing
and abstraction. See section 5.2 for information on types
in CMUCL.
Numbers are interesting because numbers are one of the few Common Lisp data types
that have direct support in conventional hardware. If a number can be
represented in the way that the hardware expects it, then there is a big
efficiency advantage.
Using hardware representations is problematical in Common Lisp due to
dynamic typing (where the type of a value may be unknown at compile
time.) It is possible to compile code for statically typed portions
of a Common Lisp program with efficiency comparable to that obtained in
statically typed languages such as C, but not all Common Lisp
implementations succeed. There are two main barriers to efficient
numerical code in Common Lisp:
- The compiler must prove that the numerical expression is in fact
statically typed, and
- The compiler must be able to somehow reconcile the conflicting
demands of the hardware mandated number representation with the
Common Lisp requirements of dynamic typing and garbage-collecting
dynamic storage allocation.
Because of its type inference (see section 5.3) and efficiency
notes (see section 5.13), Python is better than
conventional Common Lisp compilers at ensuring that numerical expressions
are statically typed. Python also goes somewhat farther than existing
compilers in the area of allowing native machine number
representations in the presence of garbage collection.
Common Lisp's dynamic typing requires that it be possible to represent
any value with a fixed length object, known as a descriptor.
This fixed-length requirement is implicit in features such as:
- Data types (like simple-vector) that can contain any type
of object, and that can be destructively modified to contain
different objects (of possibly different types.)
- Functions that can be called with any type of argument, and that
can be redefined at run time.
In order to save space, a descriptor is invariably represented as a
single word. Objects that can be directly represented in the
descriptor itself are said to be immediate. Descriptors for
objects larger than one word are in reality pointers to the memory
actually containing the object.
Representing objects using pointers has two major disadvantages:
- The memory pointed to must be allocated on the heap, so it must
eventually be freed by the garbage collector. Excessive heap
allocation of objects (or ``consing'') is inefficient in several
ways. See section 5.12.2.
- Representing an object in memory requires the compiler to emit
additional instructions to read the actual value in from memory, and
then to write the value back after operating on it.
The introduction of garbage collection makes things even worse, since
the garbage collector must be able to determine whether a descriptor
is an immediate object or a pointer. This requires that a few bits in
each descriptor be dedicated to the garbage collector. The loss of a
few bits doesn't seem like much, but it has a major efficiency
implication---objects whose natural machine representation is a
full word (integers and single-floats) cannot have an immediate
representation. So the compiler is forced to use an unnatural
immediate representation (such as fixnum) or a natural pointer
representation (with the attendant consing overhead.)
5.11.2 |
Non-Descriptor Representations |
|
From the discussion above, we can see that the standard descriptor
representation has many problems, the worst being number consing.
Common Lisp compilers try to avoid these descriptor efficiency problems by using
non-descriptor representations. A compiler that uses non-descriptor
representations can compile this function so that it does no number consing:
(defun multby (vec n)
(declare (type (simple-array single-float (*)) vec)
(single-float n))
(dotimes (i (length vec))
(setf (aref vec i)
(* n (aref vec i)))))
If a descriptor representation were used, each iteration of the loop might
cons two floats and do three times as many memory references.
As its negative definition suggests, the range of possible non-descriptor
representations is large. The performance improvement from non-descriptor
representation depends upon both the number of types that have non-descriptor
representations and the number of contexts in which the compiler is forced to
use a descriptor representation.
Many Common Lisp compilers support non-descriptor representations for
float types such as single-float and double-float
(section 5.11.7.) Python adds support for full
word integers (see section 5.11.6), characters
(see section 5.11.11) and system-area pointers (unconstrained
pointers, see section 6.5.) Many Common Lisp compilers
support non-descriptor representations for variables (section
5.11.3) and array elements (section
5.11.8.) Python adds support for
non-descriptor arguments and return values in local call
(see section 5.11.10) and structure slots (see section 5.11.9).
In order to use a non-descriptor representation for a variable or
expression intermediate value, the compiler must be able to prove that
the value is always of a particular type having a non-descriptor
representation. Type inference (see section 5.3) often needs
some help from user-supplied declarations. The best kind of type
declaration is a variable type declaration placed at the binding
point:
(let ((x (car l)))
(declare (single-float x))
...)
Use of the, or of variable declarations not at the binding form
is insufficient to allow non-descriptor representation of the
variable---with these declarations it is not certain that all
values of the variable are of the right type. It is sometimes useful
to introduce a gratuitous binding that allows the compiler to change
to a non-descriptor representation, like:
(etypecase x
((signed-byte 32)
(let ((x x))
(declare (type (signed-byte 32) x))
...))
...)
The declaration on the inner x is necessary here due to a phase
ordering problem. Although the compiler will eventually prove that
the outer x is a (signed-byte 32) within that
etypecase branch, the inner x would have been optimized
away by that time. Declaring the type makes let optimization more
cautious.
Note that storing a value into a global (or special) variable
always forces a descriptor representation. Wherever possible, you
should operate only on local variables, binding any referenced globals
to local variables at the beginning of the function, and doing any
global assignments at the end.
Efficiency notes signal use of inefficient representations, so
programmer's needn't continuously worry about the details of
representation selection (see section 5.13.3.)
In Common Lisp, arithmetic operations are generic.3
The + function can be passed fixnums, bignums,
ratios, and various kinds of floats and
complexes, in any combination. In addition to the inherent
complexity of bignum and ratio operations, there is also
a lot of overhead in just figuring out which operation to do and what
contagion and canonicalization rules apply. The complexity of generic
arithmetic is so great that it is inconceivable to open code it.
Instead, the compiler does a function call to a generic arithmetic
routine, consuming many instructions before the actual computation
even starts.
This is ridiculous, since even Common Lisp programs do a lot of
arithmetic, and the hardware is capable of doing operations on small
integers and floats with a single instruction. To get acceptable
efficiency, the compiler special-cases uses of generic arithmetic that
are directly implemented in the hardware. In order to open code
arithmetic, several constraints must be met:
- All the arguments must be known to be a good type of number.
- The result must be known to be a good type of number.
- Any intermediate values such as the result of (+ a b)
in the call (+ a b c) must be known to be a good type of
number.
- All the above numbers with good types must be of the same
good type. Don't try to mix integers and floats or different float
formats.
The ``good types'' are (signed-byte 32),
(unsigned-byte 32), single-float,
double-float, (complex single-float), and (complex
double-float). See sections 5.11.5, 5.11.6
and 5.11.7 for more discussion of good numeric types.
float is not a good type, since it might mean either
single-float or double-float. integer is not a
good type, since it might mean bignum. rational is not
a good type, since it might mean ratio. Note however that
these types are still useful in declarations, since type inference may
be able to strengthen a weak declaration into a good one, when it
would be at a loss if there was no declaration at all
(see section 5.3). The integer and
unsigned-byte (or non-negative integer) types are especially
useful in this regard, since they can often be strengthened to a good
integer type.
As noted above, CMUCL has support for (complex single-float)
and (complex double-float). These can be unboxed and, thus,
are quite efficient. However, arithmetic with complex types such as:
(complex float)
(complex fixnum)
will be significantly slower than the good complex types but is still
faster than bignum or ratio arithmetic, since the
implementation is much simpler.
Note: don't use / to divide integers unless you want the
overhead of rational arithmetic. Use truncate even when you
know that the arguments divide evenly.
You don't need to remember all the rules for how to get open-coded
arithmetic, since efficiency notes will tell you when and where there
is a problem---see section 5.13.
A fixnum is a ``FIXed precision NUMber''. In modern Common Lisp
implementations, fixnums can be represented with an immediate
descriptor, so operating on fixnums requires no consing or memory
references. Clever choice of representations also allows some
arithmetic operations to be done on fixnums using hardware supported
word-integer instructions, somewhat reducing the speed penalty for
using an unnatural integer representation.
It is useful to distinguish the fixnum type from the fixnum
representation of integers. In Python, there is absolutely nothing
magical about the fixnum type in comparison to other finite
integer types. fixnum is equivalent to (is defined with
deftype to be) (signed-byte 30). fixnum is
simply the largest subset of integers that can be represented
using an immediate fixnum descriptor.
Unlike in other Common Lisp compilers, it is in no way desirable to use
the fixnum type in declarations in preference to more
restrictive integer types such as bit, (integer -43
7) and (unsigned-byte 8). Since Python does
understand these integer types, it is preferable to use the more
restrictive type, as it allows better type inference
(see section 5.3.4.)
The small, efficient fixnum is contrasted with bignum, or ``BIG
NUMber''. This is another descriptor representation for integers, but
this time a pointer representation that allows for arbitrarily large
integers. Bignum operations are less efficient than fixnum
operations, both because of the consing and memory reference overheads
of a pointer descriptor, and also because of the inherent complexity
of extended precision arithmetic. While fixnum operations can often
be done with a single instruction, bignum operations are so complex
that they are always done using generic arithmetic.
A crucial point is that the compiler will use generic arithmetic if it
can't prove that all the arguments, intermediate values, and
results are fixnums. With bounded integer types such as
fixnum, the result type proves to be especially problematical,
since these types are not closed under common arithmetic operations
such as +, -, * and /. For example,
(1+ (the fixnum x)) does not necessarily evaluate to a
fixnum. Bignums were added to Common Lisp to get around this
problem, but they really just transform the correctness problem ``if
this add overflows, you will get the wrong answer'' to the efficiency
problem ``if this add might overflow then your program will run
slowly (because of generic arithmetic.)''
There is just no getting around the fact that the hardware only
directly supports short integers. To get the most efficient open
coding, the compiler must be able to prove that the result is a good
integer type. This is an argument in favor of using more restrictive
integer types: (1+ (the fixnum x)) may not always be a
fixnum, but (1+ (the (unsigned-byte 8) x)) always
is. Of course, you can also assert the result type by putting in lots
of the declarations and then compiling with safety
0.
Python is unique in its efficient implementation of arithmetic
on full-word integers through non-descriptor representations and open coding.
Arithmetic on any subtype of these types:
(signed-byte 32)
(unsigned-byte 32)
is reasonably efficient, although subtypes of fixnum remain
somewhat more efficient.
If a word integer must be represented as a descriptor, then the
bignum representation is used, with its associated consing
overhead. The support for word integers in no way changes the
language semantics, it just makes arithmetic on small bignums vastly
more efficient. It is fine to do arithmetic operations with mixed
fixnum and word integer operands; just declare the most
specific integer type you can, and let the compiler decide what
representation to use.
In fact, to most users, the greatest advantage of word integer
arithmetic is that it effectively provides a few guard bits on the
fixnum representation. If there are missing assertions on
intermediate values in a fixnum expression, the intermediate results
can usually be proved to fit in a word. After the whole expression is
evaluated, there will often be a fixnum assertion on the final result,
allowing creation of a fixnum result without even checking for
overflow.
The remarks in section 5.11.5 about fixnum result type also
apply to word integers; you must be careful to give the compiler
enough information to prove that the result is still a word integer.
This time, though, when we blow out of word integers we land in into
generic bignum arithmetic, which is much worse than sleazing from
fixnums to word integers. Note that mixing
(unsigned-byte 32) arguments with arguments of any signed
type (such as fixnum) is a no-no, since the result might not be
unsigned.
5.11.7 |
Floating Point Efficiency |
|
Arithmetic on objects of type single-float and double-float is
efficiently implemented using non-descriptor representations and open coding.
As for integer arithmetic, the arguments must be known to be of the same float
type. Unlike for integer arithmetic, the results and intermediate values
usually take care of themselves due to the rules of float contagion, i.e.
(1+ (the single-float x)) is always a single-float.
Although they are not specially implemented, short-float and
long-float are also acceptable in declarations, since they are
synonyms for the single-float and double-float types,
respectively.
In CMUCL, list-style float type specifiers such as
(single-float 0.0 1.0) will be used to good effect.
For example, in this function,
(defun square (x)
(declare (type (single-float 0f0 10f0)))
(* x x))
Python can deduce that the
return type of the function square is (single-float
0f0 100f0).
Many union types are also supported so that
(+ (the (or (integer 1 1) (integer 5 5)) x)
(the (or (integer 10 10) (integer 20 20)) y))
has the inferred type (or (integer 11 11) (integer 15 15)
(integer 21 21) (integer 25 25)). This also works for
floating-point numbers. Member types are also supported.
CMUCL can also infer types for many mathematical functions
including square root, exponential and logarithmic functions,
trignometric functions and their inverses, and hyperbolic functions
and their inverses. For numeric code, this can greatly enhance
efficiency by allowing the compiler to use specialized versions of
the functions instead of the generic versions. The greatest benefit
of this type inference is determining that the result of the
function is real-valued number instead of possibly being
a complex-valued number.
For example, consider the function
(defun fun (x)
(declare (type (single-float (0f0) 100f0) x))
(values (sqrt x) (log x)))
With this declaration, the compiler can determine that the argument
to sqrt and log are always non-negative so that the result
is always a single-float. In fact, the return type for this
function is derived to be (values (single-float 0f0 10f0)
(single-float * 2f0)).
If the declaration were reduced to just (declare
(single-float x)), the argument to sqrt and log
could be negative. This forces the use of the generic versions of
these functions because the result could be a complex number.
We note, however, that proper interval arithmetic is not fully
implemented in the compiler so the inferred types may be slightly in
error due to round-off errors. This round-off error could
accumulate to cause the compiler to erroneously deduce the result
type and cause code to be removed as being
unreachable.4Thus, the declarations should only be precise enough for the
compiler to deduce that a real-valued argument to a function would
produce a real-valued result. The efficiency notes
(see section 5.13.3) from the compiler will guide you
on what declarations might be useful.
When a float must be represented as a descriptor, a pointer representation is
used, creating consing overhead. For this reason, you should try to avoid
situations (such as full call and non-specialized data structures) that force a
descriptor representation. See sections 5.11.8,
5.11.9 and 5.11.10.
See section 2.1.2 for information on the extensions to support IEEE
floating point.
5.11.7.1 |
Signed Zeroes and Special Functions |
|
CMUCL supports IEEE signed zeroes. In typical usage, the signed
zeroes are not a problem and can be treated as an unsigned zero.
However, some of the special functions have branch points at zero, so
care must be taken.
For example, suppose we have the function
(defun fun (x)
(declare (type (single-float 0f0) x))
(log x))
The derived result of the function is (OR SINGLE-FLOAT
(COMPLEX SINGLE-FLOAT)) because the declared values for
x includes both -0.0 and 0.0 and (log -0.0) is
actually a complex number. Because of this, the generic complex log
routine is used.
If the declaration for x were (single-float (0f0)) so +0.0
is not included or (or (single-float (0f0)) (member 0f0)) so
+0.0 is include but not -0.0, the derived type would be
single-float for both cases. By declaring x this way,
the log can be implemented using a fast real-valued log routine
instead of the generic log routine.
CMUCL implements the branch cuts and values given by
Kahan5.
Common Lisp supports specialized array element types through the
:element-type argument to make-array. When an array has a
specialized element type, only elements of that type can be stored in
the array. From this restriction comes two major efficiency
advantages:
- A specialized array can save space by packing multiple elements
into a single word. For example, a base-char array can have
4 elements per word, and a bit array can have 32. This
space-efficient representation is possible because it is not
necessary to separately indicate the type of each element.
- The elements in a specialized array can be given the same
non-descriptor representation as the one used in registers and on
the stack, eliminating the need for representation conversions when
reading and writing array elements. For objects with pointer
descriptor representations (such as floats and word integers) there
is also a substantial consing reduction because it is not necessary
to allocate a new object every time an array element is modified.
These are the specialized element types currently supported:
bit
(unsigned-byte 2)
(unsigned-byte 4)
(unsigned-byte 8)
(unsigned-byte 16)
(unsigned-byte 32)
(signed-byte 8)
(signed-byte 16)
(signed-byte 30)
(signed-byte 32)
base-character
single-float
double-float
ext:double-double-float
(complex single-float)
(complex double-float)
(complex ext:double-double-float)
Although a simple-vector can hold any type of object, t
should still be considered a specialized array type, since arrays with
element type t are specialized to hold descriptors.
When using non-descriptor representations, it is particularly
important to make sure that array accesses are open-coded, since in
addition to the generic operation overhead, efficiency is lost when
the array element is converted to a descriptor so that it can be
passed to (or from) the generic access routine. You can detect
inefficient array accesses by enabling efficiency notes,
see section 5.13. See section 5.10.3.
5.11.9 |
Specialized Structure Slots |
|
Structure slots declared by the :type defstruct slot option
to have certain known numeric types are also given non-descriptor
representations. These types (and subtypes of these types) are supported:
(unsigned-byte 32)
single-float
double-float
(complex single-float)
(complex double-float)
The primary advantage of specialized slot representations is a large
reduction spurious memory allocation and access overhead of programs
that intensively use these types.
5.11.10 |
Interactions With Local Call |
|
Local call has many advantages (see section 5.6); one relevant to
our discussion here is that local call extends the usefulness of
non-descriptor representations. If the compiler knows from the
argument type that an argument has a non-descriptor representation,
then the argument will be passed in that representation. The easiest
way to ensure that the argument type is known at compile time is to
always declare the argument type in the called function, like:
(defun 2+f (x)
(declare (single-float x))
(+ x 2.0))
The advantages of passing arguments and return values in a non-descriptor
representation are the same as for non-descriptor representations in general:
reduced consing and memory access (see section 5.11.2.) This
extends the applicative programming styles discussed in section
5.6 to numeric code. Also, if source files are kept reasonably
small, block compilation can be used to reduce number consing to a minimum.
Note that non-descriptor return values can only be used with the known return
convention (section 5.6.5.) If the compiler can't prove that
a function always returns the same number of values, then it must use the
unknown values return convention, which requires a descriptor representation.
Pay attention to the known return efficiency notes to avoid number consing.
5.11.11 |
Representation of Characters |
|
Python also uses a non-descriptor representation for characters when
convenient. This improves the efficiency of string manipulation, but is
otherwise pretty invisible; characters have an immediate descriptor
representation, so there is not a great penalty for converting a character to a
descriptor. Nonetheless, it may sometimes be helpful to declare
character-valued variables as base-character.
5.12 |
General Efficiency Hints |
|
This section is a summary of various implementation costs and ways to get
around them. These hints are relatively unrelated to the use of the Python
compiler, and probably also apply to most other Common Lisp implementations. In
each section, there are references to related in-depth discussion.
At this point, the advantages of compiling code relative to running it
interpreted probably need not be emphasized too much, but remember that
in CMUCL, compiled code typically runs hundreds of times faster than
interpreted code. Also, compiled (fasl) files load significantly faster
than source files, so it is worthwhile compiling files which are loaded many
times, even if the speed of the functions in the file is unimportant.
Even disregarding the efficiency advantages, compiled code is as good or better
than interpreted code. Compiled code can be debugged at the source level (see
chapter 3), and compiled code does more error checking. For these
reasons, the interpreter should be regarded mainly as an interactive command
interpreter, rather than as a programming language implementation.
Do not be concerned about the performance of your program until you
see its speed compiled. Some techniques that make compiled code run
faster make interpreted code run slower.
5.12.2 |
Avoid Unnecessary Consing |
|
Consing is another name for allocation of storage, as done by the
cons function (hence its name.) cons is by no means the
only function which conses---so does make-array and many
other functions. Arithmetic and function call can also have hidden
consing overheads. Consing hurts performance in the following ways:
- Consing reduces memory access locality, increasing paging
activity.
- Consing takes time just like anything else.
- Any space allocated eventually needs to be reclaimed, either by
garbage collection or by starting a new lisp process.
Consing is not undiluted evil, since programs do things other than
consing, and appropriate consing can speed up the real work. It would
certainly save time to allocate a vector of intermediate results that
are reused hundreds of times. Also, if it is necessary to copy a
large data structure many times, it may be more efficient to update
the data structure non-destructively; this somewhat increases update
overhead, but makes copying trivial.
Note that the remarks in section 5.1.5 about the
importance of separating tuning from coding also apply to consing
overhead. The majority of consing will be done by a small portion of
the program. The consing hot spots are even less predictable than the
CPU hot spots, so don't waste time and create bugs by doing
unnecessary consing optimization. During initial coding, avoid
unnecessary side-effects and cons where it is convenient. If
profiling reveals a consing problem, then go back and fix the
hot spots.
See section 5.11.2 for a discussion of how to avoid number consing
in Python.
5.12.3 |
Complex Argument Syntax |
|
Common Lisp has very powerful argument passing mechanisms. Unfortunately, two
of the most powerful mechanisms, rest arguments and keyword arguments, have a
significant performance penalty:
-
With keyword arguments, the called function has to parse the supplied keywords
by iterating over them and checking them against the desired keywords.
- With rest arguments, the function must cons a list to hold the arguments. If a
function is called many times or with many arguments, large amounts of memory
will be allocated.
Although rest argument consing is worse than keyword parsing, neither problem
is serious unless thousands of calls are made to such a function. The use of
keyword arguments is strongly encouraged in functions with many arguments or
with interfaces that are likely to be extended, and rest arguments are often
natural in user interface functions.
Optional arguments have some efficiency advantage over keyword
arguments, but their syntactic clumsiness and lack of extensibility
has caused many Common Lisp programmers to abandon use of optionals
except in functions that have obviously simple and immutable
interfaces (such as subseq), or in functions that are only
called in a few places. When defining an interface function to be
used by other programmers or users, use of only required and keyword
arguments is recommended.
Parsing of defmacro keyword and rest arguments is done at
compile time, so a macro can be used to provide a convenient syntax
with an efficient implementation. If the macro-expanded form contains
no keyword or rest arguments, then it is perfectly acceptable in inner
loops.
Keyword argument parsing overhead can also be avoided by use of inline
expansion (see section 5.8) and block compilation (section
5.7.)
Note: the compiler open-codes most heavily used system functions which have
keyword or rest arguments, so that no run-time overhead is involved.
One of the traditional Common Lisp programming styles is a highly applicative one,
involving the use of mapping functions and many lists to store intermediate
results. To compute the sum of the square-roots of a list of numbers, one
might say:
(apply #'+ (mapcar #'sqrt list-of-numbers))
This programming style is clear and elegant, but unfortunately results
in slow code. There are two reasons why:
-
The creation of lists of intermediate results causes much
consing (see 5.12.2).
- Each level of application requires another scan down the list.
Thus, disregarding other effects, the above code would probably take
twice as long as a straightforward iterative version.
An example of an iterative version of the same code:
(do ((num list-of-numbers (cdr num))
(sum 0 (+ (sqrt (car num)) sum)))
((null num) sum))
See sections 5.3.1 and 5.4.1
for a discussion of the interactions of iteration constructs with type
inference and variable optimization. Also, section
5.6.4 discusses an applicative style of
iteration.
5.12.5 |
Trace Files and Disassembly |
|
In order to write efficient code, you need to know the relative costs
of different operations. The main reason why writing efficient
Common Lisp code is difficult is that there are so many operations, and
the costs of these operations vary in obscure context-dependent ways.
Although efficiency notes point out some problem areas, the only way
to ensure generation of the best code is to look at the assembly code
output.
The disassemble function is a convenient way to get the assembly code for a
function, but it can be very difficult to interpret, since the correspondence
with the original source code is weak. A better (but more awkward) option is
to use the :trace-file argument to compile-file to generate a trace
file.
A trace file is a dump of the compiler's internal representations,
including annotated assembly code. Each component in the program gets
four pages in the trace file (separated by `` L''):
- The implicit-continuation (or IR1) representation of the
optimized source. This is a dump of the flow graph representation
used for ``source level'' optimizations. As you will quickly
notice, it is not really very close to the source. This
representation is not very useful to even sophisticated users.
- The Virtual Machine (VM, or IR2) representation of the program.
This dump represents the generated code as sequences of ``Virtual
OPerations'' (VOPs.) This representation is intermediate between
the source and the assembly code---each VOP corresponds fairly
directly to some primitive function or construct, but a given VOP
also has a fairly predictable instruction sequence. An operation
(such as +) may have multiple implementations with different
cost and applicability. The choice of a particular VOP such as
+/fixnum or +/single-float represents this choice of
implementation. Once you are familiar with it, the VM
representation is probably the most useful for determining what
implementation has been used.
- An assembly listing, annotated with the VOP responsible for
generating the instructions. This listing is useful for figuring
out what a VOP does and how it is implemented in a particular
context, but its large size makes it more difficult to read.
- A disassembly of the generated code, which has all
pseudo-operations expanded out, but is not annotated with VOPs.
Note that trace file generation takes much space and time, since the trace file
is tens of times larger than the source file. To avoid huge confusing trace
files and much wasted time, it is best to separate the critical program portion
into its own file and then generate the trace file from this small file.
Efficiency notes are messages that warn the user that the compiler has
chosen a relatively inefficient implementation for some operation.
Usually an efficiency note reflects the compiler's desire for more
type information. If the type of the values concerned is known to the
programmer, then additional declarations can be used to get a more
efficient implementation.
Efficiency notes are controlled by the
extensions:inhibit-warnings (see section 4.7.1)
optimization quality. When speed is greater than
extensions:inhibit-warnings, efficiency notes are enabled.
Note that this implicitly enables efficiency notes whenever
speed is increased from its default of 1.
Consider this program with an obscure missing declaration:
(defun eff-note (x y z)
(declare (fixnum x y z))
(the fixnum (+ x y z)))
If compiled with (speed 3) (safety 0), this note is given:
In: DEFUN EFF-NOTE
(+ X Y Z)
==>
(+ (+ X Y) Z)
Note: Forced to do inline (signed-byte 32) arithmetic (cost 3).
Unable to do inline fixnum arithmetic (cost 2) because:
The first argument is a (INTEGER -1073741824 1073741822),
not a FIXNUM.
This efficiency note tells us that the result of the intermediate
computation (+ x y) is not known to be a fixnum, so
the addition of the intermediate sum to z must be done less
efficiently. This can be fixed by changing the definition of
eff-note:
(defun eff-note (x y z)
(declare (fixnum x y z))
(the fixnum (+ (the fixnum (+ x y)) z)))
The main cause of inefficiency is the compiler's lack of adequate
information about the types of function argument and result values.
Many important operations (such as arithmetic) have an inefficient
general (generic) case, but have efficient implementations that can
usually be used if there is sufficient argument type information.
Type efficiency notes are given when a value's type is uncertain.
There is an important distinction between values that are not
known to be of a good type (uncertain) and values that are known
not to be of a good type. Efficiency notes are given mainly for the
first case (uncertain types.) If it is clear to the compiler that that
there is not an efficient implementation for a particular function
call, then an efficiency note will only be given if the
extensions:inhibit-warnings optimization quality is 0
(see section 4.7.1.)
In other words, the default efficiency notes only suggest that you add
declarations, not that you change the semantics of your program so
that an efficient implementation will apply. For example, compilation
of this form will not give an efficiency note:
(elt (the list l) i)
even though a vector access is more efficient than indexing a list.
5.13.2 |
Efficiency Notes and Type Checking |
|
It is important that the eff-note example above used
(safety 0). When type checking is enabled, you may get apparently
spurious efficiency notes. With (safety 1), the note has this extra
line on the end:
The result is a (INTEGER -1610612736 1610612733), not a FIXNUM.
This seems strange, since there is a the declaration on the result of that
second addition.
In fact, the inefficiency is real, and is a consequence of Python's
treating declarations as assertions to be verified. The compiler
can't assume that the result type declaration is true---it must
generate the result and then test whether it is of the appropriate
type.
In practice, this means that when you are tuning a program to run
without type checks, you should work from the efficiency notes
generated by unsafe compilation. If you want code to run efficiently
with type checking, then you should pay attention to all the
efficiency notes that you get during safe compilation. Since user
supplied output type assertions (e.g., from the) are
disregarded when selecting operation implementations for safe code,
you must somehow give the compiler information that allows it to prove
that the result truly must be of a good type. In our example, it
could be done by constraining the argument types more:
(defun eff-note (x y z)
(declare (type (unsigned-byte 18) x y z))
(+ x y z))
Of course, this declaration is acceptable only if the arguments to eff-note
always are (unsigned-byte 18) integers.
5.13.3 |
Representation Efficiency Notes |
|
When operating on values that have non-descriptor representations
(see section 5.11.2), there can be a substantial time and consing
penalty for converting to and from descriptor representations. For
this reason, the compiler gives an efficiency note whenever it is
forced to do a representation coercion more expensive than
*efficiency-note-cost-threshold*.
Inefficient representation coercions may be due to type uncertainty,
as in this example:
(defun set-flo (x)
(declare (single-float x))
(prog ((var 0.0))
(setq var (gorp))
(setq var x)
(return var)))
which produces this efficiency note:
In: DEFUN SET-FLO
(SETQ VAR X)
Note: Doing float to pointer coercion (cost 13) from X to VAR.
The variable var is not known to always hold values of type
single-float, so a descriptor representation must be used for its value.
In this sort of situation, adding a declaration will eliminate the inefficiency.
Often inefficient representation conversions are not due to type
uncertainty---instead, they result from evaluating a
non-descriptor expression in a context that requires a descriptor
result:
-
Assignment to or initialization of any data structure other than
a specialized array (see section 5.11.8), or
- Assignment to a special variable, or
- Passing as an argument or returning as a value in any function
call that is not a local call (see section 5.11.10.)
If such inefficient coercions appear in a ``hot spot'' in the program, data
structures redesign or program reorganization may be necessary to improve
efficiency. See sections 5.7, 5.11 and
5.14.
Because representation selection is done rather late in compilation,
the source context in these efficiency notes is somewhat vague, making
interpretation more difficult. This is a fairly straightforward
example:
(defun cf+ (x y)
(declare (single-float x y))
(cons (+ x y) t))
which gives this efficiency note:
In: DEFUN CF+
(CONS (+ X Y) T)
Note: Doing float to pointer coercion (cost 13), for:
The first argument of CONS.
The source context form is almost always the form that receives the value being
coerced (as it is in the preceding example), but can also be the source form
which generates the coerced value. Compiling this example:
(defun if-cf+ (x y)
(declare (single-float x y))
(cons (if (grue) (+ x y) (snoc)) t))
produces this note:
In: DEFUN IF-CF+
(+ X Y)
Note: Doing float to pointer coercion (cost 13).
In either case, the note's text explanation attempts to include
additional information about what locations are the source and
destination of the coercion. Here are some example notes:
(IF (GRUE) X (SNOC))
Note: Doing float to pointer coercion (cost 13) from X.
(SETQ VAR X)
Note: Doing float to pointer coercion (cost 13) from X to VAR.
Note that the return value of a function is also a place to which coercions may
have to be done:
(DEFUN F+ (X Y) (DECLARE (SINGLE-FLOAT X Y)) (+ X Y))
Note: Doing float to pointer coercion (cost 13) to "<return value>".
Sometimes the compiler is unable to determine a name for the source or
destination, in which case the source context is the only clue.
These variables control the verbosity of efficiency notes:
[Variable]
*efficiency-note-cost-threshold*
Before printing some efficiency notes, the compiler compares the
value of this variable to the difference in cost between the chosen
implementation and the best potential implementation. If the
difference is not greater than this limit, then no note is printed.
The units are implementation dependent; the initial value suppresses
notes about ``trivial'' inefficiencies. A value of 1 will
note any inefficiency.
[Variable]
*efficiency-note-limit*
When printing some efficiency notes, the compiler reports possible
efficient implementations. The initial value of 2 prevents
excessively long efficiency notes in the common case where there is
no type information, so all implementations are possible.
The first step in improving a program's performance is to profile the
activity of the program to find where it spends its time. The best
way to do this is to use the profiling utility found in the
profile package. This package provides a macro profile
that encapsulates functions with statistics gathering code.
[Variable]
profile:*timed-functions*
This variable holds a list of all functions that are currently being
profiled.
[Macro]
profile:profile {name |:callers t}*
This macro wraps profiling code around the named functions. As in
trace, the names are not evaluated. If a function is
already profiled, then the function is unprofiled and reprofiled
(useful to notice function redefinition.) A warning is printed for
each name that is not a defined function.
If :callers t is specified, then each function that calls
this function is recorded along with the number of calls made.
[Macro]
profile:unprofile {name}*
This macro removes profiling code from the named functions. If no
names are supplied, all currently profiled functions are
unprofiled.
[Macro]
profile:profile-all &key :package :callers-p
This macro in effect calls profile:profile for each
function in the specified package which defaults to
*package*. :callers-p has the same meaning as in
profile:profile.
[Macro]
profile:report-time {name}*
This macro prints a report for each named function of the
following information:
-
The total CPU time used in that function for all calls,
- the total number of bytes consed in that function for all
calls,
- the total number of calls,
- the average amount of CPU time per call.
Summary totals of the CPU time, consing and calls columns are
printed. An estimate of the profiling overhead is also printed (see
below). If no names are supplied, then the times for all
currently profiled functions are printed.
[Macro]
reset-time {name}*
This macro resets the profiling counters associated with the
named functions. If no names are supplied, then all
currently profiled functions are reset.
Start by profiling big pieces of a program, then carefully choose which
functions close to, but not in, the inner loop are to be profiled next.
Avoid profiling functions that are called by other profiled functions, since
this opens the possibility of profiling overhead being included in the reported
times.
If the per-call time reported is less than 1/10 second, then consider the clock
resolution and profiling overhead before you believe the time. It may be that
you will need to run your program many times in order to average out to a
higher resolution.
5.14.3 |
Nested or Recursive Calls |
|
The profiler attempts to compensate for nested or recursive calls. Time and
consing overhead will be charged to the dynamically innermost (most recent)
call to a profiled function. So profiling a subfunction of a profiled function
will cause the reported time for the outer function to decrease. However if an
inner function has a large number of calls, some of the profiling overhead may
``leak'' into the reported time for the outer function. In general, be wary of
profiling short functions that are called many times.
Unless you are very lucky, the length of your machine's clock ``tick'' is
probably much longer than the time it takes simple function to run. For
example, on the IBM RT, the clock resolution is 1/50 second. This means that
if a function is only called a few times, then only the first couple decimal
places are really meaningful.
Note however, that if a function is called many times, then the statistical
averaging across all calls should result in increased resolution. For example,
on the IBM RT, if a function is called a thousand times, then a resolution of
tens of microseconds can be expected.
The added profiling code takes time to run every time that the profiled
function is called, which can disrupt the attempt to collect timing
information. In order to avoid serious inflation of the times for functions
that take little time to run, an estimate of the overhead due to profiling is
subtracted from the times reported for each function.
Although this correction works fairly well, it is not totally accurate,
resulting in times that become increasingly meaningless for functions with
short runtimes. This is only a concern when the estimated profiling overhead
is many times larger than reported total CPU time.
The estimated profiling overhead is not represented in the reported total CPU
time. The sum of total CPU time and the estimated profiling overhead should be
close to the total CPU time for the entire profiling run (as determined by the
time macro.) Time unaccounted for is probably being used by functions that
you forgot to profile.
5.14.6 |
Additional Timing Utilities |
|
[Macro]
time form
This macro evaluates form, prints some timing and memory
allocation information to *trace-output*, and returns any
values that form returns. The timing information includes
real time, user run time, and system run time. This macro executes
a form and reports the time and consing overhead. If the
time form is not compiled (e.g. it was typed at top-level),
then compile will be called on the form to give more accurate
timing information. If you really want to time interpreted speed,
you can say:
(time (eval 'form))
Things that execute fairly quickly should be timed more than once,
since there may be more paging overhead in the first timing. To
increase the accuracy of very short times, you can time multiple
evaluations:
(time (dotimes (i 100) form))
[Function]
extensions:get-bytes-consed
This function returns the number of bytes allocated since the first
time you called it. The first time it is called it returns zero.
The above profiling routines use this to report consing information.
[Variable]
extensions:*gc-run-time*
This variable accumulates the run-time consumed by garbage
collection, in the units returned by
get-internal-run-time.
[Constant]
internal-time-units-per-second
The value of internal-time-units-per-second is 100.
There are two general kinds of timing information provided by the
time macro and other profiling utilities: real time and run
time. Real time is elapsed, wall clock time. It will be affected in
a fairly obvious way by any other activity on the machine. The more
other processes contending for CPU and memory, the more real time will
increase. This means that real time measurements are difficult to
replicate, though this is less true on a dedicated workstation. The
advantage of real time is that it is real. It tells you really how
long the program took to run under the benchmarking conditions. The
problem is that you don't know exactly what those conditions were.
Run time is the amount of time that the processor supposedly spent
running the program, as opposed to waiting for I/O or running other
processes. ``User run time'' and ``system run time'' are numbers
reported by the Unix kernel. They are supposed to be a measure of how
much time the processor spent running your ``user'' program (which
will include GC overhead, etc.), and the amount of time that the
kernel spent running ``on your behalf.''
Ideally, user time should be totally unaffected by benchmarking
conditions; in reality user time does depend on other system activity,
though in rather non-obvious ways.
System time will clearly depend on benchmarking conditions. In Lisp
benchmarking, paging activity increases system run time (but not by as much
as it increases real time, since the kernel spends some time waiting for
the disk, and this is not run time, kernel or otherwise.)
In my experience, the biggest trap in interpreting kernel/user run time is
to look only at user time. In reality, it seems that the sum of kernel
and user time is more reproducible. The problem is that as system activity
increases, there is a spurious decrease in user run time. In effect, as
paging, etc., increases, user time leaks into system time.
So, in practice, the only way to get truly reproducible results is to run
with the same competing activity on the system. Try to run on a machine
with nobody else logged in, and check with ``ps aux'' to see if there are any
system processes munching large amounts of CPU or memory. If the ratio
between real time and the sum of user and system time varies much between
runs, then you have a problem.
5.14.8 |
Benchmarking Techniques |
|
Given these imperfect timing tools, how do should you do benchmarking? The
answer depends on whether you are trying to measure improvements in the
performance of a single program on the same hardware, or if you are trying to
compare the performance of different programs and/or different hardware.
For the first use (measuring the effect of program modifications with
constant hardware), you should look at both system+user and real time to
understand what effect the change had on CPU use, and on I/O (including
paging.) If you are working on a CPU intensive program, the change in
system+user time will give you a moderately reproducible measure of
performance across a fairly wide range of system conditions. For a CPU
intensive program, you can think of system+user as ``how long it would have
taken to run if I had my own machine.'' So in the case of comparing CPU
intensive programs, system+user time is relatively real, and reasonable to
use.
For programs that spend a substantial amount of their time paging, you
really can't predict elapsed time under a given operating condition without
benchmarking in that condition. User or system+user time may be fairly
reproducible, but it is also relatively meaningless, since in a paging or
I/O intensive program, the program is spending its time waiting, not
running, and system time and user time are both measures of run time.
A change that reduces run time might increase real time by increasing
paging.
Another common use for benchmarking is comparing the performance of
the same program on different hardware. You want to know which
machine to run your program on. For comparing different machines
(operating systems, etc.), the only way to compare that makes sense is
to set up the machines in exactly the way that they will
normally be run, and then measure real time. If the
program will normally be run along with X, then run X. If the program
will normally be run on a dedicated workstation, then be sure nobody
else is on the benchmarking machine. If the program will normally be
run on a machine with three other Lisp jobs, then run three other Lisp
jobs. If the program will normally be run on a machine with 64MB of
memory, then run with 64MB. Here, ``normal'' means ``normal for that
machine''.
If you have a program you believe to be CPU intensive, then you might be
tempted to compare ``run'' times across systems, hoping to get a meaningful
result even if the benchmarking isn't done under the expected running
condition. Don't to this, for two reasons:
-
The operating systems might not compute run time in the same
way.
- Under the real running condition, the program might not be CPU
intensive after all.
In the end, only real time means anything---it is the amount of time you
have to wait for the result. The only valid uses for run time are:
-
To develop insight into the program. For example, if run time
is much less than elapsed time, then you are probably spending lots
of time paging.
- To evaluate the relative performance of CPU intensive programs
in the same environment.
- 1
- The source
transformation in this example doesn't represent the preservation of
evaluation order implicit in the compiler's internal representation.
Where necessary, the back end will reintroduce temporaries to
preserve the semantics.
- 2
- Note
that the code for x and y isn't actually replicated.
- 3
- As Steele
notes in CLTL II, this is a generic conception of generic, and is
not to be confused with the CLOS concept of a generic function.
- 4
- This, however, has not actually happened, but
it is a possibility.
- 5
- Kahan, W., ``Branch Cuts for Complex Elementary
Functions, or Much Ado About Nothing's Sign Bit''
in Iserles and Powell (eds.) The State of the Art
in Numerical Analysis, pp. 165-211, Clarendon
Press, 1987