20343291362

Committed 18 Dec 2025 04:08PM UTC coverage: 74.393%. First build

Build # 20343291362

Build Type

Pull #98

github

Committed by

web-flow

Commit Message

Merge 745a3b5c5 into 1e200414b

Pull Request Pull Request #98: Add RankUnchecked::prefetch

Run Details

0 of 20 new or added lines in 4 files covered. (0.0%)

4471 of 6010 relevant lines covered (74.39%)

122541723.78 hits per line

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

62.86

/src/utils/mod.rs

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

//! Utility traits and implementations.
use common_traits::{Atomic, IntoAtomic};

pub mod lenders;
pub use lenders::*;

pub mod sig_store;
use rand::{RngCore, SeedableRng};
pub use sig_store::*;

pub mod fair_chunks;
pub use fair_chunks::FairChunks;

pub mod mod2_sys;
pub use mod2_sys::*;

/// An error type raised when attempting to cast a non-atomic type to an atomic
/// type with incompatible alignments.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct CannotCastToAtomicError<T: IntoAtomic>(core::marker::PhantomData<T>);

impl<T: IntoAtomic> Default for CannotCastToAtomicError<T> {
    fn default() -> Self {
        CannotCastToAtomicError(core::marker::PhantomData)
    }
}

impl<T: IntoAtomic> core::fmt::Display for CannotCastToAtomicError<T> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        assert_ne!(
            core::mem::align_of::<T>(),
            core::mem::align_of::<T::AtomicType>()
        );
        write!(
            f,
            "Cannot cast {} (align_of: {}) to atomic type {} (align_of: {}) because the have incompatible alignments",
            core::any::type_name::<T>(),
            core::mem::align_of::<T>(),
            core::any::type_name::<T::AtomicType>(),
            core::mem::align_of::<T::AtomicType>()
        )
    }
}

impl<T: IntoAtomic + core::fmt::Debug> core::error::Error for CannotCastToAtomicError<T> {}

/// Transmutes a vector of elements of non-atomic type into a vector of elements
/// of the associated atomic type.
///
/// [It is not safe to transmute a
/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
/// implements a correct transmutation of the vector content.
///
/// Since the alignment of the atomic type might be greater than that of the
/// non-atomic type, we can only perform a direct transmutation when the
/// alignment of the atomic type is greater than or equal to that of the
/// non-atomic type. In this case, we simply reinterpret the vector's pointer.
///
/// Otherwise, we fall back to a safe but less efficient method that allocates a
/// new vector and copies the elements one by one. The compiler might be able
/// to optimize this case away in some situations.
pub fn transmute_vec_into_atomic<W: IntoAtomic>(v: Vec<W>) -> Vec<W::AtomicType> {
    if core::mem::align_of::<W::AtomicType>() == core::mem::align_of::<W>() {
        let mut v = std::mem::ManuallyDrop::new(v);
        unsafe { Vec::from_raw_parts(v.as_mut_ptr() as *mut W::AtomicType, v.len(), v.capacity()) }
    } else {
        v.into_iter().map(W::to_atomic).collect()
    }
}

/// Transmutes a vector of elements of atomic type into a vector of elements of
/// the associated atomic non-atomic type.
///
/// [It is not safe to transmute a
/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
/// implements a correct transmutation of the vector content.
pub fn transmute_vec_from_atomic<A: Atomic>(v: Vec<A>) -> Vec<A::NonAtomicType> {
    let mut v = std::mem::ManuallyDrop::new(v);
    // this is always safe because atomic types have bigger or equal alignment
    // than their non-atomic counterparts
    unsafe {
        Vec::from_raw_parts(
            v.as_mut_ptr() as *mut A::NonAtomicType,
            v.len(),
            v.capacity(),
        )
    }
}

/// Transmutes a boxed slice of elements of non-atomic type into a boxed slice
/// of elements of the associated atomic type.
///
/// See [`transmute_vec_into_atomic`] for details.
pub fn transmute_boxed_slice_into_atomic<W: IntoAtomic + Copy>(
    b: Box<[W]>,
) -> Box<[W::AtomicType]> {
    if core::mem::align_of::<W::AtomicType>() == core::mem::align_of::<W>() {
        let mut b = std::mem::ManuallyDrop::new(b);
        unsafe { Box::from_raw(b.as_mut() as *mut [W] as *mut [W::AtomicType]) }
    } else {
        IntoIterator::into_iter(b).map(W::to_atomic).collect()
    }
}

/// Transmutes a boxed slice of values of atomic type into a boxed slice of
/// values of the associated non-atomic type.
///
/// [It is not safe to transmute a
/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
/// implements a correct transmutation of the vector content.
pub fn transmute_boxed_slice_from_atomic<A: Atomic>(b: Box<[A]>) -> Box<[A::NonAtomicType]> {
    let mut b = std::mem::ManuallyDrop::new(b);
    unsafe { Box::from_raw(b.as_mut() as *mut [A] as *mut [A::NonAtomicType]) }
}

pub struct Mwc192 {
    x: u64,
    y: u64,
    c: u64,
}

impl Mwc192 {
    const MWC_A2: u64 = 0xffa04e67b3c95d86;
}

impl RngCore for Mwc192 {
    fn next_u64(&mut self) -> u64 {
        let result = self.y;
        let t = (Self::MWC_A2 as u128)
            .wrapping_mul(self.x as u128)
            .wrapping_add(self.c as u128);
        self.x = self.y;
        self.y = t as u64;
        self.c = (t >> 64) as u64;
        result
    }

    fn next_u32(&mut self) -> u32 {
        self.next_u64() as u32
    }

    fn fill_bytes(&mut self, dst: &mut [u8]) {
        let mut left = dst;
        while left.len() >= 8 {
            let (l, r) = { left }.split_at_mut(8);
            left = r;
            let chunk: [u8; 8] = self.next_u64().to_le_bytes();
            l.copy_from_slice(&chunk);
        }
        let n = left.len();
        if n > 4 {
            let chunk: [u8; 8] = self.next_u64().to_le_bytes();
            left.copy_from_slice(&chunk[..n]);
        } else if n > 0 {
            let chunk: [u8; 4] = self.next_u32().to_le_bytes();
            left.copy_from_slice(&chunk[..n]);
        }
    }
}

impl SeedableRng for Mwc192 {
    type Seed = [u8; 16];

    fn from_seed(seed: Self::Seed) -> Self {
        let mut s0 = [0; 8];
        s0.copy_from_slice(&seed[..8]);
        let mut s1 = [0; 8];
        s1.copy_from_slice(&seed[8..]);

        Mwc192 {
            x: u64::from_ne_bytes(s0),
            y: u64::from_ne_bytes(s1),
            c: 1,
        }
    }
}

/// Prefetch the cache line containing `s[index]` into all levels of the cache.
pub fn prefetch_index<T>(s: &[T], index: usize) {
    let ptr = s.as_ptr().wrapping_add(index) as *const i8;
    #[cfg(target_arch = "x86_64")]
    unsafe {
        std::arch::x86_64::_mm_prefetch(ptr, std::arch::x86_64::_MM_HINT_T0);
    }
    #[cfg(target_arch = "x86")]
    unsafe {
        std::arch::x86::_mm_prefetch(ptr, std::arch::x86::_MM_HINT_T0);
    }
    #[cfg(target_arch = "aarch64")]
    unsafe {
        std::arch::aarch64::_prefetch(ptr, std::arch::aarch64::_PREFETCH_LOCALITY3);
    }
    #[cfg(not(any(target_arch = "x86_64", target_arch = "x86", target_arch = "aarch64")))]
    {
        // Do nothing.
    }
}

1	/*
2	*
3	* SPDX-FileCopyrightText: 2025 Inria
4	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
5	*
6	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7	*/
8
9	//! Utility traits and implementations.
10	use common_traits::{Atomic, IntoAtomic};
11
12	pub mod lenders;
13	pub use lenders::*;
14
15	pub mod sig_store;
16	use rand::{RngCore, SeedableRng};
17	pub use sig_store::*;
18
19	pub mod fair_chunks;
20	pub use fair_chunks::FairChunks;
21
22	pub mod mod2_sys;
23	pub use mod2_sys::*;
24
25	/// An error type raised when attempting to cast a non-atomic type to an atomic
26	/// type with incompatible alignments.
27	#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
28	pub struct CannotCastToAtomicError<T: IntoAtomic>(core::marker::PhantomData<T>);
29
30	impl<T: IntoAtomic> Default for CannotCastToAtomicError<T> {
31	fn default() -> Self {	×
32	CannotCastToAtomicError(core::marker::PhantomData)	×
33	}
34	}
35
36	impl<T: IntoAtomic> core::fmt::Display for CannotCastToAtomicError<T> {
37	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {	×
38	assert_ne!(	×
39	core::mem::align_of::<T>(),	×
40	core::mem::align_of::<T::AtomicType>()	×
41	);
42	write!(	×
43	f,	×
44	"Cannot cast {} (align_of: {}) to atomic type {} (align_of: {}) because the have incompatible alignments",
45	core::any::type_name::<T>(),	×
46	core::mem::align_of::<T>(),	×
47	core::any::type_name::<T::AtomicType>(),	×
48	core::mem::align_of::<T::AtomicType>()	×
49	)
50	}
51	}
52
53	impl<T: IntoAtomic + core::fmt::Debug> core::error::Error for CannotCastToAtomicError<T> {}
54
55	/// Transmutes a vector of elements of non-atomic type into a vector of elements
56	/// of the associated atomic type.
57	///
58	/// [It is not safe to transmute a
59	/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
60	/// implements a correct transmutation of the vector content.
61	///
62	/// Since the alignment of the atomic type might be greater than that of the
63	/// non-atomic type, we can only perform a direct transmutation when the
64	/// alignment of the atomic type is greater than or equal to that of the
65	/// non-atomic type. In this case, we simply reinterpret the vector's pointer.
66	///
67	/// Otherwise, we fall back to a safe but less efficient method that allocates a
68	/// new vector and copies the elements one by one. The compiler might be able
69	/// to optimize this case away in some situations.
70	pub fn transmute_vec_into_atomic<W: IntoAtomic>(v: Vec<W>) -> Vec<W::AtomicType> {	371✔
71	if core::mem::align_of::<W::AtomicType>() == core::mem::align_of::<W>() {	371✔
72	let mut v = std::mem::ManuallyDrop::new(v);	1,113✔
73	unsafe { Vec::from_raw_parts(v.as_mut_ptr() as *mut W::AtomicType, v.len(), v.capacity()) }	1,484✔
74	} else {
75	v.into_iter().map(W::to_atomic).collect()	×
76	}
77	}
78
79	/// Transmutes a vector of elements of atomic type into a vector of elements of
80	/// the associated atomic non-atomic type.
81	///
82	/// [It is not safe to transmute a
83	/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
84	/// implements a correct transmutation of the vector content.
85	pub fn transmute_vec_from_atomic<A: Atomic>(v: Vec<A>) -> Vec<A::NonAtomicType> {	546✔
86	let mut v = std::mem::ManuallyDrop::new(v);	1,638✔
87	// this is always safe because atomic types have bigger or equal alignment
88	// than their non-atomic counterparts
89	unsafe {
90	Vec::from_raw_parts(
91	v.as_mut_ptr() as *mut A::NonAtomicType,	546✔
92	v.len(),	546✔
93	v.capacity(),	546✔
94	)
95	}
96	}
97
98	/// Transmutes a boxed slice of elements of non-atomic type into a boxed slice
99	/// of elements of the associated atomic type.
100	///
101	/// See [`transmute_vec_into_atomic`] for details.
102	pub fn transmute_boxed_slice_into_atomic<W: IntoAtomic + Copy>(	2✔
103	b: Box<[W]>,
104	) -> Box<[W::AtomicType]> {
105	if core::mem::align_of::<W::AtomicType>() == core::mem::align_of::<W>() {	2✔
106	let mut b = std::mem::ManuallyDrop::new(b);	6✔
107	unsafe { Box::from_raw(b.as_mut() as mut [W] as mut [W::AtomicType]) }	4✔
108	} else {
109	IntoIterator::into_iter(b).map(W::to_atomic).collect()	×
110	}
111	}
112
113	/// Transmutes a boxed slice of values of atomic type into a boxed slice of
114	/// values of the associated non-atomic type.
115	///
116	/// [It is not safe to transmute a
117	/// vector](https://doc.rust-lang.org/std/mem/fn.transmute.html). This method
118	/// implements a correct transmutation of the vector content.
119	pub fn transmute_boxed_slice_from_atomic<A: Atomic>(b: Box<[A]>) -> Box<[A::NonAtomicType]> {	42✔
120	let mut b = std::mem::ManuallyDrop::new(b);	126✔
121	unsafe { Box::from_raw(b.as_mut() as mut [A] as mut [A::NonAtomicType]) }	84✔
122	}
123
124	pub struct Mwc192 {
125	x: u64,
126	y: u64,
127	c: u64,
128	}
129
130	impl Mwc192 {
131	const MWC_A2: u64 = 0xffa04e67b3c95d86;
132	}
133
134	impl RngCore for Mwc192 {
135	fn next_u64(&mut self) -> u64 {	4,735,876✔
136	let result = self.y;	9,471,752✔
137	let t = (Self::MWC_A2 as u128)	9,471,752✔
138	.wrapping_mul(self.x as u128)	9,471,752✔
139	.wrapping_add(self.c as u128);	9,471,752✔
140	self.x = self.y;	4,735,876✔
141	self.y = t as u64;	4,735,876✔
142	self.c = (t >> 64) as u64;	4,735,876✔
143	result	4,735,876✔
144	}
145
146	fn next_u32(&mut self) -> u32 {	×
147	self.next_u64() as u32	×
148	}
149
150	fn fill_bytes(&mut self, dst: &mut [u8]) {	263✔
151	let mut left = dst;	526✔
152	while left.len() >= 8 {	9,471,819✔
153	let (l, r) = { left }.split_at_mut(8);	18,943,112✔
154	left = r;	9,471,556✔
155	let chunk: [u8; 8] = self.next_u64().to_le_bytes();	28,414,668✔
156	l.copy_from_slice(&chunk);	9,471,556✔
157	}
158	let n = left.len();	789✔
159	if n > 4 {	361✔
160	let chunk: [u8; 8] = self.next_u64().to_le_bytes();	588✔
161	left.copy_from_slice(&chunk[..n]);	294✔
162	} else if n > 0 {	263✔
163	let chunk: [u8; 4] = self.next_u32().to_le_bytes();	×
164	left.copy_from_slice(&chunk[..n]);	×
165	}
166	}
167	}
168
169	impl SeedableRng for Mwc192 {
170	type Seed = [u8; 16];
171
172	fn from_seed(seed: Self::Seed) -> Self {	263✔
173	let mut s0 = [0; 8];	526✔
174	s0.copy_from_slice(&seed[..8]);	789✔
175	let mut s1 = [0; 8];	526✔
176	s1.copy_from_slice(&seed[8..]);	789✔
177
178	Mwc192 {
179	x: u64::from_ne_bytes(s0),	789✔
180	y: u64::from_ne_bytes(s1),	263✔
181	c: 1,
182	}
183	}
184	}
185
186	/// Prefetch the cache line containing `s[index]` into all levels of the cache.
NEW 187	pub fn prefetch_index<T>(s: &[T], index: usize) {	×
NEW 188	let ptr = s.as_ptr().wrapping_add(index) as *const i8;	×
NEW 189	#[cfg(target_arch = "x86_64")]	×
190	unsafe {
NEW 191	std::arch::x86_64::_mm_prefetch(ptr, std::arch::x86_64::_MM_HINT_T0);	×
192	}
NEW 193	#[cfg(target_arch = "x86")]	×
194	unsafe {
NEW 195	std::arch::x86::_mm_prefetch(ptr, std::arch::x86::_MM_HINT_T0);	×
196	}
NEW 197	#[cfg(target_arch = "aarch64")]	×
198	unsafe {
NEW 199	std::arch::aarch64::_prefetch(ptr, std::arch::aarch64::_PREFETCH_LOCALITY3);	×
200	}
201	#[cfg(not(any(target_arch = "x86_64", target_arch = "x86", target_arch = "aarch64")))]
202	{
203	// Do nothing.
204	}
205	}

vigna / sux-rs / 20343291362

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