Click here to Skip to main content
Click here to Skip to main content

A Simple and Generic Cache

By , 17 Oct 2005
Rate this:
Please Sign up or sign in to vote.

Introduction

Having known all my years as a programmer what caching is and what it is used for, I have never once been in a situation where it was critically necessary. We all know how caching can dramatically boost performance in certain situations, but more often than not, developers do not use caching in those situations.

In this article I will take you through some code for developing a simple but generic caching object. Each item in the cache is stored as an object. The cache will use the Least-Recently-Used (LRU) replacement method to expire cached items. I plan writing a follow up article on a more advanced cache with more features and more replacement methods supported.

A Quick Overview of the Process

Very generally speaking, a user (usually a piece of software) requires some resource. This resource can really be anything including large files, datasets/datareaders or a resource over the web to name a few. Whenever the acquisition of such a resource is an expensive operation in terms of time and/or CPU cycles, the resource becomes a candidate for caching.

The user will typically request this resource from the cache first to avoid having to undergo the expensive acquisition of it. If the resource is contained in the cache, it is returned to the requestor, otherwise, it is acquired elsewhere and handed to the cache to store for future retrieval.

The cache explained in this article works on this model. The user or requestor is an application or service. It will reference the GenericCache class library. The generic cache provides a callback to acquire a resource from the user and add it to the cache. When the user wants to acquire the resource, the Fetch() method is called and the item is retrieved. If the item is not in the cache, the GenericCache object will use the user's implementation of the callback to acquire the resource, add it to the cache and return the cached resource.

Using the code

The source code provided in the downloads section is a complete Visual Studio 2003 project with the solution file.

Note: It is assumed that the reader is familiar with the Dictionary data type and the key-value pair model that a dictionary follows. This data type is the basis for this caching library.

Containing the Cached Items

In my search to find a suitable container class for the cached items, I came across the NameObjectCollectionBase abstract class provided by the .NET Framework in the System.Collections.Specialized namespace. This class provides functionality to store items in a hash table fashion as well as in an indexed ArrayList. This suited the need I had to quickly access items in a FIFO manner and also access the items with unique keys. Hash table keys are, by their nature, not unique but in the derived class I did not allow duplicate keys to be used.

Let's have a look at the class:

using System;
using System.Collections.Specialized;

namespace GenericCache
{
    // Inherits from the NameObjectCollectionBase abstract class.
    // This class will act as the content container and is also
    // a wrapper for the functionality of the
    // NameObjectCollectionBase class.
    internal class Dictionary : NameObjectCollectionBase
    {
    
        // Nothing special is done in the constructor and
        // the base class' constructor is called.
        public Dictionary( int p_initialCapacity ) : base( p_initialCapacity )
        {
        }

        // Removes the oldest item from the cache.
        public object Remove( out string p_key )
        {
            object toReturn;

            if ( this.Count < 1 )
            {
                // Nothing to remove.
                        p_key = null;                
                return null;
            }

            // Get the oldest cache item.
            toReturn = this.BaseGet( 0 );

            //Get the oldest item key.
            p_key = this.BaseGetKey( 0 );

            // Remove the oldest item.
            this.BaseRemoveAt( 0 );

            return toReturn;
        }

        // Indexer to get a cached item.
        public object this[ string p_key ]
        {
            get
            {
                return ResetItem( p_key );
            }
        }

        // Add a cache item.
        public void Add( string p_key, ref object p_item )
        {
            // The cache item will automatically be
            // added to the end of the underlying ArrayList.
            this.BaseAdd( p_key, p_item );
        }

        // Retrieves a cached item from the NameObjectCollectionBase
        // and returns it. Also, the retrieved item is removed and
        // then added again to ensure its age is reset.
        object ResetItem( string p_key )
        {
            object tempItem;

            tempItem = this.BaseGet( p_key );

            // If the retrieved item is null,
            // it isn't reset.
            if ( tempItem != null )
            {
                this.BaseRemove( p_key );
                this.BaseAdd( p_key, tempItem );
            }

            return tempItem;
        }

        // Clears the entire contents of the cache.
        public void Clear()
        {
            this.BaseClear();
        }
    }
}

Most of the code is self explanatory but for clarity, I will explain what some of the methods do:

  • public object Remove( out string p_key );

    The replacement method used for expired cache items, is the Least-Recently-Used method. This method expires cache items, from the ones that have been accessed long ago, to the ones that have been accessed most recently. The NameObjectCollectionBase class uses an ArrayList underlying, this provides us with the functionality to remove the oldest items first. Later on we'll see that when a cached item is accessed, it is removed from the container and then added again to reset its age.

    First this method checks that the container contains items. If not, it simply returns null and the out parameter is set to null as well. If it does contain items, the item in the underlying ArrayList with index 0 is removed. This ensures that the least recently used items are removed first. The method returns the removed item and sets the out p_key to the removed item's key.

  • object ResetItem( string p_key );

    This private method resets an item's age by removing it from the underlying ArrayList (from a specific index) and adding it again at the end of the underlying ArrayList.

Two Events Defined

In our main Cache object (discussed a little further down), two events and two delegates are defined:

  • public delegate void CacheItemExpiredEventHandler( object p_source, CacheItemExpiredEventArgs p_e );
  • public event CacheItemExpiredEventHandler CacheItemExpired;

    The CacheItemExpiredEventHandler is a delegate to handle the event of a cache item expiring. This event is fired whenever an item has been removed from the cache as a result of the capacity being reached. The following is the definition for the CacheItemExpiredEventArgs class:

    using System;
    
    namespace GenericCache
    {
        // Holds the CacheItemExpired event arguments.
        public class CacheItemExpiredEventArgs
        {
    
            string key;
            object item;
    
            public CacheItemExpiredEventArgs( string p_key, ref object p_item )
            {
                key = p_key;
                item = p_item;
            }
    
            public object Item
            {
                get
                {
                    return item;
                }
            }
    
            public string Key
            {
                get
                {
                    return key;
                }
            }
        }
    }

    It simply holds a reference to the object that has expired and the key that was used for access to that object.

  • public delegate object FetchItemEventHandler( object p_source, FetchItemEventArgs p_e );
  • public event FetchItemEventHandler FetchItem;

    The FetchItemEventHandler is a delegate to handle the event of a cache item being fetched from the user for caching. This event is fired whenever an item has been requested from the cache but was not found. The cache then asks the user to provide the item as a returned object in the event implementation. The following is the definition for the FetchItemEventArgs class:

    using System;
    
    namespace GenericCache
    {
    
        // Holds the FetchItem event arguments.
        public class FetchItemEventArgs
        {
    
            string key;
    
            public FetchItemEventArgs( string p_key )
            {
                key = p_key;
            }
    
            public string Key
            {
                get
                {
                    return key;
                }
            }
        }
    }

    It simply holds a reference to the key that was used in acquiring the item.

    This event has a return type of object. The user "catching" this event provides the requested item by returning it from the event implementation.

The Cache Class

Here is the code and an explanation for some of the methods following it:

using System;
using System.Threading;

namespace GenericCache
{
    // This delegate will be used as a definition for the event
    // to notify the caller that an item has expired.
    public delegate void CacheItemExpiredEventHandler( object p_source, 
                                     CacheItemExpiredEventArgs p_e  );

    // This delegate will be used as a definition to get an 
    // item if it does not exist in the cache.
    public delegate object FetchItemEventHandler( object p_source, 
                                        FetchItemEventArgs p_e  );

    // Cache class. All the members of this class is thread safe.
    public class Cache
    {

        // Notifies the user that a cache item has expired.
        public event CacheItemExpiredEventHandler    CacheItemExpired;
        // Gets an item to cache if it doesn't exist in the cache.
        public event FetchItemEventHandler            FetchItem;

        // Holds the instance of the dictionary container.
        Dictionary                     dictionary;
        // The maximum size of the cache.
        int                            capacity;
        // A ReaderWriterLock to synchronize access to the dictionary.
        ReaderWriterLock               dictionaryLock;
    
        public Cache( int p_initialSize, int p_capacity ) : base()
        {
            // Initial size cannot be smaller than 1.
            if ( p_initialSize < 1 )
                p_initialSize = 1;

            // Capacity cannot be smaller than 0.
            // If capacity is 0, there is no maximum size for
            // the cache and it will always grow.
            if ( p_capacity < 0 )
                p_capacity = 0;

            dictionary = new Dictionary( p_initialSize );
            capacity = p_capacity;

            // Instantiate the lock.
            dictionaryLock = new ReaderWriterLock();
        }

        // Allows the user to retrieve a cached item from the
        // cache. If it doesn't exist in the cache, it is
        // retrieved with the FetchItem event and entered into
        // the cache.
        public object Fetch( string p_key )
        {
            object tempItem;

            dictionaryLock.AcquireReaderLock( -1 );

            try
            {
                // Get the item from the cache dictionary.
                tempItem = dictionary[ p_key ];
            }
            finally
            {
                dictionaryLock.ReleaseReaderLock();                
            }

            if ( tempItem != null )
            {
                // If the item exists, return it to the user.
                return tempItem;
            }

            // The item is not in the cache.
            // If no user has bound the FetchItem event,
            // then the correct item cannot be retrieved.
            // So null is simply returned.
            if ( FetchItem == null )
                return null;

            // Fetch the correct item from the user by
            // raising the FetchItem event.
            tempItem = FetchItem( this, new FetchItemEventArgs( p_key ) );

            // Nulls are not inserted into the cache.
            if ( tempItem == null )
                return null;

            // The fetched item is not null. Call the 
            // RemoveItems method to remove items that
            // are too old.
            RemoveItems();

            dictionaryLock.AcquireWriterLock( -1 );

            try
            {
                // Add the new item to the cache.
                dictionary.Add( p_key, ref tempItem);
            }
            finally
            {
                dictionaryLock.ReleaseWriterLock();
            }

            return tempItem;
        }

        // Gets the size of the cache.
        public int Count
        {
            get
            {
                dictionaryLock.AcquireReaderLock( -1 );

                try
                {
                    return dictionary.Count;
                }
                finally
                {
                    dictionaryLock.ReleaseReaderLock(); 
                }
            }
        }

        // Clears the entire content of the cache.
        public void Clear()
        {
            dictionaryLock.AcquireWriterLock( -1 );
            dictionary.Clear();
            dictionaryLock.ReleaseWriterLock();
        }

        // Removes oldest items until the number of items in the 
        // cache is below capacity.
        void RemoveItems()
        {
            string tempKey;
            object tempItem;

            dictionaryLock.AcquireWriterLock( -1 );

            try
            {
                if ( capacity == 0 )
                    return;

                while ( capacity - 1 < dictionary.Count )
                {
    
                    tempItem = dictionary.Remove( out tempKey );
    
                    if ( CacheItemExpired != null )
                        CacheItemExpired( this, 
                          new CacheItemExpiredEventArgs( tempKey, 
                                                ref tempItem ) );
                }
            }
            finally
            {
                dictionaryLock.ReleaseWriterLock();
            }
        }

        // Gets or sets the capacity of the cache.
        public int Capacity
        {
            get
            {
                return capacity;
            }
            set
            {
                capacity = value;

                if ( capacity < 0 )
                    capacity = 0;
            }
        }
    }
}

This class is the only one that will be publicly exposed to the user. All the other classes so far have been internal classes as it is used only by the Cache class. Cache is completely thread-safe.

The Cache class holds only the two events discussed earlier and two private variables namely:

  • Dictionary dictionary;
  • int capacity;

The dictionary variable holds an instance of the Dictionary class also discussed earlier. The capacity variable holds the maximum number of items that can be held by the cache before it starts expiring items. This capacity can be set to 0 which will indicate that the user does not want items to be expired ever.

The following methods are discussed:

  • public Cache( int p_initialSize, int p_capacity ) : base() - The only constructor.

    The two if statements force p_initialSize to be of minimum 1 and p_capacity to be of minimum 0. The local variable capacity is set to p_capacity and an instance of a Dictionary is created and stored in dictionary.

  • void RemoveItems();

    The RemoveItems private method will remove items from the dictionary until the number of items is 1 less than the capacity of the cache. It is called before an item is inserted into the dictionary and ensures that the item can be inserted without further capacity checking. With each removal of an item, the CacheItemExpired event is raised to inform the user that an item has expired.

  • public object Fetch( string p_key );

    A user would use this public method to acquire a cached item from the cache. The key for the required object is provided through the p_key parameter.

    The dictionary indexer is called by tempItem = dictionary[ p_key ];. In this method, the item's age is automatically reset if it exists in the dictionary. If the item is found in the cache, it is simply returned.

    If the item is not found, tempItem would be null and the item must be fetched from the user. The FetchItem event is raised, and what is returned as a result is the item to be cached. Since the cache does not store nulls, null is returned if the event yielded a null value and nothing is added to the cache. RemoveItems() is called to ensure that there is space in the dictionary to add a new item. The newly acquired item is added to the cache and returned to be used by the user.

Conclusion

Although there are many more (advanced) features one can add to such a cache implementation, I felt that what I have discussed in this article, is the bare minimum one would need to add efficiency to expensive resource acquisition. Readers of this article can contact me on the forum message board below, should they have any questions or comments regarding this article.

History

  • 2005-10-17 - Used a ReaderWriterLock instead of a normal lock.
  • 2005-10-06 - Article submitted.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Andre Trollip
Software Developer (Senior) Electronics South Africa Forum
South Africa South Africa
B.Sc (Comp. Science)
16 years software development experience.
 
Adventure junkie & keen golfer.
Follow on   Twitter

Comments and Discussions

 
GeneralMy vote of 5 Pinmemberndoro759-Sep-10 22:45 
GeneralVery slow under compact framework Pinmemberronzulu23-Dec-06 18:51 
GeneralRe: Very slow under compact framework PinmemberAndre Trollip9-Sep-10 22:10 
GeneralHelp PinmemberSaiprabhu21-Feb-06 5:54 
GeneralRe: Help Pinmemberdotph26-Mar-07 22:05 
GeneralProblem with ReaderWriterLock implementation Pinmemberglarock9-Nov-05 11:25 
QuestionWhere's the article???? Pinmembermpreddie196419-Oct-05 8:07 
General&quot;generic&quot; word is reserverd for generic-templates in dotNet 2.0 PinmemberKrzysztof Marzencki11-Oct-05 20:01 
GeneralRe: &quot;generic&quot; word is reserverd for generic-templates in dotNet 2.0 PinmemberAndré Trollip11-Oct-05 20:45 
GeneralReaderWriterLock PinmemberWerdna11-Oct-05 16:13 
GeneralRe: ReaderWriterLock [modified] PinmemberAndré Trollip11-Oct-05 20:42 
Questionbut? Pinmembervadivhere10-Oct-05 21:43 
AnswerRe: but? PinmemberAndré Trollip11-Oct-05 1:57 
AnswerRe: but? PinmemberDarran Hayes12-Oct-05 11:56 
GeneralRe: but? PinmemberGaza1312-Oct-05 12:17 
GeneralRe: but? PinmemberAndré Trollip12-Oct-05 20:41 
GeneralRe: but? PinsussAnonymous14-Oct-05 1:21 
GeneralRe: but? PinmemberAndré Trollip12-Oct-05 20:35 
GeneralRe: but? Pinmemberbalazs_hideghety13-Jun-06 21:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140421.2 | Last Updated 17 Oct 2005
Article Copyright 2005 by Andre Trollip
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid