Caching algorithms

Discussion in 'Java' started by timasmith@hotmail.com, Jul 28, 2006.

  1. Guest

    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
    , Jul 28, 2006
    #1
    1. Advertising

  2. Eric Sosman Guest

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

    --
    Eric Sosman, Jul 28, 2006
    #2
    1. Advertising

  3. Guest

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

    >
    > --
    >
    , Jul 29, 2006
    #3
  4. Eric Sosman Guest

    wrote:

    > Eric Sosman wrote:
    >
    >> 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
    lid
    Eric Sosman, Jul 29, 2006
    #4
  5. Guest

    Eric Sosman wrote:
    > wrote:
    >
    > > Eric Sosman wrote:
    > >
    > >> 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
    > lid


    Now thats very nice, thanks for the tip!
    , Jul 29, 2006
    #5
  6. H. S. Lahman Guest

    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

    Pathfinder Solutions
    http://www.pathfindermda.com
    blog: http://pathfinderpeople.blogs.com/hslahman
    "Model-Based Translation: The Next Step in Agile Development". Email
    for your copy.
    Pathfinder is hiring:
    http://www.pathfindermda.com/about_us/careers_pos3.php.
    (888)OOA-PATH
    H. S. Lahman, Jul 29, 2006
    #6
  7. -----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-----
    Hendrik Maryns, Jul 31, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andreas
    Replies:
    0
    Views:
    499
    Andreas
    Dec 2, 2003
  2. abhinav

    encryption algorithms

    abhinav, Dec 26, 2004, in forum: VHDL
    Replies:
    2
    Views:
    634
  3. Hypo
    Replies:
    6
    Views:
    399
  4. Troy Simpson

    Fragment Caching inside page caching?

    Troy Simpson, Jan 19, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    773
    Troy Simpson
    Jan 19, 2004
  5. JimLad
    Replies:
    3
    Views:
    905
    JimLad
    Jan 21, 2010
Loading...

Share This Page