Caching algorithms

Thread view:

timasmith@hotmail.com - 28 Jul 2006 20:11 GMT

Hi,

Are there any standard caching algorithms for method calls.

I setup a scheme which works, but I hate to reuse it if there is
something better.

Essentially what I do is keep a Hashtable with the key the
concatenated, delimeted method name and parameters.

For example

public Object getStaticReference(int i, int j) {
String key = getKey(i,j);
if (hashtable contains key) {
return object from hashtable;
else
call method, store and return object
}

private String getKey(params...) {
String key = getCallingMethodName() + ":" + i + ":" + j;
return key;
}

What do you think?

thanks

Tim

Reply to this Message

Eric Sosman - 28 Jul 2006 21:41 GMT

timasmith@hotmail.com wrote On 07/28/06 15:11,:

> Hi,
>
[quoted text clipped - 22 lines]
>
> What do you think?

First, I'd think that this only makes sense if the
actual computation is very expensive or is the sort
of thing that really ought not be repeated. What are
your objectives?

Second, I'd look for a less clunky key than a String.
Your example shows a pair of integers; why not write a
tiny little IntegerPair class and use that instead?

Third, I'd worry about old, stale argument/value
pairs sitting around clogging up the HashMap long after
they've outlived their usefulness, tying up gobs and
gobs of memory to no purpose. I'd want to incorporate
a cache-aging mechanism, or maybe look into one of those
WeakReferenceThingummies (I've never used 'em myself, but
I've heard vague mention of them and would research them
if I were planning to implement this sort of thing).

Fourth, I'd wonder about that getCallingMethodName()
thing. I can't think of a way to implement it with
reasonable efficiency (throwing and catching an exception
and scrutinizing its stack seems the only way). More to the
point, why should I expect the wrapped method to behave
differently when called from foo() than from bar()? And
if it behaves the same, why shouldn't I return the same
value to bar() that was computed and cached on behalf
of foo()?

Finally, I'd be very careful about using this
approach if the cached/returned objects are mutable.
That's not to say I'd completely rule out caching, just
that I'd be very cautious about it ...

Signature

Eric.Sosman@sun.com

Reply to this Message

timasmith@hotmail.com - 29 Jul 2006 01:13 GMT

> timasmith@hotmail.com wrote On 07/28/06 15:11,:
> > Hi,
[quoted text clipped - 28 lines]
> of thing that really ought not be repeated. What are
> your objectives?

Exactly, these are expensive calls.

> Second, I'd look for a less clunky key than a String.
> Your example shows a pair of integers; why not write a
> tiny little IntegerPair class and use that instead?

The String *is* clunky but I have dozens of methods, often with a
variety of parameters.
getStaticReference(int i); getStaticReference(int i, int j);
getStaticReference(String s);
getStaticReference2(long l); getStaticReference3(); etc.

I have a feeling something in Java5 with variable method parameters
might help.

> Third, I'd worry about old, stale argument/value
> pairs sitting around clogging up the HashMap long after
[quoted text clipped - 4 lines]
> I've heard vague mention of them and would research them
> if I were planning to implement this sort of thing).

Agreed on the aging, I am weak on the WeakReferences

> Fourth, I'd wonder about that getCallingMethodName()
> thing. I can't think of a way to implement it with
> reasonable efficiency (throwing and catching an exception
> and scrutinizing its stack seems the only way).

Right that is how I did it

More to the

> point, why should I expect the wrapped method to behave
> differently when called from foo() than from bar()?

This problem does not occur - above the getCallingMethodName() looks
at the right and only method - which is the one calling getKey - if it
is a different calling method then it needs a different cached result

And

> if it behaves the same, why shouldn't I return the same
> value to bar() that was computed and cached on behalf
[quoted text clipped - 4 lines]
> That's not to say I'd completely rule out caching, just
> that I'd be very cautious about it ...

Mmm, good point, they are not meant to be mutable but I would have to
put something in place to make that so (I trust noone...)

I still think I am reinventing the wheel or if not a wheel perhaps a
database component.

Reply to this Message

Eric Sosman - 29 Jul 2006 02:21 GMT

>>timasmith@hotmail.com wrote On 07/28/06 15:11,:
>>
[quoted text clipped - 10 lines]
> getStaticReference(String s);
> getStaticReference2(long l); getStaticReference3(); etc.

Use a separate cache for each. This will also obviate the
mucking about with trying to get the name of the calling method.

Signature

Eric Sosman
esosman@acm-dot-org.invalid

Reply to this Message

timasmith@hotmail.com - 29 Jul 2006 03:49 GMT

> >>timasmith@hotmail.com wrote On 07/28/06 15:11,:
> >>
[quoted text clipped - 17 lines]
> Eric Sosman
> esosman@acm-dot-org.invalid

Now thats very nice, thanks for the tip!

Reply to this Message

Hendrik Maryns - 31 Jul 2006 12:11 GMT

>> Third, I'd worry about old, stale argument/value
>> pairs sitting around clogging up the HashMap long after
[quoted text clipped - 6 lines]
>
> Agreed on the aging, I am weak on the WeakReferences

Have a look at ReferenceMap in Jakarta Commons Collections, it does
exactly what you want. Not that I am sure this is going the right way,
btw. Are you trying to use dynamic programming? Usually, matrices with
strictly defined semantics are used there.

H.
- --
Hendrik Maryns

==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html

Reply to this Message

H. S. Lahman - 29 Jul 2006 18:54 GMT

Responding to Timasmith...

Basically I agree with Sosman's points. But let me take a somewhat
different spin...

> Are there any standard caching algorithms for method calls.

Why do you need to cache method calls at all? In particular,...

> I setup a scheme which works, but I hate to reuse it if there is
> something better.
[quoted text clipped - 11 lines]
> call method, store and return object
> }

Here you seem to be caching objects rather than methods (unless you are
making functions first class objects, which is an OO no-no).

It is also not clear what method you are calling in the 'else'. It
seems to be a constructor to create an object to cache and return.
Surely that would depend on i and j, which means a lot of processing
context is being omitted here. That also implies that i and j probably
have fixed bounds to support deterministic mapping. That all makes me
wonder exactly what problem you are trying to solve.

BTW, note that since you always fill the matrix, using a hash doesn't
make a lot of sense over a simple 2D array since sparseness is not an
issue. (Unless only a small subset of possible {i,j} combinations is
used in any given execution of the application AND the subset varies
arbitrarily from one execution to the next, which seems kind of odd.)

*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info@pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH

Reply to this Message

Caching algorithms

Free Magazines