From 6b6cdae7ce95681d6a1194be70b375494166a8c6 Mon Sep 17 00:00:00 2001 From: Martin Haug Date: Sun, 27 Jun 2021 12:28:40 +0200 Subject: Testing for incremental Also, constraint bugfixes. --- src/layout/incremental.rs | 155 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 145 insertions(+), 10 deletions(-) (limited to 'src/layout/incremental.rs') diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs index a5c3cea3..e1d1ffba 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -7,13 +7,15 @@ use super::*; pub struct LayoutCache { /// Maps from node hashes to the resulting frames and regions in which the /// frames are valid. - pub frames: HashMap, + pub frames: HashMap>, + /// In how many compilations this cache has been used. + age: usize, } impl LayoutCache { /// Create a new, empty layout cache. pub fn new() -> Self { - Self { frames: HashMap::new() } + Self { frames: HashMap::new(), age: 0 } } /// Clear the cache. @@ -26,12 +28,68 @@ impl LayoutCache { where F: FnMut(usize) -> bool, { - self.frames.retain(|_, entry| f(entry.level)); + for (_, hash_ident) in self.frames.iter_mut() { + hash_ident.retain(|entry| f(entry.level)); + } } /// Amount of items in the cache. pub fn len(&self) -> usize { - self.frames.len() + self.frames.iter().map(|(_, e)| e.len()).sum() + } + + /// Prepare the cache for the next round of compilation + pub fn turnaround(&mut self) { + self.age += 1; + for entry in self.frames.iter_mut().flat_map(|(_, x)| x.iter_mut()) { + for i in 0 .. (entry.temperature.len() - 1) { + entry.temperature[i] = entry.temperature[i + 1]; + } + *entry.temperature.last_mut().unwrap() = Some(0); + } + } + + /// What is the deepest level in the cache? + pub fn levels(&self) -> usize { + self.frames + .iter() + .flat_map(|(_, x)| x) + .map(|entry| entry.level + 1) + .max() + .unwrap_or(0) + } + + /// Fetches the appropriate entry from the cache if there is any. + pub fn get( + &mut self, + hash: u64, + regions: Regions, + ) -> Option>>> { + self.frames.get_mut(&hash).and_then(|frames| { + for frame in frames { + let res = frame.check(regions.clone()); + if res.is_some() { + return res; + } + } + + None + }) + } + + /// Inserts a new frame set into the cache. + pub fn insert( + &mut self, + hash: u64, + frames: Vec>>, + level: usize, + ) { + let entry = FramesEntry::new(frames, level); + if let Some(variants) = self.frames.get_mut(&hash) { + variants.push(entry); + } else { + self.frames.insert(hash, vec![entry]); + } } } @@ -42,19 +100,72 @@ pub struct FramesEntry { pub frames: Vec>>, /// How nested the frame was in the context is was originally appearing in. pub level: usize, + /// How much the element was accessed during the last five compilations, the + /// most current one being the last element. `None` variants indicate that + /// the element is younger than five compilations. + temperature: [Option; 5], } impl FramesEntry { + /// Construct a new instance. + pub fn new(frames: Vec>>, level: usize) -> Self { + let mut temperature = [None; 5]; + temperature[4] = Some(0); + Self { frames, level, temperature } + } + /// Checks if the cached [`Frame`] is valid for the given regions. - pub fn check(&self, mut regions: Regions) -> Option>>> { + pub fn check(&mut self, mut regions: Regions) -> Option>>> { for (i, frame) in self.frames.iter().enumerate() { if (i != 0 && !regions.next()) || !frame.constraints.check(®ions) { return None; } } + let tmp = self.temperature.get_mut(4).unwrap(); + *tmp = Some(tmp.map_or(1, |x| x + 1)); + Some(self.frames.clone()) } + + /// Get the amount of compilation cycles this item has remained in the + /// cache. + pub fn age(&self) -> usize { + let mut age = 0; + for &temp in self.temperature.iter().rev() { + if temp.is_none() { + break; + } + age += 1; + } + age + } + + /// Get the amount of consecutive cycles in which this item has not + /// been used. + pub fn cooldown(&self) -> usize { + let mut age = 0; + for (i, &temp) in self.temperature.iter().enumerate().rev() { + match temp { + Some(temp) => { + if temp > 0 { + return self.temperature.len() - 1 - i; + } + } + None => { + return age; + } + } + age += 1 + } + + age + } + + /// Whether this element was used in the last compilation cycle. + pub fn hit(&self) -> bool { + self.temperature.last().unwrap().unwrap_or(0) != 0 + } } #[derive(Debug, Copy, Clone, PartialEq)] @@ -107,15 +218,22 @@ impl Constraints { let base = regions.base.to_spec(); let current = regions.current.to_spec(); - current.eq_by(&self.min, |x, y| y.map_or(true, |y| x >= &y)) + let res = current.eq_by(&self.min, |&x, y| y.map_or(true, |y| x.fits(y))) && current.eq_by(&self.max, |x, y| y.map_or(true, |y| x < &y)) - && current.eq_by(&self.exact, |x, y| y.map_or(true, |y| x == &y)) - && base.eq_by(&self.base, |x, y| y.map_or(true, |y| x == &y)) + && current.eq_by(&self.exact, |&x, y| y.map_or(true, |y| x.approx_eq(y))) + && base.eq_by(&self.base, |&x, y| y.map_or(true, |y| x.approx_eq(y))); + + res } /// Changes all constraints by adding the argument to them if they are set. - pub fn mutate(&mut self, size: Size) { - for x in &mut [self.min, self.max, self.exact, self.base] { + pub fn mutate(&mut self, size: Size, regions: &Regions) { + for x in std::array::IntoIter::new([ + &mut self.min, + &mut self.max, + &mut self.exact, + &mut self.base, + ]) { if let Some(horizontal) = x.horizontal.as_mut() { *horizontal += size.width; } @@ -123,6 +241,23 @@ impl Constraints { *vertical += size.height; } } + + self.exact = zip(self.exact, regions.current.to_spec(), |_, o| o); + self.base = zip(self.base, regions.base.to_spec(), |_, o| o); + } +} + +fn zip( + one: Spec>, + other: Spec, + mut f: F, +) -> Spec> +where + F: FnMut(Length, Length) -> Length, +{ + Spec { + vertical: one.vertical.map(|r| f(r, other.vertical)), + horizontal: one.horizontal.map(|r| f(r, other.horizontal)), } } -- cgit v1.2.3 From 57bd3e23c79878d106ab8be17c71caca6c4f5a7c Mon Sep 17 00:00:00 2001 From: Martin Date: Sun, 27 Jun 2021 17:08:40 +0200 Subject: Apply suggestions from code review Co-authored-by: Laurenz --- src/layout/incremental.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/layout/incremental.rs') diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs index e1d1ffba..953b76be 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -101,7 +101,7 @@ pub struct FramesEntry { /// How nested the frame was in the context is was originally appearing in. pub level: usize, /// How much the element was accessed during the last five compilations, the - /// most current one being the last element. `None` variants indicate that + /// most recent one being the last element. `None` variants indicate that /// the element is younger than five compilations. temperature: [Option; 5], } -- cgit v1.2.3 From 9bd8b7ddac046f581dc750e148147901d08cb0f4 Mon Sep 17 00:00:00 2001 From: Martin Haug Date: Sun, 27 Jun 2021 18:06:39 +0200 Subject: Code review, new stack test --- src/layout/incremental.rs | 117 ++++++++++++++++++++++------------------------ 1 file changed, 57 insertions(+), 60 deletions(-) (limited to 'src/layout/incremental.rs') diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs index 953b76be..a3051d0f 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -1,4 +1,5 @@ -use std::{collections::HashMap, ops::Deref}; +use std::collections::{hash_map::Entry, HashMap}; +use std::ops::Deref; use super::*; @@ -6,7 +7,9 @@ use super::*; #[derive(Default, Debug, Clone)] pub struct LayoutCache { /// Maps from node hashes to the resulting frames and regions in which the - /// frames are valid. + /// frames are valid. The right hand side of the hash map is a vector of + /// results because across one or more compilations, multiple different + /// layouts of the same node may have been requested. pub frames: HashMap>, /// In how many compilations this cache has been used. age: usize, @@ -28,16 +31,11 @@ impl LayoutCache { where F: FnMut(usize) -> bool, { - for (_, hash_ident) in self.frames.iter_mut() { - hash_ident.retain(|entry| f(entry.level)); + for (_, entries) in self.frames.iter_mut() { + entries.retain(|entry| f(entry.level)); } } - /// Amount of items in the cache. - pub fn len(&self) -> usize { - self.frames.iter().map(|(_, e)| e.len()).sum() - } - /// Prepare the cache for the next round of compilation pub fn turnaround(&mut self) { self.age += 1; @@ -45,11 +43,11 @@ impl LayoutCache { for i in 0 .. (entry.temperature.len() - 1) { entry.temperature[i] = entry.temperature[i + 1]; } - *entry.temperature.last_mut().unwrap() = Some(0); + *entry.temperature.last_mut().unwrap() = 0; } } - /// What is the deepest level in the cache? + /// The amount of levels stored in the cache. pub fn levels(&self) -> usize { self.frames .iter() @@ -85,16 +83,17 @@ impl LayoutCache { level: usize, ) { let entry = FramesEntry::new(frames, level); - if let Some(variants) = self.frames.get_mut(&hash) { - variants.push(entry); - } else { - self.frames.insert(hash, vec![entry]); + match self.frames.entry(hash) { + Entry::Occupied(o) => o.into_mut().push(entry), + Entry::Vacant(v) => { + v.insert(vec![entry]); + } } } } -#[derive(Debug, Clone)] /// Cached frames from past layouting. +#[derive(Debug, Clone)] pub struct FramesEntry { /// The cached frames for a node. pub frames: Vec>>, @@ -103,15 +102,20 @@ pub struct FramesEntry { /// How much the element was accessed during the last five compilations, the /// most recent one being the last element. `None` variants indicate that /// the element is younger than five compilations. - temperature: [Option; 5], + temperature: [usize; 5], + /// For how long the element already exists. + age: usize, } impl FramesEntry { /// Construct a new instance. pub fn new(frames: Vec>>, level: usize) -> Self { - let mut temperature = [None; 5]; - temperature[4] = Some(0); - Self { frames, level, temperature } + Self { + frames, + level, + temperature: [0; 5], + age: 1, + } } /// Checks if the cached [`Frame`] is valid for the given regions. @@ -122,8 +126,7 @@ impl FramesEntry { } } - let tmp = self.temperature.get_mut(4).unwrap(); - *tmp = Some(tmp.map_or(1, |x| x + 1)); + self.temperature[4] = self.temperature[4] + 1; Some(self.frames.clone()) } @@ -131,43 +134,35 @@ impl FramesEntry { /// Get the amount of compilation cycles this item has remained in the /// cache. pub fn age(&self) -> usize { - let mut age = 0; - for &temp in self.temperature.iter().rev() { - if temp.is_none() { - break; - } - age += 1; - } - age + self.age } /// Get the amount of consecutive cycles in which this item has not /// been used. pub fn cooldown(&self) -> usize { - let mut age = 0; + let mut cycle = 0; for (i, &temp) in self.temperature.iter().enumerate().rev() { - match temp { - Some(temp) => { - if temp > 0 { - return self.temperature.len() - 1 - i; - } - } - None => { - return age; + if self.age > i { + if temp > 0 { + return self.temperature.len() - 1 - i; } + } else { + return cycle; } - age += 1 + + cycle += 1 } - age + cycle } /// Whether this element was used in the last compilation cycle. pub fn hit(&self) -> bool { - self.temperature.last().unwrap().unwrap_or(0) != 0 + self.temperature.last().unwrap() != &0 } } +/// These constraints describe regions that match them. #[derive(Debug, Copy, Clone, PartialEq)] pub struct Constraints { /// The minimum available length in the region. @@ -218,49 +213,45 @@ impl Constraints { let base = regions.base.to_spec(); let current = regions.current.to_spec(); - let res = current.eq_by(&self.min, |&x, y| y.map_or(true, |y| x.fits(y))) + current.eq_by(&self.min, |&x, y| y.map_or(true, |y| x.fits(y))) && current.eq_by(&self.max, |x, y| y.map_or(true, |y| x < &y)) && current.eq_by(&self.exact, |&x, y| y.map_or(true, |y| x.approx_eq(y))) - && base.eq_by(&self.base, |&x, y| y.map_or(true, |y| x.approx_eq(y))); - - res + && base.eq_by(&self.base, |&x, y| y.map_or(true, |y| x.approx_eq(y))) } - /// Changes all constraints by adding the argument to them if they are set. + /// Changes all constraints by adding the `size` to them if they are `Some`. pub fn mutate(&mut self, size: Size, regions: &Regions) { - for x in std::array::IntoIter::new([ + for spec in std::array::IntoIter::new([ &mut self.min, &mut self.max, &mut self.exact, &mut self.base, ]) { - if let Some(horizontal) = x.horizontal.as_mut() { + if let Some(horizontal) = spec.horizontal.as_mut() { *horizontal += size.width; } - if let Some(vertical) = x.vertical.as_mut() { + if let Some(vertical) = spec.vertical.as_mut() { *vertical += size.height; } } - self.exact = zip(self.exact, regions.current.to_spec(), |_, o| o); - self.base = zip(self.base, regions.base.to_spec(), |_, o| o); + self.exact = override_if_some(self.exact, regions.current.to_spec()); + self.base = override_if_some(self.base, regions.base.to_spec()); } } -fn zip( +fn override_if_some( one: Spec>, other: Spec, - mut f: F, -) -> Spec> -where - F: FnMut(Length, Length) -> Length, -{ +) -> Spec> { Spec { - vertical: one.vertical.map(|r| f(r, other.vertical)), - horizontal: one.horizontal.map(|r| f(r, other.horizontal)), + vertical: one.vertical.map(|_| other.vertical), + horizontal: one.horizontal.map(|_| other.horizontal), } } +/// Carries an item that only applies to certain regions and the constraints +/// that describe these regions. #[derive(Debug, Copy, Clone, PartialEq)] pub struct Constrained { pub item: T, @@ -275,8 +266,14 @@ impl Deref for Constrained { } } +/// Extends length-related options by providing convenience methods for setting +/// minimum and maximum lengths on them, even if they are `None`. pub trait OptionExt { + // Sets `other` as the value if the Option is `None` or if it contains a + // value larger than `other`. fn set_min(&mut self, other: Length); + // Sets `other` as the value if the Option is `None` or if it contains a + // value smaller than `other`. fn set_max(&mut self, other: Length); } -- cgit v1.2.3 From 6f518c172805b6ac067a692eb8971c7ec1e50608 Mon Sep 17 00:00:00 2001 From: Martin Date: Sun, 27 Jun 2021 18:30:25 +0200 Subject: Adjust comments Co-authored-by: Laurenz Update tests/typ/layout/stack.typ Co-authored-by: Laurenz --- src/layout/incremental.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/layout/incremental.rs') diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs index a3051d0f..b6a059c5 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -162,7 +162,7 @@ impl FramesEntry { } } -/// These constraints describe regions that match them. +/// Describe regions that match them. #[derive(Debug, Copy, Clone, PartialEq)] pub struct Constraints { /// The minimum available length in the region. -- cgit v1.2.3 From e9960b89424ab67e633076ccc9f8c420316b076a Mon Sep 17 00:00:00 2001 From: Martin Haug Date: Sun, 27 Jun 2021 18:57:08 +0200 Subject: Code review: Reverse temperature --- src/layout/incremental.rs | 67 +++++++++++++++++++++++++---------------------- 1 file changed, 36 insertions(+), 31 deletions(-) (limited to 'src/layout/incremental.rs') diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs index b6a059c5..9eda0402 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -26,6 +26,11 @@ impl LayoutCache { self.frames.clear(); } + /// Amount of items in the cache. + pub fn len(&self) -> usize { + self.frames.iter().map(|(_, e)| e.len()).sum() + } + /// Retains all elements for which the closure on the level returns `true`. pub fn retain(&mut self, mut f: F) where @@ -41,9 +46,10 @@ impl LayoutCache { self.age += 1; for entry in self.frames.iter_mut().flat_map(|(_, x)| x.iter_mut()) { for i in 0 .. (entry.temperature.len() - 1) { - entry.temperature[i] = entry.temperature[i + 1]; + entry.temperature[i + 1] = entry.temperature[i]; } - *entry.temperature.last_mut().unwrap() = 0; + entry.temperature[0] = 0; + entry.age += 1; } } @@ -99,12 +105,11 @@ pub struct FramesEntry { pub frames: Vec>>, /// How nested the frame was in the context is was originally appearing in. pub level: usize, - /// How much the element was accessed during the last five compilations, the - /// most recent one being the last element. `None` variants indicate that - /// the element is younger than five compilations. - temperature: [usize; 5], /// For how long the element already exists. age: usize, + /// How much the element was accessed during the last five compilations, the + /// most recent one being the first element. + temperature: [usize; 5], } impl FramesEntry { @@ -113,8 +118,8 @@ impl FramesEntry { Self { frames, level, - temperature: [0; 5], age: 1, + temperature: [0; 5], } } @@ -126,7 +131,7 @@ impl FramesEntry { } } - self.temperature[4] = self.temperature[4] + 1; + self.temperature[0] += 1; Some(self.frames.clone()) } @@ -141,16 +146,11 @@ impl FramesEntry { /// been used. pub fn cooldown(&self) -> usize { let mut cycle = 0; - for (i, &temp) in self.temperature.iter().enumerate().rev() { - if self.age > i { - if temp > 0 { - return self.temperature.len() - 1 - i; - } - } else { + for &temp in &self.temperature[.. self.age] { + if temp > 0 { return cycle; } - - cycle += 1 + cycle += 1; } cycle @@ -158,7 +158,7 @@ impl FramesEntry { /// Whether this element was used in the last compilation cycle. pub fn hit(&self) -> bool { - self.temperature.last().unwrap() != &0 + self.temperature[0] != 0 } } @@ -213,10 +213,10 @@ impl Constraints { let base = regions.base.to_spec(); let current = regions.current.to_spec(); - current.eq_by(&self.min, |&x, y| y.map_or(true, |y| x.fits(y))) + current.eq_by(&self.min, |x, y| y.map_or(true, |y| x.fits(y))) && current.eq_by(&self.max, |x, y| y.map_or(true, |y| x < &y)) - && current.eq_by(&self.exact, |&x, y| y.map_or(true, |y| x.approx_eq(y))) - && base.eq_by(&self.base, |&x, y| y.map_or(true, |y| x.approx_eq(y))) + && current.eq_by(&self.exact, |x, y| y.map_or(true, |y| x.approx_eq(y))) + && base.eq_by(&self.base, |x, y| y.map_or(true, |y| x.approx_eq(y))) } /// Changes all constraints by adding the `size` to them if they are `Some`. @@ -235,18 +235,13 @@ impl Constraints { } } - self.exact = override_if_some(self.exact, regions.current.to_spec()); - self.base = override_if_some(self.base, regions.base.to_spec()); - } -} + let current = regions.current.to_spec(); + let base = regions.base.to_spec(); -fn override_if_some( - one: Spec>, - other: Spec, -) -> Spec> { - Spec { - vertical: one.vertical.map(|_| other.vertical), - horizontal: one.horizontal.map(|_| other.horizontal), + self.exact.horizontal.set_if_some(current.horizontal); + self.exact.vertical.set_if_some(current.vertical); + self.base.horizontal.set_if_some(base.horizontal); + self.base.vertical.set_if_some(base.vertical); } } @@ -272,9 +267,13 @@ pub trait OptionExt { // Sets `other` as the value if the Option is `None` or if it contains a // value larger than `other`. fn set_min(&mut self, other: Length); + // Sets `other` as the value if the Option is `None` or if it contains a // value smaller than `other`. fn set_max(&mut self, other: Length); + + /// Sets `other` as the value if the Option is `Some`. + fn set_if_some(&mut self, other: Length); } impl OptionExt for Option { @@ -291,4 +290,10 @@ impl OptionExt for Option { None => *self = Some(other), } } + + fn set_if_some(&mut self, other: Length) { + if self.is_some() { + *self = Some(other); + } + } } -- cgit v1.2.3