Cache.h

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 1999-2009 Soeren Sonnenburg
00008  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
00009  */
00010 
00011 #ifndef _CACHE_H__
00012 #define _CACHE_H__
00013 
00014 #include "lib/common.h"
00015 #include "lib/io.h"
00016 #include "lib/Mathematics.h"
00017 #include "base/SGObject.h"
00018 
00019 #include <stdlib.h>
00020 
00021 namespace shogun
00022 {
00031 template<class T> class CCache : public CSGObject
00032 {
00034     struct TEntry
00035     {
00037         int64_t usage_count;
00039         bool locked;
00041         T* obj;
00042     };
00043 
00044     public:
00055     CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries)
00056     : CSGObject()
00057     {
00058         if (cache_size==0 || obj_size==0 || num_entries==0)
00059         {
00060             SG_INFO("doing without cache.\n");
00061             cache_block=NULL;
00062             lookup_table=NULL;
00063             cache_table=NULL;
00064             cache_is_full=false;
00065             nr_cache_lines=0;
00066             entry_size=0;
00067             return;
00068         }
00069 
00070         entry_size=obj_size;
00071         nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
00072 
00073         SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T));
00074         cache_block=new T[obj_size*nr_cache_lines];
00075         lookup_table=new TEntry[num_entries];
00076         cache_table=new TEntry*[nr_cache_lines];
00077 
00078         ASSERT(cache_block);
00079         ASSERT(lookup_table);
00080         ASSERT(cache_table);
00081 
00082         int64_t i;
00083         for (i=0; i<nr_cache_lines; i++)
00084             cache_table[i]=NULL;
00085 
00086         for (i=0; i<num_entries; i++)
00087         {
00088             lookup_table[i].usage_count=-1;
00089             lookup_table[i].locked=false;
00090             lookup_table[i].obj=NULL;
00091         }
00092         cache_is_full=false;
00093 
00094         //reserve the very last cache line
00095         //as scratch buffer
00096         nr_cache_lines--;
00097     }
00098 
00099     virtual ~CCache()
00100     {
00101         delete[] cache_block;
00102         delete[] lookup_table;
00103         delete[] cache_table;
00104     }
00105 
00111     inline bool is_cached(int64_t number)
00112     {
00113         return (lookup_table && lookup_table[number].obj);
00114     }
00115 
00121     inline T* lock_entry(int64_t number)
00122     {
00123         if (lookup_table)
00124         {
00125             lookup_table[number].usage_count++;
00126             lookup_table[number].locked=true;
00127             return lookup_table[number].obj;
00128         }
00129         else
00130             return NULL;
00131     }
00132 
00137     inline void unlock_entry(int64_t number)
00138     {
00139         if (lookup_table)
00140             lookup_table[number].locked=false;
00141     }
00142 
00150     T* set_entry(int64_t number)
00151     {
00152         if (lookup_table)
00153         {
00154             // first look for the element with smallest usage count
00155             //int64_t min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line
00156             int64_t min_idx=0;
00157             int64_t min=-1;
00158             bool found_free_line=false;
00159 
00160             int64_t start=0;
00161             for (start=0; start<nr_cache_lines; start++)
00162             {
00163                 if (!cache_table[start])
00164                 {
00165                     min_idx=start;
00166                     min=-1;
00167                     found_free_line=true;
00168                     break;
00169                 }
00170                 else
00171                 {
00172                     if (!cache_table[start]->locked)
00173                     {
00174                         min=cache_table[start]->usage_count;
00175                         min_idx=start;
00176                         found_free_line=true;
00177                         break;
00178                     }
00179                 }
00180             }
00181 
00182             for (int64_t i=start; i<nr_cache_lines; i++)
00183             {
00184                 if (!cache_table[i])
00185                 {
00186                     min_idx=i;
00187                     min=-1;
00188                     found_free_line=true;
00189                     break;
00190                 }
00191                 else
00192                 {
00193                     int64_t v=cache_table[i]->usage_count;
00194 
00195                     if (v<min && !cache_table[i]->locked)
00196                     {
00197                         min=v;
00198                         min_idx=i;
00199                         found_free_line=true;
00200                     }
00201                 }
00202             }
00203 
00204             if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
00205                 cache_is_full=true;
00206 
00207             if (found_free_line)
00208             {
00209                 // and overwrite it.
00210                 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
00211                     min_idx=nr_cache_lines; //scratch entry
00212 
00213                 if (cache_table[min_idx])
00214                     cache_table[min_idx]->obj=NULL;
00215 
00216                 cache_table[min_idx]=&lookup_table[number];
00217                 lookup_table[number].obj=&cache_block[entry_size*min_idx];
00218 
00219                 //lock cache entry;
00220                 lookup_table[number].usage_count=0;
00221                 lookup_table[number].locked=true;
00222                 return lookup_table[number].obj;
00223             }
00224             else
00225                 return NULL;
00226         }
00227         else 
00228             return NULL;
00229     }
00230 
00232     inline virtual const char* get_name() const { return "Cache"; }
00233 
00234     protected:
00236     bool cache_is_full;
00238     int64_t entry_size;
00240     int64_t nr_cache_lines;
00242     TEntry* lookup_table;
00244     TEntry** cache_table;
00246     T* cache_block;
00247 };
00248 }
00249 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation