The universe just told me again that I can make dumb mistakes with the best of them (note to universe: “you don’t have to tell me this, I already know!”). For the sake of this post, imagine that you need to optimize some code similar to
(defun test-0 (y) (let ((other 2)) (doit (lambda (x) (+ other x)) y)))
doit is something like
(defun doit (fn arg) (funcall fn arg))
I.e., I need to call some function using a closure that makes
reference to an outer lexical variable (
other in this
specific case). A problem with the code above is that the
closure is going to get re-allocated with every call: if I
(doit #'test-0 2) a 100,000 times, I’ll need make
space for the closure every time and I’ll cons more than
necessary and take extra time at that.
I decided that I wanted to pull the
lambda form out so that
I could tell the compiler more about it. Thus I had:
(defun test-1-a (y) (let ((other 2)) (let ((fun (lambda (x) (+ other x)))) (doit fun y))))
(You gentle readers probably already see the morass towards which I head… keep quiet.)
The intent of separating out the
lambda this way is that I
can tell Lisp that it needed allocate the closure on the
heap; i.e., that it can go away once I leave the body of
test-1-a; i.e., that it has dynamic-extent. This
would look like:
;;; WRONG (defun test-1-b (y) (let ((other 2)) (let ((fun (lambda (x) (+ other x)))) ;;;; WRONG - fun is a variable, not a function! (declare (dynamic-extent (function fun))) (doit fun y))))
If your Lisp doesn’t notice your mistake and tell you about it, then you might be like me and wonder why this optimization doesn’t help. Here is table showing the functions and the amount of time and space is takes to call them 100,000 times on misterx, my oldish OS X laptop.
milliseconds conses test-0 46 2,400,704 test-1-a 41 4,800,096 test-1-b 38 4,800,096
As you can see, the declaration doesn’t do squat (I’m not sure yet why the space needs actually double for the test-1 variants but that’s not part of the sad story I’m telling…).
A co-worker more clever than I pointed out that
fun isn’t a
function, it’s a variable and that I’d hopped to the wrong
level of abstraction. The variation I really wanted was
(defun test-2-a (y) (let ((other 2)) (flet ((fn (x) (+ other x))) (doit #'fn y)))) (defun test-2-b (y) (let ((other 2)) (flet ((fn (x) (+ other x))) (declare (dynamic-extent (function fn))) (doit #'fn y))))
I find these variants more transparent and only wish that I
hadn’t fallen into my initial
lambda trap in the beginning.
As is often the case, once I’d headed down door #1, it became
hard to see my mistake until someone else’s eyes pointed out
the obvious. Does it matter? Oh yes! Here’s the completion of
the table above:
milliseconds conses test-2-a 8 2,400,096 test-2-b 4 96
Not only do we get a speed boost, we also get a big space win
A positive outcome of this muck-about is that I found and fixed a bug in bind‘s handling of some declarations. It’ll get pushed out eventually.
I also noticed that SBCL (version 1.0.20) catches the errant declaration and prints a warning. As of version 8.1, Allegro Common Lisp does not (if you want to send reports from others Lisps, I’ll update this post).
Happy New Year; let’s make it great one!