[N-World Contents] [Book Contents] [Prev] [Next] [Index]

N·World includes many tools for optimizing your Lisp code. In this chapter, you'll learn how to:

Optimizing Math with Anti-Generic Functions

Compared to a language like C, Lisp is a fairly high-level language. As a result, Lisp programmers do not have to be as explicit in Lisp about how certain operations are to be performed. Lisp itself steps in wherever it can to make decisions for you. For example, the following simple Lisp addition function with three integer arguments:

(+ 1 2 3)
returns the value

6
which is also of type integer.The addition function itself is generic, which means that its' arguments do not have to be of a specific type. However, Lisp must still make internal decisions about the types of the arguments so it can allocate storage space and determine the type of the result. In our example, this was fairly simple, since we provided the function with constants as arguments. Lisp knew ahead of time that these arguments were integers, and it was able to determine that the result of this operation with integers is another integer.

However, suppose you provide arguments of different types, e.g.

(+ 1 2 3.0)
The value 3.0 is of type float. Lisp recognizes this and returns

6.0
When Lisp evaluates the function, it determines that one of the arguments is of the type float. As a result the function returns a value of type float. The manner in which Lisp makes these decisions can generate processor overhead. To understand how, first consider how Lisp evaluates a simple form like the one above.

First, Lisp must break function down into it's basic components. The basic addition function in Lisp is designed to work with two arguments. If more than two arguments are passed to this function, as in our example, they must first be divided into a series of nested pairs. For our example addition function, (+ 1 2 3), this process yields:

(+ (+ 1 (+ 2 3)))
A more complex example yeilds a longer list, for example:

(+ 1 2 3 4 5)
becomes

(+ 1(+2 (+3 (+ 4 5)
Again, because we have provided Lisp with constant values, it knows that the value returned by this function must be an integer. However, suppose we had defined a function which accepted three arguments and then summed them?

(defun foo (a b c)


(+ a b c))
Lisp assumes that all of the arguments are numbers because addition is a math operation, but it knows nothing more specific about the values it is passed. Lisp can only conclude that the response must be a number between +infinity and -infinity, but cannot be more specific. As a result, it allocates a large amount of memory to handle this value, as well as the arguments passed to the function. In addition, this penalty is incurred twice, because the operation

(+ a b c)
expands after compiling to

(+ (+ a b) c))
Lisp uses the unbounded type number to hold the intermediate values of the sum of b and c, as well as the eventual result. You can see explicitly how Lisp makes these decisions by compiling our example with a declare statement:

(compile


		(defun foo (a b c)


		(declare (:explain :types))


				(+ a b c)))
Lisp returns the following descriptive data:

;Examining a call to +_2OP with arguments:


;  call to +_2OP type (NUMBER * *)


;  symeval C type T


; which returns a value of type (NUMBER * *)


;Examining a call to +_2OP with arguments:


1;  symeval A type T


1;  symeval B type T


2; which returns a value of type (NUMBER * *)


FOO


NIL


NIL
First, Lisp breaks our list of three arguments into two nested pairs

(+ a (+ b c))
and evaluates them separately with two calls to the function +_2OP. In the first addition, Lisp cannot predict what type A and B are going to be when passed to the function, so it evaluates them as type T, which means essentially any type. However, Lisp knows that the result of this operation must be a number, and expresses this conclusion in the statement on line 2. However, Lisp has no idea how large or small these numbers might end up being, so it assigns them an infinite range with the symbol (* *).

The result of the first addition is passed, along with argument c, to the +2_OP operation a second time. Lisp follows the same logic, assigning type T to c, and type Number to the result of the first addition operation. The result of this addition will also be a number.

Although Lisp relieves you of the responsibility of explicitly declaring the type of your arguments when you create an expression like (+ a b c), it must still evaluate the true types of your arguments in order to perform the addition at machine code level. It is this process of evaluating the types of the arguments in a function, which, though concealed from you, expands the size of the compiled code and consumes processor time. This expansion of the code can be graphically illustrated by deassembling a seemingly simple function like foo.

1. Use disassemble to view a compiled function in assembly language 

(disassemble `foo)
The result is well over 100 lines of machine code. Nearly all of this code is devoted to determining the types of the arguments supplied to foo, and routing these arguments to the correct algorithms for evaluation.

You can dramatically reduce the amount of machine code generated when a function is compiled by explicitly informing the compiler of the types you wish to pass to a function. For example, try compiling and disassembling the following version of foo

(compile


		(defun foo ()


		(declare (:explain :types))


				(+ 1 2 3)))
Disassembling this function yields only a few lines of machine code. Because there are no arguments to foo, and the operands to be added are all integers, Lisp is able to forego the complex process of deciding how to treat variables of unknown type. Instead, it passes the values 1, 2, and 3 directly to the appropriate function.

Unfortunately, you will rarely be building functions with constants. You can still obtain nearly the same performance, however, by declaring your functions argument types in the function itself. Doing so means that these functions will operate correctly if passed values of a specific type. Because this is the opposite of standard Lisp, these are called anti-generic function.

In an anti-generic function, you use macros which combine the math operation being performed with the type of the arguments involved. Generally, these types are f for floats and i for integers. In addition, these macros take care of arranging your arguments in the optimal pattern for Lisp to evaluate. For example, the expression

(f+ a b c)
expands first into

(f! (+ (f! (+ (f! a) (f! b))) (f! c)))
The original form expands fully into this form:

(the single-float


  (+ (the single-float


       (+ (the single-float a)


          (the single-float b)))


     (the single-float c)))
The f+ macro expands the addition operation into nested pairs, and also explicitly types the arguments passed to it. In addition, the first declaration instructs the compiler to return a value of type single-float.

NCL Anti-Generic Functions

Nichimen Common Lisp (NCL) includes a wide array of anti-generic functions intended for use with float, double float, and fixnum arguments. Each of these is exported by the NCL package. They can be used without package specifiers in nearly all situtations.

There are 7 basic groups of anti-generic functions:

Declarations

These forms are shorthand macros for the various type definition forms. For example, the I! macro is equivalent to "The fixnum ...".

Table 12.1 Anti-generic declarations.
Fixnum Float Double Float Comments
I!

 F!

 D!

 All accept single FLOAT args.

Relational Operators

Table 12.2 Anti-generic relational operators.
Fixnum Float Double Float Comments
I=

 F=

 D=

 Equivalent to =. Accept multiple args.

I/=

 F/=

 D/=

 Returns T if all args are different.

>I>

 >F>

 >D>

 Equivalent to >.

I<

 F<

 D<

 Equivalent to <.

=>I>=

 =>F>=

 =>D>=

 Equivalent to >=

I<=

 F<=

 D<-=

 Equivalent to <=

Predicates

Table 12.3 Anti-generic predicates.
Fixnum Float Double Float Comments
IPLUSP

 FPLUSP

 DPLUSP

 Equivalent to PLUSP.

IMINUSP

 FMINUSP

 DMINUSP

 Equivalent to MINUSP

Arithmetic Operators

Table 12.4 Anti-generic arithmetic operators.
Fixnum Float Double Float Comments
I+

 F+

 D+

 Equivalent to +

I-

 F-

 D-

 Equivalent to -

I*

 F*

 D*

 Equivalent to *

I/

 F/

 D/

 Equivalent to /.

Trigonometric Functions

Table 12.5 Anti-generic trigonometric operators.
Float Double Float Comments
FSIN

 DSIN

 Equivalent to SIN

FCOS

 DCOS

 Equivalent to COS

FTAN

 DTAN

 Equivalent to TAN

FASIN

 DASIN

 Equivalent to ASIN

FACOS

 DACOS

 Equivalent to ACOS

FATAN

 DATAN

 Equivalent to TAN

FSIND

 DSIND

 Sine of number in degrees

FCOSD

 DCOSD

 Cosine of number in degrees.

FTAND

 DTAND

 Tangent of number in degrees.

FDEGREES

 DDEGREES

 Radians to degrees

FRADIANS

 DRADIANS

 Degrees to radians

Math Utilities

Table 12.6 Anti-generic math utilities..
Fixnum Float Double Float Comments

FEXPT

 DEXPT

 Equivalent to EXPT

 FFIX

 DFIX

 Truncates to next least fixnum: (ncl:FFIX 1.9)=>1

 FFIXR

 DFIXR

 Rounds to nearest fixnum (ncl:FFIXR 1.9) =>2

 FSQRT

 DSQRT

 Equivalent to SQRT

IABS

 FABS

 DABS

 Eqvivalent to ABS.

IMIN

 FMIN

 DMIN

 Equivalent to MIN

IMAX

 FMAX

 DMAX

 Equivalent to MAX

IINCF

Increments arg by 1.

IDECF

Decrements arg by 1

IAVG

 FAVG

Returns rounded average for fixnums, average for floats.

 FSQR

Squares argument.

Multiple Values Bind Utilities

Use these functions to parse ftriplets and other structures which contain several values:

The following syntax is for multiple-ivalue-bind, but all three share the same general syntax:

(multiple-ivalue-bind vars form &BODY body)

Values bound with these macros have scope only within the calling form. Here's an example of a multiple binding:

(multiple-ivalue-bind (a b c

Optimization with Floating Point Vectors

A vector is a single dimensional array. Vectors and lists are very similar. However, the processor time required to access any given component of a list increases with the length of the list, whereas the time required to access a vector component is constant. However, it takes a constant amount of time to add items to the front of a list, while the time required to add elements to an array increases proportionately with the length of the array.

The NGCL contains built in facilities for creating and manipulating several different types of floating-point vectors. Vector types include:

Ftriplets

An ftriplet is a vector with with three floating point elements. Although you may use ftriplets for any purpose, they are typically used to store 3D cartesian coordinates. Regardless of the type of any values you pass to functions which create ftriplets, they are converted into floating-point values.

Creating Ftriplets

Create ftriplets with 3D:MAKE-FTRIPLET!:

(3D:MAKE-FTRIPLET! &OPTIONAL x y z)
where x, y, and z must be of the real type.

For example, to make an ftriplet with 1.0, 2.0, and 3.0:

(3d:make-ftriplet! 1.0 2.0 3.0)
returns an ftriplet:

#(1.0 2.0 3.0)
The three numeric arguments are optional. Failure to supply an argument results in that element of the vector defaulting to 0.0:

(3d:make-ftriplet! 1.0 2.0)
returns an ftriplet:

#(1.0 2.0 0.0)
Failure to supply any arguments to this macro results in an array with 0.0 in each element:

(3d:make-ftriplet!)
returns an ftriplet:

#(0.0 0.0 0.0)

Creating Origin Ftriplets

 You can quickly and easily create an ftriplet with x, y, and z values of 0 with 3D:ORIGIN-FTRIPLET:

(3D:ORIGIN-FTRIPLET)
returns an ftriplet:

#(0.0 0.0 0.0)

Creating Ftriplets Interactively

 You can also use a pop-up menu to create ftriplets. 3D:MENU-GET-FTRIPLET generates a pop-up menu like the one in Figure 12.1

Figure 12.1 The menu-get-ftriplet pop-up menu (default)

3D:MENU-GET-FTRIPLET has the following form:

(3d:menu-get-ftriplet initial-value &OPTIONAL


		label-string value-string do-it-method 


		precision relative?)


)

Reading Ftriplets

Because ftriplets are arrays, all of the standard Lisp functions for accessing arrays (such as aref) will work with ftriplets. However, the NGCL provides some handy tools for returning ftriplets and for returning individual elements of ftriplets.

Returning Parts of Ftriplets

You can return the x, y, or z elements of an ftriplet singly with one of three similar macros:

For example:

(3D:FTRIPLET-X (3d:make-ftriplet! 1.0 2.0 3.0))
returns 1.0.

Binding Multiple Values

You can bind the components of ftriplets to variables using the macro 3D:FTRIPLET-VALUES-BIND.

(ftriplet-values-bind (x y z) (make-ftriplet! 1.0 2.0 3.0) 


                (format t "X=~d~%" x)


                (format t "Y=~d~%" y)


                (format t "Z=~d~%" z)


                )
which returns

X=1.0


Y=2.0


Z=3.0


NIL
Note: Because ftriplet-values-bind is a macro, the values extracted from the ftriplet (x, y, and z in this example) are only defined within the scope of the macro. You must bind these values to variables with wider scope to use them outside of the macro!

Modifying Ftriplets

Several functions allow for the modification of ftriplets after they are initialized. You can scale, displace, and replace values in ftriplets. These functions are particularly useful when you are manipulating coordinate values during object translations and transformations.

Replacing Ftriplet Elements

Let's assume we've defined an ftriplet with x, y, and z values of 1.0, 2.0, and 3.0, and bound it to ftvar. 

(setf ftvar (3d:make-ftriplet! 1.0 2.0 3.0))


#(1.0 2.0 3.0)
You can change any element of the array by adding a setf form to one of the macros which returns the individual elements of the ftriplet. For example:

(setf (ftriplet-z ftvar) 6.6)
changes the value of the ftriplet to

#(1.0 2.0 6.6)
You can also use 3D:FILL-FTRIPLET function to manipulate individual elements of ftriplets. For example, the following form changes the y value of ftvar (as first defined above) to 6.6:

(3D:FILL-FTRIPLET ftvar nil 6.6 nil)
The ftvar variable now evaluates to

#(1.0 6.6 3.0)

Scaling Ftriplet Values

 3D:SCALE-FTRIPLET applies a scaling factor to each element of an ftriplet, and returns the result in a new ftriplet. You can apply a single scaling factor to one or all elements of the ftriplet. You can also apply different scaling factors to each element of the array. 3D:SCALE-FTRIPLET has the following basic form:

(3d:scale-ftriplet triplet-var 


			(x-factor &OPTIONAL y-factor z-factor)


			(&OPTIONAL into-triplet-var)


)
For example, given ftvar as described above, the following form doubles all the elements of the ftriplet:

(3d:scale-ftriplet ftvar (2))


#(2.0 4.0 6.0)
If you provide two scale-factors to the scale-ftriplet macro, the first factor will be applied to the x-element of the ftriplet, and the second factor will be applied to the y and z elements of the ftriplet. For example, given ftvar as defined above:

(3d:scale-ftriplet ftvar (2 4))
returns

#(2.0 8.0 12.0)
Finally, providing three scale factors results in each element of the ftriplet being scaled by the corresponding factor. For example, given ftvar as defined above:

(3d:scale-ftriplet ftvar (2 3 4))
returns

#(2.0 6.0 12.0)
This example changes the values in ftvar. The following example does not alter the values of ftvar, but stores the result of the scale in another ftriplet, nuftvar:

(3d:scale-ftriplet ftvar (2) nuftvar)


#(2.0 4.0 6.0)
Note that into-triplet-var must be bound to a defined ftriplet, or the macro returns an error. Of course, you could create into-triplet-var within the scale-ftriplet form, but this is cumbersome.

Moving Ftriplet Values

You can apply displacement to ftriplet values in much the same way that you scale them. You can use 3D:MOVE-FTRIPLET to apply a displacement to the elements of an ftriplet:

(3D:MOVE-FTRIPLET ftriplet-var (x-displacement &OPTIONAL


		y-displacement z-displacement) &OPTIONAL into-triplet-var)
For example, given ftvar as first defined above, the following form adds 10.0 to all elements of the ftriplet:

(3d:move-ftriplet ftvar (10.0 10.0 10.0))
Lisp returns the new value of ftvar:

#(11.0 12.0 13.0)
Unlike scale-ftriplet, you must provide x, y, and z displacements to move-ftriplet, or the macro returns an error.


[N-World Contents] [Book Contents] [Prev] [Next] [Index]

Another fine product from Nichimen documentation!

Copyright © 1996, Nichimen Graphics Corporation. All rights reserved.