Struct AutoWithThreshold

Source

pub struct AutoWithThreshold<const D: usize>;

Expand description

The AutoWithThreshold policy reclaims closed nodes whenever the utilization falls below a certain threshold which is determined by the constant parameter D.

This is a generalization of the Auto policy; in particular, Auto is equivalent to AutoWithThreshold<2>.
Its constant parameter D defines the utilization threshold to trigger the memory reclaim operation.
Specifically, memory of closed nodes will be reclaimed whenever the ratio of closed nodes to all nodes exceeds one over 2^D. The greater the D, the greater the utilization threshold.
- when D = 0: memory will be reclaimed when utilization is below 0.00% (equivalent to never).
- when D = 1: memory will be reclaimed when utilization is below 50.00%.
- when D = 2: memory will be reclaimed when utilization is below 75.00%.
- when D = 3: memory will be reclaimed when utilization is below 87.50%.
- when D = 4: memory will be reclaimed when utilization is below 93.75%.

Compared to Lazy, auto approach has the following pros & cons:

(+) Node indices (NodeIdx<V>) created for an auto-reclaim tree will can be implicitly invalidated. Recall that, analogous to random access to an array element with its index, node indices allow for constant time access to the corresponding node. A node index can be invalidated if either of the following happens (i) the node is removed from the tree, (ii) other nodes are removed from the tree triggering a memory reclaim operation. With auto policy, both the explicit (i) and implicit (ii) invalidation can occur.
(-) Uses memory efficiently making sure that utilization can never go below a constant threshold.

Since Auto is the default memory policy, we do not need to include it in the tree type signature.

In order to observe the impact of the memory reclaim policy on validity of the node indices, please see the Examples section of MemoryPolicy.