Dynamic scope memoization

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/

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/

PC> Instead of testing for boundness of *expensive-cache*, why not just
PC> test for nil?

indeed

"Leslie P. Polzer" <leslie.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

On Nov 6, 9:34*pm, Pascal Costanza <p...@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...@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/