Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Caching algorithms

Reply
Thread Tools

Caching algorithms

 
 
timasmith@hotmail.com
Guest
Posts: n/a
 
      07-28-2006
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 With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-28-2006


http://www.velocityreviews.com/forums/(E-Mail Removed) wrote On 07/28/06 15:11,:
> 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 ...

--
(E-Mail Removed)

 
Reply With Quote
 
 
 
 
timasmith@hotmail.com
Guest
Posts: n/a
 
      07-29-2006
Eric Sosman wrote:
> (E-Mail Removed) wrote On 07/28/06 15:11,:
> > 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?


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.

>
> --
> (E-Mail Removed)


 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      07-29-2006
(E-Mail Removed) wrote:

> Eric Sosman wrote:
>
>>(E-Mail 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.

--
Eric Sosman
(E-Mail Removed)lid
 
Reply With Quote
 
timasmith@hotmail.com
Guest
Posts: n/a
 
      07-29-2006

Eric Sosman wrote:
> (E-Mail Removed) wrote:
>
> > Eric Sosman wrote:
> >
> >>(E-Mail 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.
>
> --
> Eric Sosman
> (E-Mail Removed)lid


Now thats very nice, thanks for the tip!

 
Reply With Quote
 
H. S. Lahman
Guest
Posts: n/a
 
      07-29-2006
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 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 Removed) for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(88OOA-PATH



 
Reply With Quote
 
Hendrik Maryns
Guest
Posts: n/a
 
      07-31-2006
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

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


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-----
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Disable page caching without disabling caching of jpegs andstylesheets etc JimLad ASP .Net 3 01-21-2010 10:13 AM
Fragment Caching inside page caching? Troy Simpson ASP .Net 0 01-19-2004 11:57 AM
Map n algorithms to m functional units Andreas VHDL 0 12-02-2003 02:34 PM
trouble with caching or caching the trouble Hypo ASP .Net 6 08-01-2003 07:11 AM



Advertisments