Panda3D
Loading...
Searching...
No Matches
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
23class AdaptiveLruPage;
24
25// See the comment in the head of AdaptiveLruPage, below, for an explanation
26// of these two silly little classes.
27class EXPCL_PANDA_GOBJ AdaptiveLruPageDynamicList : public LinkedListNode {
28public:
29 friend class AdaptiveLru;
30};
31
32class EXPCL_PANDA_GOBJ AdaptiveLruPageStaticList : public LinkedListNode {
33public:
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 */
45class EXPCL_PANDA_GOBJ AdaptiveLru : public Namable {
46PUBLISHED:
47 explicit AdaptiveLru(const std::string &name, size_t max_size);
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
73private:
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 */
136PUBLISHED:
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
163private:
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
182inline std::ostream &operator << (std::ostream &out, const AdaptiveLru &lru) {
183 lru.output(out);
184 return out;
185}
186
187inline std::ostream &operator << (std::ostream &out, const AdaptiveLruPage &page) {
188 page.output(out);
189 return out;
190}
191
192#if 0
193BEGIN_PUBLISH
194void test_adaptive_lru();
195END_PUBLISH
196#endif
197
198#include "adaptiveLru.I"
199
200#endif
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
One atomic piece that may be managed by a AdaptiveLru chain.
A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have...
Definition adaptiveLru.h:45
This is a standard, non-reentrant mutex, similar to the Mutex class.
Definition lightMutex.h:41
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:26
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.