Re: [boost] Re: Interest in a cache class?

From: Rainer Deyke (root_at_[hidden])
Date: 2002-03-09 21:41:57

----- Original Message -----
From: "danl_miller" <danl_miller_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, March 09, 2002 3:35 PM
Subject: [boost] Re: Interest in a cache class?

> --- In boost_at_y..., "Rainer Deyke" <root_at_r...> wrote:
> > I have written a templated cache class for my personal use.  Is
> there
> > interest in this for inclusion in Boost?
> >
> >
> > --
> > Rainer Deyke | root_at_r... | http://rainerdeyke.com
>
>   Please provide any background, references, and/or prior art of the
> school-of-thought from where the cache class template concept comes.

What I have currently is a generalization of a bitmap cache.  It uses
a variety of techniques from various sources, none of them
particularily novel.  I haven't seen this particular combination used
before.  Maybe a different combination is more appropriate for boost.

My design goals were:

  - Objects are loaded on demand.
  - Objects are discarded when no longer needed.
  - Fast access to items in the cache.
  - Relatively efficient overall (in time and memory).
  - Relatively easy to implement.

Sample usage:
  cache<string, bitmap> bitmap_cache;
  cache<string, bitmap>::handle bitmap_handle =
bitmap_cache["foo.bmp"];
  bitmap_handle->draw();

The class 'cache::handle' deserves some special attention.  The
existance of a 'cache::handle' does not guarantee that the associated
object is currently cached.  Instead, it exists to avoid the O(lg n)
access time of 'cache::operator[]'.  Dereferencing a 'cache::handle'
takes constant time if the associated object is in the cache (and
indeterminate time otherwise).

>   Please explain the mission and scope-of-usage for this cache class
> template which have.  For example, the following questions about a
> "cache class template" come to mind:
>
>   What is being cached?

Currently, bitmaps and sounds.  In theory, any C++ object.  There is
some overhead associated with the current design that makes it
impractical for very small objects.

>   From which slower-throughput storage/etc is the cached-stuff
coming?

Anything.  This is determined by a policy class.  They can even be
generated algorithmically.

>   What stimulus causes the stuff to migrate to cached-stuff?

Dereference of a 'cache<...>::handle'.

>   What stimulus causes the cached-stuff to migrate to stuff?'

Calls to 'cache<...>::discard', or cache overflow (i.e. the migration
of stuff to cached-stuff beyond a user-defined maximum).

>   Can the cache operate in a read mode, write mode, or both
> simultaneously?

Read mode.  Adding write mode would not be overly difficult, but I
have not had need for it yet.

>   Which datatypes are permitted to be within the stuff &
cached-stuff
> (e.g., are pointers permitted to be within the cached-stuff &
stuff)?

Any C++ object is permitted.

>   If pointers are permitted to be within cached-stuff & stuff, then
do
> addresses undergo translation as they go from initial-RAM-cache to
> slower medium (presumably not RAM) back to retrieval-RAM-cache where
> the retrieval-RAM-cache might be in a different
process/address-space
> than the initial-RAM-cache?

This is the responsibility of the policy class.

>   Given the most expansive definition of what "cache class template"
> could possibly mean (e.g., something similar to ObjectStore), yes,
> such a full-featured in-RAM cache of C++ objects capable of existing
> outside of RAM in a slower medium shared between processes would be
> very useful.  But maybe such a huge undertaking  is not what you
> intend.  Please be more specific.

My aim is completely different.  My cache is about 220 lines of C++
code, written in one day.  It is not a persistance system; it is
merely a cache.  Given a resource that has a short identifier (for
example a filename) and a larger full representation (for example a
bitmap in memory) with a way of converting the short identifier into
the larger representation (i.e. by loading the file into memory), it
keeps those resources that have been used recently in memory and only
stores the short identifier and some bookkeeping data for those
resources that have not been used recently.

--
Rainer Deyke | root_at_[hidden] | http://rainerdeyke.com