unCLog

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)))

where 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 call (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 from the dynamic-extent declaration.

Two addenda:

1. 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.

2. 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!

lisp