- Generated on Sun Feb 2 2025 21:18:15 for Open Model Railroad Network (OpenMRN) by
1.9.8
|
Open Model Railroad Network (OpenMRN)
|
The GlobalLruCounter and a set of LruCounter<> objects cooperate in order to create an approximate LRU order over a set of objects. More...
#include <LruCounter.hxx>
Public Member Functions | |
| GlobalLruCounter (unsigned bits_per_bit=2) | |
| Constructor. | |
| void | tick () |
Private Attributes | |
| unsigned | bitsPerBit_ |
| Setting defining the exponent. | |
| unsigned | tick_ {0} |
| Rolling counter of global ticks. | |
Friends | |
| template<class T > | |
| class | LruCounter |
The GlobalLruCounter and a set of LruCounter<> objects cooperate in order to create an approximate LRU order over a set of objects.
The particular optimization criterion is that the memory storage per object should be very low. (Target is one byte.) Touching an object is constant time, but there is linear time background maintenance operations that need to run regularly. Picking the oldest object is linear time. The oldest concept is an approximation in that the older an object becomes the less time granularity is available to distinguish exact age. This is generally fine in applications.
How to use:
Create one GlobalLruCounter. Create for each tracked object an LruCounter<uint8_t> or LruCounter<uint16_t>.
Periodically call the tick() function once on the GlobalLruCounter, then for each live object the tick(global) function. This is linear cost in the number of tracked objects, so do it rather rarely (e.g. once per second).
When a specific object is used, call the touch() function on it.
When the oldest object needs to be selected, pick the one which has the highest returned value() from its LruCounter<>.
Theory of operation:
The GlobalLruCounter maintains a global tick count. It gets incremented by one in each tick. In the per-object local counter we only increment the counter for a subset of the global ticks. How many global ticks we skip between two local counter increments depends on the age of the object. The older an object becomes the more rarely we increment the object's counter.
Specifically, if the object counter has reached to be k bits long, then we only increment it, when the global counter's bottom k bits are all zero. Example: if the object counter is 35 (6 bits long), then we increment it to 36 when the global counter is divisible by 64 (all 6 bottom bits are zero). In a variant we double the zero-bits requirement, needing that the bottom 12 bits are all zero.
Example calculations, assuming 1 tick per second:
+----------------------------------------------------------------—+ | Exponent 1 bit/bit 2 bits/bit | +---------—+---------------------------------------------------—+
| data type: | |
|---|---|
| uint8_t | max count: ~43k max count: 9.5M |
| (0.5 days) (110 days) | |
| end granularity: 256 end granularity: 64k | |
| (4 min) (0.5 days) |
+---------—+---------------------------------------------------—+ | uint16_t | max count: ~2.8B max count: 161T | | | (100 years) (5M years) | | | end granularity: 64k end granularity: 4B | | | (0.5 days) (136 years) | +---------—+---------------------------------------------------—+
Definition at line 98 of file LruCounter.hxx.
|
inline |
Constructor.
| bits_per_bit | How aggressive the exponential downsampling should be. Meaningful values are 1 and 2. |
Definition at line 104 of file LruCounter.hxx.
|
inline |
Definition at line 108 of file LruCounter.hxx.
|
friend |
Definition at line 114 of file LruCounter.hxx.
|
private |
Setting defining the exponent.
Definition at line 116 of file LruCounter.hxx.
|
private |
Rolling counter of global ticks.
This is used by the local counters to synchronize their increments.
Definition at line 119 of file LruCounter.hxx.
1.9.8