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

1 Comments:

Anonymous Anonymous said...

you might be interested in this paper

7:03 pm  

Post a Comment

Links to this post:

Create a Link

<< Home