Panda3D
Loading...
Searching...
No Matches
adaptiveLru.cxx
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.cxx
10 * @author drose
11 * @date 2008-09-03
12 */
13
14#include "adaptiveLru.h"
15#include "config_gobj.h"
16#include "clockObject.h"
17#include "indent.h"
18
19using std::cerr;
20using std::ostream;
21
22static const int HIGH_PRIORITY_SCALE = 4;
23static const int LOW_PRIORITY_RANGE = 25;
24
25/**
26 *
27 */
28AdaptiveLru::
29AdaptiveLru(const std::string &name, size_t max_size) :
30 Namable(name)
31{
32 _total_size = 0;
33 _max_size = max_size;
34
35 _current_frame_identifier = 0;
36 _weight = adaptive_lru_weight;
37 _max_updates_per_frame = adaptive_lru_max_updates_per_frame;
38
39 // Initialize our list heads to empty.
40 _static_list._next = &_static_list;
41 _static_list._prev = &_static_list;
42
43 int index;
44 for (index = 0; index < LPP_TotalPriorities; ++index) {
45 _page_array[index]._next = &_page_array[index];
46 _page_array[index]._prev = &_page_array[index];
47 }
48}
49
50/**
51 *
52 */
53AdaptiveLru::
54~AdaptiveLru() {
55#ifndef NDEBUG
56 // We're shutting down. Force-remove everything remaining, but don't
57 // explicitly evict it (that would force vertex buffers to write themselves
58 // to disk unnecessarily).
59
60 while (_static_list._next != &_static_list) {
61 nassertv(_static_list._next != nullptr);
62 AdaptiveLruPage *page = (AdaptiveLruPage *)(AdaptiveLruPageStaticList *)_static_list._next;
63
64 page->_lru = nullptr;
65 ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
66 ((AdaptiveLruPageStaticList *)page)->remove_from_list();
67 }
68#endif
69}
70
71/**
72 * This only updates a number of pages up to the specified maximum_updates.
73 * Assumes the lock is held.
74 */
76do_partial_lru_update(int num_updates) {
77 // Iterate sequentially through the static list of pages. As we process
78 // each page, pop it and push it back on the tail. Stop when we have
79 // processed num_updates, or come back to the starting one.
80
81 AdaptiveLruPageStaticList *start_node = (AdaptiveLruPageStaticList *)_static_list._next;
82 if (start_node == &_static_list) {
83 // List is empty.
84 return;
85 }
86
87 AdaptiveLruPageStaticList *node = start_node;
88 do {
90 if (--num_updates <= 0) {
91 return;
92 }
93
95 node->remove_from_list();
96 node->insert_before(&_static_list);
97 node = next;
98 } while (node != start_node && node != &_static_list);
99}
100
101/**
102 * This updates the page's average utilization. Priority LPP_New is
103 * considered to be average usage of 1.0 (which means the page is used once
104 * per frame on average). Priorities < LPP_New are for pages used more than
105 * once per frame and Priorities > LPP_New are for pages used less than once
106 * per frame.
107 *
108 * Assumes the lock is held.
109 */
112 int target_priority = page->_priority;
113 unsigned int lifetime_frames = _current_frame_identifier - page->_first_frame_identifier;
114 if (lifetime_frames > 0) {
115 if (page->_update_frame_identifier) {
116 unsigned int update_frames;
117
118 update_frames = (_current_frame_identifier - page->_update_frame_identifier);
119 if (update_frames > 0) {
120 if (page->_update_total_usage > 0) {
121 PN_stdfloat update_average_frame_utilization =
122 (PN_stdfloat) (page->_update_total_usage) / (PN_stdfloat)update_frames;
123
124 page->_average_frame_utilization =
125 calculate_exponential_moving_average(update_average_frame_utilization,
126 page->_average_frame_utilization);
127 } else {
128 page->_average_frame_utilization *= 1.0f - _weight;
129 }
130
131 target_priority = page->_priority;
132 if (page->_average_frame_utilization >= 1.0f) {
133 int integer_average_frame_utilization;
134
135 integer_average_frame_utilization =
136 (int) ((page->_average_frame_utilization - 1.0f) *
137 (PN_stdfloat) HIGH_PRIORITY_SCALE);
138 if (integer_average_frame_utilization >= LPP_New) {
139 integer_average_frame_utilization = LPP_New;
140 }
141 integer_average_frame_utilization = LPP_New -
142 integer_average_frame_utilization;
143 target_priority = integer_average_frame_utilization;
144 } else {
145 int integer_average_frame_utilization;
146
147 integer_average_frame_utilization = (int)
148 (page->_average_frame_utilization *
149 (PN_stdfloat) LOW_PRIORITY_RANGE);
150 integer_average_frame_utilization = LOW_PRIORITY_RANGE -
151 integer_average_frame_utilization;
152 target_priority = LPP_New + integer_average_frame_utilization;
153 }
154 }
155 }
156
157 page->_update_frame_identifier = _current_frame_identifier;
158 page->_update_total_usage = 0;
159 }
160
161 if (target_priority != page->_priority) {
162 page->_priority = std::min(std::max(target_priority, 0), LPP_TotalPriorities - 1);
163 ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
164 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
165 }
166}
167
168/**
169 * Adds the page to the LRU for the first time, or marks it recently-accessed
170 * if it has already been added.
171 *
172 * If lru is NULL, it means to remove this page from its LRU.
173 */
176 if (lru != _lru && _lru != nullptr) {
177 // It was previously on a different LRU. Remove it first.
178 _lru->do_remove_page(this);
179 _lru = nullptr;
180 }
181
182 if (lru == _lru) {
183 if (_lru != nullptr) {
184 // It's already on this LRU. Access it.
185 _lru->do_access_page(this);
186 }
187 } else {
188 nassertv(lru != nullptr);
189 // Add it to a new LRU.
190 _lru = lru;
191
192 _priority = AdaptiveLru::LPP_New;
193 _first_frame_identifier = _lru->_current_frame_identifier;
194 _current_frame_identifier = _lru->_current_frame_identifier;
195 _lru->do_add_page(this);
196 }
197}
198
199/**
200 * Returns the total size of the pages that were enqueued since the last call
201 * to begin_epoch().
202 */
204count_active_size() const {
205 size_t counted_size = 0;
206
207 AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next;
208 while (node != &_static_list) {
209 AdaptiveLruPage *page = (AdaptiveLruPage *)node;
210 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
211 counted_size += page->_lru_size;
212 }
213 node = (AdaptiveLruPageStaticList *)node->_next;
214 }
215
216 return counted_size;
217}
218
219/**
220 * Marks the end of the previous epoch and the beginning of the next one.
221 * This will evict any objects that are pending eviction, and also update any
222 * internal bookkeeping.
223 */
225begin_epoch() {
226 LightMutexHolder holder(_lock);
227 do_partial_lru_update(_max_updates_per_frame);
228 if (_total_size > _max_size) {
229 do_evict_to(_max_size, false);
230 }
231
232 _current_frame_identifier = ClockObject::get_global_clock()->get_frame_count();
233}
234
235/**
236 *
237 */
238void AdaptiveLru::
239output(ostream &out) const {
240 LightMutexHolder holder(_lock);
241 out << "AdaptiveLru " << get_name()
242 << ", " << _total_size << " of " << _max_size;
243}
244
245/**
246 *
247 */
248void AdaptiveLru::
249write(ostream &out, int indent_level) const {
250 indent(out, indent_level) << *this << ":\n";
251
252 // We write out the list backwards. Things we write out first are the
253 // freshest in the LRU. Things at the end of the list will be the next to
254 // be evicted.
255
256 LightMutexHolder holder(_lock);
257
258 int index;
259 for (index = 0; index < LPP_TotalPriorities; ++index) {
260 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._prev;
261 if (node != &_page_array[index]) {
262 indent(out, indent_level + 2) << "Priority " << index << ":\n";
263 while (node != &_page_array[index]) {
264 AdaptiveLruPage *page = (AdaptiveLruPage *)node;
265 indent(out, indent_level + 4) << *page;
266
267 if (page->_current_frame_identifier + 1 >= _current_frame_identifier) {
268 out << " (active)";
269 }
270 out << "\n";
271
272 node = (AdaptiveLruPageDynamicList *)node->_prev;
273 }
274 }
275 }
276
277#ifndef NDEBUG
278 ((AdaptiveLru *)this)->do_validate();
279#endif
280}
281
282/**
283 * Adds a new page the the LRU.
284 */
287 nassertv(page != nullptr && page->_lru == this);
288 LightMutexHolder holder(_lock);
289
290 _total_size += page->_lru_size;
291 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
292 ((AdaptiveLruPageStaticList *)page)->insert_before(&_static_list);
293}
294
295/**
296 * Removes a page from the LRU.
297 */
300 nassertv(page != nullptr && page->_lru == this);
301 LightMutexHolder holder(_lock);
302
303 _total_size -= page->_lru_size;
304 ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
305 ((AdaptiveLruPageStaticList *)page)->remove_from_list();
306}
307
308/**
309 * Marks a page accessed.
310 */
313 nassertv(page != nullptr && page->_lru == this);
314 LightMutexHolder holder(_lock);
315
316 if (page->_current_frame_identifier == _current_frame_identifier) {
317 // This is the second or more time this page is accessed this frame.
318 ++(page->_current_frame_usage);
319
320 } else {
321 // This page has not yet been accessed this frame. Update it.
322 page->_current_frame_identifier = _current_frame_identifier;
323 page->_last_frame_usage = page->_current_frame_usage;
324 page->_current_frame_usage = 1;
325 }
326
327 // Move it to the tail of its priority list.
328 ((AdaptiveLruPageDynamicList *)page)->remove_from_list();
329 ((AdaptiveLruPageDynamicList *)page)->insert_before(&_page_array[page->_priority]);
330
331 ++(page->_update_total_usage);
332}
333
334/**
335 * Evicts pages until the LRU is within the indicated size. Assumes the lock
336 * is already held. If hard_evict is false, does not evict "active" pages
337 * that were added within this epoch.
338 */
340do_evict_to(size_t target_size, bool hard_evict) {
341 int attempts;
342
343 attempts = 0;
344 do {
345 // page out lower priority pages first
346 int index;
347 for (index = LPP_TotalPriorities - 1; index >= 0; index--) {
348
349 // Store the current end of the list. If pages re-enqueue themselves
350 // during this traversal, we don't want to visit them twice.
351 AdaptiveLruPageDynamicList *end = (AdaptiveLruPageDynamicList *)_page_array[index]._prev;
352
353 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next;
354
355 while (node != &_page_array[index]) {
357 AdaptiveLruPage *page = (AdaptiveLruPage *)node;
358
359 if (attempts == 0 &&
360 (page->_current_frame_identifier + 1 >= _current_frame_identifier)) {
361 // avoid swapping out pages used in the current and last frame on
362 // the first attempt
363
364 } else {
365 // We must release the lock while we call evict_lru().
366 _lock.unlock();
367 page->evict_lru();
368 _lock.lock();
369
370 if (_total_size <= target_size) {
371 // We've evicted enough to satisfy our target.
372 return;
373 }
374 }
375 if (node == end) {
376 // We've reached the former end of the list. Stop here; everything
377 // after has been re-queued.
378 break;
379 }
380 node = next;
381 }
382 }
383 attempts++;
384 } while (hard_evict && attempts < 2);
385}
386
387/**
388 * Checks that the LRU is internally consistent. Assume the lock is already
389 * held.
390 */
392do_validate() {
393 bool okflag = true;
395
396 // First, walk through the dynamic pages.
397 size_t counted_size = 0;
398 int index;
399 for (index = 0; index < LPP_TotalPriorities; ++index) {
400 AdaptiveLruPageDynamicList *node = (AdaptiveLruPageDynamicList *)_page_array[index]._next;
401 while (node != &_page_array[index]) {
402 AdaptiveLruPage *page = (AdaptiveLruPage *)node;
403 counted_size += page->_lru_size;
404 if (page->_priority != index) {
405 nout << "page " << page << " has priority " << page->_priority
406 << " but is in queue " << index << "\n";
407 okflag = false;
408 }
409
410 bool inserted_ok = pages.insert(page).second;
411 if (!inserted_ok) {
412 nout << "page " << page << " appears more than once in the dynamic index\n";
413 okflag = false;
414 }
415 node = (AdaptiveLruPageDynamicList *)node->_next;
416 }
417 }
418
419 if (counted_size != _total_size) {
420 nout << "count " << counted_size << " bytes in dynamic index, but have " << _total_size << " on record\n";
421 okflag = false;
422 }
423
424 // Now, walk through the static pages.
425 counted_size = 0;
426 AdaptiveLruPageStaticList *node = (AdaptiveLruPageStaticList *)_static_list._next;
427 while (node != &_static_list) {
428 AdaptiveLruPage *page = (AdaptiveLruPage *)node;
429 counted_size += page->_lru_size;
430
431 if (pages.find(page) == pages.end()) {
432 nout << "page " << page << " appears in dynamic index, but not in static index (or multiple times in static index)\n";
433 okflag = false;
434 } else {
435 pages.erase(page);
436 }
437 node = (AdaptiveLruPageStaticList *)node->_next;
438 }
439
440 if (counted_size != _total_size) {
441 nout << "count " << counted_size << " bytes in static index, but have " << _total_size << " on record\n";
442 okflag = false;
443 }
444
445 return okflag;
446}
447
448/**
449 *
450 */
451AdaptiveLruPage::
452AdaptiveLruPage(size_t lru_size) :
453 _lru(nullptr),
454 _lru_size(lru_size),
455 _priority(0),
456 _first_frame_identifier(0),
457 _current_frame_identifier(0),
458 _update_frame_identifier(0),
459 _current_frame_usage(0),
460 _last_frame_usage(0),
461 _update_total_usage(0),
462 _average_frame_utilization(1.0f)
463{
464}
465
466/**
467 *
468 */
469AdaptiveLruPage::
470AdaptiveLruPage(const AdaptiveLruPage &copy) :
471 _lru(nullptr),
472 _lru_size(copy._lru_size),
473 _priority(0),
474 _first_frame_identifier(0),
475 _current_frame_identifier(0),
476 _update_frame_identifier(0),
477 _current_frame_usage(0),
478 _last_frame_usage(0),
479 _update_total_usage(0),
480 _average_frame_utilization(1.0f)
481{
482}
483
484/**
485 *
486 */
487void AdaptiveLruPage::
488operator = (const AdaptiveLruPage &copy) {
490}
491
492/**
493 *
494 */
495AdaptiveLruPage::
496~AdaptiveLruPage() {
497 if (_lru != nullptr) {
498 dequeue_lru();
499 }
500}
501
502/**
503 * Evicts the page from the LRU. Called internally when the LRU determines
504 * that it is full. May also be called externally when necessary to
505 * explicitly evict the page.
506 *
507 * It is legal for this method to either evict the page as requested, do
508 * nothing (in which case the eviction will be requested again at the next
509 * epoch), or requeue itself on the tail of the queue (in which case the
510 * eviction will be requested again much later).
511 */
516
517/**
518 *
519 */
520void AdaptiveLruPage::
521output(ostream &out) const {
522 out << "page " << this << ", " << _lru_size;
523}
524
525/**
526 *
527 */
528void AdaptiveLruPage::
529write(ostream &out, int indent_level) const {
530 indent(out, indent_level) << *this << "\n";
531}
532
533/**
534 * Returns the number of frames since the page was first added to its LRU.
535 * Returns 0 if it does not have an LRU.
536 */
538get_num_frames() const {
539 if (_lru == nullptr) {
540 return 0;
541 }
542 return _lru->_current_frame_identifier - _first_frame_identifier;
543}
544
545/**
546 * Returns the number of frames since the page was last accessed on its LRU.
547 * Returns 0 if it does not have an LRU.
548 */
551 if (_lru == nullptr) {
552 return 0;
553 }
554 return _lru->_current_frame_identifier - _current_frame_identifier;
555}
556
557
558#if 0
559
560/**
561 * Unit test function for Lru.
562 */
563void
564test_adaptive_lru() {
565 int maximum_memory = 3000000;
566 AdaptiveLru *lru = new AdaptiveLru("test", maximum_memory);
567
568 AdaptiveLruPage *lru_page_0;
569 AdaptiveLruPage *lru_page_1;
570 AdaptiveLruPage *lru_page_2;
571 AdaptiveLruPage *lru_page_3;
572 AdaptiveLruPage *lru_page_4;
573 AdaptiveLruPage *lru_page_5;
574
575 lru_page_0 = new AdaptiveLruPage(1000000);
576 cerr << "created lru_page_0: " << lru_page_0 << "\n";
577 lru_page_0->enqueue_lru(lru);
578
579 lru_page_1 = new AdaptiveLruPage(1000000);
580 cerr << "created lru_page_1: " << lru_page_1 << "\n";
581 lru_page_1->enqueue_lru(lru);
582
583 lru_page_2 = new AdaptiveLruPage(1000000);
584 cerr << "created lru_page_2: " << lru_page_2 << "\n";
585 lru_page_2->enqueue_lru(lru);
586
587 lru_page_3 = new AdaptiveLruPage(1000000);
588 cerr << "created lru_page_3: " << lru_page_3 << "\n";
589 lru_page_3->enqueue_lru(lru);
590
591 lru_page_4 = new AdaptiveLruPage(1000000);
592 cerr << "created lru_page_4: " << lru_page_4 << "\n";
593 lru_page_4->enqueue_lru(lru);
594
595 lru_page_5 = new AdaptiveLruPage(1000000);
596 cerr << "created lru_page_5: " << lru_page_5 << "\n";
597 lru_page_5->enqueue_lru(lru);
598
599 int total_frames = 300;
600 int index;
601 for (index = 0; index < total_frames; index++) {
602 cerr << "FRAME " << index << "\n";
603
604 lru->begin_epoch();
605
606 if (index <= 5) {
607 lru_page_0->mark_used_lru(lru);
608 }
609
610 lru_page_1->mark_used_lru(lru);
611 lru_page_1->mark_used_lru(lru);
612
613 if (index & 0x01) {
614 lru_page_2->mark_used_lru(lru);
615 }
616
617 if ((index % 10) == 0) {
618 lru_page_3->mark_used_lru(lru);
619 }
620
621 if (index >= 100) {
622 lru_page_4->mark_used_lru(lru);
623 }
624
625 if (index >= 200) {
626 lru_page_5->mark_used_lru(lru);
627 }
628
629 if (!lru->validate()) {
630 cerr << "Failed validation\n";
631 break;
632 }
633 }
634
635 delete lru;
636 delete lru_page_0;
637 delete lru_page_1;
638 delete lru_page_2;
639 delete lru_page_3;
640 delete lru_page_4;
641 delete lru_page_5;
642}
643
644#endif // test_adaptive_lru
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
One atomic piece that may be managed by a AdaptiveLru chain.
size_t get_lru_size() const
Returns the size of this page as reported to the LRU, presumably in bytes.
void set_lru_size(size_t lru_size)
Specifies the size of this page, presumably in bytes, although any unit is possible.
virtual void evict_lru()
Evicts the page from the LRU.
void mark_used_lru() const
To be called when the page is used; this will move it to the tail of the AdaptiveLru queue it is alre...
unsigned int get_num_inactive_frames() const
Returns the number of frames since the page was last accessed on its LRU.
unsigned int get_num_frames() const
Returns the number of frames since the page was first added to its LRU.
void enqueue_lru(AdaptiveLru *lru)
Adds the page to the LRU for the first time, or marks it recently-accessed if it has already been add...
void dequeue_lru()
Removes the page from its AdaptiveLru.
A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have...
Definition adaptiveLru.h:45
bool do_validate()
Checks that the LRU is internally consistent.
void do_add_page(AdaptiveLruPage *page)
Adds a new page the the LRU.
void update_page(AdaptiveLruPage *page)
This updates the page's average utilization.
void begin_epoch()
Marks the end of the previous epoch and the beginning of the next one.
void do_access_page(AdaptiveLruPage *page)
Marks a page accessed.
void do_evict_to(size_t target_size, bool hard_evict)
Evicts pages until the LRU is within the indicated size.
void do_partial_lru_update(int num_updates)
This only updates a number of pages up to the specified maximum_updates.
size_t count_active_size() const
Returns the total size of the pages that were enqueued since the last call to begin_epoch().
bool validate()
Checks that the LRU is internally self-consistent.
Definition adaptiveLru.I:76
void do_remove_page(AdaptiveLruPage *page)
Removes a page from the LRU.
get_frame_count
Returns the number of times tick() has been called since the ClockObject was created,...
Definition clockObject.h:94
static ClockObject * get_global_clock()
Returns a pointer to the global ClockObject.
void unlock()
Alias for release() to match C++11 semantics.
void lock()
Alias for acquire() to match C++11 semantics.
Similar to MutexHolder, but for a light mutex.
A base class for all things which can have a name.
Definition namable.h:26
This is our own Panda specialization on the default STL set.
Definition pset.h:49
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
std::ostream & indent(std::ostream &out, int indent_level)
A handy function for doing text formatting.
Definition indent.cxx:20
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.