18761474399

Committed 23 Oct 2025 08:43PM UTC coverage: 61.976% (-0.06%) from 62.035%

Build # 18761474399

Build Type

push

github

Committed by

vigna

Commit Message

Goodbye le_bins/be_bins

Run Details

5201 of 8392 relevant lines covered (61.98%)

27888380.24 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::rngs::SmallRng;
use rand::Rng;
use rand::SeedableRng;
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 src: 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.src)?.as_str() {
        BE::NAME => match args._static {
            true => bench_webgraph::<BE, Static>(args),
            false => bench_webgraph::<BE, Dynamic>(args),
        },
        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.src).endianness::<E>().load()?;

        let seq_graph = BvGraphSeq::with_basename(&args.src)
            .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.src)
            .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.src)
                            .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.src)
                            .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.src)
                            .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.src)
                            .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.src)
                        .endianness::<E>()
                        .dispatch::<Dynamic>()
                        .mode::<Mmap>()
                        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::SEQUENTIAL)
                        .load()?,
                    args.repeats,
                );
            }
            (None, false) => {
                bench_seq(
                    BvGraphSeq::with_basename(&args.src)
                        .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::rngs::SmallRng;
16	use rand::Rng;
17	use rand::SeedableRng;
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 src: 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.src)?.as_str() {	×
60	BE::NAME => match args._static {	×
61	true => bench_webgraph::<BE, Static>(args),	×
62	false => bench_webgraph::<BE, Dynamic>(args),	×
63	},
64	LE::NAME => match args._static {	×
65	true => bench_webgraph::<LE, Static>(args),	×
66	false => bench_webgraph::<LE, Dynamic>(args),	×
67	},
68	e => panic!("Unknown endianness: {}", e),	×
69	}
70	}
71
72	fn bench_random(graph: impl RandomAccessGraph, samples: usize, repeats: usize, first: bool) {	×
73	// Random-access speed test
74	for _ in 0..repeats {	×
75	let mut rng = SmallRng::seed_from_u64(0);	×
76	let mut c: u64 = 0;	×
77	let num_nodes = graph.num_nodes();	×
78	let start = std::time::Instant::now();	×
79	if first {	×
80	for _ in 0..samples {	×
81	black_box(
82	graph	×
83	.successors(rng.random_range(0..num_nodes))	×
84	.into_iter()	×
85	.next()	×
86	.unwrap_or(0),	×
87	);
88	c += 1;	×
89	}
90	} else {
91	for _ in 0..samples {	×
92	c += black_box(	×
93	graph	×
94	.successors(rng.random_range(0..num_nodes))	×
95	.into_iter()	×
96	.count() as u64,	×
97	);
98	}
99	}
100
101	println!(	×
102	"{}: {:>20} ns/arc",	×
103	if first { "First" } else { "Random" },	×
104	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
105	);
106	}
107	}
108
109	fn bench_seq(graph: impl SequentialGraph, repeats: usize) {	×
110	for _ in 0..repeats {	×
111	let mut c: u64 = 0;	×
112
113	let start = std::time::Instant::now();	×
114	let mut iter = graph.iter();	×
115	while let Some((_, succ)) = iter.next() {	×
116	c += succ.into_iter().count() as u64;	×
117	}
118	println!(	×
119	"Sequential:{:>20} ns/arc",	×
120	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
121	);
122
123	assert_eq!(c, graph.num_arcs_hint().unwrap());	×
124	}
125	}
126
127	fn bench_webgraph<E: Endianness, D: Dispatch>(args: CliArgs) -> Result<()>	×
128	where
129	MmapHelper<u32>: CodesReaderFactoryHelper<E>,
130	for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek,
131	{
132	if args.check {	×
133	let graph = BvGraph::with_basename(&args.src).endianness::<E>().load()?;	×
134
135	let seq_graph = BvGraphSeq::with_basename(&args.src)	×
136	.endianness::<E>()
137	.load()?;
138
139	let mut deg_reader = seq_graph.offset_deg_iter();	×
140
141	// Check that sequential and random-access interfaces return the same result
142	for_![ (node, seq_succ) in seq_graph {	×
143	let succ = graph.successors(node);	×
144
145	assert_eq!(deg_reader.next_degree()?, seq_succ.len());	×
146	assert_eq!(succ.collect_vec(), seq_succ.collect_vec());	×
147	}];
148	} else if args.degrees {	×
149	let seq_graph = BvGraphSeq::with_basename(&args.src)	×
150	.endianness::<E>()
151	.load()?;
152
153	for _ in 0..args.repeats {	×
154	let mut deg_reader = seq_graph.offset_deg_iter();	×
155
156	let mut c: u64 = 0;	×
157	let start = std::time::Instant::now();	×
158	for _ in 0..seq_graph.num_nodes() {	×
159	c += black_box(deg_reader.next_degree()? as u64);	×
160	}
161	println!(	×
162	"Degrees Only:{:>20} ns/arc",	×
163	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
164	);
165
166	assert_eq!(c, seq_graph.num_arcs_hint().unwrap());	×
167	}
168	} else {
169	match (	×
170	args.random,	×
171	std::any::TypeId::of::<D>() == std::any::TypeId::of::<Dynamic>(),	×
172	) {
173	(Some(samples), true) => {	×
174	if args.slice {	×
175	bench_random(
176	BvGraph::with_basename(&args.src)	×
177	.endianness::<E>()	×
178	.dispatch::<Dynamic>()	×
179	.mode::<Mmap>()	×
180	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
181	.load()?	×
182	.offsets_to_slice(),	×
183	samples,	×
184	args.repeats,	×
185	args.first,	×
186	);
187	} else {
188	bench_random(
189	BvGraph::with_basename(&args.src)	×
190	.endianness::<E>()	×
191	.dispatch::<Dynamic>()	×
192	.mode::<Mmap>()	×
193	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
194	.load()?,	×
195	samples,	×
196	args.repeats,	×
197	args.first,	×
198	);
199	}
200	}
201	(Some(samples), false) => {	×
202	if args.slice {	×
203	bench_random(
204	BvGraph::with_basename(&args.src)	×
205	.endianness::<E>()	×
206	.dispatch::<Static>()	×
207	.mode::<Mmap>()	×
208	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
209	.load()?	×
210	.offsets_to_slice(),	×
211	samples,	×
212	args.repeats,	×
213	args.first,	×
214	);
215	} else {
216	bench_random(
217	BvGraph::with_basename(&args.src)	×
218	.endianness::<E>()	×
219	.dispatch::<Static>()	×
220	.mode::<Mmap>()	×
221	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
222	.load()?,	×
223	samples,	×
224	args.repeats,	×
225	args.first,	×
226	);
227	}
228	}
229	(None, true) => {	×
230	bench_seq(
231	BvGraphSeq::with_basename(&args.src)	×
232	.endianness::<E>()	×
233	.dispatch::<Dynamic>()	×
234	.mode::<Mmap>()	×
235	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
236	.load()?,	×
237	args.repeats,	×
238	);
239	}
240	(None, false) => {	×
241	bench_seq(
242	BvGraphSeq::with_basename(&args.src)	×
243	.endianness::<E>()	×
244	.dispatch::<Static>()	×
245	.mode::<Mmap>()	×
246	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
247	.load()?,	×
248	args.repeats,	×
249	);
250	}
251	}
252	}
253	Ok(())	×
254	}

vigna / webgraph-rs / 18761474399

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