23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Coverage Stats

6655 of 9754 relevant lines covered (68.23%)

46582760.24 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/cli/src/bench/bf_visit.rs

/*
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use anyhow::Result;
use clap::Parser;
use dsi_bitstream::prelude::*;
use dsi_progress_logger::prelude::*;
use std::collections::VecDeque;
use std::path::PathBuf;
use sux::prelude::BitVec;
use sux::traits::BitVecOpsMut;
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(name = "bf-visit", about = "Benchmarks a breadth-first visit.", long_about = None, next_line_help = true)]
pub struct CliArgs {
    /// The basename of the graph.​
    pub basename: PathBuf,
    /// Static dispatch (default parameters for the BV format).​
    #[arg(short = 'S', long = "static")]
    pub _static: bool,
    /// Number of repeats (usually to warm up the cache or memory mapping).​
    #[arg(short = 'R', long, default_value_t = 1)]
    pub repeats: usize,

    #[clap(long, default_value = "false")]
    /// Use memory mapping instead of loading the graph into memory.​
    pub mmap: bool,
}

pub fn main(args: CliArgs) -> Result<()> {
    let config = BvGraph::with_basename(&args.basename);

    for _ in 0..args.repeats {
        match (get_endianness(&args.basename)?.as_str(), args.mmap) {
            #[cfg(feature = "be_bins")]
            (BE::NAME, true) => match args._static {
                true => visit(
                    config
                        .clone()
                        .mode::<Mmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                        .endianness::<BE>()
                        .dispatch::<Static>()
                        .load()?,
                )?,
                false => visit(config.clone().endianness::<BE>().load()?)?,
            },
            #[cfg(feature = "be_bins")]
            (BE::NAME, false) => match args._static {
                true => visit(
                    config
                        .clone()
                        .mode::<LoadMmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                        .endianness::<BE>()
                        .dispatch::<Static>()
                        .load()?,
                )?,
                false => visit(config.clone().endianness::<BE>().load()?)?,
            },
            #[cfg(feature = "le_bins")]
            (LE::NAME, true) => match args._static {
                true => visit(
                    config
                        .clone()
                        .mode::<Mmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                        .endianness::<LE>()
                        .dispatch::<Static>()
                        .load()?,
                )?,
                false => visit(config.clone().endianness::<LE>().load()?)?,
            },
            #[cfg(feature = "le_bins")]
            (LE::NAME, false) => match args._static {
                true => visit(
                    config
                        .clone()
                        .mode::<LoadMmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                        .endianness::<LE>()
                        .dispatch::<Static>()
                        .load()?,
                )?,
                false => visit(config.clone().endianness::<LE>().load()?)?,
            },
            (e, _) => panic!("Unknown endianness: {}", e),
        };
    }
    Ok(())
}

fn visit(graph: impl RandomAccessGraph) -> Result<()> {
    let num_nodes = graph.num_nodes();
    let mut seen: BitVec = BitVec::new(num_nodes);
    let mut queue = VecDeque::new();

    let mut pl = progress_logger![
        display_memory = true,
        item_name = "node",
        local_speed = true,
        expected_updates = Some(num_nodes),
    ];
    pl.start("Visiting graph...");

    for start in 0..num_nodes {
        if seen[start] {
            continue;
        }
        queue.push_back(start as _);
        seen.set(start, true);

        while !queue.is_empty() {
            pl.light_update();
            let current_node = queue.pop_front().unwrap();
            for succ in graph.successors(current_node) {
                if !seen[succ] {
                    queue.push_back(succ);
                    seen.set(succ as _, true);
                }
            }
        }
    }

    pl.done();

    Ok(())
}

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
9	use anyhow::Result;
10	use clap::Parser;
11	use dsi_bitstream::prelude::*;
12	use dsi_progress_logger::prelude::*;
13	use std::collections::VecDeque;
14	use std::path::PathBuf;
15	use sux::prelude::BitVec;
16	use sux::traits::BitVecOpsMut;
17	use webgraph::prelude::*;
18
19	#[derive(Parser, Debug)]
20	#[command(name = "bf-visit", about = "Benchmarks a breadth-first visit.", long_about = None, next_line_help = true)]
21	pub struct CliArgs {
22	/// The basename of the graph.
23	pub basename: PathBuf,
24	/// Static dispatch (default parameters for the BV format).
25	#[arg(short = 'S', long = "static")]
26	pub _static: bool,
27	/// Number of repeats (usually to warm up the cache or memory mapping).
28	#[arg(short = 'R', long, default_value_t = 1)]
29	pub repeats: usize,
30
31	#[clap(long, default_value = "false")]
32	/// Use memory mapping instead of loading the graph into memory.
33	pub mmap: bool,
34	}
35
36	pub fn main(args: CliArgs) -> Result<()> {	×
37	let config = BvGraph::with_basename(&args.basename);	×
38
39	for _ in 0..args.repeats {	×
40	match (get_endianness(&args.basename)?.as_str(), args.mmap) {	×
41	#[cfg(feature = "be_bins")]
42	(BE::NAME, true) => match args._static {	×
43	true => visit(
44	config	×
45	.clone()	×
46	.mode::<Mmap>()	×
47	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
48	.endianness::<BE>()	×
49	.dispatch::<Static>()	×
50	.load()?,	×
51	)?,
52	false => visit(config.clone().endianness::<BE>().load()?)?,	×
53	},
54	#[cfg(feature = "be_bins")]
55	(BE::NAME, false) => match args._static {	×
56	true => visit(
57	config	×
58	.clone()	×
59	.mode::<LoadMmap>()	×
60	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
61	.endianness::<BE>()	×
62	.dispatch::<Static>()	×
63	.load()?,	×
64	)?,
65	false => visit(config.clone().endianness::<BE>().load()?)?,	×
66	},
67	#[cfg(feature = "le_bins")]
68	(LE::NAME, true) => match args._static {	×
69	true => visit(
70	config	×
71	.clone()	×
72	.mode::<Mmap>()	×
73	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
74	.endianness::<LE>()	×
75	.dispatch::<Static>()	×
76	.load()?,	×
77	)?,
78	false => visit(config.clone().endianness::<LE>().load()?)?,	×
79	},
80	#[cfg(feature = "le_bins")]
81	(LE::NAME, false) => match args._static {	×
82	true => visit(
83	config	×
84	.clone()	×
85	.mode::<LoadMmap>()	×
86	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
87	.endianness::<LE>()	×
88	.dispatch::<Static>()	×
89	.load()?,	×
90	)?,
91	false => visit(config.clone().endianness::<LE>().load()?)?,	×
92	},
93	(e, _) => panic!("Unknown endianness: {}", e),	×
94	};
95	}
96	Ok(())	×
97	}
98
99	fn visit(graph: impl RandomAccessGraph) -> Result<()> {	×
100	let num_nodes = graph.num_nodes();	×
101	let mut seen: BitVec = BitVec::new(num_nodes);	×
102	let mut queue = VecDeque::new();	×
103
104	let mut pl = progress_logger![	×
105	display_memory = true,	×
106	item_name = "node",	×
107	local_speed = true,	×
108	expected_updates = Some(num_nodes),	×
109	];
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	}

vigna / webgraph-rs / 23365769388

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous