Panda3D
panda
src
gobj
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
*/
135
class
EXPCL_PANDA_GOBJ
AdaptiveLruPage
:
public
AdaptiveLruPageDynamicList
,
public
AdaptiveLruPageStaticList
{
136
PUBLISHED:
137
explicit
AdaptiveLruPage
(
size_t
lru_size);
138
AdaptiveLruPage
(
const
AdaptiveLruPage
©);
139
void
operator = (
const
AdaptiveLruPage
©);
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:41
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.
Generated on Sun Dec 27 2020 13:23:00 for Panda3D by
1.8.20