From 4f9c14c256b08458c873290a5e34eb493156532e Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Sat, 5 Jan 2019 15:26:16 +0100 Subject: [PATCH] deduplicate RangeMap elements in iter_mut This cuts down execution time of the benchmark in the OP of https://github.com/solson/miri/issues/593 by another 25%, and it cuts max-RSS by 90% (!) --- src/lib.rs | 2 +- src/range_map.rs | 111 ++++++++++++++++++++++++----------------- src/stacked_borrows.rs | 2 +- 3 files changed, 67 insertions(+), 48 deletions(-) diff --git a/src/lib.rs b/src/lib.rs index bb6c9e3ca50..a8fd432282a 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,4 +1,4 @@ -#![feature(rustc_private)] +#![feature(rustc_private, range_contains)] #![allow(clippy::cast_lossless)] diff --git a/src/range_map.rs b/src/range_map.rs index 5b7a940329b..d157cbf0549 100644 --- a/src/range_map.rs +++ b/src/range_map.rs @@ -12,26 +12,16 @@ use rustc::ty::layout::Size; -// Representation: offset-length-data tuples, sorted by offset. #[derive(Clone, Debug)] struct Elem { - offset: u64, - len: NonZeroU64, + range: ops::Range, // the range covered by this element, never empty data: T, } -// Length is always > 0. #[derive(Clone, Debug)] pub struct RangeMap { v: Vec>, } -impl Elem { - #[inline(always)] - fn contains(&self, offset: u64) -> bool { - offset >= self.offset && offset < self.offset + self.len.get() - } -} - impl RangeMap { /// Create a new RangeMap for the given size, and with the given initial value used for /// the entire range. @@ -41,8 +31,7 @@ pub fn new(size: Size, init: T) -> RangeMap { let mut map = RangeMap { v: Vec::new() }; if size > 0 { map.v.push(Elem { - offset: 0, - len: NonZeroU64::new(size).unwrap(), + range: 0..size, data: init }); } @@ -57,11 +46,11 @@ fn find_offset(&self, offset: u64) -> usize { loop { let candidate = left.checked_add(right).unwrap() / 2; let elem = &self.v[candidate]; - if elem.offset > offset { + if offset < elem.range.start { // we are too far right (offset is further left) debug_assert!(candidate < right); // we are making progress right = candidate; - } else if offset >= elem.offset + elem.len.get() { + } else if offset >= elem.range.end { // we are too far left (offset is further right) debug_assert!(candidate >= left); // we are making progress left = candidate+1; @@ -85,12 +74,12 @@ pub fn iter<'a>(&'a self, offset: Size, len: Size) -> impl Iterator bool T: Clone, { let elem = &mut self.v[index]; - let first_len = split_offset.checked_sub(elem.offset) - .expect("The split_offset is before the element to be split"); - assert!(first_len <= elem.len.get(), - "The split_offset is after the element to be split"); - if first_len == 0 || first_len == elem.len.get() { + if split_offset == elem.range.start || split_offset == elem.range.end { // Nothing to do return false; } + debug_assert!(elem.range.contains(&split_offset), + "The split_offset is not in the element to be split"); // Now we really have to split. Reduce length of first element. - let second_len = elem.len.get() - first_len; - elem.len = NonZeroU64::new(first_len).unwrap(); + let second_range = split_offset..elem.range.end; + elem.range.end = split_offset; // Copy the data, and insert 2nd element let second = Elem { - offset: split_offset, - len: NonZeroU64::new(second_len).unwrap(), + range: second_range, data: elem.data.clone(), }; self.v.insert(index+1, second); @@ -137,7 +123,7 @@ pub fn iter_mut<'a>( len: Size, ) -> impl Iterator + 'a where - T: Clone, + T: Clone + PartialEq, { let offset = offset.bytes(); let len = len.bytes(); @@ -149,33 +135,53 @@ pub fn iter_mut<'a>( &mut [] } else { // Make sure we got a clear beginning - let mut first = self.find_offset(offset); - if self.split_index(first, offset) { + let mut first_idx = self.find_offset(offset); + if self.split_index(first_idx, offset) { // The newly created 2nd element is ours - first += 1; + first_idx += 1; } - let first = first; // no more mutation + let first_idx = first_idx; // no more mutation // Find our end. Linear scan, but that's okay because the iteration // is doing the same linear scan anyway -- no increase in complexity. - let mut end = first; // the last element to be included + // We combine this scan with a scan for duplicates that we can merge, to reduce + // the number of elements. + let mut equal_since_idx = first_idx; + let mut end_idx = first_idx; // when the loop is done, this is the first excluded element. loop { - let elem = &self.v[end]; - if elem.offset+elem.len.get() < offset+len { - // We need to scan further. - end += 1; - debug_assert!(end < self.v.len(), "iter_mut: end-offset {} is out-of-bounds", offset+len); - } else { - // `elem` is the last included element. Stop search. + // Compute if `end` is the last element we need to look at. + let done = (self.v[end_idx].range.end >= offset+len); + // We definitely need to include `end`, so move the index. + end_idx += 1; + debug_assert!(done || end_idx < self.v.len(), "iter_mut: end-offset {} is out-of-bounds", offset+len); + // see if we want to merge everything in `equal_since..end` (exclusive at the end!) + if done || self.v[end_idx].data != self.v[equal_since_idx].data { + // Everything in `equal_since..end` was equal. Make them just one element covering + // the entire range. + let equal_elems = end_idx - equal_since_idx; // number of equal elements + if equal_elems > 1 { + // Adjust the range of the first element to cover all of them. + let equal_until = self.v[end_idx - 1].range.end; // end of range of last of the equal elements + self.v[equal_since_idx].range.end = equal_until; + // Delete the rest of them. + self.v.splice(equal_since_idx+1..end_idx, std::iter::empty()); + // Adjust `end_idx` because we made the list shorter. + end_idx -= (equal_elems - 1); + } + // Go on scanning. + equal_since_idx = end_idx; + } + // Leave loop if this is the last element. + if done { break; } } - let end = end; // no more mutation + let end_idx = end_idx-1; // Move to last included instead of first excluded index. // We need to split the end as well. Even if this performs a // split, we don't have to adjust our index as we only care about // the first part of the split. - self.split_index(end, offset+len); + self.split_index(end_idx, offset+len); // Now we yield the slice. `end` is inclusive. - &mut self.v[first..=end] + &mut self.v[first_idx..=end_idx] }; slice.iter_mut().map(|elem| &mut elem.data) } @@ -241,18 +247,31 @@ fn gaps() { } } assert_eq!(map.v.len(), 6); - assert_eq!( to_vec(&map, 10, 10), vec![23, 42, 23, 23, 23, 43, 23, 23, 23, 23] ); assert_eq!(to_vec(&map, 13, 5), vec![23, 23, 43, 23, 23]); + for x in map.iter_mut(Size::from_bytes(15), Size::from_bytes(5)) { *x = 19; } assert_eq!(map.v.len(), 6); - assert_eq!(map.iter(Size::from_bytes(19), Size::from_bytes(1)) - .map(|&t| t).collect::>(), vec![19]); + assert_eq!( + to_vec(&map, 10, 10), + vec![23, 42, 23, 23, 23, 19, 19, 19, 19, 19] + ); + // Should be seeing two blocks with 19 + assert_eq!(map.iter(Size::from_bytes(15), Size::from_bytes(2)) + .map(|&t| t).collect::>(), vec![19, 19]); + + // a NOP iter_mut should trigger merging + for x in map.iter_mut(Size::from_bytes(15), Size::from_bytes(5)) { } + assert_eq!(map.v.len(), 5); + assert_eq!( + to_vec(&map, 10, 10), + vec![23, 42, 23, 23, 23, 19, 19, 19, 19, 19] + ); } } diff --git a/src/stacked_borrows.rs b/src/stacked_borrows.rs index 27d4a4f7f7b..1fc705c03bb 100644 --- a/src/stacked_borrows.rs +++ b/src/stacked_borrows.rs @@ -67,7 +67,7 @@ pub enum BorStackItem { } /// Extra per-location state -#[derive(Clone, Debug)] +#[derive(Clone, Debug, PartialEq, Eq)] pub struct Stack { borrows: Vec, // used as a stack; never empty frozen_since: Option, // virtual frozen "item" on top of the stack -- 2.44.0