/// we never have the unknown-to-known boundary in an SRW group.
unknown_bottom: Option<SbTag>,
- /// 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
}
/// 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
}
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;
}
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),
"{:?} {:?}",
/// 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,
.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
}
// If we didn't find the tag in the cache, fall back to a linear search of the
- // whole stack, and add the tag to the stack.
+ // whole stack, and add the tag to the cache.
for (stack_idx, item) in self.borrows.iter().enumerate().rev() {
- if tag == item.tag && item.perm.grants(access) {
+ if tag == item.tag() && item.perm().grants(access) {
#[cfg(feature = "stack-cache")]
- self.cache.add(stack_idx, tag);
+ self.cache.add(stack_idx, *item);
return Some(stack_idx);
}
}
#[cfg(feature = "stack-cache")]
fn find_granting_cache(&mut self, access: AccessKind, tag: SbTag) -> Option<usize> {
- // 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 {
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);
// 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 {
}
// 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();
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 },
}
}
}
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);
}
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);
+ }
+ }
}
}
}
// 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
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;
}
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) {
projects / rust.git / blobdiff