Struct ParLowMem

pub struct ParLowMem<G: RandomAccessGraph> { /* private fields */ }

Low-memory parallel breadth-first visits.

“Low memory” refers to the fact that the visit is parallelized by dividing the visit queue in chunks of approximately equal size, but nodes are visited when they are discovered, rather than when they are extracted from the visit queue. This approach makes unnecessary to store parents in the visit queue, thus reducing the memory usage, even if this visit supports EventPred. However, the visiting cost is distributed unevenly among the threads, as it depends on the sum of the outdegrees of the nodes in a chunk, which might differ significantly between chunks.

If the cost of the callbacks is significant, you can use a fair parallel visit to distribute the visiting cost evenly among the threads.

Examples

Let’s compute the breadth-first tree starting from 0. We will be using a SyncSlice from the sync_cell_slice crate to store the parent of each node.

use webgraph_algo::visits::Parallel;
use webgraph_algo::visits::breadth_first::{*, self};
use webgraph_algo::thread_pool;
use webgraph::graphs::vec_graph::VecGraph;
use webgraph::labels::proj::Left;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering;
use std::ops::ControlFlow::Continue;
use no_break::NoBreak;
use sync_cell_slice::SyncSlice;

let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
let mut visit = breadth_first::ParLowMem::new(&graph);
let mut tree = vec![0_usize; 4];
let mut tree_sync = tree.as_sync_slice();
visit.par_visit(
    [0],
    |event|
    {
        // Store the parent
        if let EventPred::Unknown { node, pred, ..} = event {
            // There will be exactly one set for each node
            unsafe { tree_sync[node].set(pred) };
        }
        Continue(())
    },
    &thread_pool![],
).continue_value_no_break();

assert_eq!(tree[0], 0);
assert_eq!(tree[1], 0);
assert_eq!(tree[2], 1);
assert_eq!(tree[3], 1);

Implementations

impl<G: RandomAccessGraph> ParLowMem<G>

pub fn new(graph: G) -> Self

Creates a low-memory parallel breadth-first visit.

This constructor uses a default granularity of 128 nodes. Use with_granularity to set a different granularity.

Arguments

• graph: the graph to visit.

pub fn with_granularity(graph: G, granularity: Granularity) -> Self

Creates a low-memory parallel breadth-first visit.

Arguments

• graph: the graph to visit.

• granularity: High granularity reduces overhead, but may lead to decreased performance on graphs with a skewed outdegree distribution. From this parameter, we derive a node granularity.

Trait Implementations

impl<G: RandomAccessGraph + Sync> Parallel<EventPred> for ParLowMem<G>

fn par_visit_filtered_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, EventPred) -> ControlFlow<E, ()> + Sync, F: Fn(&mut T, FilterArgsPred) -> bool + Sync>( &mut self, roots: R, init: T, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value and a filter function.

fn reset(&mut self)

Resets the visit status, making it possible to reuse it.

fn par_visit_filtered<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync, F: Fn(A::FilterArgs) -> bool + Sync>( &mut self, roots: R, callback: C, filter: F, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with a filter function.

fn par_visit_with<R: IntoIterator<Item = usize>, T: Clone + Send + Sync, E: Send, C: Fn(&mut T, A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, init: T, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes with an initialization value.

fn par_visit<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync>( &mut self, roots: R, callback: C, thread_pool: &ThreadPool, ) -> ControlFlow<E, ()>

Visits the graph from the specified nodes.