Saturday, September 23, 2006

arnesi continuations

I've just moved back to the UK from Australia. With a few days of jet-lagged downtime I've managed to fit in some fiddling with CL. The CVS version of SBCL now appears to work with Slime under Win32 (which is very very cool), and I've been playing with with-call/cc from arnesi. It took a bit of fiddling to realise that you need to use defun/cc - documentation seems to be quite thin on the ground. Once I twigged, it was pretty easy to port Fig 22.4 of OnLisp to CL:

(defparameter *paths* nil)

(defun/cc choose (choices)
(if (null choices)
(let/cc cc
(push (lambda () (kall cc (choose (cdr choices)))) *paths*)
(kall cc (car choices)))))

(defun/cc fail ()
(if (null *paths*)
(kall arnesi::*toplevel-k* '@)
(funcall (pop *paths*))))

So that now Fig 22.3 can be written:

(defun/cc two-numbers ()
(list (choose '(0 1 2 3 4 5))
(choose '(0 1 2 3 4 5))))

(defun parlor-trick (sum)
(let ((nums (two-numbers)))
(if (= (apply #'+ nums) sum)
`(the sum of ,@nums)

Wednesday, June 21, 2006

How much memory gets allocated when you call a generic function?

I was wondering what actually happens when you call a generic function - specifically, how much memory would get allocated. I've become a bit addicted to clisp's ext:times macro because it provides quite a good insight into the performance characteristics of a function.

I knocked together a quick test and got some results...and then got distracted making a nice way to collect and display the results. It turned into quite a fun little one-evening project that exercised some string manipulation and use of format.

So here's the code to define my 'show-bytes-allocated' macro:

(asdf:oos 'asdf:load-op "split-sequence")
(import 'split-sequence:split-sequence)

(defun make-adjustable-string ()
(make-array '(0) :element-type 'base-char :fill-pointer 0 :adjustable t))

(defmacro times-to-string (&body body)
`(let ((times (make-adjustable-string))
(with-output-to-string (*trace-output* times)
(setf result (ext:times ,@body)))
(values result times)))

(defmacro bytes-allocated (&body body)
`(let ((result))
(destructuring-bind (head perm-count perm-bytes temp-count temp-bytes)
(find-if (lambda (e) (equal (first e) "Total"))
(mapcar (lambda (l) (split-sequence #\Space l
:remove-empty-subseqs t))
(split-sequence #\Newline
(multiple-value-bind (r s) (times-to-string ,@body)
(setf result r)
:remove-empty-subseqs t)))
(declare (ignore head perm-count temp-count))
(list (read-from-string perm-bytes) (read-from-string temp-bytes) ',@body result))))

(defmacro show-bytes-allocated (&body body)
(format t "~20A ~20A ~10@A ~10@A~%" "Form" "Result" "Permament" "Temporary")
(format t "~63,,,'-A~%" "")
,@(mapcar (lambda (form)
`(destructuring-bind (permament temporary f r) (bytes-allocated ,form)
(format t "~20S ~20S ~10D ~10D~%" f r permament temporary)))

This let me quite easily write a little test, creating a couple of classes and a generic function:

(defclass foo ()

(defclass bar ()

(defgeneric com (thing))

(defmethod com (thing)
(declare (ignore thing))

(defmethod com ((thing foo))
(declare (ignore thing))

(defmethod com ((thing bar))
(declare (ignore thing))

(defparameter athing nil)
(defparameter afoo (make-instance 'foo))
(defparameter abar (make-instance 'bar))

(com athing)
(com afoo)
(com abar)
(com athing)
(com afoo)
(com abar))

Here's the output:

Form Result Permament Temporary
(COM AFOO) FOO 52 1744
(COM ABAR) BAR 52 1772

So we can see that the first time a generic function is called on a particular thing it goes away and allocates a bunch of stuff, but then subsequent calls to it don't need any more allocations.

Disassembling (function com) after each call is quite instructive too - you can see how the function is modified each time. I expect that there's a limit to how many specialisations it'll keep around. It helps my mental model of generic functions to know that they behave in this way.

Another interesting thing I found whilst writing it is that nearly every time I'm tempted to use dolist, I always end up actually using mapcar.

Saturday, June 17, 2006

Silly idea?

I wonder if it's worth considering setting up something that'll generate C++ code from sexps? Similar to the various HTML or HLSL/CG generators. Might be interesting to think about...

Wednesday, June 14, 2006

Update Functions

Ah, it's been a while.

I managed to get even better performance by precreating all the bitmaps for the cells. Obvious really, but it's now running pretty well.

Since the whole point of this exercise is for me to experiment with lisp features I've been experimenting with storing an update and render closure in each cell. This has worked out really nicely, allowing me to have a more efficient board update when opening up empty cells and also the ability to do neat effects like control the speed that the board opens up.

So the function below creates an update function that'll expose surrounding cells on the next update:

(defun show-surrounding-cells ()
(make-updatefn (board ix iy)
(do-surrounding-cells (mine-x mine-y board ix iy)
(let ((cell (aref (board-cells board) mine-x mine-y)))
(when (cell-mine-count cell)
(setf (cell-updatefn cell) (update-expose)))))

It's also possible to create animation effects by using an update function and a render function sharing the same closure:

(defun hit-mine (cell speed)
(let ((count *cell-size*)
(delay speed))

((render (bitmap board ix iy left top right bottom cell mouse-inside)

(draw-cell bitmap board ix iy left top right bottom cell mouse-inside)

(let ((remain (- *cell-size* count)))
(alleg:blit *invisible-cell* bitmap
remain remain
(+ remain left) (+ remain top)
(- *cell-size* (* 2 remain)) (- *cell-size* (* 2 remain))))))

(setf (cell-renderfn cell) #'render)

(make-updatefn ()
((zerop delay) (decf count) (setf delay speed))
(t (decf delay)))
(if (zerop count)
(setf (cell-renderfn cell) nil)

So this one makes the invisible cell bitmap shrink to nothingness leaving the new one behind.

I can create higher-level update functions as well. One useful one is delay, that just waits a certain number of frames before switching the given function in.

(defun delay-update (count function)
(make-updatefn ()
(decf count)
(if (zerop count)

However, this leaves open the possibility of setting an update function over the top of another one that might be doing useful work. We can deal with this nicely with a combine update function:

(defun combine-updatefn (fn1 fn2)
(make-updatefn (board ix iy)
(setf fn1 (when fn1 (funcall fn1 board ix iy))
fn2 (when fn2 (funcall fn2 board ix iy)))
((and fn1 fn2) self)
(fn1 fn1)
(fn2 fn2)
(t nil))))

This runs both the update functions, eventually removing itself when one of the sub ones finishes.

As a debugging aid I can print out the current function on each cell, and it should be possible to set it up to inspect a particulary cell by clicking on it. Very cool potential there.

The great thing about this is that means I can store arbitrary data on a cell and do processing on it without having to make room for it in my main cell datastrucure. So by doing this I've decoupled the update logic and animation data from my simple board representation. Of course this sort of thing isn't limited to lisp, but it's an interesting way to think about it that falls into place quite naturally.

My latest distraction is trying to get SLIME and CLISP to work better with macro argument lists. I've been doing some hacking replacing lisp's standard defmacro with my own version that stores away some extra data, but I think the proper solution is going to be modifying CLISP itself.

Thursday, April 13, 2006

Profiling and Optimisation

I've managed to spend some time profiling. It turns out that it makes things much easier if everything is put in a package - then you can do slime-profile-package rather than fiddling with profiling each function individually.

The first results shows that we're spending most of our time talking through CFFI to get values of variables. This turned out to be mostly things like *font* and *mouse-x*. So I've added a system to allow easy updating of these variables through a couple of macros - define-updateable-var and update-var that uses the symbol plist to record a function to execute when updating the variable. Now I only calculate colors on initialisation and grab the updated version of things like *mouse-x* once per frame. This has resulted in much better performance - the fan on my laptop doesn't turn on while running it anymore and it seems to hover around 30% of CPU usage. I've also inlined draw-cell which made quite a big difference.

The new profile shows a much more evenly distributed set of function calls.

I'm going to be spending some time now playing around with cl-emb and cl-who to generate a photo-album style website.

Saturday, March 18, 2006

Nearly playable...

Managed to find some time for some more fiddling. I've made the board display a bit prettier and it detects mouse presses and updates it all. It's dog slow at the moment though - is actually unplayable unless I compile it. Guess it's time to learn about profiling and optimising in lisp.

A couple of useful macros came out of it:

  • with-board-geometry sets up an environment where a bunch of useful variables are defined - cell-width, total-width, total board area, etc. So the mouse click detection and board drawing code both use this.
  • do-all-cells iterates over all the cells in the board and evaluates the given form on them.
  • do-surrounding-cells iterates over all the cells surrounding a given cell
  • do-steps is a simple wrapper around do that increments a given variable by a certain amount for a given number of times. This is used when drawing the board.
So it is nice to have code that looks like this:

(do-all-cells (ix iy board)
(update-cell-visibility board ix iy))

(defun add-counts-for-mine (board mine-x mine-y)
"Increment the mine counts for all cells surrounding mine-x mine-y"
(let ((cells (board-cells board)))
(do-surrounding-cells (ix iy board mine-x mine-y)
(when (cell-mine-count (aref cells ix iy))
(incf (cell-mine-count (aref cells ix iy)))))))

Sunday, March 12, 2006

cl-alleg on Sourceforge

I've set up a sourceforge project for hosting the Allegro/CFFI stuff: