home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 21 / IOPROG_21.ISO / SOFT / CACHECL1.ZIP / CACHE.H next >
Encoding:
C/C++ Source or Header  |  1996-07-12  |  22.9 KB  |  525 lines
  1. /*
  2.                            C A C H E    C L A S S
  3.                               for Borland C++ 4.5
  4.                                         Version 1
  5.  
  6.    Andrew Sterian
  7.    asterian@umich.edu
  8.    July 11, 1996
  9.  
  10.    Introduction
  11.    ============
  12.  
  13.    The Cache class implements a simple caching mechanism with "least
  14.    recently used" (LRU) replacement. It is useful for cases in which you
  15.    have some memory to spare and you wish to speed up access to frequently
  16.    used resources, of which not all will fit into available memory. Thus,
  17.    you know you have room in memory for more than 1 resource, but you don't
  18.    have room to store all possible resources in memory, so you want to
  19.    store some of them. The Cache class helps you to manage the storage in
  20.    memory of some subset of all possible resources and therefore speed up
  21.    your resource accesses.
  22.  
  23.    For an example of where a cache may be useful, consider a word
  24.    processing program that uses many fonts. In painting the editing window,
  25.    each time a new font must be displayed on the screen the existing font
  26.    has to be deleted and a new font created for use. Font creation may take
  27.    a long time, so to speed up the process it would be nice to pre-create
  28.    the fonts and store them in memory, ready for use. The problem is that
  29.    fonts can also take up a lot of memory, and creating and storing all
  30.    possible fonts in memory is unacceptable.
  31.  
  32.    If the user is only working with a small subset of all fonts, we need
  33.    only store that subset in memory. But which fonts are in the subset? And
  34.    what if the subset of fonts changes over time? The Cache class manages
  35.    this situation by maintaining a list of the last N resources (fonts)
  36.    used (N is the "cache depth", passed to the constructor of the class).
  37.    When the N+1th resource needs to be created, the Cache class will remove
  38.    the least recently used (LRU) resource of the existing N resources in
  39.    memory to make room for the new entry. Thus, at any time, there are a
  40.    maximum of N resources taking up memory, and they are precisely the last
  41.    N resources that were needed by the application.
  42.  
  43.    The reason for keeping the last N resources in memory is due to a
  44.    property of many programs known as "temporal locality of reference". In
  45.    plain English, this means that a program tends to use resources that it
  46.    has already (recently) used. For example, memory caches in
  47.    microprocessors exploit the fact that much of an application's code
  48.    consists of loops that are localized to a fairly small area of memory.
  49.    The CPU will therefore likely need to fetch instruction words from
  50.    addresses that have already been recently accessed (code in the loop).
  51.  
  52.    Data, too, often exhibits locality of reference. Consider the simple
  53.    task of updating a variable. First, its value is retrieved (resulting in
  54.    a memory access), the value is modified, then written back. But the
  55.    write-back occurs to the memory address that was just accessed, so
  56.    keeping this address in the cache immediately saves one reference. If
  57.    this variable will be used more than once in the code that follows (as
  58.    is often the case) then we save a reference each time the variable is
  59.    accessed.
  60.  
  61.    If, however, the application does NOT exhibit good temporal locality of
  62.    reference, then a cache may be of little or no use. Comparing the number
  63.    of cache "hits" to the total number of accesses is usually a good
  64.    benchmark of the cache's utility. CPU program data caches often exhibit
  65.    hit rates exceeding 90%, a great savings.
  66.  
  67.    Design Requirements
  68.    ===================
  69.  
  70.    To use the Cache class you need to provide two things:
  71.  
  72.     1. A "key class". This key class will be used as a label for the
  73.        resources that you wish to load. For example, if the resources we
  74.        are working with are fonts, the "key label" may be the alphabetic
  75.        name of the font, such as "MS Sans Serif 10".
  76.  
  77.        The key class needs to provide:
  78.             - a meaningful equality (==) operator
  79.             - either a member function with prototype
  80.                     unsigned HashValue(void) const
  81.  
  82.               or you need to provide a global function:
  83.                     unsigned HashValue(KeyClass& key)
  84.  
  85.               This function needs to return an unsigned quantity that is a
  86.               deterministic function of the key object. This unsigned
  87.               quantity need not be unique for different key objects,
  88.               although this may improve performance. Computing a "good"
  89.               hash value for a generic object has been called a study in
  90.               art more than science, although there are some general
  91.               principles to follow (Reingold and Hansen, "Data Structures
  92.               in Pascal", Little, Brown & Co. 1986):
  93.  
  94.                 * the hash value should depend upon every bit of the key
  95.                 * the hash value should break up naturally occurring
  96.                   clusters of elements. That is, if two keys are somehow
  97.                   logically related (for example, different point sizes of
  98.                   the same typeface) then their hash values should not be
  99.                   similar.
  100.                 * the hash value should be computed very quickly. Remember,
  101.                   the idea of a cache is to save time.
  102.  
  103.               The April 1996 issue of "Dr. Dobb's Journal" contains a brief
  104.               article on this topic and even provides some code for a good,
  105.               generalized hashing function.
  106.  
  107.             - a default constructor (just to keep the class libraries
  108.               happy, this constructor need not do anything meaningful)
  109.  
  110.        Note that your "key class" need not be a class at all, it can be
  111.        some built-in type, like 'int', for which you write a global
  112.        HashValue() function.
  113.  
  114.     2. A "resource class". This class encapsulates the resource that we are
  115.        trying to manage.
  116.  
  117.        The resource class must:
  118.             - provide a constructor of the form:
  119.                     ResourceClass(const KeyClass& key)
  120.  
  121.               That is, given a key belonging to the key class described
  122.               above, the resource class constructor should be able to find
  123.               and acquire the resource corresponding to this key.
  124.  
  125.             - acquire the resource in the constructor
  126.  
  127.             - release the resource in the destructor
  128.  
  129.        The last two points are important. The Cache class implementation
  130.        does not assume the existence of any Acquire() or Release()
  131.        functions in the resource class to explicitly construct and free the
  132.        resource. It is assumed that the resource management is performed in
  133.        the constructor and destructor of the resource class.
  134.  
  135.        This behavior is considered to be a "good thing"(tm). The features
  136.        of the C++ language ensure that no destructor is called for a class
  137.        that has not been completely constructed. To this end, it is further
  138.        suggested that the resource allocation in the constructor be
  139.        performed in the instantiation part of the constructor, not the
  140.        initialization. For example, this is preferred:
  141.  
  142.                     class ResourceClass {           // PREFERRED
  143.                     public:
  144.                         ResourceClass(const KeyClass& key)
  145.                             : data(GetResource(key)) { }
  146.                         ~ResourceClass() { FreeResource(data); }
  147.                         MyData* data;
  148.                     };
  149.  
  150.        over the following:
  151.  
  152.                     class ResourceClass {           // ***NOT RECOMMENDED***
  153.                     public:
  154.                         ResourceClass(const KeyClass& key)
  155.                             { data = GetResource(key); }
  156.                         ~ResourceClass() { FreeResource(data); }
  157.                         MyData* data;
  158.                     };
  159.  
  160.        which can lead to incorrect behavior if resource acquisition fails.
  161.  
  162.    Usage
  163.    =====
  164.  
  165.    Once you have designed your key class and resource class, you can
  166.    instantiate a cache for this resource as follows:
  167.  
  168.             typedef Cache<KeyClass, ResourceClass> MyCache;
  169.             MyCache *theCache = new MyCache(depth);
  170.  
  171.    where 'depth' indicates the cache depth, or the maximum number of
  172.    resources that you want cached at any one time. Obviously, the larger
  173.    the depth the better the performance but the more memory will be used.
  174.  
  175.    The Cache constructor takes an optional second parameter which is the
  176.    size of the internal hash table to use. This table is not visible
  177.    outside the Cache class but its size has an impact on performance.
  178.    Larger hash tables lead to faster searches through the cache, but will
  179.    obviously use more memory. Do note, however, that it is highly
  180.    recommended that the hash table size be a prime number, or else
  181.    performance can severely degrade in certain circumstances. The default
  182.    hash table size is 109. For some reason, the default hash table size
  183.    provided by Borland is 111 which is not prime (in fact, it has the small
  184.    prime 3 as a factor making it one of the poorest odd table sizes you
  185.    could use).
  186.  
  187.    The main interface to the cache is nearly transparent. Whenever you wish
  188.    to acquire a resource, create a key for the resource and simply call the
  189.    Load() member function:
  190.  
  191.                     KeyClass lKey(parameters);
  192.                     ResourceClass* lRes = theCache->Load(lKey);
  193.  
  194.    If the resource is already in the cache, then Load() will return a
  195.    pointer to the existing resource. Otherwise, Load() will construct a new
  196.    ResourceClass object (passing the key to the constructor), add the
  197.    object to the cache, and pass back the pointer to the object. In either
  198.    case, you don't have to worry about what is or is not in the cache, the
  199.    Cache class does it all for you. Just use Load() to always create
  200.    resources.
  201.  
  202.    If the resource to be loaded is not in the cache and the cache is full,
  203.    then the least recently used item in the cache will be discarded to make
  204.    room for the new resource. The destructor for ResourceClass, therefore,
  205.    should release the resource since it will be invoked at this time.
  206.  
  207.    There are other member functions in the Cache class that may be of
  208.    interest. These functions are provided for support of debugging or
  209.    statistics gathering and need not be used in normal operation.
  210.  
  211.         - unsigned long Hits(void)
  212.             returns the number of cache "hits" encountered since the cache
  213.             was created or since the last Flush() operation. A cache "hit"
  214.             occurs when the Load() function is called and the desired
  215.             resource is already in the cache.
  216.  
  217.         - unsigned long Misses(void)
  218.             returns the number of cache "misses", but is otherwise
  219.             identical to the Hits() function. A cache "miss" occurs when
  220.             Load() is called but the desired resource is NOT in the cache
  221.             and must be created. The "hit rate" can be simply computed as
  222.             100.0*Hits()/(Hits()+Misses()).
  223.  
  224.         - void Flush(void)
  225.             removes all items from the cache (calling all ResourceClass
  226.             destructors to physically release the resources) and resets the
  227.             cache-hit and cache-miss counters.
  228.  
  229.         - void Depth(void)
  230.             returns the current cache depth. The cache depth is specified
  231.             in the constructor but may be increased (see below).
  232.  
  233.         - void Depth(unsigned newDepth)
  234.             This form of the Depth() function increases the cache depth to
  235.             the size specified by 'newDepth'. If 'newDepth' is smaller than
  236.             the current depth, then nothing happens.
  237.  
  238.         - unsigned CachedItems(void)
  239.             returns the number of items in the cache
  240.  
  241.         - ResourceClass *LRUItemPeek(void)
  242.             returns a pointer to the resource element that is in the cache
  243.             and was the least recently used. That is, this points to the
  244.             resource that will be the next to be removed from the cache
  245.             (unless it loses its least-recently-used status by being
  246.             accessed through Load()). If the cache is empty, this function
  247.             returns NULL.
  248.  
  249.         - void LRUItemPop(void)
  250.             removes the least-recently-used resource from the cache,
  251.             calling the destructor for the resource class element so the
  252.             physical resource is released. If the cache is empty, this
  253.             function does nothing.
  254.  
  255.    Example
  256.    =======
  257.  
  258.    Here is a real example for how to use the Cache class. The running
  259.    example of fonts as resources that we've been using is cumbersome since
  260.    fonts have so many parameters associated with them, so we will use
  261.    something easier, a Windows bitmap resource. This may be useful for a
  262.    program that uses very many bitmaps and does not wish to store them all
  263.    in memory. Yet, the bitmaps exhibit good temporal locality of reference
  264.    so that a bitmap that was used recently is likely to be used again soon.
  265.  
  266.    A bitmap is loaded using the Windows LoadBitmap() function, which
  267.    requires us to specify an instance handle (to identify the executable
  268.    file containing the bitmap resource), as well as the name of the bitmap
  269.    resource as a string (we're ignoring the MAKEINTRESOURCE possibility).
  270.    The key class must include these two values:
  271.  
  272.         class BitmapKey {
  273.         public:
  274.             BitmapKey(HINSTANCE hInstance, string bitmapName)
  275.                 : inst(hInstance), name(bitmapName) { }
  276.  
  277.             BitmapKey() {}  // default constructor to keep libraries happy
  278.  
  279.             operator ==(const BitmapKey& obj) {
  280.                 return inst==obj.inst && name==obj.name;
  281.             }
  282.             unsigned HashValue(void) const {
  283.                 // We conveniently use the hash() function of the string
  284.                 // class. The hash function given here has no claim to
  285.                 // being "good".
  286.                 return (inst ^ name.hash());
  287.             }
  288.             HINSTANCE inst;
  289.             string name;
  290.         };
  291.  
  292.    Now we must define a class that encapsulates the actual bitmap. It must
  293.    also define how to load the bitmap (given a BitmapKey element) and
  294.    release the resource.
  295.  
  296.         class BitmapClass {
  297.         public:
  298.             // Load physical resource in constructor
  299.             BitmapClass(const BitmapKey& key)
  300.                 : handle(LoadBitmap(key.inst, key.name.c_str()))
  301.                 { }
  302.  
  303.             // Release resource in destructor
  304.             ~BitmapClass() { DeleteObject(handle); }
  305.  
  306.             HBITMAP handle;
  307.         }
  308.  
  309.    Done! To use the above classes in a program, we may do something like
  310.    the following:
  311.  
  312.         Cache<BitmapKey, BitmapClass> bmCache(10);  // Cache up to 10 bitmaps
  313.  
  314.         while (1) {
  315.             string s;
  316.  
  317.             GetBitmapName(s);   // Ask user for a valid bitmap name
  318.  
  319.             BitmapClass* bm = bmCache.Load(BitmapKey(hInstance, s));
  320.  
  321.             DrawBitmap(bm->handle); // Draw the bitmap on the screen
  322.         }
  323.  
  324.    Of course, this program has no temporal locality of reference since the
  325.    user can ask for any bitmap in any order, thus this program is unlikely
  326.    to benefit from using a cache. But hopefully it demonstrates the basic
  327.    principles of using the Cache class.
  328.  
  329.    Future Work
  330.    ===========
  331.  
  332.    This code was written in one evening. Consequently, there is lots of
  333.    room for improvement. Off the top of my head, I can think of the
  334.    following possible refinements or optimizations:
  335.  
  336.         - An allocator specialized for the CacheItem class can be used to
  337.           provide faster mark-and-release style memory management for the
  338.           class, making insertions and removals of cache items from the
  339.           hash table more efficient.
  340.  
  341.         - A mechanism for turning off the cache altogether could be
  342.           implemented. This is often useful for debugging or for comparing
  343.           with-cache and without-cache performance without having to modify
  344.           the code (although a depth of 1 would be a good approximation).
  345.           Come to think of it, I can't remember why I didn't want to allow
  346.           the depth to be reduced. Otherwise, shrinking the depth to 1
  347.           would basically be equivalent to turning the cache off.
  348.  
  349.         - The DDJ article mentioned above makes a case for using a closed
  350.           hash table with linear rehashing instead of the traditional
  351.           implementation of an open hash table (linked list for each hash
  352.           slot). This would require redefining the TDictionary class to use
  353.           a customized (closed) hash table instead of the supplied Borland
  354.           implementation. If the number of items to be cached is known a
  355.           priori and a table size can be created that is at least twice
  356.           this number, then this may provide some performance improvement.
  357.           All this work is certainly not worth it for me, though.
  358.  
  359.         - LRU is generally a good replacement policy but improvements on
  360.           this basic approach exist. For example, shadow directories
  361.           (Pomerene et. al. 1984).
  362.  
  363.         - One source of inefficiency in this code is the call to Detach()
  364.           in the markRecentlyUsed() routine. This call essentially performs
  365.           a linear search through the LRU list to find the item before
  366.           removing it from its current position and adding it back to the
  367.           tail. For large cache depths, this linear search can be costly. A
  368.           more intelligent data structure arrangement could probably reduce
  369.           this O(N) search into an O(log N) or even constant-time search.
  370.           My use of the Cache class usually uses small depths (10 or 20) so
  371.           a linear search is not a big deal for me.
  372.  
  373.         - In the dictionary, for a given hash slot any new items are added
  374.           to either the head or tail of the linked list at that slot (I
  375.           haven't dived into Borland's code to figure out which one). If we
  376.           are to exploit temporal locality of reference to its fullest, we
  377.           should ensure that the most recently used cache item comes at the
  378.           head. This is because we predict that it will be used again soon,
  379.           so a search through this list would stop as close to the head as
  380.           possible (for minimum searching time). If the hash table size is
  381.           greater than the cache depth, then each linked list will likely
  382.           have at most 2 or 3 elements so this issue is probably no big
  383.           deal.
  384.  
  385.    Administrivia
  386.    =============
  387.  
  388.    This code is CommunityWare. You may use it at no cost. If you do use it,
  389.    however, I ask that you consider taking a useful C++ class that you have
  390.    written and releasing it to the public for free.
  391.  
  392.    Please feel free to drop me some e-mail if you do find this class
  393.    useful, I'd love to hear from you! If you have questions or problems
  394.    regarding this code, then please write me, but I am afraid that I cannot
  395.    guarantee any kind of support or aid in getting this software to work.
  396.    This software is provided "as is".
  397.  
  398.    If you modify this code, please keep a record of modifications
  399.    (including your name, so that I am not held responsible for your changes
  400.    :-)
  401.  
  402.    Andrew Sterian
  403.    asterian@umich.edu
  404. */
  405.  
  406. #ifndef _CACHE_H_
  407. #define _CACHE_H_
  408.  
  409. #include <classlib/assoc.h>     // Defines TAssociation classes
  410. #include <classlib/dict.h>      // Defines TDictionary classes
  411. #include <classlib/dlistimp.h>  // Defines TDoubleList classes
  412.  
  413. template <class K, class T>
  414. class Cache {
  415. public:
  416.     // Each entry in the dictionary (a CacheItem) consists of a key and
  417.     // a pointer to a resource class based on that key.
  418.     typedef TDIAssociation<K,T> CacheItem;
  419.  
  420.     Cache(unsigned depth, unsigned hashSize = 109)
  421.         : mDict(hashSize), mDepth(depth), mHits(0), mMisses(0) {
  422.         CHECK(depth >= 1);
  423.         mDict.OwnsElements(1);
  424.     }
  425.     ~Cache() { mDict.Flush(); } // Ensure all resources are freed
  426.  
  427.     void Flush(void) { mDict.Flush(); mLRUList.Flush(); mHits=mMisses=0; }
  428.     unsigned      Depth(void) const { return mDepth; }
  429.     void          Depth(unsigned newDepth) {
  430.         if (newDepth > mDepth) mDepth=newDepth;
  431.     }
  432.  
  433.     // This is the main accessor of the Cache class. It should be used to
  434.     // create all resources.
  435.     T* Load(const K& key);
  436.  
  437.     unsigned long Hits(void) const { return mHits; }
  438.     unsigned long Misses(void) const { return mMisses; }
  439.     unsigned      CachedItems(void) const { return mLRUList.GetItemsInContainer(); }
  440.  
  441.     // For debugging, these functions can be useful.
  442.     T* LRUItemPeek(void) const {
  443.         return CachedItems() ? CONST_CAST(T *, mLRUList.PeekHead()->Value())
  444.                              : 0;
  445.     }
  446.     void LRUItemPop(void) {
  447.         if (CachedItems()) discardLRUItem();
  448.     }
  449.  
  450. protected:
  451.     TIDictionaryAsHashTable<CacheItem> mDict;
  452.     TIDoubleListImp<CacheItem>         mLRUList;
  453.     unsigned mDepth;
  454.     unsigned long mHits;
  455.     unsigned long mMisses;
  456.  
  457.     void markRecentlyUsed(CacheItem *lItemPtr);
  458.     void addCacheItem(CacheItem *lItemPtr);
  459.     void discardLRUItem(void);
  460. };
  461.  
  462. template <class K, class T>
  463. void Cache<K,T>::markRecentlyUsed(CacheItem *lItemPtr)
  464. {
  465.     // Find the object in the LRU list, wherever it may be, and remove it
  466.     mLRUList.Detach(lItemPtr);
  467.  
  468.     // Now add it at the tail. Most recently used objects are at the tail
  469.     // of this list, so that LRU objects float to the head.
  470.     mLRUList.AddAtTail(lItemPtr);
  471. }
  472.  
  473. template <class K, class T>
  474. void Cache<K,T>::addCacheItem(CacheItem *lItemPtr)
  475. {
  476.     // Add the pointer to the item to the LRU list
  477.     mLRUList.AddAtTail(lItemPtr);
  478.  
  479.     // Add it to the Dictionary too
  480.     mDict.Add(lItemPtr);
  481. }
  482.  
  483. template <class K, class T>
  484. void Cache<K,T>::discardLRUItem(void)
  485. {
  486.     CHECK(! mLRUList.IsEmpty());
  487.  
  488.     // Get the item from the head of the LRU list
  489.     CacheItem *lHead = mLRUList.PeekHead();
  490.     mLRUList.DetachAtHead();
  491.  
  492.     // Now remove it from the dictionary
  493.     mDict.Detach(lHead);
  494. }
  495.  
  496. template <class K, class T>
  497. T* Cache<K,T>::Load(const K& key)
  498. {
  499.     CacheItem lLook(key, 0), *lItem;
  500.  
  501.     // First look for the key in the dictionary. If found, it's a cache
  502.     // hit and we just return the associated resource. Otherwise we
  503.     // must construct the resource and add this new entry into the cache.
  504.     if ((lItem = mDict.Find(&lLook)) != 0) {
  505.         mHits++;
  506.         markRecentlyUsed(lItem);
  507.     } else {
  508.         mMisses++;
  509.  
  510.         // Get a new object by constructing it as T(key)
  511.         lItem = new CacheItem(key, new T(key));
  512.  
  513.         // Remove the LRU entry from the dictionary if we've exceeded our depth
  514.         if (mLRUList.GetItemsInContainer() >= mDepth) {
  515.             discardLRUItem();
  516.         }
  517.  
  518.         // Add new item to dictionary
  519.         addCacheItem(lItem);
  520.     }
  521.     return CONST_CAST(T *, lItem->Value());
  522. }
  523. #endif // _CACHE_H_
  524.  
  525.