From 9ced08956902e7aeb6fd52c05fbac935de11c699 Mon Sep 17 00:00:00 2001 From: Taras Tsugrii Date: Sat, 29 Jul 2023 19:42:22 -0700 Subject: [rustc_data_structures] Use partition_point to find binary_search_slice end. --- .../src/binary_search_util/mod.rs | 29 ++++++---------------- 1 file changed, 8 insertions(+), 21 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/binary_search_util/mod.rs b/compiler/rustc_data_structures/src/binary_search_util/mod.rs index bc8a6b9eac0..332ad8af33b 100644 --- a/compiler/rustc_data_structures/src/binary_search_util/mod.rs +++ b/compiler/rustc_data_structures/src/binary_search_util/mod.rs @@ -14,31 +14,18 @@ where let start = data.partition_point(|x| key_fn(x) < *key); // At this point `start` either points at the first entry with equal or // greater key or is equal to `size` in case all elements have smaller keys + // Invariant: start == size || key_fn(&data[start]) >= *key if start == size || key_fn(&data[start]) != *key { return &[]; }; + // Invariant: start < size && key_fn(&data[start]) == *key - // Now search forward to find the *last* one. - let mut end = start; - let mut previous = start; - let mut step = 1; - loop { - end = end.saturating_add(step).min(size); - if end == size || key_fn(&data[end]) != *key { - break; - } - previous = end; - step *= 2; - } - step = end - previous; - while step > 1 { - let half = step / 2; - let mid = end - half; - if key_fn(&data[mid]) != *key { - end = mid; - } - step -= half; - } + // Find the first entry with key > `key`. Skip `start` entries since + // key_fn(&data[start]) == *key + // Invariant: offset == size || key_fn(&data[offset]) >= *key + let offset = start + 1; + let end = data[offset..].partition_point(|x| key_fn(x) <= *key) + offset; + // Invariant: end == size || key_fn(&data[end]) > *key &data[start..end] } -- cgit 1.4.1-3-g733a5 From 97bc528877b698df2f61dd743b1a155ca3f5eead Mon Sep 17 00:00:00 2001 From: Taras Tsugrii Date: Sun, 5 Nov 2023 17:35:37 -0600 Subject: Remove invariant comments --- compiler/rustc_data_structures/src/binary_search_util/mod.rs | 4 ---- 1 file changed, 4 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/binary_search_util/mod.rs b/compiler/rustc_data_structures/src/binary_search_util/mod.rs index 332ad8af33b..1c6e227cec4 100644 --- a/compiler/rustc_data_structures/src/binary_search_util/mod.rs +++ b/compiler/rustc_data_structures/src/binary_search_util/mod.rs @@ -14,18 +14,14 @@ where let start = data.partition_point(|x| key_fn(x) < *key); // At this point `start` either points at the first entry with equal or // greater key or is equal to `size` in case all elements have smaller keys - // Invariant: start == size || key_fn(&data[start]) >= *key if start == size || key_fn(&data[start]) != *key { return &[]; }; - // Invariant: start < size && key_fn(&data[start]) == *key // Find the first entry with key > `key`. Skip `start` entries since // key_fn(&data[start]) == *key - // Invariant: offset == size || key_fn(&data[offset]) >= *key let offset = start + 1; let end = data[offset..].partition_point(|x| key_fn(x) <= *key) + offset; - // Invariant: end == size || key_fn(&data[end]) > *key &data[start..end] } -- cgit 1.4.1-3-g733a5 From 510fcd318b61d0e45165cdb0de880ee2f4f9cde2 Mon Sep 17 00:00:00 2001 From: Mark Rousskov Date: Wed, 17 Jan 2024 17:09:04 -0500 Subject: Use UnhashMap for a few more maps This avoids hashing data that's already hashed. --- compiler/rustc_data_structures/src/hashes.rs | 12 +++++++++++- compiler/rustc_data_structures/src/stable_hasher.rs | 14 +++++++++++++- compiler/rustc_span/src/hygiene.rs | 4 ++-- compiler/rustc_span/src/source_map.rs | 4 ++-- 4 files changed, 28 insertions(+), 6 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/hashes.rs b/compiler/rustc_data_structures/src/hashes.rs index 291ee5bbe26..1564eeb4bae 100644 --- a/compiler/rustc_data_structures/src/hashes.rs +++ b/compiler/rustc_data_structures/src/hashes.rs @@ -75,11 +75,21 @@ impl fmt::LowerHex for Hash64 { } } -#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Default)] +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default)] pub struct Hash128 { inner: u128, } +// We expect Hash128 to be well mixed. So there's no point in hashing both parts. +// +// This also allows using Hash128-containing types in UnHash-based hashmaps, which would otherwise +// debug_assert! that we're hashing more than a single u64. +impl std::hash::Hash for Hash128 { + fn hash(&self, h: &mut H) { + h.write_u64(self.truncate().as_u64()); + } +} + impl Hash128 { #[inline] pub fn truncate(self) -> Hash64 { diff --git a/compiler/rustc_data_structures/src/stable_hasher.rs b/compiler/rustc_data_structures/src/stable_hasher.rs index afe26f80de8..52304c72a2f 100644 --- a/compiler/rustc_data_structures/src/stable_hasher.rs +++ b/compiler/rustc_data_structures/src/stable_hasher.rs @@ -314,7 +314,19 @@ impl_stable_traits_for_trivial_type!(char); impl_stable_traits_for_trivial_type!(()); impl_stable_traits_for_trivial_type!(Hash64); -impl_stable_traits_for_trivial_type!(Hash128); + +// We need a custom impl as the default hash function will only hash half the bits. For stable +// hashing we want to hash the full 128-bit hash. +impl HashStable for Hash128 { + #[inline] + fn hash_stable(&self, _: &mut CTX, hasher: &mut StableHasher) { + self.as_u128().hash(hasher); + } +} + +unsafe impl StableOrd for Hash128 { + const CAN_USE_UNSTABLE_SORT: bool = true; +} impl HashStable for ! { fn hash_stable(&self, _ctx: &mut CTX, _hasher: &mut StableHasher) { diff --git a/compiler/rustc_span/src/hygiene.rs b/compiler/rustc_span/src/hygiene.rs index d03965b539c..5be794f3e17 100644 --- a/compiler/rustc_span/src/hygiene.rs +++ b/compiler/rustc_span/src/hygiene.rs @@ -330,7 +330,7 @@ pub(crate) struct HygieneData { /// would have collisions without a disambiguator. /// The keys of this map are always computed with `ExpnData.disambiguator` /// set to 0. - expn_data_disambiguators: FxHashMap, + expn_data_disambiguators: UnhashMap, } impl HygieneData { @@ -359,7 +359,7 @@ impl HygieneData { dollar_crate_name: kw::DollarCrate, }], syntax_context_map: FxHashMap::default(), - expn_data_disambiguators: FxHashMap::default(), + expn_data_disambiguators: UnhashMap::default(), } } diff --git a/compiler/rustc_span/src/source_map.rs b/compiler/rustc_span/src/source_map.rs index 72a8b23721d..df7635e447d 100644 --- a/compiler/rustc_span/src/source_map.rs +++ b/compiler/rustc_span/src/source_map.rs @@ -10,8 +10,8 @@ //! information, source code snippets, etc. use crate::*; -use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::sync::{IntoDynSyncSend, MappedReadGuard, ReadGuard, RwLock}; +use rustc_data_structures::unhash::UnhashMap; use std::fs; use std::io::{self, BorrowedBuf, Read}; use std::path::{self}; @@ -164,7 +164,7 @@ impl FileLoader for RealFileLoader { #[derive(Default)] struct SourceMapFiles { source_files: monotonic::MonotonicVec>, - stable_id_to_source_file: FxHashMap>, + stable_id_to_source_file: UnhashMap>, } pub struct SourceMap { -- cgit 1.4.1-3-g733a5 From 63446d00ee2005125b1e4a7c3f00547101065709 Mon Sep 17 00:00:00 2001 From: John Kåre Alsaker Date: Tue, 26 Sep 2023 22:34:09 +0200 Subject: Remove `OneThread` --- compiler/rustc_data_structures/src/marker.rs | 1 - compiler/rustc_data_structures/src/sync.rs | 56 ---------------------------- compiler/rustc_session/src/session.rs | 15 ++++---- 3 files changed, 8 insertions(+), 64 deletions(-) (limited to 'compiler/rustc_data_structures/src') diff --git a/compiler/rustc_data_structures/src/marker.rs b/compiler/rustc_data_structures/src/marker.rs index 266e54604a6..a9ccfbed411 100644 --- a/compiler/rustc_data_structures/src/marker.rs +++ b/compiler/rustc_data_structures/src/marker.rs @@ -177,7 +177,6 @@ cfg_match! { [Vec where T: DynSync, A: std::alloc::Allocator + DynSync] [Box where T: ?Sized + DynSync, A: std::alloc::Allocator + DynSync] [crate::sync::RwLock where T: DynSend + DynSync] - [crate::sync::OneThread where T] [crate::sync::WorkerLocal where T: DynSend] [crate::intern::Interned<'a, T> where 'a, T: DynSync] [crate::tagged_ptr::CopyTaggedPtr where P: Sync + crate::tagged_ptr::Pointer, T: Sync + crate::tagged_ptr::Tag, const CP: bool] diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index 48edfba8da0..adcb6ceaebf 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -43,7 +43,6 @@ pub use crate::marker::*; use std::collections::HashMap; use std::hash::{BuildHasher, Hash}; -use std::ops::{Deref, DerefMut}; mod lock; pub use lock::{Lock, LockGuard, Mode}; @@ -309,8 +308,6 @@ cfg_match! { use parking_lot::RwLock as InnerRwLock; - use std::thread; - /// This makes locks panic if they are already held. /// It is only useful when you are running in a single thread const ERROR_CHECKING: bool = false; @@ -445,56 +442,3 @@ impl Clone for RwLock { RwLock::new(self.borrow().clone()) } } - -/// A type which only allows its inner value to be used in one thread. -/// It will panic if it is used on multiple threads. -#[derive(Debug)] -pub struct OneThread { - #[cfg(parallel_compiler)] - thread: thread::ThreadId, - inner: T, -} - -#[cfg(parallel_compiler)] -unsafe impl std::marker::Sync for OneThread {} -#[cfg(parallel_compiler)] -unsafe impl std::marker::Send for OneThread {} - -impl OneThread { - #[inline(always)] - fn check(&self) { - #[cfg(parallel_compiler)] - assert_eq!(thread::current().id(), self.thread); - } - - #[inline(always)] - pub fn new(inner: T) -> Self { - OneThread { - #[cfg(parallel_compiler)] - thread: thread::current().id(), - inner, - } - } - - #[inline(always)] - pub fn into_inner(value: Self) -> T { - value.check(); - value.inner - } -} - -impl Deref for OneThread { - type Target = T; - - fn deref(&self) -> &T { - self.check(); - &self.inner - } -} - -impl DerefMut for OneThread { - fn deref_mut(&mut self) -> &mut T { - self.check(); - &mut self.inner - } -} diff --git a/compiler/rustc_session/src/session.rs b/compiler/rustc_session/src/session.rs index 3f6c70a18d3..cba6ce0d235 100644 --- a/compiler/rustc_session/src/session.rs +++ b/compiler/rustc_session/src/session.rs @@ -14,7 +14,9 @@ use rustc_data_structures::flock; use rustc_data_structures::fx::{FxHashMap, FxIndexSet}; use rustc_data_structures::jobserver::{self, Client}; use rustc_data_structures::profiling::{SelfProfiler, SelfProfilerRef}; -use rustc_data_structures::sync::{AtomicU64, DynSend, DynSync, Lock, Lrc, OneThread}; +use rustc_data_structures::sync::{ + AtomicU64, DynSend, DynSync, Lock, Lrc, MappedReadGuard, ReadGuard, RwLock, +}; use rustc_errors::annotate_snippet_emitter_writer::AnnotateSnippetEmitter; use rustc_errors::emitter::{DynEmitter, HumanEmitter, HumanReadableErrorType}; use rustc_errors::json::JsonEmitter; @@ -35,7 +37,6 @@ use rustc_target::spec::{ }; use std::any::Any; -use std::cell::{self, RefCell}; use std::env; use std::fmt; use std::ops::{Div, Mul}; @@ -149,7 +150,7 @@ pub struct Session { /// Input, input file path and output file path to this compilation process. pub io: CompilerIO, - incr_comp_session: OneThread>, + incr_comp_session: RwLock, /// Used by `-Z self-profile`. pub prof: SelfProfilerRef, @@ -533,9 +534,9 @@ impl Session { *incr_comp_session = IncrCompSession::InvalidBecauseOfErrors { session_directory }; } - pub fn incr_comp_session_dir(&self) -> cell::Ref<'_, PathBuf> { + pub fn incr_comp_session_dir(&self) -> MappedReadGuard<'_, PathBuf> { let incr_comp_session = self.incr_comp_session.borrow(); - cell::Ref::map(incr_comp_session, |incr_comp_session| match *incr_comp_session { + ReadGuard::map(incr_comp_session, |incr_comp_session| match *incr_comp_session { IncrCompSession::NotInitialized => panic!( "trying to get session directory from `IncrCompSession`: {:?}", *incr_comp_session, @@ -548,7 +549,7 @@ impl Session { }) } - pub fn incr_comp_session_dir_opt(&self) -> Option> { + pub fn incr_comp_session_dir_opt(&self) -> Option> { self.opts.incremental.as_ref().map(|_| self.incr_comp_session_dir()) } @@ -1176,7 +1177,7 @@ pub fn build_session( parse_sess, sysroot, io, - incr_comp_session: OneThread::new(RefCell::new(IncrCompSession::NotInitialized)), + incr_comp_session: RwLock::new(IncrCompSession::NotInitialized), prof, code_stats: Default::default(), optimization_fuel, -- cgit 1.4.1-3-g733a5