22046400135

Committed 16 Feb 2026 12:49AM UTC coverage: 72.401% (+11.3%) from 61.096%

Build # 22046400135

Build Type

push

github

Committed by

vigna

Commit Message

fmt

Coverage Stats

6060 of 8370 relevant lines covered (72.4%)

48832055.95 hits per line

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

0.0

/cli/src/bench/bvgraph.rs

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

use crate::GlobalArgs;
use anyhow::Result;
use clap::Parser;
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
use dsi_bitstream::prelude::*;
use itertools::Itertools;
use lender::*;
use rand::RngExt;
use rand::SeedableRng;
use rand::rngs::SmallRng;
use std::hint::black_box;
use std::path::PathBuf;
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(name = "bvgraph", about = "Benchmarks the Rust BvGraph implementation.", long_about = None)]
pub struct CliArgs {
    /// The basename of the graph.
    pub basename: PathBuf,

    /// Perform a random-access test on this number of randomly selected nodes.
    #[arg(short, long)]
    pub random: Option<usize>,

    /// The number of repeats.
    #[arg(short = 'R', long, default_value = "10")]
    pub repeats: usize,

    /// In random-access tests, test just access to the first successor.
    #[arg(short = 'f', long)]
    pub first: bool,

    /// Static dispatch for speed tests (default BvGraph parameters).
    #[arg(short = 'S', long = "static")]
    pub _static: bool,

    /// Test sequential high-speed offset/degree scanning.
    #[arg(short = 'd', long)]
    pub degrees: bool,

    /// Do not test speed, but check that the sequential and random-access successor lists are the same.
    #[arg(short = 'c', long)]
    pub check: bool,

    /// Expand offsets into a slice of usize before testing random-access
    /// successor lists.
    #[arg(long)]
    pub slice: bool,
}

pub fn main(_global_args: GlobalArgs, args: CliArgs) -> Result<()> {
    match get_endianness(&args.basename)?.as_str() {
        #[cfg(feature = "be_bins")]
        BE::NAME => match args._static {
            true => bench_webgraph::<BE, Static>(args),
            false => bench_webgraph::<BE, Dynamic>(args),
        },
        #[cfg(feature = "le_bins")]
        LE::NAME => match args._static {
            true => bench_webgraph::<LE, Static>(args),
            false => bench_webgraph::<LE, Dynamic>(args),
        },
        e => panic!("Unknown endianness: {}", e),
    }
}

fn bench_random(graph: impl RandomAccessGraph, samples: usize, repeats: usize, first: bool) {
    // Random-access speed test
    for _ in 0..repeats {
        let mut rng = SmallRng::seed_from_u64(0);
        let mut c: u64 = 0;
        let num_nodes = graph.num_nodes();
        let start = std::time::Instant::now();
        if first {
            for _ in 0..samples {
                black_box(
                    graph
                        .successors(rng.random_range(0..num_nodes))
                        .into_iter()
                        .next()
                        .unwrap_or(0),
                );
                c += 1;
            }
        } else {
            for _ in 0..samples {
                c += black_box(
                    graph
                        .successors(rng.random_range(0..num_nodes))
                        .into_iter()
                        .count() as u64,
                );
            }
        }

        println!(
            "{}:    {:>20} ns/arc",
            if first { "First" } else { "Random" },
            (start.elapsed().as_secs_f64() / c as f64) * 1e9
        );
    }
}

fn bench_seq(graph: impl SequentialGraph, repeats: usize) {
    for _ in 0..repeats {
        let mut c: u64 = 0;

        let start = std::time::Instant::now();
        let mut iter = graph.iter();
        while let Some((_, succ)) = iter.next() {
            c += succ.into_iter().count() as u64;
        }
        println!(
            "Sequential:{:>20} ns/arc",
            (start.elapsed().as_secs_f64() / c as f64) * 1e9
        );

        assert_eq!(c, graph.num_arcs_hint().unwrap());
    }
}

fn bench_webgraph<E: Endianness, D: Dispatch>(args: CliArgs) -> Result<()>
where
    MmapHelper<u32>: CodesReaderFactoryHelper<E>,
    for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek,
{
    if args.check {
        let graph = BvGraph::with_basename(&args.basename)
            .endianness::<E>()
            .load()?;

        let seq_graph = BvGraphSeq::with_basename(&args.basename)
            .endianness::<E>()
            .load()?;

        let mut deg_reader = seq_graph.offset_deg_iter();

        // Check that sequential and random-access interfaces return the same result
        for_![ (node, seq_succ) in seq_graph {
            let succ = graph.successors(node);

            assert_eq!(deg_reader.next_degree()?, seq_succ.len());
            assert_eq!(succ.collect_vec(), seq_succ.collect_vec());
        }];
    } else if args.degrees {
        let seq_graph = BvGraphSeq::with_basename(&args.basename)
            .endianness::<E>()
            .load()?;

        for _ in 0..args.repeats {
            let mut deg_reader = seq_graph.offset_deg_iter();

            let mut c: u64 = 0;
            let start = std::time::Instant::now();
            for _ in 0..seq_graph.num_nodes() {
                c += black_box(deg_reader.next_degree()? as u64);
            }
            println!(
                "Degrees Only:{:>20} ns/arc",
                (start.elapsed().as_secs_f64() / c as f64) * 1e9
            );

            assert_eq!(c, seq_graph.num_arcs_hint().unwrap());
        }
    } else {
        match (
            args.random,
            std::any::TypeId::of::<D>() == std::any::TypeId::of::<Dynamic>(),
        ) {
            (Some(samples), true) => {
                if args.slice {
                    bench_random(
                        BvGraph::with_basename(&args.basename)
                            .endianness::<E>()
                            .dispatch::<Dynamic>()
                            .mode::<Mmap>()
                            .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                            .load()?
                            .offsets_to_slice(),
                        samples,
                        args.repeats,
                        args.first,
                    );
                } else {
                    bench_random(
                        BvGraph::with_basename(&args.basename)
                            .endianness::<E>()
                            .dispatch::<Dynamic>()
                            .mode::<Mmap>()
                            .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                            .load()?,
                        samples,
                        args.repeats,
                        args.first,
                    );
                }
            }
            (Some(samples), false) => {
                if args.slice {
                    bench_random(
                        BvGraph::with_basename(&args.basename)
                            .endianness::<E>()
                            .dispatch::<Static>()
                            .mode::<Mmap>()
                            .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                            .load()?
                            .offsets_to_slice(),
                        samples,
                        args.repeats,
                        args.first,
                    );
                } else {
                    bench_random(
                        BvGraph::with_basename(&args.basename)
                            .endianness::<E>()
                            .dispatch::<Static>()
                            .mode::<Mmap>()
                            .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
                            .load()?,
                        samples,
                        args.repeats,
                        args.first,
                    );
                }
            }
            (None, true) => {
                bench_seq(
                    BvGraphSeq::with_basename(&args.basename)
                        .endianness::<E>()
                        .dispatch::<Dynamic>()
                        .mode::<Mmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::SEQUENTIAL)
                        .load()?,
                    args.repeats,
                );
            }
            (None, false) => {
                bench_seq(
                    BvGraphSeq::with_basename(&args.basename)
                        .endianness::<E>()
                        .dispatch::<Static>()
                        .mode::<Mmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::SEQUENTIAL)
                        .load()?,
                    args.repeats,
                );
            }
        }
    }
    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use crate::GlobalArgs;
9	use anyhow::Result;
10	use clap::Parser;
11	use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
12	use dsi_bitstream::prelude::*;
13	use itertools::Itertools;
14	use lender::*;
15	use rand::RngExt;
16	use rand::SeedableRng;
17	use rand::rngs::SmallRng;
18	use std::hint::black_box;
19	use std::path::PathBuf;
20	use webgraph::prelude::*;
21
22	#[derive(Parser, Debug)]
23	#[command(name = "bvgraph", about = "Benchmarks the Rust BvGraph implementation.", long_about = None)]
24	pub struct CliArgs {
25	/// The basename of the graph.
26	pub basename: PathBuf,
27
28	/// Perform a random-access test on this number of randomly selected nodes.
29	#[arg(short, long)]
30	pub random: Option<usize>,
31
32	/// The number of repeats.
33	#[arg(short = 'R', long, default_value = "10")]
34	pub repeats: usize,
35
36	/// In random-access tests, test just access to the first successor.
37	#[arg(short = 'f', long)]
38	pub first: bool,
39
40	/// Static dispatch for speed tests (default BvGraph parameters).
41	#[arg(short = 'S', long = "static")]
42	pub _static: bool,
43
44	/// Test sequential high-speed offset/degree scanning.
45	#[arg(short = 'd', long)]
46	pub degrees: bool,
47
48	/// Do not test speed, but check that the sequential and random-access successor lists are the same.
49	#[arg(short = 'c', long)]
50	pub check: bool,
51
52	/// Expand offsets into a slice of usize before testing random-access
53	/// successor lists.
54	#[arg(long)]
55	pub slice: bool,
56	}
57
58	pub fn main(_global_args: GlobalArgs, args: CliArgs) -> Result<()> {	×
59	match get_endianness(&args.basename)?.as_str() {	×
60	#[cfg(feature = "be_bins")]
61	BE::NAME => match args._static {	×
62	true => bench_webgraph::<BE, Static>(args),	×
63	false => bench_webgraph::<BE, Dynamic>(args),	×
64	},
65	#[cfg(feature = "le_bins")]
66	LE::NAME => match args._static {	×
67	true => bench_webgraph::<LE, Static>(args),	×
68	false => bench_webgraph::<LE, Dynamic>(args),	×
69	},
70	e => panic!("Unknown endianness: {}", e),	×
71	}
72	}
73
74	fn bench_random(graph: impl RandomAccessGraph, samples: usize, repeats: usize, first: bool) {	×
75	// Random-access speed test
76	for _ in 0..repeats {	×
77	let mut rng = SmallRng::seed_from_u64(0);	×
78	let mut c: u64 = 0;	×
79	let num_nodes = graph.num_nodes();	×
80	let start = std::time::Instant::now();	×
81	if first {	×
82	for _ in 0..samples {	×
83	black_box(
84	graph	×
85	.successors(rng.random_range(0..num_nodes))	×
86	.into_iter()	×
87	.next()	×
88	.unwrap_or(0),	×
89	);
90	c += 1;	×
91	}
92	} else {
93	for _ in 0..samples {	×
94	c += black_box(	×
95	graph	×
96	.successors(rng.random_range(0..num_nodes))	×
97	.into_iter()	×
98	.count() as u64,	×
99	);
100	}
101	}
102
103	println!(	×
104	"{}: {:>20} ns/arc",	×
105	if first { "First" } else { "Random" },	×
106	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
107	);
108	}
109	}
110
111	fn bench_seq(graph: impl SequentialGraph, repeats: usize) {	×
112	for _ in 0..repeats {	×
113	let mut c: u64 = 0;	×
114
115	let start = std::time::Instant::now();	×
116	let mut iter = graph.iter();	×
117	while let Some((_, succ)) = iter.next() {	×
118	c += succ.into_iter().count() as u64;	×
119	}
120	println!(	×
121	"Sequential:{:>20} ns/arc",	×
122	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
123	);
124
125	assert_eq!(c, graph.num_arcs_hint().unwrap());	×
126	}
127	}
128
129	fn bench_webgraph<E: Endianness, D: Dispatch>(args: CliArgs) -> Result<()>	×
130	where
131	MmapHelper<u32>: CodesReaderFactoryHelper<E>,
132	for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek,
133	{
134	if args.check {	×
135	let graph = BvGraph::with_basename(&args.basename)	×
136	.endianness::<E>()
137	.load()?;
138
139	let seq_graph = BvGraphSeq::with_basename(&args.basename)	×
140	.endianness::<E>()
141	.load()?;
142
143	let mut deg_reader = seq_graph.offset_deg_iter();	×
144
145	// Check that sequential and random-access interfaces return the same result
146	for_![ (node, seq_succ) in seq_graph {	×
147	let succ = graph.successors(node);	×
148
149	assert_eq!(deg_reader.next_degree()?, seq_succ.len());	×
150	assert_eq!(succ.collect_vec(), seq_succ.collect_vec());	×
151	}];
152	} else if args.degrees {	×
153	let seq_graph = BvGraphSeq::with_basename(&args.basename)	×
154	.endianness::<E>()
155	.load()?;
156
157	for _ in 0..args.repeats {	×
158	let mut deg_reader = seq_graph.offset_deg_iter();	×
159
160	let mut c: u64 = 0;	×
161	let start = std::time::Instant::now();	×
162	for _ in 0..seq_graph.num_nodes() {	×
163	c += black_box(deg_reader.next_degree()? as u64);	×
164	}
165	println!(	×
166	"Degrees Only:{:>20} ns/arc",	×
167	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
168	);
169
170	assert_eq!(c, seq_graph.num_arcs_hint().unwrap());	×
171	}
172	} else {
173	match (	×
174	args.random,	×
175	std::any::TypeId::of::<D>() == std::any::TypeId::of::<Dynamic>(),	×
176	) {
177	(Some(samples), true) => {	×
178	if args.slice {	×
179	bench_random(
180	BvGraph::with_basename(&args.basename)	×
181	.endianness::<E>()	×
182	.dispatch::<Dynamic>()	×
183	.mode::<Mmap>()	×
184	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
185	.load()?	×
186	.offsets_to_slice(),	×
187	samples,	×
188	args.repeats,	×
189	args.first,	×
190	);
191	} else {
192	bench_random(
193	BvGraph::with_basename(&args.basename)	×
194	.endianness::<E>()	×
195	.dispatch::<Dynamic>()	×
196	.mode::<Mmap>()	×
197	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
198	.load()?,	×
199	samples,	×
200	args.repeats,	×
201	args.first,	×
202	);
203	}
204	}
205	(Some(samples), false) => {	×
206	if args.slice {	×
207	bench_random(
208	BvGraph::with_basename(&args.basename)	×
209	.endianness::<E>()	×
210	.dispatch::<Static>()	×
211	.mode::<Mmap>()	×
212	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
213	.load()?	×
214	.offsets_to_slice(),	×
215	samples,	×
216	args.repeats,	×
217	args.first,	×
218	);
219	} else {
220	bench_random(
221	BvGraph::with_basename(&args.basename)	×
222	.endianness::<E>()	×
223	.dispatch::<Static>()	×
224	.mode::<Mmap>()	×
225	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
226	.load()?,	×
227	samples,	×
228	args.repeats,	×
229	args.first,	×
230	);
231	}
232	}
233	(None, true) => {	×
234	bench_seq(
235	BvGraphSeq::with_basename(&args.basename)	×
236	.endianness::<E>()	×
237	.dispatch::<Dynamic>()	×
238	.mode::<Mmap>()	×
239	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
240	.load()?,	×
241	args.repeats,	×
242	);
243	}
244	(None, false) => {	×
245	bench_seq(
246	BvGraphSeq::with_basename(&args.basename)	×
247	.endianness::<E>()	×
248	.dispatch::<Static>()	×
249	.mode::<Mmap>()	×
250	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
251	.load()?,	×
252	args.repeats,	×
253	);
254	}
255	}
256	}
257	Ok(())	×
258	}

vigna / webgraph-rs / 22046400135

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