What does it mean to "open code" something in Common Lisp?

Question

In the SBCL user manual there are several references to the term "open code". Common Lisp hackers also use this term when referring to optimizing code.

Could you please explain what it means to "open code" something and give an example of how it works?

Jumbo

Section 4.5 explains it pretty explicitly: it's inlining. There's even an example. Is there part of it that is unclear? – Lexicologist

I overlooked that, sorry. I also read literature where the term "open code" seemed to be used for something else, hence the need for clarification. It looks like this term is mostly used in the SBCL community. – Jumbo

Answer 1

What It Is

Open-coding, AKA inlining, means replacing function calls with inline assembly. The idea is that funcall and apply are expensive (they require saving and restoring the stack &c) and replacing them with the few operations which constitute the function can be beneficial.

E.g., the function 1+ is a single instruction when the argument is a fixnum (which it usually is in practice), so turning the funcall into the two parallel branches (fixnum and otherwise) would be a win.

How to Control it

Declarations

They user can control this optimization explicitly by the inline declaration (which implementations are free to ignore).

The user can also influence this optimization by the optimize declaration.

Both will affect inlining the code of a function defined just as a function (see below).

Macros

The "old" way is to implement the function as a macro. E.g., instead of

(defun last1f (list)
  (car (last list)))

write

(defmacro last1m (list)
  `(car (last ,list)))

and last1m will be always open-coded. The problem with this approach is that you cannot use last1m as a function - you cannot pass it to, say, mapcar.

Thus Common Lisp has an alternative way - compiler macros, which tell the compiler how to transform the form before compiling it:

(define-compiler-macro last1f (list)
   ;; use in conjunction with (defun last1f ...)
   `(car (last ,list)))

See also the excellent examples in the aforelinked CLHS page.

Its Effects on Optimization

A comment asked about the effects of inlining, i.e., what optimizations result from it. E.g., constant propagation in addition to eliminating a function call.

The answer to this question is left to implementations. IOW, the CL standard does not specify what optimizations must be done.

However, Minimal Compilation implies that if an implementation does something (e.g. constant folding), it will be done for compiler macros too.

For more details, you should compare the results of disassemble with and without the declarations and whatnot and see the effects.

For explanations, you should ask the vendor (e.g., by using the appropriate tag here - e.g., sbcl, clisp, &c).

Austriahungary

Thank you @sds, does open coding has a relationship with "compiler macros" as well or is it irrelevant? – Jumbo

You are welcome; please see edit about the macros and compiler macros – Austriahungary

are function calls so expensive in CL? in C++, inline functions allow the compiler to optimize across function boundaries, and this optimization opportunity is the true speedup of inlining there. is that different in CL? – Salesclerk

@SusanneOberhauser: it really depends on the specific implementation, but, generally speaking, a function call does have have cost in any language (stack monipulation) – Austriahungary

yes I understand that there is a small overhead for function calls in any language, including C. now the very nice response elaborates on that extensively. however. the significant benefit of inlining lies in the compiler being able to do (for example) const propagation of some computation out of the inlined function body to before the loop which invokes the function. and the accepted response doesn't even mention that core benefit of inline optimization. – Salesclerk

@SusanneOberhauser: I added section _ Effects on Optimization_ - does this address your concern? – Austriahungary