14398898444

Committed 11 Apr 2025 08:24AM UTC coverage: 56.011% (-0.4%) from 56.361%

Build # 14398898444

Build Type

push

github

Committed by

vigna

Commit Message

Fixed test

Coverage Stats

8 of 8 new or added lines in 1 file covered. (100.0%)

477 existing lines in 19 files now uncovered.

3993 of 7129 relevant lines covered (56.01%)

20186811.3 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() {
        #[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.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	#[cfg(feature = "be_bins")]
UNCOV 61	BE::NAME => match args._static {	×
UNCOV 62	true => bench_webgraph::<BE, Static>(args),	×
UNCOV 63	false => bench_webgraph::<BE, Dynamic>(args),	×
64	},
65	#[cfg(feature = "le_bins")]
66	LE::NAME => match args._static {	×
UNCOV 67	true => bench_webgraph::<LE, Static>(args),	×
UNCOV 68	false => bench_webgraph::<LE, Dynamic>(args),	×
69	},
UNCOV 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 {	×
UNCOV 77	let mut rng = SmallRng::seed_from_u64(0);	×
UNCOV 78	let mut c: u64 = 0;	×
UNCOV 79	let num_nodes = graph.num_nodes();	×
80	let start = std::time::Instant::now();	×
UNCOV 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(	×
UNCOV 95	graph	×
96	.successors(rng.random_range(0..num_nodes))	×
UNCOV 97	.into_iter()	×
UNCOV 98	.count() as u64,	×
99	);
100	}
101	}
102
103	println!(	×
104	"{}: {:>20} ns/arc",	×
UNCOV 105	if first { "First" } else { "Random" },	×
UNCOV 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 {	×
UNCOV 113	let mut c: u64 = 0;	×
114
UNCOV 115	let start = std::time::Instant::now();	×
UNCOV 116	let mut iter = graph.iter();	×
117	while let Some((_, succ)) = iter.next() {	×
118	c += succ.into_iter().count() as u64;	×
119	}
UNCOV 120	println!(	×
121	"Sequential:{:>20} ns/arc",	×
122	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
123	);
124
UNCOV 125	assert_eq!(c, graph.num_arcs_hint().unwrap());	×
126	}
127	}
128
UNCOV 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	{
UNCOV 134	if args.check {	×
135	let graph = BvGraph::with_basename(&args.src).endianness::<E>().load()?;	×
136
UNCOV 137	let seq_graph = BvGraphSeq::with_basename(&args.src)	×
138	.endianness::<E>()
139	.load()?;
140
141	let mut deg_reader = seq_graph.offset_deg_iter();	×
142
143	// Check that sequential and random-access interfaces return the same result
UNCOV 144	for_![ (node, seq_succ) in seq_graph {	×
UNCOV 145	let succ = graph.successors(node);	×
146
147	assert_eq!(deg_reader.next_degree()?, seq_succ.len());	×
UNCOV 148	assert_eq!(succ.collect_vec(), seq_succ.collect_vec());	×
149	}];
150	} else if args.degrees {	×
151	let seq_graph = BvGraphSeq::with_basename(&args.src)	×
152	.endianness::<E>()
153	.load()?;
154
UNCOV 155	for _ in 0..args.repeats {	×
156	let mut deg_reader = seq_graph.offset_deg_iter();	×
157
UNCOV 158	let mut c: u64 = 0;	×
UNCOV 159	let start = std::time::Instant::now();	×
UNCOV 160	for _ in 0..seq_graph.num_nodes() {	×
161	c += black_box(deg_reader.next_degree()? as u64);	×
162	}
UNCOV 163	println!(	×
164	"Degrees Only:{:>20} ns/arc",	×
165	(start.elapsed().as_secs_f64() / c as f64) * 1e9	×
166	);
167
UNCOV 168	assert_eq!(c, seq_graph.num_arcs_hint().unwrap());	×
169	}
170	} else {
171	match (	×
UNCOV 172	args.random,	×
UNCOV 173	std::any::TypeId::of::<D>() == std::any::TypeId::of::<Dynamic>(),	×
174	) {
UNCOV 175	(Some(samples), true) => {	×
UNCOV 176	if args.slice {	×
177	bench_random(
178	BvGraph::with_basename(&args.src)	×
179	.endianness::<E>()	×
UNCOV 180	.dispatch::<Dynamic>()	×
181	.mode::<Mmap>()	×
182	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
UNCOV 183	.load()?	×
184	.offsets_to_slice(),	×
185	samples,	×
186	args.repeats,	×
187	args.first,	×
188	);
189	} else {
190	bench_random(
191	BvGraph::with_basename(&args.src)	×
192	.endianness::<E>()	×
193	.dispatch::<Dynamic>()	×
UNCOV 194	.mode::<Mmap>()	×
UNCOV 195	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
UNCOV 196	.load()?,	×
197	samples,	×
198	args.repeats,	×
199	args.first,	×
200	);
201	}
202	}
203	(Some(samples), false) => {	×
204	if args.slice {	×
205	bench_random(
UNCOV 206	BvGraph::with_basename(&args.src)	×
UNCOV 207	.endianness::<E>()	×
UNCOV 208	.dispatch::<Static>()	×
209	.mode::<Mmap>()	×
210	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
UNCOV 211	.load()?	×
212	.offsets_to_slice(),	×
213	samples,	×
214	args.repeats,	×
215	args.first,	×
216	);
217	} else {
218	bench_random(
219	BvGraph::with_basename(&args.src)	×
220	.endianness::<E>()	×
221	.dispatch::<Static>()	×
UNCOV 222	.mode::<Mmap>()	×
UNCOV 223	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	×
UNCOV 224	.load()?,	×
225	samples,	×
226	args.repeats,	×
227	args.first,	×
228	);
229	}
230	}
231	(None, true) => {	×
232	bench_seq(
233	BvGraphSeq::with_basename(&args.src)	×
UNCOV 234	.endianness::<E>()	×
UNCOV 235	.dispatch::<Dynamic>()	×
UNCOV 236	.mode::<Mmap>()	×
237	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
UNCOV 238	.load()?,	×
239	args.repeats,	×
240	);
241	}
242	(None, false) => {	×
243	bench_seq(
244	BvGraphSeq::with_basename(&args.src)	×
245	.endianness::<E>()	×
UNCOV 246	.dispatch::<Static>()	×
UNCOV 247	.mode::<Mmap>()	×
248	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::SEQUENTIAL)	×
UNCOV 249	.load()?,	×
250	args.repeats,	×
251	);
252	}
253	}
254	}
255	Ok(())	×
256	}

vigna / webgraph-rs / 14398898444

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