Panda3D

adaptiveLru.h

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 &copy);
00149   void operator = (const AdaptiveLruPage &copy);
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
 All Classes Functions Variables Enumerations