Hi, I have several methods that do expensive searches
and I want to cache the values to improve the performance.
Rather than redundantly building in caching mechanisms
into each such method, instead i've set up a macro called
def-cached-method. This looks much like defmethod except
that internally it defines a method and an around method.
The around method handles caching the return value in a
lexically scoped hash table.
I have to give the macro an additional argument/parameter
named get-key which is an expression of the variables in
the lambda list of the method. the get-key expression is
responsible for generating the hash-key.
The problem I am having is that the size of the
cache is not changing like i would expect. I print the
size of the hash table before and after assigning
a new value into it, and i see that the size is the same.
Is there some obvious reason this is happening?
Is my lexically scoped cache variable actually doing what
I expect. I expect that each method of a different name
that I'm created by using def-cached-method uses a
different hash table.
Why could it be that at the BEFORE and AFTER lines below,
the same hash table size is printed?
(defmacro def-cached-method (method-name lambda-list get-key &rest body)
`(progn
(let ((cache (make-hash-table :test #'equal)))
(defmethod ,method-name :around ,lambda-list
(let* ((key ,get-key)
(value (gethash key cache)))
(cond
(value
(car value))
(t
;; BEFORE
(format t "before cache ~A ~D~%" ',method-name (hash-table-size
cache))
(setf value (call-next-method)
(gethash key cache) (list value))
;; AFTER
(format t "after cache ~A ~D~%" ',method-name (hash-table-size cache))
value)))))
(defmethod ,method-name ,lambda-list
,@body)))
;;------------------------------
;; example of usage
(def-cached-method any-valid-comb ((self piece))
(cons self (get-state-key (blocker (team self))))
(loop for key being the hash-keys of (eff-comb-table self)
do
(dolist (comb (gethash key (eff-comb-table self)))
(when (is-valid-comb (team self) self comb :verbose nil)
(return-from any-valid-comb comb)))))
From: Rahul Jain
Subject: Re: macros, lexical scope, and around methods
Date:
Message-ID: <87oei1pbse.fsf@nyct.net>
Jim Newton <·····@rdrop.com> writes:
> Hi, I have several methods that do expensive searches
> and I want to cache the values to improve the performance.
> Rather than redundantly building in caching mechanisms
> into each such method, instead i've set up a macro called
> def-cached-method. This looks much like defmethod except
> that internally it defines a method and an around method.
> The around method handles caching the return value in a
> lexically scoped hash table.
There is already a memoization library. In debian it is available as
cl-memoization. It is from ftp.cs.umbc.edu/pub/Memoization.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Jim Newton <·····@rdrop.com> writes:
> The problem I am having is that the size of the cache is not
> changing like i would expect. I print the size of the hash table
> before and after assigning a new value into it, and i see that the
> size is the same.
You probably want HASH-TABLE-COUNT.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Jim Newton wrote:
> Hi, I have several methods that do expensive searches
> and I want to cache the values to improve the performance.
> Rather than redundantly building in caching mechanisms
> into each such method, instead i've set up a macro called
> def-cached-method. This looks much like defmethod except
> that internally it defines a method and an around method.
> The around method handles caching the return value in a
> lexically scoped hash table.
>
> I have to give the macro an additional argument/parameter
> named get-key which is an expression of the variables in
> the lambda list of the method. the get-key expression is
> responsible for generating the hash-key.
>
> The problem I am having is that the size of the
> cache is not changing like i would expect. I print the
> size of the hash table before and after assigning
> a new value into it, and i see that the size is the same.
Peter already pointed you to the fact that there is a difference between
HASH-TABLE-SIZE and HASH-TABLE-COUNT. The former tells you something
about the current capacity (so to speak) whereas the latter gives you
the number of actual entries.
What I find odd in your code is that you are defining a cache on a
per-method basis. Shouldn't this be per function or per generic function?
It would be interesting to write a generic function class that
automatically caches results without using up around methods. The basic
scheme would be this:
(defclass cached-generic-function (standard-generic-function)
((cache (make-hash-table :test #'equal))))
(defmethod compute-discriminating-function :before
((gf cached-generic-function))
(clrhash (slot-value gf 'cache)))
(defmethod compute-effective-method
((gf cached-generic-function) combination methods)
`(multiple-value-bind
(result foundp)
(gethash args (slot-value ,gf 'cache))
(if foundp result
(setf (gethash args (slot-value ,gf 'cache))
,(call-next-method)))))
...except that you don't have access to the args list in
compute-effective-method, but there are ways to make this work.
Pascal
--
Pascal Costanza University of Bonn
·········@p-cos.net Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Hi Pascal, this is a clever idea you have but i'm not
sure it meets the specification.... If i have two methods
for the same generic function but specializing two different
lambda lists, then i want two different caches.
yes you are right my method does take up around methods,
which makes me ask why are we only allowed a single
around method. i wish around methods were stackable
but they are not.
Your solution does address the problem of clearing
the hash when you redefine the method... a problem
that i was handling by a global list of hashes which
i had to purge manually.
Pascal Costanza wrote:
>
> What I find odd in your code is that you are defining a cache on a
> per-method basis. Shouldn't this be per function or per generic function?
>
> It would be interesting to write a generic function class that
> automatically caches results without using up around methods. The basic
> scheme would be this:
>
> (defclass cached-generic-function (standard-generic-function)
> ((cache (make-hash-table :test #'equal))))
>
> (defmethod compute-discriminating-function :before
> ((gf cached-generic-function))
> (clrhash (slot-value gf 'cache)))
>
> (defmethod compute-effective-method
> ((gf cached-generic-function) combination methods)
> `(multiple-value-bind
> (result foundp)
> (gethash args (slot-value ,gf 'cache))
> (if foundp result
> (setf (gethash args (slot-value ,gf 'cache))
> ,(call-next-method)))))
>
> ...except that you don't have access to the args list in
> compute-effective-method, but there are ways to make this work.
>
>
>
> Pascal
>
From: Edi Weitz
Subject: Re: macros, lexical scope, and around methods
Date:
Message-ID: <ur7muvoqk.fsf@agharta.de>
On Mon, 15 Nov 2004 19:38:46 +0100, Jim Newton <·····@rdrop.com> wrote:
> i wish around methods were stackable but they are not.
I read this and though "Hey, this is CLOS - there /must/ be a way to
do that..."
So I studied the CLHS entry for DEFINE-METHOD-COMBINATION and modified
one of the examples to look like this:
(define-method-combination foo ()
((primary () :required t)
(around foo-around-qualifier-p))
(let* ((form (if (rest primary)
`(call-method ,(first primary)
,(rest primary))
`(call-method ,(first primary))))
(around (stable-sort around #'<
:key #'(lambda (method)
(second (method-qualifiers method))))))
(if around
`(call-method ,(first around)
(,@(rest around)
(make-method ,form)))
form)))
(defun foo-around-qualifier-p (method-qualifiers)
(and (= (length method-qualifiers) 2)
(eq (first method-qualifiers) :around)
(typep (second method-qualifiers) '(integer 0 *))))
(defgeneric quux (x)
(:method-combination foo))
(defmethod quux ((x integer))
(format t "Called with integer ~A~%" x))
(defmethod quux :around 3 ((x integer))
(format t "Around 3 method before~%")
(call-next-method)
(format t "Around 3 method after~%"))
(defmethod quux :around 1 ((x integer))
(format t "Around 1 method before~%")
(call-next-method)
(format t "Around 1 method after~%"))
In LispWorks I get what I expected:
CL-USER> (load "foo.lisp")
; Loading text file c:\home\foo.lisp
#P"c:/home/foo.lisp"
CL-USER> (quux 42)
Around 1 method before
Around 3 method before
Called with integer 42
Around 3 method after
Around 1 method after
NIL
However, in CMUCL 19a, SBCL 0.8.16, and AllegroCL 7.0 I get error
messages. In CMUCL and SBCL ("More than one method of type AROUND with
the same specializers.") I'm pretty sure this is a bug because they
have the same problem with the penultimate example in the CLHS. With
AllegroCL ("attempt to take the length of a non-sequence: 3") I also
think this is an error but maybe there's a bug in my code
above. Comments? I'll check with the vendors.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
> However, in CMUCL 19a, SBCL 0.8.16, and AllegroCL 7.0 I get error
> messages. In CMUCL and SBCL ("More than one method of type AROUND with
> the same specializers.") I'm pretty sure this is a bug because they
> have the same problem with the penultimate example in the CLHS. With
> AllegroCL ("attempt to take the length of a non-sequence: 3") I also
> think this is an error but maybe there's a bug in my code
> above. Comments? I'll check with the vendors.
Allogro doesn't accept more than one qualifier and tries to interpret
the second qualifier as a lambda list. I have already reported this as a
bug to Franz. I don't know the source of the bug in CMUCL and SBCL,
but this is against the MOP specification.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
From: Edi Weitz
Subject: Re: macros, lexical scope, and around methods
Date:
Message-ID: <uis86xn65.fsf@agharta.de>
On Mon, 15 Nov 2004 23:56:29 +0100, Pascal Costanza <········@web.de> wrote:
> Allogro doesn't accept more than one qualifier and tries to
> interpret the second qualifier as a lambda list. I have already
> reported this as a bug to Franz.
Yeah, me too... :)
> I don't know the source of the bug in CMUCL and SBCL, but this is
> against the MOP specification.
Well, at least Christophe Rhodes argues that LispWorks' behaviour
(which is what I would like to have) is against the CLHS
specification:
<http://thread.gmane.org/gmane.lisp.cmucl.devel/7067>
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
>>I don't know the source of the bug in CMUCL and SBCL, but this is
>>against the MOP specification.
>
> Well, at least Christophe Rhodes argues that LispWorks' behaviour
> (which is what I would like to have) is against the CLHS
> specification:
>
> <http://thread.gmane.org/gmane.lisp.cmucl.devel/7067>
OK, he's right (and that's a pity).
Pascal
--
Pascal Costanza University of Bonn
·········@p-cos.net Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Jim Newton wrote:
> Hi Pascal, this is a clever idea you have but i'm not
> sure it meets the specification.... If i have two methods
> for the same generic function but specializing two different
> lambda lists, then i want two different caches.
Hm, in this case an option would possibly be to define your own method
metaobject class, roughly like this:
(defclass cached-method (standard-method)
((cache :initform (make-hash-table))))
(defmethod make-method-lambda
((gf cached-generic-function)
(method cached-method)
lambda-expression environment)
(declare (ignore environment))
(multiple-value-bind
(method-lambda method-initargs)
(call-next-method)
(values `(multiple-value-bind
(result foundp)
(gethash args (slot-value method 'cache))
(if foundp
result
,method-lambda))
method-initargs)))
(defmethod reinitialize-instance :after
((gf cached-generic-function) &rest args)
(declare (ignore args))
(mapc #'clrhash (generic-function-methods gf)))
The problem here is that most MOPs don't implement make-method-lambda
correctly, and some not at all.
> yes you are right my method does take up around methods,
> which makes me ask why are we only allowed a single
> around method. i wish around methods were stackable
> but they are not.
You can do anything you want in your own method combination and/or
generic function class. For example, you could reserve a specific method
qualifier for your own uses (:system-around, or some such), and then
combine it with the rest accordingly.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
It is looking better, but still there is the little
problem of determining the hash key. In my original
around method implementation I passed an expresion
which got inserted into the GETHASH call. This was
possible because it used a defmacro. What I need
here is not to index the hash with the method
parameters, but rather index the hash with some
function of the parameters. I know the function
at method definition time. And when I call the
method i want the key generated by calling the
key-gen-fun on the arguments i pass to the method.
e.g., (my-method 1 2 3)
in this case i want the key-gen-fun applied to
the list (1 2 3)
so is there a way to specify the :KEY-GEN-FUN
when i define the method? And what does the
make-method-lambda need to specify as the second
argument to FUNCALL below?
I also thought about simply calling a particular
named method rather than funcall, and allow the
user to override that method per something but
i'm not sure per what the methods lambda list
needs to be.
(defclass cached-method (standard-method)
((cache :initform (make-hash-table))
(key-gen-fun :initarg key-gen-fun)))
;;;;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(defmethod make-method-lambda
((gf cached-generic-function)
(method cached-method)
lambda-expression environment)
(declare (ignore environment))
(multiple-value-bind
(method-lambda method-initargs)
(call-next-method)
(values `(multiple-value-bind
(result foundp)
(gethash (funcall (slot-value method 'key-gen-fun)
?????????)
;;;;;;;;;;;;;;;;;;;;;;;;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
(slot-value method 'cache))
(if foundp
result
,method-lambda))
method-initargs)))
Pascal Costanza wrote:
>
> Jim Newton wrote:
>
>> Hi Pascal, this is a clever idea you have but i'm not
>> sure it meets the specification.... If i have two methods
>> for the same generic function but specializing two different
>> lambda lists, then i want two different caches.
>
>
> Hm, in this case an option would possibly be to define your own method
> metaobject class, roughly like this:
>
> (defclass cached-method (standard-method)
> ((cache :initform (make-hash-table))))
>
> (defmethod make-method-lambda
> ((gf cached-generic-function)
> (method cached-method)
> lambda-expression environment)
> (declare (ignore environment))
> (multiple-value-bind
> (method-lambda method-initargs)
> (call-next-method)
> (values `(multiple-value-bind
> (result foundp)
> (gethash args (slot-value method 'cache))
> (if foundp
> result
> ,method-lambda))
> method-initargs)))
>
> (defmethod reinitialize-instance :after
> ((gf cached-generic-function) &rest args)
> (declare (ignore args))
> (mapc #'clrhash (generic-function-methods gf)))
>
> The problem here is that most MOPs don't implement make-method-lambda
> correctly, and some not at all.
>
>> yes you are right my method does take up around methods,
>> which makes me ask why are we only allowed a single
>> around method. i wish around methods were stackable
>> but they are not.
>
>
> You can do anything you want in your own method combination and/or
> generic function class. For example, you could reserve a specific method
> qualifier for your own uses (:system-around, or some such), and then
> combine it with the rest accordingly.
>
>
> Pascal
>
Jim Newton <·····@rdrop.com> wrote in message news:<···············@uni-berlin.de>...
> It is looking better, but still there is the little
> problem of determining the hash key. In my original
> around method implementation I passed an expresion
> which got inserted into the GETHASH call. This was
> possible because it used a defmacro. What I need
> here is not to index the hash with the method
> parameters, but rather index the hash with some
> function of the parameters. I know the function
> at method definition time. And when I call the
> method i want the key generated by calling the
> key-gen-fun on the arguments i pass to the method.
>
? is there some reason to not do the entire cache maintenance in the
method combination. the descriptions did not imply that the effective
value would vary according to the particular methods combined, but
rather with the actual arguments. if that is so, just take e.weitz'
suggestion a step further:
the method combination accepts the key function as an optional
argument to the generic function definition. this key function would
be applied to the actual arguments to generate the key. they are
available as an option to the method combination function.
the cache hashtable can be bound to a slot in a specialized generic
function instance, so there is no need to close over it. this works if
the cache scope is the entire generic function. if not, as an
alternative, the first primary method could be used as a key in a
generic-function-scope cache to get a specialization-specific-scope
cache. (but, why?) if it is really necessary to muck up the works, one
could even define a method role for exactly the method which should
serve as the key. (anyway...)
the effective combination form can manage this cache directly, in the
same sort of way as the standard combination forces an around methods
to be invoked before before/after/primary methods, so there is no need
for additional methods.
?
> e.g., (my-method 1 2 3)
> in this case i want the key-gen-fun applied to
> the list (1 2 3)
>
> so is there a way to specify the :KEY-GEN-FUN
> when i define the method? And what does the
> make-method-lambda need to specify as the second
> argument to FUNCALL below?
why not specify it when you define the generic function?
>
> ...
james anderson wrote:
>
> ? is there some reason to not do the entire cache maintenance in the
> method combination. the descriptions did not imply that the effective
> value would vary according to the particular methods combined, but
> rather with the actual arguments. if that is so, just take e.weitz'
> suggestion a step further:
>
>>e.g., (my-method 1 2 3)
>>in this case i want the key-gen-fun applied to
>>the list (1 2 3)
>>
>>so is there a way to specify the :KEY-GEN-FUN
>>when i define the method? And what does the
>>make-method-lambda need to specify as the second
>>argument to FUNCALL below?
>
>
> why not specify it when you define the generic function?
The answer to this is a bit difficult to explain without
explaining the entire problem. however, in my case
the cache key is a function of the arguments. My arguments
are objects of some class which are being dynamically
modified as the program progresses. When I call the
same method on the same object later, some of the
slots of the object might have changed, or some of the
slots might reference other objects the slots of which
might have changed. I need to be able to generate
perhaps a different hash key in every method.
However, i only need such a cache one some of the methods.
I.e., the methods which are expensive to compute. I may
not need the cache on some other methods because they
may not be as compute intensive.
Example. suppose you have a chess game.
a PLAYER class with two instances WHITE and BLACK.
and each PLAYER instance contains 8 PAWN instances,
1 QUEEN instance, 1 KING instance, etc...
If I have a generic function CALC-BEST-MOVE,
a method specializing on PLAYER, one specializing
on PIECE which works for all pieces except the KING,
and one specializing on KING which handles KING as a
special case.
The best next move depends on the state of the entire
board.
The KEY-GEN-FUN must encode the state of the board.
but the state of the board will be the same when calculating
the best move for the KING and the next move for the PAWN.
So the key must also encode the piece in itself.
Thus i need to have seperate caches for KING and normal
PIECES.
Now what should the CALC-BEST-MOVE do when passed WHITE?
well it should simply iterate over all the pieces, call
CALC-BEST-MOVE on each piece, and return the best of those
16 piece-wise bests. this operation is simply delegated
to 16 other operations which are themselves cached. therefore
it is not necessary to cache the CALC-BEST-MOVE specialing
on PLAYER.
Does this example enlighten or obfuscate?
-jim
Jim Newton wrote:
> It is looking better, but still there is the little
> problem of determining the hash key. In my original
> around method implementation I passed an expresion
> which got inserted into the GETHASH call. This was
> possible because it used a defmacro. What I need
> here is not to index the hash with the method
> parameters, but rather index the hash with some
> function of the parameters. I know the function
> at method definition time. And when I call the
> method i want the key generated by calling the
> key-gen-fun on the arguments i pass to the method.
[...]
My code had a bug. make-method-lambda returns a lambda expression, not
just some code. Corrections below.
> (defclass cached-method (standard-method)
> ((cache :initform (make-hash-table))
> (key-gen-fun :initarg key-gen-fun)))
> ;;;;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> (defmethod make-method-lambda
> ((gf cached-generic-function)
> (method cached-method)
> lambda-expression environment)
> (declare (ignore environment))
> (multiple-value-bind
> (method-lambda method-initargs)
> (call-next-method)
> (values `(multiple-value-bind
> (result foundp)
> (gethash (funcall (slot-value method 'key-gen-fun)
> ?????????)
> ;;;;;;;;;;;;;;;;;;;;;;;;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> (slot-value method 'cache))
> (if foundp
> result
> ,method-lambda))
> method-initargs)))
This would be:
(defmethod make-method-lambda
((gf cached-generic-function)
(method cached-method)
lambda-expression environment)
(declare (ignore environment))
(multiple-value-bind
(method-lambda method-initargs)
(call-next-method)
(values `(lambda (args &rest more-args)
(declare (dynamic-extent more-args))
(multiple-value-bind
(result foundp)
(gethash (apply (slot-value method 'key-gen-fun) args)
(slot-value method 'cache))
(if foundp
result
(apply ,method-lambda args more-args))))
method-initargs)))
(But I still haven't tested this, so don't expect this to work out of
the box.)
Pascal
--
Pascal Costanza University of Bonn
·········@p-cos.net Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Jim Newton wrote:
> Hi Pascal, this is a clever idea you have but i'm not
> sure it meets the specification.... If i have two methods
> for the same generic function but specializing two different
> lambda lists, then i want two different caches.
Pardon the idiocy, but ... why is this useful?
> yes you are right my method does take up around methods,
> which makes me ask why are we only allowed a single
> around method. i wish around methods were stackable
> but they are not.
Pardon? Of course they are: they're just methods like any other and
you can define many of them. Do you mean `why can you only define one
around method for each set of argument classes?'? Well, because
they're methods I guess.
--tim
Jim Newton wrote:
> Your solution does address the problem of clearing
> the hash when you redefine the method... a problem
> that i was handling by a global list of hashes which
> i had to purge manually.
Here is another way to achieve this without going through the MOP:
(defmethod some-method (x y z)
(let ((cache (load-time-value (make-hash-table)))
(key (key-function x y z))
(or (gethash key cache)
(setf (gethash key cache)
some-code))))
...which you can translate into an appropriate macro.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
You know there is really no need to modify anything. I could
simply write it as a normal macro which imbeds the checking of
the cache in the primary method.
Can anyone think of a better way than this? is there really
any reason to use the MOP or around methods for this purpose?
-jim
(defmacro def-cached-method ( method-name lambda-list get-key &rest body)
`(progn
(let (( cache (make-hash-table :test #'equal)))
(unless (find cache *state-caches*)
(push cache *state-caches*))
(defmethod ,method-name ,lambda-list
(let* (( key ,get-key)
( value (gethash key cache)))
(cond
( value
(car value))
(t
(setf value (progn ,@body)
(gethash key cache) (list value))
value)))))))
Pascal Costanza wrote:
>
> Jim Newton wrote:
>
>> Your solution does address the problem of clearing
>> the hash when you redefine the method... a problem
>> that i was handling by a global list of hashes which
>> i had to purge manually.
>
>
> Here is another way to achieve this without going through the MOP:
>
> (defmethod some-method (x y z)
> (let ((cache (load-time-value (make-hash-table)))
> (key (key-function x y z))
> (or (gethash key cache)
> (setf (gethash key cache)
> some-code))))
>
> ...which you can translate into an appropriate macro.
>
>
> Pascal
>
Jim Newton wrote:
> You know there is really no need to modify anything. I could
> simply write it as a normal macro which imbeds the checking of
> the cache in the primary method.
>
> Can anyone think of a better way than this? is there really
> any reason to use the MOP or around methods for this purpose?
If at some later stage you would like to make such methods available for
the compile-time environment (by wrapping such a method definition in an
(eval-when (:compile-toplevel ...) ...) form), your approach wouldn't
work because your method definitions wouldn't be top-level definitions
anymore. This is circumvented by using load-time-value in my code. I
don't think there is a good enough reason to use the MOP or some such,
except that a MOP-based approach would allow you to ensure that the
caches are always in place - you cannot forget them anymore after the
generic function has been given the right generic function class. But
that's about it, and you trade this for some inconveniences because of
MOP incompatibilities across CL implementations when you want to port
your code.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."