18279564945

Committed 06 Oct 2025 11:36AM UTC coverage: 48.839% (-0.2%) from 49.006%

Build # 18279564945

Build Type

push

github

Committed by

vigna

Commit Message

Moved SortPairs to MemoryUsage

Run Details

12 of 23 new or added lines in 6 files covered. (52.17%)

14 existing lines in 3 files now uncovered.

3890 of 7965 relevant lines covered (48.84%)

23444471.85 hits per line

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

22.39

/webgraph/src/utils/mod.rs

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

//! Miscellaneous utilities.

use rand::Rng;
use std::path::PathBuf;

/// An enum expressing the memory requirements for batched algorithms
/// such as [`SortPairs`] and [`ParSortPairs`].
pub enum MemoryUsage {
    /// The target overall memory usage in bytes.
    MemorySize(usize),
    /// The number of elements in a batch.
    ///
    /// Note that the size of elements depends on the size of
    /// labels for labelled graphs, and that the actual memory
    /// usage may depend on the implementation (e.g., [`SortPairs`]
    /// will use this number of elements, but [`ParSortPairs`] will
    /// use this number of elements multiplied by the square of
    /// the number of threads).
    BatchSize(usize),
}

/// Default implementation, returning half of the physical RAM.
impl Default for MemoryUsage {
    fn default() -> Self {
        Self::from_perc(0.5)
    }
}

impl MemoryUsage {
    /// Creates a new memory usage expressed as a percentage of the
    /// physical RAM.
    pub fn from_perc(perc: f64) -> Self {
        let system = sysinfo::System::new_with_specifics(
            sysinfo::RefreshKind::nothing()
                .with_memory(sysinfo::MemoryRefreshKind::nothing().with_ram()),
        );
        MemoryUsage::MemorySize(
            usize::try_from((system.total_memory() as f64 * perc / 100.0) as u64)
                .expect("System memory overflows usize"),
        )
    }

    /// Returns the batch size for elements of type `T`.
    ///
    /// If the [memory usage is expressed as a number of
    /// bytes](MemoryUsage::MemorySize), this method divides the number of bytes
    /// by the size of `T` to obtain the number of elements. Otherwise, [it just
    /// returns specified batch size](MemoryUsage::BatchSize).
    pub fn batch_size<T>(&self) -> usize {
        match &self {
            MemoryUsage::MemorySize(memory_size) => {
                let elem_size = std::mem::size_of::<T>();
                assert!(elem_size > 0, "Element size cannot be zero");
                memory_size / elem_size
            }
            MemoryUsage::BatchSize(batch_size) => *batch_size,
        }
    }
}

/// Creates a new random dir inside the given folder
pub fn temp_dir<P: AsRef<std::path::Path>>(base: P) -> anyhow::Result<PathBuf> {
    let mut base = base.as_ref().to_owned();
    const ALPHABET: &[u8] = b"0123456789abcdef";
    let mut rnd = rand::rng();
    let mut random_str = String::new();
    loop {
        random_str.clear();
        for _ in 0..16 {
            let idx = rnd.random_range(0..ALPHABET.len());
            random_str.push(ALPHABET[idx] as char);
        }
        base.push(&random_str);

        if !base.exists() {
            std::fs::create_dir(&base)?;
            return Ok(base);
        }
        base.pop();
    }
}

mod circular_buffer;
pub(crate) use circular_buffer::*;

mod mmap_helper;
pub use mmap_helper::*;

mod java_perm;
pub use java_perm::*;

mod granularity;
pub use granularity::*;

pub mod sort_pairs;
pub use sort_pairs::SortPairs;

pub mod par_sort_pairs;
pub use par_sort_pairs::ParSortPairs;

use crate::graphs::bvgraph::{Decode, Encode};

/// A decoder that encodes the read values using the given encoder.
/// This is commonly used to change the codes of a graph without decoding and
/// re-encoding it but by changing the codes.
pub struct Converter<D: Decode, E: Encode> {
    pub decoder: D,
    pub encoder: E,
    pub offset: usize,
}

impl<D: Decode, E: Encode> Decode for Converter<D, E> {
    // TODO: implement correctly start_node/end_node
    #[inline(always)]
    fn read_outdegree(&mut self) -> u64 {
        let res = self.decoder.read_outdegree();
        self.offset += self.encoder.write_outdegree(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_reference_offset(&mut self) -> u64 {
        let res = self.decoder.read_reference_offset();
        self.offset += self.encoder.write_reference_offset(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_block_count(&mut self) -> u64 {
        let res = self.decoder.read_block_count();
        self.offset += self.encoder.write_block_count(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_block(&mut self) -> u64 {
        let res = self.decoder.read_block();
        self.offset += self.encoder.write_block(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_interval_count(&mut self) -> u64 {
        let res = self.decoder.read_interval_count();
        self.offset += self.encoder.write_interval_count(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_interval_start(&mut self) -> u64 {
        let res = self.decoder.read_interval_start();
        self.offset += self.encoder.write_interval_start(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_interval_len(&mut self) -> u64 {
        let res = self.decoder.read_interval_len();
        self.offset += self.encoder.write_interval_len(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_first_residual(&mut self) -> u64 {
        let res = self.decoder.read_first_residual();
        self.offset += self.encoder.write_first_residual(res).unwrap();
        res
    }
    #[inline(always)]
    fn read_residual(&mut self) -> u64 {
        let res = self.decoder.read_residual();
        self.offset += self.encoder.write_residual(res).unwrap();
        res
    }
}

/// Utility macro to create [`thread_pools`](`rayon::ThreadPool`).
///
/// There are two forms of this macro:
/// * Create a [`ThreadPool`](rayon::ThreadPool) with the default settings:
/// ```
/// # use webgraph::thread_pool;
/// let t: rayon::ThreadPool = thread_pool![];
/// ```
/// * Create a [`ThreadPool`](rayon::ThreadPool) with a given number of threads:
/// ```
/// # use webgraph::thread_pool;
/// let t: rayon::ThreadPool = thread_pool![7];
/// assert_eq!(t.current_num_threads(), 7);
/// ```
#[macro_export]
macro_rules! thread_pool {
    () => {
        rayon::ThreadPoolBuilder::new()
            .build()
            .expect("Cannot build a ThreadPool with default parameters")
    };
    ($num_threads:expr) => {
        rayon::ThreadPoolBuilder::new()
            .num_threads($num_threads)
            .build()
            .unwrap_or_else(|_| {
                panic!(
                    "Cannot build a ThreadPool with default parameters and {} threads",
                    $num_threads,
                )
            })
    };
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Miscellaneous utilities.
9
10	use rand::Rng;
11	use std::path::PathBuf;
12
13	/// An enum expressing the memory requirements for batched algorithms
14	/// such as [`SortPairs`] and [`ParSortPairs`].
15	pub enum MemoryUsage {
16	/// The target overall memory usage in bytes.
17	MemorySize(usize),
18	/// The number of elements in a batch.
19	///
20	/// Note that the size of elements depends on the size of
21	/// labels for labelled graphs, and that the actual memory
22	/// usage may depend on the implementation (e.g., [`SortPairs`]
23	/// will use this number of elements, but [`ParSortPairs`] will
24	/// use this number of elements multiplied by the square of
25	/// the number of threads).
26	BatchSize(usize),
27	}
28
29	/// Default implementation, returning half of the physical RAM.
30	impl Default for MemoryUsage {
31	fn default() -> Self {	×
32	Self::from_perc(0.5)	×
33	}
34	}
35
36	impl MemoryUsage {
37	/// Creates a new memory usage expressed as a percentage of the
38	/// physical RAM.
39	pub fn from_perc(perc: f64) -> Self {	×
40	let system = sysinfo::System::new_with_specifics(
41	sysinfo::RefreshKind::nothing()	×
42	.with_memory(sysinfo::MemoryRefreshKind::nothing().with_ram()),	×
43	);
44	MemoryUsage::MemorySize(
45	usize::try_from((system.total_memory() as f64 * perc / 100.0) as u64)	×
46	.expect("System memory overflows usize"),	×
47	)
48	}
49
50	/// Returns the batch size for elements of type `T`.
51	///
52	/// If the [memory usage is expressed as a number of
53	/// bytes](MemoryUsage::MemorySize), this method divides the number of bytes
54	/// by the size of `T` to obtain the number of elements. Otherwise, [it just
55	/// returns specified batch size](MemoryUsage::BatchSize).
56	pub fn batch_size<T>(&self) -> usize {	131✔
57	match &self {	131✔
NEW 58	MemoryUsage::MemorySize(memory_size) => {	×
NEW 59	let elem_size = std::mem::size_of::<T>();	×
NEW 60	assert!(elem_size > 0, "Element size cannot be zero");	×
NEW 61	memory_size / elem_size	×
62	}
63	MemoryUsage::BatchSize(batch_size) => *batch_size,	262✔
64	}
65	}
66	}
67
68	/// Creates a new random dir inside the given folder
69	pub fn temp_dir<P: AsRef<std::path::Path>>(base: P) -> anyhow::Result<PathBuf> {	9✔
70	let mut base = base.as_ref().to_owned();	27✔
71	const ALPHABET: &[u8] = b"0123456789abcdef";
72	let mut rnd = rand::rng();	18✔
73	let mut random_str = String::new();	18✔
74	loop {	×
75	random_str.clear();	18✔
76	for _ in 0..16 {	297✔
77	let idx = rnd.random_range(0..ALPHABET.len());	144✔
78	random_str.push(ALPHABET[idx] as char);	144✔
79	}
80	base.push(&random_str);	27✔
81
82	if !base.exists() {	9✔
83	std::fs::create_dir(&base)?;	18✔
84	return Ok(base);	9✔
85	}
86	base.pop();	×
87	}
88	}
89
90	mod circular_buffer;
91	pub(crate) use circular_buffer::*;
92
93	mod mmap_helper;
94	pub use mmap_helper::*;
95
96	mod java_perm;
97	pub use java_perm::*;
98
99	mod granularity;
100	pub use granularity::*;
101
102	pub mod sort_pairs;
103	pub use sort_pairs::SortPairs;
104
105	pub mod par_sort_pairs;
106	pub use par_sort_pairs::ParSortPairs;
107
108	use crate::graphs::bvgraph::{Decode, Encode};
109
110	/// A decoder that encodes the read values using the given encoder.
111	/// This is commonly used to change the codes of a graph without decoding and
112	/// re-encoding it but by changing the codes.
113	pub struct Converter<D: Decode, E: Encode> {
114	pub decoder: D,
115	pub encoder: E,
116	pub offset: usize,
117	}
118
119	impl<D: Decode, E: Encode> Decode for Converter<D, E> {
120	// TODO: implement correctly start_node/end_node
121	#[inline(always)]
122	fn read_outdegree(&mut self) -> u64 {	×
123	let res = self.decoder.read_outdegree();	×
124	self.offset += self.encoder.write_outdegree(res).unwrap();	×
125	res	×
126	}
127	#[inline(always)]
128	fn read_reference_offset(&mut self) -> u64 {	×
129	let res = self.decoder.read_reference_offset();	×
130	self.offset += self.encoder.write_reference_offset(res).unwrap();	×
131	res	×
132	}
133	#[inline(always)]
134	fn read_block_count(&mut self) -> u64 {	×
135	let res = self.decoder.read_block_count();	×
136	self.offset += self.encoder.write_block_count(res).unwrap();	×
137	res	×
138	}
139	#[inline(always)]
140	fn read_block(&mut self) -> u64 {	×
141	let res = self.decoder.read_block();	×
142	self.offset += self.encoder.write_block(res).unwrap();	×
143	res	×
144	}
145	#[inline(always)]
146	fn read_interval_count(&mut self) -> u64 {	×
147	let res = self.decoder.read_interval_count();	×
148	self.offset += self.encoder.write_interval_count(res).unwrap();	×
149	res	×
150	}
151	#[inline(always)]
152	fn read_interval_start(&mut self) -> u64 {	×
153	let res = self.decoder.read_interval_start();	×
154	self.offset += self.encoder.write_interval_start(res).unwrap();	×
155	res	×
156	}
157	#[inline(always)]
158	fn read_interval_len(&mut self) -> u64 {	×
159	let res = self.decoder.read_interval_len();	×
160	self.offset += self.encoder.write_interval_len(res).unwrap();	×
161	res	×
162	}
163	#[inline(always)]
164	fn read_first_residual(&mut self) -> u64 {	×
165	let res = self.decoder.read_first_residual();	×
166	self.offset += self.encoder.write_first_residual(res).unwrap();	×
167	res	×
168	}
169	#[inline(always)]
170	fn read_residual(&mut self) -> u64 {	×
171	let res = self.decoder.read_residual();	×
172	self.offset += self.encoder.write_residual(res).unwrap();	×
173	res	×
174	}
175	}
176
177	/// Utility macro to create [`thread_pools`](`rayon::ThreadPool`).
178	///
179	/// There are two forms of this macro:
180	/// * Create a [`ThreadPool`](rayon::ThreadPool) with the default settings:
181	/// ```
182	/// # use webgraph::thread_pool;
183	/// let t: rayon::ThreadPool = thread_pool![];
184	/// ```
185	/// * Create a [`ThreadPool`](rayon::ThreadPool) with a given number of threads:
186	/// ```
187	/// # use webgraph::thread_pool;
188	/// let t: rayon::ThreadPool = thread_pool![7];
189	/// assert_eq!(t.current_num_threads(), 7);
190	/// ```
191	#[macro_export]
192	macro_rules! thread_pool {
193	() => {
194	rayon::ThreadPoolBuilder::new()
195	.build()
196	.expect("Cannot build a ThreadPool with default parameters")
197	};
198	($num_threads:expr) => {
199	rayon::ThreadPoolBuilder::new()
200	.num_threads($num_threads)
201	.build()
202	.unwrap_or_else(\|_\| {	×
203	panic!(	×
204	"Cannot build a ThreadPool with default parameters and {} threads",	×
205	$num_threads,
206	)
207	})
208	};
209	}

vigna / webgraph-rs / 18279564945

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