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))
         result)
     (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)
                                            s)
                                          :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)
  `(progn
     (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)))
               body)))

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

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

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


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


(show-bytes-allocated
  (com athing)
  (com afoo)
  (com abar)
  (com athing)
  (com afoo)
  (com abar))

Here's the output:

Form                 Result                Permament  Temporary
---------------------------------------------------------------
(COM ATHING)         SOMETHING                   192      15716
(COM AFOO)           FOO                          52       1744
(COM ABAR)           BAR                          52       1772
(COM ATHING)         SOMETHING                     0          0
(COM AFOO)           FOO                           0          0
(COM ABAR)           BAR                           0          0

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.

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

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

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)) 
   
 (labels 
  ((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 () 
  (cond 
    ((zerop delay) (decf count) (setf delay speed)) 
    (t (decf delay))) 
  (if (zerop count) 
   (progn 
     (setf (cell-renderfn cell) nil) 
     nil) 
   self))))) 

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

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))) 
 (cond 
   ((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.