org.hd.d.pg2k.svrCore
Class MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V>

java.lang.Object
  org.hd.d.pg2k.svrCore.MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V>

All Implemented Interfaces:

MemoryTools.CacheMiniMap<K,V>, MemoryTools.Compactable

Enclosing class:

MemoryTools

public static final class MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V>
extends java.lang.Object
implements MemoryTools.CacheMiniMap<K,V>, MemoryTools.Compactable

Simplified map with fixed capacity bounds that discards excess items in LRU (Least Recently Used) order to meet a hit/miss ratio goal. This adjusts its size to maintain a specific hit/miss ratio in get(), a miss being a get() that returns null, trimming away older items at insert to maintain the ratio.

This will also discard entries LRU if memory is under stress while the map is above its minimum size.

This provides optional fixed lower and upper sizes. Attempts to insert more items than the ceiling capacity will result in old items being removed in LRU order, thus leaving the newest items in the cache.

Each put() or get() makes its key/value pair the most-recently used and thus the last to be removed from the map of current key/value pairs when a series of put()s forces the map to overflow.

Thread-safe.

A lock can be held on instances of this object to make compound operations atomic.

Does not support the full Map interface.

DEFAULT_MAX_MISS_RATE

public static final float DEFAULT_MAX_MISS_RATE

Default maximum miss rate ]0.0,1.0[.

See Also:

Constant Field Values

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR

Default load factor.

See Also:

Constant Field Values

DEFAULT_MIN_SIZE

public static final int DEFAULT_MIN_SIZE

Default minimum size/capacity, also initial capacity; strictly positive.

See Also:

Constant Field Values

lhm

private final java.util.LinkedHashMap<K,V> lhm

Underlying LinkedHashMap on which this is based; never null.

minSize

private final int minSize

The minimum size/capacity; non-negative.

maxCapacity

private final int maxCapacity

The maximum size/capacity; strictly positive and greater than minSize.

missFracPower

private final int missFracPower

The rounded negative log2 of the maximum miss rate usable as an int shift; in the range [1,30].

trimCheckRate

private final int trimCheckRate

Number of non-miss get()s after which we consider trimming the map if meeting the max-miss-rate targets; strictly positive. This is inversely related to our maxMissRate so as to avoid us shrinking the map too quickly and throwing away rarely-accessed but still-useful items at the tail of our distribution.

name

private final java.lang.String name

Name of this container instance for tracking purposes, or null if none.

countGets

private int countGets

Count of get() calls; non-negative and usually no larger than maxCapacity.

countGetMisses

private int countGetMisses

Count of get() calls that returned null, ie misses; non-negative and no larger than countGets.

cacheTrimTryCount

private int cacheTrimTryCount

Count to trigger possible trim of cache size; non-negative.

MemoryTools.SimpleLRUMapAutoSizeForHitRate

private MemoryTools.SimpleLRUMapAutoSizeForHitRate()

Create an instance with all defaults and therefore an effectively-unbounded upper capacity of Integer.MAX_VALUE.

MemoryTools.SimpleLRUMapAutoSizeForHitRate

private MemoryTools.SimpleLRUMapAutoSizeForHitRate(float maxMissRate,
                                                   int minSize,
                                                   int maxCapacity,
                                                   float loadFactor,
                                                   java.lang.String name)

Create an instance with the given parameters.

Parameters:

maxMissRate - the target cache maximum miss rate; in the range 0.0f to 1.0f exclusive (typically << 0.1)

minSize - the minimum (and initial) capacity; non-negative

maxCapacity - the maximum capacity; greater than minCapacity and thus strictly positive)

loadFactor - the load factor of the underlying hash table; in the range 0.0f to 1.0f exclusive (typically ~0.75f)

getCompactableInstanceName

public java.lang.String getCompactableInstanceName()

Get name of this container instance for tracking purposes, or null if none.

Specified by:

getCompactableInstanceName in interface MemoryTools.Compactable

create

public static <K,V> MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V> create()

Create an instance with all defaults and therefore an effectively-unbounded upper capacity of Integer.MAX_VALUE.

create

public static <K,V> MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V> create(int minSize,
                                                                           int maxCapacity,
                                                                           java.lang.String name)

Create an instance with all defaults except for the specified minimum/maximum capacities.

create

public static <K,V> MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V> create(float maxMissRate,
                                                                           int minSize,
                                                                           java.lang.String name)

Create an instance with the given parameters. The standard default is used for the load factor, and the map size is effectively unlimited.

Parameters:

maxMissRate - the target cache maximum miss rate; in the range 0.0f to 1.0f exclusive (typically << 0.1)

minSize - the minimum (and initial) capacity; non-negative

name - for memory-footprint tuning/debugging; may be null

meetingMissRateTarget

private boolean meetingMissRateTarget()

Returns true if we are meeting/bettering the miss-rate target. Will not return true until we have a reasonable number of samples.

We avoid potentially-slow floating-point arithmetic on the call, since it may be made quite often.

get

public V get(K key)

Get an entry from the map, making it the Most Recently Used; null if no such element.

Specified by:

get in interface MemoryTools.CacheMiniMap<K,V>

create

public static <K,V> MemoryTools.SimpleLRUMapAutoSizeForHitRate<K,V> create(float maxMissRate,
                                                                           int minSize,
                                                                           int maxCapacity,
                                                                           float loadFactor,
                                                                           java.lang.String name)

Create an instance with the given parameters.

Parameters:

maxMissRate - the target cache maximum miss rate; in the range 0.0f to 1.0f exclusive (typically << 0.1)

minSize - the minimum (and initial) capacity; non-negative

maxCapacity - the maximum capacity; greater than minCapacity (and thus strictly positive)

loadFactor - the load factor of the underlying hash table; in the range 0.0f to 1.0f exclusive (typically ~0.75f)

name - for memory-footprint tuning/debugging; may be null

trimOldestEntriesIfPossible

private void trimOldestEntriesIfPossible(boolean ignoreMissRateTarget,
                                         boolean all)

Trim oldest entries providing that the miss-rate target and minimum size are met. This caps the size below the maximum if free heap space is below target.

Parameters:

ignoreMissRateTarget - if true, then ignore the miss-rate target when trimming.

trimOldestEntryIfPossible

private void trimOldestEntryIfPossible(boolean ignoreMissRateTarget)

Trim (at most one) oldest entry providing that the miss-rate target and minimum size are met.

Parameters:

ignoreMissRateTarget - if true, then ignore the miss-rate target when trimming.

compact

public void compact()

Compact by discarding some or all LRU items above the minimum size, ignoring the miss-rate target. Excessive use may reduce the effectiveness of this map.

May be automatically called in the background when memory is low/stressed.

Specified by:

compact in interface MemoryTools.Compactable

put

public V put(K key,
             V value)

Put an entry in the map, making it the Most Recently Used, returning the previous value if any.

Specified by:

put in interface MemoryTools.CacheMiniMap<K,V>

remove

public V remove(K key)

Remove an entry from the map and return the removed value, if any, else null.

Specified by:

remove in interface MemoryTools.CacheMiniMap<K,V>

clear

public void clear()

Clear the map and reset the hit/miss counters.

Specified by:

clear in interface MemoryTools.CacheMiniMap<K,V>

size

public int size()

Return the number of entries in the map; non-negative.

Specified by:

size in interface MemoryTools.CacheMiniMap<K,V>

getCopy

public java.util.Map<K,V> getCopy()

Take a copy of the map contents, which does not alter LRU; never null.

toString

public java.lang.String toString()

Provide a human-readable summary of status. Useful for debugging/tuning, for example.

Overrides:

toString in class java.lang.Object