X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fstacked_borrows%2Fstack.rs;h=1b05471618a52bc4f2507ee9c0f40e88b513a696;hb=4eff60ad6e37cd8f37e994d42c8c1ce271670bd4;hp=6e0d166086fc7ec1d95cd0ff7164b1f6fc7aea60;hpb=17acc3f71cf8a8e4f2b3c82d453982dd08e13d07;p=rust.git diff --git a/src/stacked_borrows/stack.rs b/src/stacked_borrows/stack.rs index 6e0d166086f..1b05471618a 100644 --- a/src/stacked_borrows/stack.rs +++ b/src/stacked_borrows/stack.rs @@ -27,8 +27,7 @@ pub struct Stack { /// we never have the unknown-to-known boundary in an SRW group. unknown_bottom: Option, - /// A small LRU cache of searches of the borrow stack. This only caches accesses of `Tagged`, - /// because those are unique in the stack. + /// A small LRU cache of searches of the borrow stack. #[cfg(feature = "stack-cache")] cache: StackCache, /// On a read, we need to disable all `Unique` above the granting item. We can avoid most of @@ -38,14 +37,18 @@ pub struct Stack { } /// A very small cache of searches of the borrow stack -/// This maps tags to locations in the borrow stack. Any use of this still needs to do a +/// This maps items to locations in the borrow stack. Any use of this still needs to do a /// probably-cold random access into the borrow stack to figure out what `Permission` an /// `SbTag` grants. We could avoid this by also storing the `Permission` in the cache, but /// most lookups into the cache are immediately followed by access of the full borrow stack anyway. +/// +/// It may seem like maintaining this cache is a waste for small stacks, but +/// (a) iterating over small fixed-size arrays is super fast, and (b) empirically this helps *a lot*, +/// probably because runtime is dominated by large stacks. #[cfg(feature = "stack-cache")] #[derive(Clone, Debug)] struct StackCache { - tags: [SbTag; CACHE_LEN], // Hot in find_granting + items: [Item; CACHE_LEN], // Hot in find_granting idx: [usize; CACHE_LEN], // Hot in grant } @@ -53,14 +56,14 @@ struct StackCache { impl StackCache { /// When a tag is used, we call this function to add or refresh it in the cache. /// - /// We use position in the cache to represent how recently a tag was used; the first position + /// We use the position in the cache to represent how recently a tag was used; the first position /// is the most recently used tag. So an add shifts every element towards the end, and inserts /// the new element at the start. We lose the last element. - /// This strategy is effective at keeping the most-accessed tags in the cache, but it costs a + /// This strategy is effective at keeping the most-accessed items in the cache, but it costs a /// linear shift across the entire cache when we add a new tag. - fn add(&mut self, idx: usize, tag: SbTag) { - self.tags.copy_within(0..CACHE_LEN - 1, 1); - self.tags[0] = tag; + fn add(&mut self, idx: usize, item: Item) { + self.items.copy_within(0..CACHE_LEN - 1, 1); + self.items[0] = item; self.idx.copy_within(0..CACHE_LEN - 1, 1); self.idx[0] = idx; } @@ -77,18 +80,20 @@ impl Eq for Stack {} impl<'tcx> Stack { /// Panics if any of the caching mechanisms have broken, - /// - The StackCache indices don't refer to the parallel tags, - /// - There are no Unique tags outside of first_unique..last_unique + /// - The StackCache indices don't refer to the parallel items, + /// - There are no Unique items outside of first_unique..last_unique #[cfg(feature = "expensive-debug-assertions")] fn verify_cache_consistency(&self) { - if self.borrows.len() > CACHE_LEN { - for (tag, stack_idx) in self.cache.tags.iter().zip(self.cache.idx.iter()) { - assert_eq!(self.borrows[*stack_idx].tag, *tag); + // Only a full cache needs to be valid. Also see the comments in find_granting_cache + // and set_unknown_bottom. + if self.borrows.len() >= CACHE_LEN { + for (tag, stack_idx) in self.cache.items.iter().zip(self.cache.idx.iter()) { + assert_eq!(self.borrows[*stack_idx], *tag); } } for (idx, item) in self.borrows.iter().enumerate() { - if item.perm == Permission::Unique { + if item.perm() == Permission::Unique { assert!( self.unique_range.contains(&idx), "{:?} {:?}", @@ -104,7 +109,7 @@ fn verify_cache_consistency(&self) { /// index is given it means the match was *not* in the known part of the stack. /// `Ok(None)` indicates it matched the "unknown" part of the stack. /// `Err` indicates it was not found. - pub fn find_granting( + pub(super) fn find_granting( &mut self, access: AccessKind, tag: SbTagExtra, @@ -123,7 +128,7 @@ pub fn find_granting( .rev() // search top-to-bottom .find_map(|(idx, item)| { // If the item fits and *might* be this wildcard, use it. - if item.perm.grants(access) && exposed_tags.contains(&item.tag) { + if item.perm().grants(access) && exposed_tags.contains(&item.tag()) { Some(idx) } else { None @@ -154,11 +159,11 @@ fn find_granting_tagged(&mut self, access: AccessKind, tag: SbTag) -> Option Option Option { - // When the borrow stack is empty, there are no tags we could put into the cache that would - // be valid. Additionally, since lookups into the cache are a linear search it doesn't make - // sense to use the cache when it is no smaller than a search of the borrow stack itself. + // This looks like a common-sense optimization; we're going to do a linear search of the + // cache or the borrow stack to scan the shorter of the two. This optimization is miniscule + // and this check actually ensures we do not access an invalid cache. + // When a stack is created and when items are removed from the top of the borrow stack, we + // need some valid value to populate the cache. In both cases, we try to use the bottom + // item. But when the stack is cleared in `set_unknown_bottom` there is nothing we could + // place in the cache that is correct. But due to the way we populate the cache in + // `StackCache::add`, we know that when the borrow stack has grown larger than the cache, + // every slot in the cache is valid. if self.borrows.len() <= CACHE_LEN { return None; } // Search the cache for the tag we're looking up - let cache_idx = self.cache.tags.iter().position(|t| *t == tag)?; + let cache_idx = self.cache.items.iter().position(|t| t.tag() == tag)?; let stack_idx = self.cache.idx[cache_idx]; // If we found the tag, look up its position in the stack to see if it grants // the required permission - if self.borrows[stack_idx].perm.grants(access) { + if self.cache.items[cache_idx].perm().grants(access) { + // If it does, and it's not already in the most-recently-used position, re-insert it at + // the most-recently-used position. This technically reduces the efficiency of the + // cache by duplicating elements, but current benchmarks do not seem to benefit from + // avoiding this duplication. + // But if the tag is in position 1, avoiding the duplicating add is trivial. // If it does, and it's not already in the most-recently-used position, move it there. // Except if the tag is in position 1, this is equivalent to just a swap, so do that. if cache_idx == 1 { - self.cache.tags.swap(0, 1); + self.cache.items.swap(0, 1); self.cache.idx.swap(0, 1); } else if cache_idx > 1 { - self.cache.add(stack_idx, tag); + self.cache.add(stack_idx, self.cache.items[cache_idx]); } Some(stack_idx) } else { @@ -210,7 +226,7 @@ fn insert_cache(&mut self, new_idx: usize, new: Item) { if self.unique_range.end >= new_idx { self.unique_range.end += 1; } - if new.perm == Permission::Unique { + if new.perm() == Permission::Unique { // Make sure the possibly-unique range contains the new borrow self.unique_range.start = self.unique_range.start.min(new_idx); self.unique_range.end = self.unique_range.end.max(new_idx + 1); @@ -219,7 +235,7 @@ fn insert_cache(&mut self, new_idx: usize, new: Item) { // The above insert changes the meaning of every index in the cache >= new_idx, so now // we need to find every one of those indexes and increment it. // But if the insert is at the end (equivalent to a push), we can skip this step because - // it didn't change the position of any other tags. + // it didn't change the position of any other items. if new_idx != self.borrows.len() - 1 { for idx in &mut self.cache.idx { if *idx >= new_idx { @@ -229,7 +245,7 @@ fn insert_cache(&mut self, new_idx: usize, new: Item) { } // This primes the cache for the next access, which is almost always the just-added tag. - self.cache.add(new_idx, new.tag); + self.cache.add(new_idx, new); #[cfg(feature = "expensive-debug-assertions")] self.verify_cache_consistency(); @@ -241,9 +257,9 @@ pub fn new(item: Item) -> Self { borrows: vec![item], unknown_bottom: None, #[cfg(feature = "stack-cache")] - cache: StackCache { idx: [0; CACHE_LEN], tags: [item.tag; CACHE_LEN] }, + cache: StackCache { idx: [0; CACHE_LEN], items: [item; CACHE_LEN] }, #[cfg(feature = "stack-cache")] - unique_range: if item.perm == Permission::Unique { 0..1 } else { 0..0 }, + unique_range: if item.perm() == Permission::Unique { 0..1 } else { 0..0 }, } } @@ -261,6 +277,9 @@ pub fn unknown_bottom(&self) -> Option { } pub fn set_unknown_bottom(&mut self, tag: SbTag) { + // We clear the borrow stack but the lookup cache doesn't support clearing per se. Instead, + // there is a check explained in `find_granting_cache` which protects against accessing the + // cache when it has been cleared and not yet refilled. self.borrows.clear(); self.unknown_bottom = Some(tag); } @@ -278,14 +297,19 @@ pub fn disable_uniques_starting_at crate::InterpResult<'tcx>>( let unique_range = 0..self.len(); if disable_start <= unique_range.end { - // add 1 so we don't disable the granting item let lower = unique_range.start.max(disable_start); let upper = (unique_range.end + 1).min(self.borrows.len()); for item in &mut self.borrows[lower..upper] { - if item.perm == Permission::Unique { + if item.perm() == Permission::Unique { log::trace!("access: disabling item {:?}", item); visitor(*item)?; - item.perm = Permission::Disabled; + item.set_permission(Permission::Disabled); + // Also update all copies of this item in the cache. + for it in &mut self.cache.items { + if it.tag() == item.tag() { + it.set_permission(Permission::Disabled); + } + } } } } @@ -325,7 +349,7 @@ pub fn pop_items_after crate::InterpResult<'tcx>>( // also possible that the whole cache is still valid. So we call this method to repair what // aspects of the cache are now invalid, instead of resetting the whole thing to a trivially // valid default state. - let base_tag = self.borrows[0].tag; + let base_tag = self.borrows[0]; let mut removed = 0; let mut cursor = 0; // Remove invalid entries from the cache by rotating them to the end of the cache, then @@ -334,7 +358,7 @@ pub fn pop_items_after crate::InterpResult<'tcx>>( for _ in 0..CACHE_LEN - 1 { if self.cache.idx[cursor] >= start { self.cache.idx[cursor..CACHE_LEN - removed].rotate_left(1); - self.cache.tags[cursor..CACHE_LEN - removed].rotate_left(1); + self.cache.items[cursor..CACHE_LEN - removed].rotate_left(1); removed += 1; } else { cursor += 1; @@ -342,7 +366,7 @@ pub fn pop_items_after crate::InterpResult<'tcx>>( } for i in CACHE_LEN - removed - 1..CACHE_LEN { self.cache.idx[i] = 0; - self.cache.tags[i] = base_tag; + self.cache.items[i] = base_tag; } if start < self.unique_range.start.saturating_sub(1) {