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