Panda3D
Public Types | Public Member Functions | Public Attributes | Friends

AdaptiveLru Class Reference

A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have been used more frequently (even if less recently) than other pages. More...

#include "adaptiveLru.h"

Inheritance diagram for AdaptiveLru:
Namable MemoryBase

List of all members.

Public Types

enum  LruPagePriority {
  LPP_Highest = 0, LPP_High = 10, LPP_New = 20, LPP_Normal = 25,
  LPP_Intermediate = 30, LPP_Low = 40, LPP_TotalPriorities = 50
}

Public Member Functions

 AdaptiveLru (const string &name, size_t max_size)
void begin_epoch ()
 Marks the end of the previous epoch and the beginning of the next one.
PN_stdfloat calculate_exponential_moving_average (PN_stdfloat value, PN_stdfloat average) const
void consider_evict ()
 Evicts a sequence of objects if the queue is full.
size_t count_active_size () const
 Returns the total size of the pages that were enqueued since the last call to begin_epoch().
void do_access_page (AdaptiveLruPage *page)
 Marks a page accessed.
void do_add_page (AdaptiveLruPage *page)
 Adds a new page the the LRU.
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.
void do_remove_page (AdaptiveLruPage *page)
 Removes a page from the LRU.
bool do_validate ()
 Checks that the LRU is internally consistent.
void evict_to (size_t target_size)
 Evicts a sequence of objects until the queue fits within the indicated target size, regardless of its normal max size.
size_t get_max_size () const
 Returns the max size of all objects that are allowed to be active on the LRU.
int get_max_updates_per_frame () const
 Returns the maximum number of pages the AdaptiveLru will update each frame.
size_t get_total_size () const
 Returns the total size of all objects currently active on the LRU.
PN_stdfloat get_weight () const
 Returns the weight value used to compute the exponential moving average.
void output (ostream &out) const
 Outputs the Namable.
void set_max_size (size_t max_size)
 Changes the max size of all objects that are allowed to be active on the LRU.
void set_max_updates_per_frame (int max_updates_per_frame)
 Specifies the maximum number of pages the AdaptiveLru will update each frame.
void set_weight (PN_stdfloat weight)
 Specifies the weight value used to compute the exponential moving average.
void update_page (AdaptiveLruPage *page)
 This updates the page's average utilization.
bool validate ()
 Checks that the LRU is internally self-consistent.
void write (ostream &out, int indent_level) const

Public Attributes

unsigned int _current_frame_identifier
LightMutex _lock
size_t _max_size
int _max_updates_per_frame
AdaptiveLruPageDynamicList _page_array [LPP_TotalPriorities]
AdaptiveLruPageStaticList _static_list
size_t _total_size
double _weight

Friends

class AdaptiveLruPage

Detailed Description

A basic LRU-type algorithm, except that it is adaptive and attempts to avoid evicting pages that have been used more frequently (even if less recently) than other pages.

The interface is designed to be identical to that for SimpleLru, so that it may be used as a drop-in replacement.

Definition at line 49 of file adaptiveLru.h.


Member Function Documentation

void AdaptiveLru::begin_epoch ( )

Marks the end of the previous epoch and the beginning of the next one.

This will evict any objects that are pending eviction, and also update any internal bookkeeping.

Definition at line 237 of file adaptiveLru.cxx.

References do_evict_to(), do_partial_lru_update(), ClockObject::get_frame_count(), and ClockObject::get_global_clock().

void AdaptiveLru::consider_evict ( ) [inline]

Evicts a sequence of objects if the queue is full.

Definition at line 63 of file adaptiveLru.I.

References do_evict_to().

size_t AdaptiveLru::count_active_size ( ) const

Returns the total size of the pages that were enqueued since the last call to begin_epoch().

Definition at line 213 of file adaptiveLru.cxx.

void AdaptiveLru::do_access_page ( AdaptiveLruPage page)

Marks a page accessed.

Definition at line 334 of file adaptiveLru.cxx.

Referenced by AdaptiveLruPage::enqueue_lru().

void AdaptiveLru::do_add_page ( AdaptiveLruPage page)

Adds a new page the the LRU.

Definition at line 304 of file adaptiveLru.cxx.

Referenced by AdaptiveLruPage::enqueue_lru().

void AdaptiveLru::do_evict_to ( size_t  target_size,
bool  hard_evict 
)

Evicts pages until the LRU is within the indicated size.

Assumes the lock is already held. If hard_evict is false, does not evict "active" pages that were added within this epoch.

Definition at line 366 of file adaptiveLru.cxx.

References LightMutexDirect::acquire(), AdaptiveLruPage::evict_lru(), and LightMutexDirect::release().

Referenced by begin_epoch(), consider_evict(), evict_to(), and set_max_size().

void AdaptiveLru::do_partial_lru_update ( int  num_updates)

This only updates a number of pages up to the specified maximum_updates.

Assumes the lock is held.

Definition at line 80 of file adaptiveLru.cxx.

References LinkedListNode::insert_before(), LinkedListNode::remove_from_list(), and update_page().

Referenced by begin_epoch().

void AdaptiveLru::do_remove_page ( AdaptiveLruPage page)

Removes a page from the LRU.

Definition at line 319 of file adaptiveLru.cxx.

Referenced by AdaptiveLruPage::enqueue_lru().

bool AdaptiveLru::do_validate ( )

Checks that the LRU is internally consistent.

Assume the lock is already held.

Definition at line 421 of file adaptiveLru.cxx.

Referenced by validate().

void AdaptiveLru::evict_to ( size_t  target_size) [inline]

Evicts a sequence of objects until the queue fits within the indicated target size, regardless of its normal max size.

Definition at line 78 of file adaptiveLru.I.

References do_evict_to().

size_t AdaptiveLru::get_max_size ( ) const [inline]

Returns the max size of all objects that are allowed to be active on the LRU.

Definition at line 35 of file adaptiveLru.I.

Referenced by PreparedGraphicsObjects::get_graphics_memory_limit(), and PreparedGraphicsObjects::set_graphics_memory_limit().

int AdaptiveLru::get_max_updates_per_frame ( ) const [inline]

Returns the maximum number of pages the AdaptiveLru will update each frame.

Definition at line 140 of file adaptiveLru.I.

size_t AdaptiveLru::get_total_size ( ) const [inline]

Returns the total size of all objects currently active on the LRU.

Definition at line 23 of file adaptiveLru.I.

PN_stdfloat AdaptiveLru::get_weight ( ) const [inline]

Returns the weight value used to compute the exponential moving average.

Definition at line 116 of file adaptiveLru.I.

void AdaptiveLru::output ( ostream &  out) const

Outputs the Namable.

This function simply writes the name to the output stream; most Namable derivatives will probably redefine this.

Reimplemented from Namable.

Definition at line 253 of file adaptiveLru.cxx.

void AdaptiveLru::set_max_size ( size_t  max_size) [inline]

Changes the max size of all objects that are allowed to be active on the LRU.

If the size is (size_t)-1, there is no limit.

Definition at line 49 of file adaptiveLru.I.

References do_evict_to().

Referenced by PreparedGraphicsObjects::set_graphics_memory_limit().

void AdaptiveLru::set_max_updates_per_frame ( int  max_updates_per_frame) [inline]

Specifies the maximum number of pages the AdaptiveLru will update each frame.

This is a performance optimization: keeping this number low limits the impact of the AdaptiveLru's adaptive algorithm.

Definition at line 129 of file adaptiveLru.I.

void AdaptiveLru::set_weight ( PN_stdfloat  weight) [inline]

Specifies the weight value used to compute the exponential moving average.

Definition at line 105 of file adaptiveLru.I.

void AdaptiveLru::update_page ( AdaptiveLruPage page)

This updates the page's average utilization.

Priority LPP_New is considered to be average usage of 1.0 (which means the page is used once per frame on average). Priorities < LPP_New are for pages used more than once per frame and Priorities > LPP_New are for pages used less than once per frame.

Assumes the lock is held.

Definition at line 119 of file adaptiveLru.cxx.

Referenced by do_partial_lru_update().

bool AdaptiveLru::validate ( ) [inline]

Checks that the LRU is internally self-consistent.

Returns true if successful, false if there is some problem.

Definition at line 93 of file adaptiveLru.I.

References do_validate().


The documentation for this class was generated from the following files:
 All Classes Functions Variables Enumerations