Panda3D
adaptiveLru.h
1 // Filename: adaptiveLru.h
2 // Created by: drose (03Sep08)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #ifndef ADAPTIVELRU_H
16 #define ADAPTIVELRU_H
17 
18 #include "pandabase.h"
19 #include "linkedListNode.h"
20 #include "namable.h"
21 #include "lightMutex.h"
22 #include "lightMutexHolder.h"
23 
24 class AdaptiveLruPage;
25 
26 // See the comment in the head of AdaptiveLruPage, below, for an
27 // explanation of these two silly little classes.
28 class EXPCL_PANDA_GOBJ AdaptiveLruPageDynamicList : public LinkedListNode {
29 public:
30  friend class AdaptiveLru;
31 };
32 
33 class EXPCL_PANDA_GOBJ AdaptiveLruPageStaticList : public LinkedListNode {
34 public:
35  friend class AdaptiveLru;
36 };
37 
38 ////////////////////////////////////////////////////////////////////
39 // Class : AdaptiveLru
40 // Description : A basic LRU-type algorithm, except that it is
41 // adaptive and attempts to avoid evicting pages that
42 // have been used more frequently (even if less
43 // recently) than other pages.
44 //
45 // The interface is designed to be identical to that for
46 // SimpleLru, so that it may be used as a drop-in
47 // replacement.
48 ////////////////////////////////////////////////////////////////////
49 class EXPCL_PANDA_GOBJ AdaptiveLru : public Namable {
50 PUBLISHED:
51  AdaptiveLru(const string &name, size_t max_size);
52  ~AdaptiveLru();
53 
54  INLINE size_t get_total_size() const;
55  INLINE size_t get_max_size() const;
56  INLINE void set_max_size(size_t max_size);
57  size_t count_active_size() const;
58 
59  INLINE void consider_evict();
60  INLINE void evict_to(size_t target_size);
61  void begin_epoch();
62 
63  INLINE bool validate();
64 
65  void output(ostream &out) const;
66  void write(ostream &out, int indent_level) const;
67 
68  // The following methods are specific to AdaptiveLru, and do not
69  // exist in the SimpleLru implementation. In most cases, the
70  // defaults will be sufficient, so you do not need to mess with
71  // them.
72  INLINE void set_weight(PN_stdfloat weight);
73  INLINE PN_stdfloat get_weight() const;
74 
75  INLINE void set_max_updates_per_frame(int max_updates_per_frame);
76  INLINE int get_max_updates_per_frame() const;
77 
78 private:
79  public: // temp hack
80  enum LruPagePriority {
81  LPP_Highest = 0,
82  LPP_High = 10,
83  LPP_New = 20,
84  LPP_Normal = 25,
85  LPP_Intermediate = 30,
86  LPP_Low = 40,
87  LPP_TotalPriorities = 50,
88  };
89 
90  INLINE PN_stdfloat calculate_exponential_moving_average(PN_stdfloat value, PN_stdfloat average) const;
91 
92  void do_partial_lru_update(int num_updates);
93  void update_page(AdaptiveLruPage *page);
94 
95  void do_add_page(AdaptiveLruPage *page);
96  void do_remove_page(AdaptiveLruPage *page);
97  void do_access_page(AdaptiveLruPage *page);
98 
99  void do_evict_to(size_t target_size, bool hard_evict);
100  bool do_validate();
101 
102  LightMutex _lock;
103 
104  size_t _total_size;
105  size_t _max_size;
106 
107  unsigned int _current_frame_identifier;
108  double _weight;
109  int _max_updates_per_frame;
110 
111  // This array of linked lists keeps all of the active pages, grouped
112  // by priority. We reshuffle pages among these lists as they are
113  // accessed and as they change priority in update_page().
114  AdaptiveLruPageDynamicList _page_array[LPP_TotalPriorities];
115 
116  // This linked list keeps all of the active pages, in arbitrary
117  // order. This list exists solely to allow us to incrementally
118  // update pages without having to iterate through the complex lists
119  // above and worry about losing our place. New pages are added to
120  // the tail. We also move pages from the head to the tail of this
121  // list in do_partial_lru_update() as we process each page with
122  // update_page(). Pages do not move within this list other that
123  // that.
124  AdaptiveLruPageStaticList _static_list;
125 
126  friend class AdaptiveLruPage;
127 };
128 
129 ////////////////////////////////////////////////////////////////////
130 // Class : AdaptiveLruPage
131 // Description : One atomic piece that may be managed by a AdaptiveLru
132 // chain. To use this class, inherit from it and
133 // override evict_lru().
134 //
135 // This class multiply inherits from two classes which
136 // in turn both inherit from LinkedListNode. This is
137 // just a sneaky C++ trick to allow this class to
138 // inherit from LinkedListNode twice, so that pages can
139 // be stored on two different linked lists
140 // simultaneously. The AdaptiveLru class depends on
141 // this; it maintains its pages in two different lists,
142 // one grouped by priority, and one in order by next
143 // partial update needs.
144 ////////////////////////////////////////////////////////////////////
146 PUBLISHED:
147  AdaptiveLruPage(size_t lru_size);
148  AdaptiveLruPage(const AdaptiveLruPage &copy);
149  void operator = (const AdaptiveLruPage &copy);
150 
151  virtual ~AdaptiveLruPage();
152 
153  INLINE AdaptiveLru *get_lru() const;
154 
155  void enqueue_lru(AdaptiveLru *lru);
156  INLINE void dequeue_lru();
157 
158  INLINE void mark_used_lru() const;
159  INLINE void mark_used_lru(AdaptiveLru *lru);
160 
161  INLINE size_t get_lru_size() const;
162  INLINE void set_lru_size(size_t lru_size);
163 
164  virtual void evict_lru();
165 
166  virtual void output(ostream &out) const;
167  virtual void write(ostream &out, int indent_level) const;
168 
169  // Not defined in SimpleLruPage.
170  unsigned int get_num_frames() const;
171  unsigned int get_num_inactive_frames() const;
172 
173 private:
174  AdaptiveLru *_lru;
175 
176  size_t _lru_size;
177  int _priority;
178 
179  unsigned int _first_frame_identifier; // Frame first added.
180  unsigned int _current_frame_identifier; // Frame last accessed.
181  unsigned int _update_frame_identifier; // Frame last updated.
182 
183  int _current_frame_usage;
184  int _last_frame_usage;
185  int _total_usage;
186  int _update_total_usage;
187 
188  PN_stdfloat _average_frame_utilization;
189 
190  friend class AdaptiveLru;
191 };
192 
193 inline ostream &operator << (ostream &out, const AdaptiveLru &lru) {
194  lru.output(out);
195  return out;
196 }
197 
198 inline ostream &operator << (ostream &out, const AdaptiveLruPage &page) {
199  page.output(out);
200  return out;
201 }
202 
203 #if 0
204 BEGIN_PUBLISH
205 void test_adaptive_lru();
206 END_PUBLISH
207 #endif
208 
209 #include "adaptiveLru.I"
210 
211 #endif
void output(ostream &out) const
Outputs the Namable.
Definition: namable.I:97
This just stores the pointers to implement a doubly-linked list of some kind of object.
A base class for all things which can have a name.
Definition: namable.h:29
One atomic piece that may be managed by a AdaptiveLru chain.
Definition: adaptiveLru.h:145
A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have...
Definition: adaptiveLru.h:49
This is a standard, non-reentrant mutex, similar to the Mutex class.
Definition: lightMutex.h:45