SHOGUN  v3.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
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         set_generic<T>();
00058     }
00059 
00070     CCache(int64_t cache_size, int64_t obj_size, int64_t num_entries)
00071     : CSGObject()
00072     {
00073         if (cache_size==0 || obj_size==0 || num_entries==0)
00074         {
00075             SG_INFO("doing without cache.\n")
00076             cache_block=NULL;
00077             lookup_table=NULL;
00078             cache_table=NULL;
00079             cache_is_full=false;
00080             nr_cache_lines=0;
00081             entry_size=0;
00082             return;
00083         }
00084 
00085         entry_size=obj_size;
00086         nr_cache_lines=CMath::min((int64_t) (cache_size*1024*1024/obj_size/sizeof(T)), num_entries+1);
00087 
00088         SG_INFO("creating %d cache lines (total size: %ld byte)\n", nr_cache_lines, nr_cache_lines*obj_size*sizeof(T))
00089         cache_block=SG_MALLOC(T, obj_size*nr_cache_lines);
00090         lookup_table=SG_MALLOC(TEntry, num_entries);
00091         cache_table=SG_MALLOC(TEntry*, nr_cache_lines);
00092 
00093         ASSERT(cache_block)
00094         ASSERT(lookup_table)
00095         ASSERT(cache_table)
00096 
00097         int64_t i;
00098         for (i=0; i<nr_cache_lines; i++)
00099             cache_table[i]=NULL;
00100 
00101         for (i=0; i<num_entries; i++)
00102         {
00103             lookup_table[i].usage_count=-1;
00104             lookup_table[i].locked=false;
00105             lookup_table[i].obj=NULL;
00106         }
00107         cache_is_full=false;
00108 
00109         //reserve the very last cache line
00110         //as scratch buffer
00111         nr_cache_lines--;
00112 
00113         set_generic<T>();
00114     }
00115 
00116     virtual ~CCache()
00117     {
00118         SG_FREE(cache_block);
00119         SG_FREE(lookup_table);
00120         SG_FREE(cache_table);
00121     }
00122 
00128     inline bool is_cached(int64_t number)
00129     {
00130         return (lookup_table && lookup_table[number].obj);
00131     }
00132 
00138     inline T* lock_entry(int64_t number)
00139     {
00140         if (lookup_table)
00141         {
00142             lookup_table[number].usage_count++;
00143             lookup_table[number].locked=true;
00144             return lookup_table[number].obj;
00145         }
00146         else
00147             return NULL;
00148     }
00149 
00154     inline void unlock_entry(int64_t number)
00155     {
00156         if (lookup_table)
00157             lookup_table[number].locked=false;
00158     }
00159 
00167     T* set_entry(int64_t number)
00168     {
00169         if (lookup_table)
00170         {
00171             // first look for the element with smallest usage count
00172             int64_t min_idx=0;
00173             int64_t min=-1;
00174             bool found_free_line=false;
00175 
00176             int64_t start=0;
00177             for (start=0; start<nr_cache_lines; start++)
00178             {
00179                 if (!cache_table[start])
00180                 {
00181                     min_idx=start;
00182                     min=-1;
00183                     found_free_line=true;
00184                     break;
00185                 }
00186                 else
00187                 {
00188                     if (!cache_table[start]->locked)
00189                     {
00190                         min=cache_table[start]->usage_count;
00191                         min_idx=start;
00192                         found_free_line=true;
00193                         break;
00194                     }
00195                 }
00196             }
00197 
00198             for (int64_t i=start; i<nr_cache_lines; i++)
00199             {
00200                 if (!cache_table[i])
00201                 {
00202                     min_idx=i;
00203                     min=-1;
00204                     found_free_line=true;
00205                     break;
00206                 }
00207                 else
00208                 {
00209                     int64_t v=cache_table[i]->usage_count;
00210 
00211                     if (v<min && !cache_table[i]->locked)
00212                     {
00213                         min=v;
00214                         min_idx=i;
00215                         found_free_line=true;
00216                     }
00217                 }
00218             }
00219 
00220             if (cache_table[nr_cache_lines-1]) //since this is an indicator for a full cache
00221                 cache_is_full=true;
00222 
00223             if (found_free_line)
00224             {
00225                 // and overwrite it.
00226                 if ( (lookup_table[number].usage_count-min) < 5 && cache_is_full && ! (cache_table[nr_cache_lines] && cache_table[nr_cache_lines]->locked))
00227                     min_idx=nr_cache_lines; //scratch entry
00228 
00229                 if (cache_table[min_idx])
00230                     cache_table[min_idx]->obj=NULL;
00231 
00232                 cache_table[min_idx]=&lookup_table[number];
00233                 lookup_table[number].obj=&cache_block[entry_size*min_idx];
00234 
00235                 //lock cache entry;
00236                 lookup_table[number].usage_count=0;
00237                 lookup_table[number].locked=true;
00238                 return lookup_table[number].obj;
00239             }
00240             else
00241                 return NULL;
00242         }
00243         else
00244             return NULL;
00245     }
00246 
00248     virtual const char* get_name() const { return "Cache"; }
00249 
00250     protected:
00252     bool cache_is_full;
00254     int64_t entry_size;
00256     int64_t nr_cache_lines;
00258     TEntry* lookup_table;
00260     TEntry** cache_table;
00262     T* cache_block;
00263 };
00264 }
00265 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation