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

i working microcontroller has external eeprom containing tables of information.

there large amount of information, there chance request same information cycle cycle if 'stable' - i.e. if @ constant temperature example.

reads eeprom take around 1ms, , around 30 per cycle. our cycle 100ms there significant savings had.

i therefore looking @ implementing ram cache. hit should faster 1ms since microcontroller core running @ 8mhz.

the lookup involves 16-bit address returning 16-bit data. microcontroller 32-bit.

any input on caching appreciated, if totally missing mark , should using else, linked list, or pre-existing library.

here think trying achieve:

-a cache made of array of structs. struct contain address, data , sort of counter indicating how piece of data has been accessed (readcount).

-the array sorted address normally. have efficient lookup() function lookup address , data (suggestions?)

-if got cache miss, sort array readcount determine least used cached value , throw away. fill position new value have looked eeprom. reorder array address. sorting use efficient sort (shell sort? - not sure how handle arrays)

-i somehow decrement of readcount variables tend 0 if not used. should preserve used variables.

here thoughts far (pseudocode, apologies coding style):

#define cache_size 50  //one piece of data in cache struct cacheitem     {     uint16_t address;     uint16_t data;     uint8_t readcount;     };  //array of cached addresses  struct cacheitem cache[cache_size];   //function data cache uint16_t getdatafromcache(uint16_t address)     {     uint8_t cacheresult;     struct cacheitem * cachehit; //pointer successful cache hit        //returns cache_hit if in cache, else returns cache_miss         cacheresult = lookupcache(address, cachehit);      if(cacheresult == cache_miss)         {         //think necessary weed out least accessed address         sortcachebyreadcount();//shell sort?          removelastcacheentry(); //delete last item hasn't been accessed while          data = getdatafromeeprom(address); //expensive eeprom read          //add on bottom of cache         appendtocache(address, data, 1); //1 = setting readcount 1 new addition          //think necessary make lookup function faster         sortcachebyaddress(); //shell sort?              }     else         {         data = cachehit->data; //we had hit, pull data         cachehit->readcount++; //up importance         }     return data;     }   //main function main(void)     {     testdata = getdatafromcache(1234);     } 

am going down wrong track here? input appreciated.

repeated sorting sounds expensive me. implement cache hash table on address. keep things simple, start not counting hits rather evicting old entries on seeing hash collision:

const int cache_size=32; // power of 2  struct cacheentry {      int16_t address;     int16_t value };  cacheentry cache[cache_size];  // adjust shifts 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 proves not effective enough, start fiddling around hash function.