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') 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') 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 ac58f9ae034eaba1ae2efd27d43d5e2328260461 Mon Sep 17 00:00:00 2001 From: Michael Woerister Date: Sat, 13 Jan 2024 16:32:03 +0100 Subject: Update measureme crate to version 11 --- Cargo.lock | 4 ++-- compiler/rustc_codegen_llvm/Cargo.toml | 2 +- compiler/rustc_data_structures/Cargo.toml | 2 +- compiler/rustc_middle/Cargo.toml | 2 +- compiler/rustc_query_impl/Cargo.toml | 2 +- src/tools/miri/Cargo.toml | 2 +- 6 files changed, 7 insertions(+), 7 deletions(-) (limited to 'compiler/rustc_data_structures') diff --git a/Cargo.lock b/Cargo.lock index 440def72768..697e8c81bda 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2366,9 +2366,9 @@ dependencies = [ [[package]] name = "measureme" -version = "10.1.2" +version = "11.0.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "45e381dcdad44c3c435f8052b08c5c4a1449c48ab56f312345eae12d7a693dbe" +checksum = "dfa4a40f09af7aa6faef38285402a78847d0d72bf8827006cd2a332e1e6e4a8d" dependencies = [ "log", "memmap2", diff --git a/compiler/rustc_codegen_llvm/Cargo.toml b/compiler/rustc_codegen_llvm/Cargo.toml index c12142e302d..3948a49ee2a 100644 --- a/compiler/rustc_codegen_llvm/Cargo.toml +++ b/compiler/rustc_codegen_llvm/Cargo.toml @@ -11,7 +11,7 @@ test = false bitflags = "2.4.1" itertools = "0.11" libc = "0.2" -measureme = "10.0.0" +measureme = "11" object = { version = "0.32.0", default-features = false, features = ["std", "read"] } rustc-demangle = "0.1.21" rustc_ast = { path = "../rustc_ast" } diff --git a/compiler/rustc_data_structures/Cargo.toml b/compiler/rustc_data_structures/Cargo.toml index 23949deaade..9d598c32e6f 100644 --- a/compiler/rustc_data_structures/Cargo.toml +++ b/compiler/rustc_data_structures/Cargo.toml @@ -13,7 +13,7 @@ indexmap = { version = "2.0.0" } itertools = "0.11" jobserver_crate = { version = "0.1.27", package = "jobserver" } libc = "0.2" -measureme = "10.0.0" +measureme = "11" rustc-hash = "1.1.0" rustc-rayon = { version = "0.5.0", optional = true } rustc-rayon-core = { version = "0.5.0", optional = true } diff --git a/compiler/rustc_middle/Cargo.toml b/compiler/rustc_middle/Cargo.toml index 8e6ca645f80..82e56c9cbe2 100644 --- a/compiler/rustc_middle/Cargo.toml +++ b/compiler/rustc_middle/Cargo.toml @@ -10,7 +10,7 @@ derive_more = "0.99.17" either = "1.5.0" field-offset = "0.3.5" gsgdt = "0.1.2" -measureme = "10.0.0" +measureme = "11" polonius-engine = "0.13.0" rustc-rayon = { version = "0.5.0", optional = true } rustc-rayon-core = { version = "0.5.0", optional = true } diff --git a/compiler/rustc_query_impl/Cargo.toml b/compiler/rustc_query_impl/Cargo.toml index 88eb4603069..c57f22a0da2 100644 --- a/compiler/rustc_query_impl/Cargo.toml +++ b/compiler/rustc_query_impl/Cargo.toml @@ -6,7 +6,7 @@ edition = "2021" [dependencies] # tidy-alphabetical-start field-offset = "0.3.5" -measureme = "10.0.0" +measureme = "11" rustc-rayon-core = { version = "0.5.0", optional = true } rustc_data_structures = { path = "../rustc_data_structures" } rustc_errors = { path = "../rustc_errors" } diff --git a/src/tools/miri/Cargo.toml b/src/tools/miri/Cargo.toml index 3da751c69a9..a65010b055b 100644 --- a/src/tools/miri/Cargo.toml +++ b/src/tools/miri/Cargo.toml @@ -24,7 +24,7 @@ log = "0.4" rand = "0.8" smallvec = "1.7" aes = { version = "0.8.3", features = ["hazmat"] } -measureme = "10.0.0" +measureme = "11" ctrlc = "3.2.5" # Copied from `compiler/rustc/Cargo.toml`. -- 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') 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') 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