Trait MemoryPolicy

Source

pub trait MemoryPolicy: 'static {
    type MemoryReclaimPolicy<V>: MemoryPolicy<V>
       where V: TreeVariant;
}

Expand description

Trees use a pinned vector (PinnedVec) as its underlying storage. Deletions from the tree are lazy in the sense that the nodes are closed; not removed from the vector. Therefore, deletions leave a gap in the underlying collection. How these nodes will be reclaimed is determined by the MemoryPolicy.

This is important because during memory reclaim, nodes of the collection are reorganized which invalidates the node indices which are obtained prior to this operation. Node indices, or NodeIdx, are analogous to usize indices of a slice and allow for safe direct constant time access to the node it is created for.

There are three available policies:

Auto
- The default policy.
- It automatically reclaims memory whenever the utilization falls below 75%.
- Automatic triggers of memory reclaims might lead to implicit invalidation of node indices due to ReorganizedCollection.
- It is important to note that, even when using Auto policy, tree growth will never trigger memory reclaim. Only node removing mutations such as prune can trigger node reorganization.
AutoWithThreshold
- 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.
Lazy
- It never reclaims memory.
- It never leads to implicit invalidation of node indices. In other words, a node index can only be invalidated if we prune that node from the tree (RemovedNode).

An ideal use pattern can conveniently be achieved by using auto and lazy policies together, using the free memory policy transformation methods. Such a use case is demonstrated in the example below.

§Examples

§Auto Memory Claim

Since Auto is the default memory policy, we do not need to include it in the tree type signature. The following example demonstrates how this policy impacts the validity of node indices.

The follow up example will demonstrate how to switch between the Lazy and Auto policies to make best use of these policies and use both node indices and memory efficiently.

use orx_tree::*;

// # 1 - BUILD UP

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

fn bfs_values(tree: &DynTree<i32>) -> Vec<i32> {
    tree.root().walk::<Bfs>().copied().collect()
}

// # 1. GROW

// equivalently => DynTree::<i32, Auto>::new(1)
let mut tree = DynTree::new(1);

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
let [id8] = tree.node_mut(&id4).push_children([8]);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

assert_eq!(bfs_values(&tree), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);

// all id's above are valid => the tree only grew
assert!(tree.is_node_idx_valid(&id2)); // is_valid_for => true
assert!(tree.get_node(&id4).is_some()); // get_node => Some(Node)
assert!(tree.try_node(&id6).is_ok()); // try_get_node => Ok(Node)
let _node7 = tree.node(&id7); // no panic

// # 2 - SHRINK BUT WITHOUT A MEMORY RECLAIM

// let's close two nodes (nodes 4 & 8)
// this is not enough to trigger a memory reclaim
tree.node_mut(&id4).prune();
assert_eq!(bfs_values(&tree), [1, 2, 3, 5, 6, 7, 9, 10, 11]);

assert!(tree.is_node_idx_valid(&id2)); // is_valid_for => true
assert!(tree.try_node(&id6).is_ok()); // try_get_node => Ok(Node)
let node7 = tree.node(&id7); // no panic

// what about id4 & id8 => invalidated due to RemovedNode
assert!(!tree.is_node_idx_valid(&id4));
assert!(tree.get_node(&id4).is_none());
assert_eq!(tree.try_node(&id4), Err(NodeIdxError::RemovedNode));
// let node4 = id4.node(&tree); // panics!!!

// # 3 - SHRINK TRIGGERING MEMORY RECLAIM

// let's close more nodes (7, 10, 11) to trigger the memory reclaim
tree.node_mut(&id7).prune();
assert_eq!(bfs_values(&tree), [1, 2, 3, 5, 6, 9]);

// even node 2 is still on the tree;
// its idx is invalidated => ReorganizedCollection
assert!(!tree.is_node_idx_valid(&id2));
assert_eq!(
    tree.try_node(&id2),
    Err(NodeIdxError::ReorganizedCollection)
);

// all indices obtained prior to reorganization are now invalid
// we can restore the valid indices again

let id2 = tree.root().get_child(0).unwrap().idx();
assert!(tree.is_node_idx_valid(&id2));
assert!(tree.try_node(&id2).is_ok());
let n2 = tree.node(&id2);
assert_eq!(n2.data(), &2);

§Lazy Memory Claim: Preventing Invalid Indices

Now assume that we want to make sure that the indices we cached during growth are valid during the stages #2 and #3. We can achieve this by switching to Lazy policy and only after stage #3, when we are done using the indices, we can switch back to Auto policy. Note that these transformations of the memory policies are free.

use orx_tree::*;

// # 1 - BUILD UP

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

fn bfs_values<M: MemoryPolicy>(tree: &DynTree<i32, M>) -> Vec<i32> {
    tree.root().walk::<Bfs>().copied().collect()
}

// # 1. GROW

// or just => DynTree::<i32, Lazy>::new(1);
let mut tree = DynTree::new(1).into_lazy_reclaim();

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
let [id8] = tree.node_mut(&id4).push_children([8]);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

assert_eq!(bfs_values(&tree), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]);

// all id's above are valid => we are in Lazy mode & the tree only grew
assert!(tree.is_node_idx_valid(&id2)); // is_valid_for => true
assert!(tree.get_node(&id4).is_some()); // get_node => Some(Node)
assert!(tree.try_node(&id6).is_ok()); // try_get_node => Ok(Node)
let _node7 = tree.node(&id7); // no panic!

// # 2 - SHRINK, NO MEMORY RECLAIM

// let's close two nodes (nodes 4 & 8)
tree.node_mut(&id4).prune();
assert_eq!(bfs_values(&tree), [1, 2, 3, 5, 6, 7, 9, 10, 11]);

assert!(tree.is_node_idx_valid(&id2)); // is_valid_for => true
assert!(tree.try_node(&id6).is_ok()); // try_get_node => Ok(Node)
let node7 = tree.node(&id7); // no panic

// only id4 & id8 are affected (explicit) => invalidated due to RemovedNode
assert!(!tree.is_node_idx_valid(&id4));
assert!(tree.get_node(&id4).is_none());
assert_eq!(tree.try_node(&id4), Err(NodeIdxError::RemovedNode));
// let node4 = id4.node(&tree); // panics!

// # 3 - SHRINK HEAVILY, STILL NO MEMORY RECLAIM

// let's close more nodes (7, 10, 11)
// this would've triggered memory reclaim in Auto policy, but not in Lazy policy
tree.node_mut(&id7).prune();
assert_eq!(bfs_values(&tree), [1, 2, 3, 5, 6, 9]);

// all indices are still valid ✓
assert!(tree.is_node_idx_valid(&id2));
assert!(tree.try_node(&id2).is_ok());
let n2 = tree.node(&id2);
assert_eq!(n2.data(), &2);

// # 4 - END OF HEAVY MUTATIONS, RECLAIM THE MEMORY

// since utilization was below 75% (6 active nodes / 11)
// memory is reclaimed immediately once switch to Auto.
// now, all prior indices are invalid
let tree: DynTree<i32, Auto> = tree.into_auto_reclaim();
assert!(!tree.is_node_idx_valid(&id2));
assert!(tree.get_node(&id3).is_none());
assert_eq!(
    tree.try_node(&id4),
    Err(NodeIdxError::ReorganizedCollection)
);