webgraph_cli/bench/
bf_visit.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Inria
3 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
5 *
6 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7 */
8
9use crate::GlobalArgs;
10use anyhow::Result;
11use clap::Parser;
12use dsi_bitstream::prelude::*;
13use dsi_progress_logger::prelude::*;
14use std::collections::VecDeque;
15use std::path::PathBuf;
16use sux::prelude::BitVec;
17use sux::traits::BitVecOpsMut;
18use webgraph::prelude::*;
19
20#[derive(Parser, Debug)]
21#[command(name = "bf-visit", about = "Benchmarks a breadth-first visit.", long_about = None)]
22pub struct CliArgs {
23    /// The basename of the graph.
24    pub src: PathBuf,
25    /// Static dispatch (default BvGraph parameters).
26    #[arg(short = 'S', long = "static")]
27    pub _static: bool,
28    /// Number of repeats (usually to warm up the cache or memory mapping).
29    #[arg(short = 'R', long, default_value_t = 1)]
30    pub repeats: usize,
31
32    #[clap(long, default_value = "false")]
33    /// Whether to use mmap for the graph, otherwise it will be load in memory
34    pub mmap: bool,
35}
36
37pub fn main(_global_args: GlobalArgs, args: CliArgs) -> Result<()> {
38    let config = BvGraph::with_basename(&args.src);
39
40    for _ in 0..args.repeats {
41        match (get_endianness(&args.src)?.as_str(), args.mmap) {
42            #[cfg(feature = "be_bins")]
43            (BE::NAME, true) => match args._static {
44                true => visit(
45                    config
46                        .clone()
47                        .mode::<Mmap>()
48                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
49                        .endianness::<BE>()
50                        .dispatch::<Static>()
51                        .load()?,
52                )?,
53                false => visit(config.clone().endianness::<BE>().load()?)?,
54            },
55            #[cfg(feature = "be_bins")]
56            (BE::NAME, false) => match args._static {
57                true => visit(
58                    config
59                        .clone()
60                        .mode::<LoadMmap>()
61                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
62                        .endianness::<BE>()
63                        .dispatch::<Static>()
64                        .load()?,
65                )?,
66                false => visit(config.clone().endianness::<BE>().load()?)?,
67            },
68            #[cfg(feature = "le_bins")]
69            (LE::NAME, true) => match args._static {
70                true => visit(
71                    config
72                        .clone()
73                        .mode::<Mmap>()
74                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
75                        .endianness::<LE>()
76                        .dispatch::<Static>()
77                        .load()?,
78                )?,
79                false => visit(config.clone().endianness::<LE>().load()?)?,
80            },
81            #[cfg(feature = "le_bins")]
82            (LE::NAME, false) => match args._static {
83                true => visit(
84                    config
85                        .clone()
86                        .mode::<LoadMmap>()
87                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
88                        .endianness::<LE>()
89                        .dispatch::<Static>()
90                        .load()?,
91                )?,
92                false => visit(config.clone().endianness::<LE>().load()?)?,
93            },
94            (e, _) => panic!("Unknown endianness: {}", e),
95        };
96    }
97    Ok(())
98}
99
100fn visit(graph: impl RandomAccessGraph) -> Result<()> {
101    let num_nodes = graph.num_nodes();
102    let mut seen = BitVec::new(num_nodes);
103    let mut queue = VecDeque::new();
104
105    let mut pl = ProgressLogger::default();
106    pl.display_memory(true)
107        .item_name("node")
108        .local_speed(true)
109        .expected_updates(Some(num_nodes));
110    pl.start("Visiting graph...");
111
112    for start in 0..num_nodes {
113        if seen[start] {
114            continue;
115        }
116        queue.push_back(start as _);
117        seen.set(start, true);
118
119        while !queue.is_empty() {
120            pl.light_update();
121            let current_node = queue.pop_front().unwrap();
122            for succ in graph.successors(current_node) {
123                if !seen[succ] {
124                    queue.push_back(succ);
125                    seen.set(succ as _, true);
126                }
127            }
128        }
129    }
130
131    pl.done();
132
133    Ok(())
134}
webgraph_cli/bench/bf_visit.rs

webgraph_cli/bench/
bf_visit.rs
