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 <shogun/lib/common.h>
00015 #include <shogun/io/SGIO.h>
00016 #include <shogun/mathematics/Math.h>
00017 #include <shogun/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:
00046     CCache() :CSGObject()
00047     {
00048         SG_UNSTABLE("CCache::CCache()", "\n");
00049 
00050         cache_block=NULL;
00051         lookup_table=NULL;
00052         cache_table=NULL;
00053         cache_is_full=false;
00054         nr_cache_lines=0;
00055         entry_size=0;
00056     }
00057 
00068     CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries)
00069     : CSGObject()
00070     {
00071         if (cache_size==0 || obj_size==0 || num_entries==0)
00072         {
00073             SG_INFO("doing without cache.\n");
00074             cache_block=NULL;
00075             lookup_table=NULL;
00076             cache_table=NULL;
00077             cache_is_full=false;
00078             nr_cache_lines=0;
00079             entry_size=0;
00080             return;
00081         }
00082 
00083         entry_size=obj_size;
00084         nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
00085 
00086         SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T));
00087         cache_block=SG_MALLOC(T, obj_size*nr_cache_lines);
00088         lookup_table=SG_MALLOC(TEntry, num_entries);
00089         cache_table=SG_MALLOC(TEntry*, nr_cache_lines);
00090 
00091         ASSERT(cache_block);
00092         ASSERT(lookup_table);
00093         ASSERT(cache_table);
00094 
00095         int64_t i;
00096         for (i=0; i<nr_cache_lines; i++)
00097             cache_table[i]=NULL;
00098 
00099         for (i=0; i<num_entries; i++)
00100         {
00101             lookup_table[i].usage_count=-1;
00102             lookup_table[i].locked=false;
00103             lookup_table[i].obj=NULL;
00104         }
00105         cache_is_full=false;
00106 
00107         //reserve the very last cache line
00108         //as scratch buffer
00109         nr_cache_lines--;
00110     }
00111 
00112     virtual ~CCache()
00113     {
00114         SG_FREE(cache_block);
00115         SG_FREE(lookup_table);
00116         SG_FREE(cache_table);
00117     }
00118 
00124     inline bool is_cached(int64_t number)
00125     {
00126         return (lookup_table && lookup_table[number].obj);
00127     }
00128 
00134     inline T* lock_entry(int64_t number)
00135     {
00136         if (lookup_table)
00137         {
00138             lookup_table[number].usage_count++;
00139             lookup_table[number].locked=true;
00140             return lookup_table[number].obj;
00141         }
00142         else
00143             return NULL;
00144     }
00145 
00150     inline void unlock_entry(int64_t number)
00151     {
00152         if (lookup_table)
00153             lookup_table[number].locked=false;
00154     }
00155 
00163     T* set_entry(int64_t number)
00164     {
00165         if (lookup_table)
00166         {
00167             // first look for the element with smallest usage count
00168             //int64_t min_idx=((nr_cache_lines-1)*random())/(RAND_MAX+1); //avoid the last elem and the scratch line
00169             int64_t min_idx=0;
00170             int64_t min=-1;
00171             bool found_free_line=false;
00172 
00173             int64_t start=0;
00174             for (start=0; start<nr_cache_lines; start++)
00175             {
00176                 if (!cache_table[start])
00177                 {
00178                     min_idx=start;
00179                     min=-1;
00180                     found_free_line=true;
00181                     break;
00182                 }
00183                 else
00184                 {
00185                     if (!cache_table[start]->locked)
00186                     {
00187                         min=cache_table[start]->usage_count;
00188                         min_idx=start;
00189                         found_free_line=true;
00190                         break;
00191                     }
00192                 }
00193             }
00194 
00195             for (int64_t i=start; i<nr_cache_lines; i++)
00196             {
00197                 if (!cache_table[i])
00198                 {
00199                     min_idx=i;
00200                     min=-1;
00201                     found_free_line=true;
00202                     break;
00203                 }
00204                 else
00205                 {
00206                     int64_t v=cache_table[i]->usage_count;
00207 
00208                     if (v<min && !cache_table[i]->locked)
00209                     {
00210                         min=v;
00211                         min_idx=i;
00212                         found_free_line=true;
00213                     }
00214                 }
00215             }
00216 
00217             if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
00218                 cache_is_full=true;
00219 
00220             if (found_free_line)
00221             {
00222                 // and overwrite it.
00223                 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
00224                     min_idx=nr_cache_lines; //scratch entry
00225 
00226                 if (cache_table[min_idx])
00227                     cache_table[min_idx]->obj=NULL;
00228 
00229                 cache_table[min_idx]=&lookup_table[number];
00230                 lookup_table[number].obj=&cache_block[entry_size*min_idx];
00231 
00232                 //lock cache entry;
00233                 lookup_table[number].usage_count=0;
00234                 lookup_table[number].locked=true;
00235                 return lookup_table[number].obj;
00236             }
00237             else
00238                 return NULL;
00239         }
00240         else
00241             return NULL;
00242     }
00243 
00245     virtual const char* get_name() const { return "Cache"; }
00246 
00247     protected:
00249     bool cache_is_full;
00251     int64_t entry_size;
00253     int64_t nr_cache_lines;
00255     TEntry* lookup_table;
00257     TEntry** cache_table;
00259     T* cache_block;
00260 };
00261 }
00262 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation