Embedded C - How to create a cache for expensive external reads?

Question

I am working with a microcontroller that has an external EEPROM containing tables of information.

There is a large amount of information, however there is a good chance that we will request the same information cycle to cycle if we are fairly 'stable' - i.e. if we are at a constant temperature for example.

Reads from the EEPROM take around 1ms, and we do around 30 per cycle. Our cycle is currently about 100ms so there is significant savings to be had.

I am therefore looking at implementing a RAM cache. A hit should be significantly faster than 1ms since the microcontroller core is running at 8Mhz.

The lookup involves a 16-bit address returning 16-bit data. The microcontroller is 32-bit.

Any input on caching would be greatly appreciated, especially if I am totally missing the mark and should be using something else, like a linked list, or even a pre-existing library.

Here is what I think I am trying to achieve:

-A cache made up of an array of structs. The struct would contain the address, data and some sort of counter indicating how often this piece of data has been accessed (readCount).

-The array would be sorted by address normally. I would have an efficient lookup() function to lookup an address and get the data (suggestions?)

-If I got a cache miss, I would sort the array by readCount to determine the least used cached value and throw it away. I would then fill its position with the new value I have looked up from EEPROM. I would then reorder the array by address. Any sorting would use an efficient sort (shell sort? - not sure how to handle this with arrays)

-I would somehow decrement all of the readCount variables to that they would tend to zero if not used. This should preserve constantly used variables.

Here are my thoughts so far (pseudocode, apologies for my coding style):

#define CACHE_SIZE 50

//one piece of data in the cache
struct cacheItem
    {
    uint16_t address;
    uint16_t data;
    uint8_t readCount;
    };

//array of cached addresses 
struct cacheItem cache[CACHE_SIZE]; 

//function to get data from the cache
uint16_t getDataFromCache(uint16_t address)
    {
    uint8_t cacheResult;
    struct cacheItem * cacheHit; //Pointer to a successful cache hit



    //returns CACHE_HIT if in the cache, else returns CACHE_MISS    
    cacheResult = lookUpCache(address, cacheHit);

    if(cacheResult == CACHE_MISS)
        {
        //Think this is necessary to easily weed out the least accessed address
        sortCacheByReadCount();//shell sort?

        removeLastCacheEntry(); //delete the last item that hasn't been accessed for a while

        data = getDataFromEEPROM(address); //Expensive EEPROM read

        //Add on to the bottom of the cache
        appendToCache(address, data, 1); //1 = setting readCount to 1 for new addition

        //Think this is necessary to make a lookup function faster
        sortCacheByAddress(); //shell sort?     
        }
    else
        {
        data = cacheHit->data; //We had a hit, so pull the data
        cacheHit->readCount++; //Up the importance now
        }
    return data;
    }


//Main function
main(void)
    {
    testData = getDataFromCache(1234);
    }

Am I going down the completely wrong track here? Any input is appreciated.

Answer 1

Repeated sorting sounds expensive to me. I would implement the cache as a hash table on the address. To keep things simple, I would start by not even counting hits but rather evicting old entries immediately on seeing a hash collision:

const int CACHE_SIZE=32; // power of two

struct CacheEntry { 
    int16_t address;
    int16_t value
};

CacheEntry cache[CACHE_SIZE];

// adjust shifts for different CACHE_SIZE
inline int cacheIndex(int adr) { return (((adr>>10)+(adr>>5)+adr)&(CACHE_SIZE-1)); }

int16_t cachedRead( int16_t address )
{
    int idx = cacheIndex( address );
    CacheEntry * pCache = cache+idx;
    if( address != pCache->address ) {
         pCache->value = readEeprom( address );
         pCache->address = address;
    }
    return pCache->value
}

If this proves not effective enough, I would start by fiddling around with the hash function.