Hi,
I have a function that's very expensive.
It gets called some levels into the stack, think
(defun my-algorithm ()
...
(loop
(large-foo)
...)
(defun large-foo ()
(mapcar #'expensive ...))
Now what I want is to fetch fresh results from EXPENSIVE at the start
of MY-ALGORITHM and then use a cache (think memoization) from then on
for the duration of this invocation of MY-ALGORITHM.
The program is multithreaded, by the way.
Any elegant solutions that come to your mind?
Thanks! :)
Leslie
Leslie P. Polzer wrote:
> Hi,
>
> I have a function that's very expensive.
>
> It gets called some levels into the stack, think
>
> (defun my-algorithm ()
> ...
> (loop
> (large-foo)
> ...)
>
> (defun large-foo ()
> (mapcar #'expensive ...))
>
> Now what I want is to fetch fresh results from EXPENSIVE at the start
> of MY-ALGORITHM and then use a cache (think memoization) from then on
> for the duration of this invocation of MY-ALGORITHM.
>
> The program is multithreaded, by the way.
>
> Any elegant solutions that come to your mind?
>
> Thanks! :)
(define-layered-function expensive (&rest args))
(define-layered-method expensive (&rest args) ...)
(deflayer memoization ()
((cache :initarg :cache :accessor cache :special t)))
(define-layered-method expensive
:in-layer memoization :around (&rest args)
(or (gethash args (cache (find-layer 'memoization)))
(setf (gethash args (cache (find-layer 'memoization)))
(call-next-method))))
(defun my-algorithm ()
(with-active-layers
((memoization :cache (make-hash-table :test #'equal)))
(loop ...)))
This is thread-safe in the sense that each thread will see its own
cache, and the cache is automatically removed on return from
my-algorithm. Outside of my-algorithm (when memoization is not active)
no hashtable lookup will be performed.
Pascal
P.S.: Ah, right, this uses ContextL... ;)
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Nov 6, 9:34 pm, Pascal Costanza <····@p-cos.net> wrote:
> (define-layered-function expensive (&rest args))
>
> ...
Excellent! This is the straight-forward and high-level
solution I was looking for. I have integrated it
and it works like a charm.
And it also shows that ContextL needs more examples,
I guess.
Using the lower level approach Alex has pointed out
would also be fine; I don't like the global variable,
though.
I can't really use the closure solution since the
expensive function is called about four or five levels
deep in the stack.
Thanks a lot!
Leslie
Leslie P. Polzer wrote:
> On Nov 6, 9:34 pm, Pascal Costanza <····@p-cos.net> wrote:
>
>> (define-layered-function expensive (&rest args))
>>
>> ...
>
> Excellent! This is the straight-forward and high-level
> solution I was looking for. I have integrated it
> and it works like a charm.
That's good to know. :)
> And it also shows that ContextL needs more examples,
> I guess.
That's true, but there is only so much time in the world...
Best,
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
LPP> The program is multithreaded, by the way.
then, i guess, it's better to use special variables, because typically
implementations automatically isolate them in multithreaded programs.
otherwise you'll have either to pass cache object exlicitly, or wrapped in
a closure (so large-foo receives #'expensive as parameter).
LPP> Any elegant solutions that come to your mind?
not really elegant, but i guess that's how Pascal's solution works
in a low level:
(defun expensive-inner (args) ..)
(defvar *expensive-cache*)
(defun expensive (args)
(if (boundp '*expensive-cache*)
(or (gethash args *expensive-cache*)
(setf (gethash ...) (expensive args))
(expensive args)))
(defun my-algorithm ()
(let ((*expensive-cache* (make-hash-table :test 'equal)))
....)
of course, you can add macrology as you want, if you have
more than one such case.
Alex Mizrahi wrote:
> LPP> The program is multithreaded, by the way.
>
> then, i guess, it's better to use special variables, because typically
> implementations automatically isolate them in multithreaded programs.
>
> otherwise you'll have either to pass cache object exlicitly, or wrapped in
> a closure (so large-foo receives #'expensive as parameter).
>
> LPP> Any elegant solutions that come to your mind?
>
> not really elegant, but i guess that's how Pascal's solution works
> in a low level:
>
> (defun expensive-inner (args) ..)
>
> (defvar *expensive-cache*)
>
> (defun expensive (args)
> (if (boundp '*expensive-cache*)
> (or (gethash args *expensive-cache*)
> (setf (gethash ...) (expensive args))
> (expensive args)))
>
> (defun my-algorithm ()
> (let ((*expensive-cache* (make-hash-table :test 'equal)))
> ....)
>
> of course, you can add macrology as you want, if you have
> more than one such case.
Instead of testing for boundness of *expensive-cache*, why not just test
for nil?
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
"Leslie P. Polzer" <·············@gmx.net> writes:
> Hi,
>
> I have a function that's very expensive.
>
> It gets called some levels into the stack, think
>
> (defun my-algorithm ()
> ...
> (loop
> (large-foo)
> ...)
>
> (defun large-foo ()
> (mapcar #'expensive ...))
>
> Now what I want is to fetch fresh results from EXPENSIVE at the start
> of MY-ALGORITHM and then use a cache (think memoization) from then on
> for the duration of this invocation of MY-ALGORITHM.
>
> The program is multithreaded, by the way.
>
> Any elegant solutions that come to your mind?
How about
(defun my-algorithm ()
(let ((*expensive-fn* (memoize #'expensive)))
(declare (special *expensive-fn*))
...
(loop
(large-foo)
...)))
(defun large-foo ()
(mapcar *expensive-fn* ...))
where memoize is a function returning a closure memoizing the function
given as an argument? If you don't mind passing in the function as an
argument to large-foo, you may not need the dynamic variable.
Bj�rn Lindberg
BL> How about
BL> (defun my-algorithm ()
BL> (let ((*expensive-fn* (memoize #'expensive)))
BL> (declare (special *expensive-fn*))
BL> ...
BL> (loop
BL> (large-foo)
BL> ...)))
BL> (defun large-foo ()
BL> (mapcar *expensive-fn* ...))
either globally proclaim *expensive-fn* special (that is, defvar),
or you need to add declaration in large-foo too