Abstract:

This technical session by the Atlanta Functional Programming Study Group focuses on Chapter 10 of Peter Norvig’s Paradigms of Artificial Intelligence Programming (PAIP), specifically addressing low-level efficiency in Common Lisp. The presentation explores how to transition from high-level algorithmic optimizations to hardware-level performance tuning. Key topics include the use of type declarations to enable the compiler to bypass generic function overhead, the trade-offs between "boxed" and "unboxed" data representations, and the impact of optimization qualities such as speed versus safety. Through live demonstrations and disassembly of SBCL (Steel Bank Common Lisp) machine code, the session illustrates how providing the compiler with specific type information—such as distinguishing between fixnums and generic integers or utilizing simple-arrays—can result in code that is competitive with statically compiled languages like C.

Common Lisp Efficiency: Type Declarations and Compiler Optimization

• 0:12 Performance Context: Common Lisp was standardized with the goal of being competitive with C, Fortran, and Pascal. While high-level best practices (memoization, indexing) provide significant gains, low-level efficiency requires manual type hints to reach C-tier performance.
• 8:41 The Sum-of-Squares Example: A generic implementation of a "sum of squares" function serves as the baseline. In its unoptimized state, the function uses generic sequence access and arithmetic, which incurs significant runtime overhead for type checking.
• 18:11 Type Constructors: The simple-array type is highlighted as more efficient than the general array type. A simple-array is one-dimensional and lacks complex features like fill-pointers or adjustability, allowing the compiler to generate more direct memory access patterns.
• 20:12 Optimization Qualities: The (declare (optimize ...)) form is used to prioritize compiler behavior. Values range from 0 (least important) to 3 (most important). Setting speed to 3 and safety to 0 tells the compiler to omit runtime type checks in favor of maximum execution velocity.
• 28:00 Function Inlining: The host demonstrates the inline declaration, which replaces a function call with the function's actual body code to save the cost of a jump and stack frame creation. A troubleshooting segment reveals that SBCL requires specific declaim global headers and certain debug levels to retain source code for inlining.
• 54:02 Disassembly of Generic vs. Optimized Code: By using the disassemble command, the host compares the machine code of a generic addition function against a type-declared fixnum addition.
  • Generic: Produces a heavy stack frame and calls a complex internal library function to handle potential type promotion (e.g., converting an integer to a big-num).
  • Optimized: Compiles down to a single x86-64 ADD instruction, operating directly on CPU registers.
• 1:02:40 Boxed vs. Unboxed Representations: The discussion covers how Common Lisp typically "boxes" data (wrapping raw bits with type metadata). Proper type declarations allow the compiler to "unbox" values, treating them as raw bits for arithmetic, which is a primary driver of performance in numerical computing.
• 1:09:50 Best Practices for Efficient Types:
  • Fixnums: Preferred for integers within the machine's word size.
  • Integer vs. Fixnum: Declaring a variable as integer is often insufficient for optimization because it includes "big-nums" (arbitrary-precision integers), forcing the compiler to use slower, generic math.
  • Floats: Use single-float or double-float specifically rather than the generic float to ensure the compiler uses the correct floating-point registers.
• 1:14:03 Non-Adjustable Arrays: Simple vectors and arrays are emphasized because they do not share structure or reallocate. Using svref (simple vector reference) is noted as significantly faster than the generic elt or aref functions for accessing sequence elements.