Panda3D
|
00001 // Filename: adaptiveLru.h 00002 // Created by: drose (03Sep08) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #ifndef ADAPTIVELRU_H 00016 #define ADAPTIVELRU_H 00017 00018 #include "pandabase.h" 00019 #include "linkedListNode.h" 00020 #include "namable.h" 00021 #include "lightMutex.h" 00022 #include "lightMutexHolder.h" 00023 00024 class AdaptiveLruPage; 00025 00026 // See the comment in the head of AdaptiveLruPage, below, for an 00027 // explanation of these two silly little classes. 00028 class EXPCL_PANDA_GOBJ AdaptiveLruPageDynamicList : public LinkedListNode { 00029 public: 00030 friend class AdaptiveLru; 00031 }; 00032 00033 class EXPCL_PANDA_GOBJ AdaptiveLruPageStaticList : public LinkedListNode { 00034 public: 00035 friend class AdaptiveLru; 00036 }; 00037 00038 //////////////////////////////////////////////////////////////////// 00039 // Class : AdaptiveLru 00040 // Description : A basic LRU-type algorithm, except that it is 00041 // adaptive and attempts to avoid evicting pages that 00042 // have been used more frequently (even if less 00043 // recently) than other pages. 00044 // 00045 // The interface is designed to be identical to that for 00046 // SimpleLru, so that it may be used as a drop-in 00047 // replacement. 00048 //////////////////////////////////////////////////////////////////// 00049 class EXPCL_PANDA_GOBJ AdaptiveLru : public Namable { 00050 PUBLISHED: 00051 AdaptiveLru(const string &name, size_t max_size); 00052 ~AdaptiveLru(); 00053 00054 INLINE size_t get_total_size() const; 00055 INLINE size_t get_max_size() const; 00056 INLINE void set_max_size(size_t max_size); 00057 size_t count_active_size() const; 00058 00059 INLINE void consider_evict(); 00060 INLINE void evict_to(size_t target_size); 00061 void begin_epoch(); 00062 00063 INLINE bool validate(); 00064 00065 void output(ostream &out) const; 00066 void write(ostream &out, int indent_level) const; 00067 00068 // The following methods are specific to AdaptiveLru, and do not 00069 // exist in the SimpleLru implementation. In most cases, the 00070 // defaults will be sufficient, so you do not need to mess with 00071 // them. 00072 INLINE void set_weight(PN_stdfloat weight); 00073 INLINE PN_stdfloat get_weight() const; 00074 00075 INLINE void set_max_updates_per_frame(int max_updates_per_frame); 00076 INLINE int get_max_updates_per_frame() const; 00077 00078 private: 00079 public: // temp hack 00080 enum LruPagePriority { 00081 LPP_Highest = 0, 00082 LPP_High = 10, 00083 LPP_New = 20, 00084 LPP_Normal = 25, 00085 LPP_Intermediate = 30, 00086 LPP_Low = 40, 00087 LPP_TotalPriorities = 50, 00088 }; 00089 00090 INLINE PN_stdfloat calculate_exponential_moving_average(PN_stdfloat value, PN_stdfloat average) const; 00091 00092 void do_partial_lru_update(int num_updates); 00093 void update_page(AdaptiveLruPage *page); 00094 00095 void do_add_page(AdaptiveLruPage *page); 00096 void do_remove_page(AdaptiveLruPage *page); 00097 void do_access_page(AdaptiveLruPage *page); 00098 00099 void do_evict_to(size_t target_size, bool hard_evict); 00100 bool do_validate(); 00101 00102 LightMutex _lock; 00103 00104 size_t _total_size; 00105 size_t _max_size; 00106 00107 unsigned int _current_frame_identifier; 00108 double _weight; 00109 int _max_updates_per_frame; 00110 00111 // This array of linked lists keeps all of the active pages, grouped 00112 // by priority. We reshuffle pages among these lists as they are 00113 // accessed and as they change priority in update_page(). 00114 AdaptiveLruPageDynamicList _page_array[LPP_TotalPriorities]; 00115 00116 // This linked list keeps all of the active pages, in arbitrary 00117 // order. This list exists solely to allow us to incrementally 00118 // update pages without having to iterate through the complex lists 00119 // above and worry about losing our place. New pages are added to 00120 // the tail. We also move pages from the head to the tail of this 00121 // list in do_partial_lru_update() as we process each page with 00122 // update_page(). Pages do not move within this list other that 00123 // that. 00124 AdaptiveLruPageStaticList _static_list; 00125 00126 friend class AdaptiveLruPage; 00127 }; 00128 00129 //////////////////////////////////////////////////////////////////// 00130 // Class : AdaptiveLruPage 00131 // Description : One atomic piece that may be managed by a AdaptiveLru 00132 // chain. To use this class, inherit from it and 00133 // override evict_lru(). 00134 // 00135 // This class multiply inherits from two classes which 00136 // in turn both inherit from LinkedListNode. This is 00137 // just a sneaky C++ trick to allow this class to 00138 // inherit from LinkedListNode twice, so that pages can 00139 // be stored on two different linked lists 00140 // simultaneously. The AdaptiveLru class depends on 00141 // this; it maintains its pages in two different lists, 00142 // one grouped by priority, and one in order by next 00143 // partial update needs. 00144 //////////////////////////////////////////////////////////////////// 00145 class EXPCL_PANDA_GOBJ AdaptiveLruPage : public AdaptiveLruPageDynamicList, public AdaptiveLruPageStaticList { 00146 PUBLISHED: 00147 AdaptiveLruPage(size_t lru_size); 00148 AdaptiveLruPage(const AdaptiveLruPage ©); 00149 void operator = (const AdaptiveLruPage ©); 00150 00151 virtual ~AdaptiveLruPage(); 00152 00153 INLINE AdaptiveLru *get_lru() const; 00154 00155 void enqueue_lru(AdaptiveLru *lru); 00156 INLINE void dequeue_lru(); 00157 00158 INLINE void mark_used_lru() const; 00159 INLINE void mark_used_lru(AdaptiveLru *lru); 00160 00161 INLINE size_t get_lru_size() const; 00162 INLINE void set_lru_size(size_t lru_size); 00163 00164 virtual void evict_lru(); 00165 00166 virtual void output(ostream &out) const; 00167 virtual void write(ostream &out, int indent_level) const; 00168 00169 // Not defined in SimpleLruPage. 00170 unsigned int get_num_frames() const; 00171 unsigned int get_num_inactive_frames() const; 00172 00173 private: 00174 AdaptiveLru *_lru; 00175 00176 size_t _lru_size; 00177 int _priority; 00178 00179 unsigned int _first_frame_identifier; // Frame first added. 00180 unsigned int _current_frame_identifier; // Frame last accessed. 00181 unsigned int _update_frame_identifier; // Frame last updated. 00182 00183 int _current_frame_usage; 00184 int _last_frame_usage; 00185 int _total_usage; 00186 int _update_total_usage; 00187 00188 PN_stdfloat _average_frame_utilization; 00189 00190 friend class AdaptiveLru; 00191 }; 00192 00193 inline ostream &operator << (ostream &out, const AdaptiveLru &lru) { 00194 lru.output(out); 00195 return out; 00196 } 00197 00198 inline ostream &operator << (ostream &out, const AdaptiveLruPage &page) { 00199 page.output(out); 00200 return out; 00201 } 00202 00203 #if 0 00204 BEGIN_PUBLISH 00205 void test_adaptive_lru(); 00206 END_PUBLISH 00207 #endif 00208 00209 #include "adaptiveLru.I" 00210 00211 #endif