Caching algorithms

[timasmith]

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

 

[Eric Sosman]

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?

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

 

[timasmith]

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?

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

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

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.

 

[Eric Sosman]

(e-mail address removed) wrote On 07/28/06 15:11,:

Are there any standard caching algorithms for method 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.

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

 

[timasmith]

(e-mail address removed) wrote On 07/28/06 15:11,:

Are there any standard caching algorithms for method 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.

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

Now thats very nice, thanks for the tip!

 

[H. S. Lahman]

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.

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
}

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
(e-mail address removed)
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
(e-mail address removed) for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEzeVpe+7xMGD3itQRAsexAJ9lyZIPZ5ixpM9WY26yl+QXSL7/owCfeTU6
eOqnxPKkwgrqCckLuOVktD4=
=/7ij
-----END PGP SIGNATURE-----