summaryrefslogtreecommitdiff
path: root/src/layout/incremental.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/layout/incremental.rs')
-rw-r--r--src/layout/incremental.rs451
1 files changed, 0 insertions, 451 deletions
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
deleted file mode 100644
index b68ddcdc..00000000
--- a/src/layout/incremental.rs
+++ /dev/null
@@ -1,451 +0,0 @@
-use std::cmp::Reverse;
-use std::collections::HashMap;
-use std::sync::Arc;
-
-use itertools::Itertools;
-
-use super::{Constrained, Regions};
-use crate::frame::Frame;
-use crate::geom::Scalar;
-
-const TEMP_LEN: usize = 4;
-
-/// Caches layouting artifacts.
-#[derive(Default, Clone)]
-pub struct LayoutCache {
- /// Maps from node hashes to the resulting frames and regions in which the
- /// 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.
- frames: HashMap<u64, Vec<FramesEntry>>,
- /// In how many compilations this cache has been used.
- age: usize,
- /// What cache eviction policy should be used.
- policy: EvictionPolicy,
- /// The maximum number of entries this cache should have. Can be exceeded if
- /// there are more must-keep entries.
- max_size: usize,
-}
-
-impl LayoutCache {
- /// Create a new, empty layout cache.
- pub fn new(policy: EvictionPolicy, max_size: usize) -> Self {
- Self {
- frames: HashMap::default(),
- age: 0,
- policy,
- max_size,
- }
- }
-
- /// Whether the cache is empty.
- pub fn is_empty(&self) -> bool {
- self.frames.values().all(|entry| entry.is_empty())
- }
-
- /// Amount of items in the cache.
- pub fn len(&self) -> usize {
- self.frames.values().map(Vec::len).sum()
- }
-
- /// The number of levels stored in the cache.
- pub fn levels(&self) -> usize {
- self.entries().map(|entry| entry.level + 1).max().unwrap_or(0)
- }
-
- /// An iterator over all entries in the cache.
- pub fn entries(&self) -> impl Iterator<Item = &FramesEntry> + '_ {
- self.frames.values().flatten()
- }
-
- /// Fetch matching cached frames if there are any.
- pub fn get(
- &mut self,
- hash: u64,
- regions: &Regions,
- ) -> Option<Vec<Constrained<Arc<Frame>>>> {
- self.frames
- .get_mut(&hash)?
- .iter_mut()
- .find_map(|entry| entry.lookup(regions))
- }
-
- /// Insert a new frame entry into the cache.
- pub fn insert(&mut self, hash: u64, entry: FramesEntry) {
- self.frames.entry(hash).or_default().push(entry);
- }
-
- /// Clear the cache.
- pub fn clear(&mut self) {
- self.frames.clear();
- }
-
- /// Retains all elements for which the closure on the level returns `true`.
- pub fn retain<F>(&mut self, mut f: F)
- where
- F: FnMut(usize) -> bool,
- {
- for entries in self.frames.values_mut() {
- entries.retain(|entry| f(entry.level));
- }
- }
-
- /// Prepare the cache for the next round of compilation.
- pub fn turnaround(&mut self) {
- self.age += 1;
- for entry in self.frames.values_mut().flatten() {
- if entry.temperature[0] > 0 {
- entry.used_cycles += 1;
- }
-
- let last = *entry.temperature.last().unwrap();
- for i in (1 .. TEMP_LEN).rev() {
- entry.temperature[i] = entry.temperature[i - 1];
- }
-
- entry.temperature[0] = 0;
- entry.ancient_hits += last as usize;
- entry.age += 1;
- }
-
- self.evict();
- self.frames.retain(|_, v| !v.is_empty());
- }
-
- /// Evict the cache according to the policy.
- fn evict(&mut self) {
- let len = self.len();
- if len <= self.max_size {
- return;
- }
-
- match self.policy {
- EvictionPolicy::LeastRecentlyUsed => {
- // We find the element with the largest cooldown that cannot fit
- // anymore.
- let threshold = self
- .entries()
- .map(|f| Reverse(f.cooldown()))
- .k_smallest(len - self.max_size)
- .last()
- .unwrap()
- .0;
-
- for entries in self.frames.values_mut() {
- entries.retain(|f| f.cooldown() < threshold);
- }
- }
- EvictionPolicy::LeastFrequentlyUsed => {
- let threshold = self
- .entries()
- .map(|f| Scalar(f.hits() as f64 / f.age() as f64))
- .k_smallest(len - self.max_size)
- .last()
- .unwrap()
- .0;
-
- for entries in self.frames.values_mut() {
- entries.retain(|f| f.hits() as f64 / f.age() as f64 > threshold);
- }
- }
- EvictionPolicy::Patterns => {
- let kept = self.entries().filter(|f| f.properties().must_keep()).count();
-
- let remaining_capacity = self.max_size - kept.min(self.max_size);
- if len - kept <= remaining_capacity {
- return;
- }
-
- let threshold = self
- .entries()
- .filter(|f| !f.properties().must_keep())
- .map(|f| Scalar(f.hits() as f64 / f.age() as f64))
- .k_smallest((len - kept) - remaining_capacity)
- .last()
- .unwrap()
- .0;
-
- for entries in self.frames.values_mut() {
- entries.retain(|f| {
- f.properties().must_keep()
- || f.hits() as f64 / f.age() as f64 > threshold
- });
- }
- }
- EvictionPolicy::None => {}
- }
- }
-}
-
-/// Cached frames from past layouting.
-#[derive(Debug, Clone)]
-pub struct FramesEntry {
- /// The cached frames for a node.
- frames: Vec<Constrained<Arc<Frame>>>,
- /// How nested the frame was in the context is was originally appearing in.
- level: usize,
- /// 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: [u8; TEMP_LEN],
- /// All past usages that do not fit in the temperature array.
- ancient_hits: usize,
- /// Amount of cycles in which the element has been used at all.
- used_cycles: usize,
-}
-
-impl FramesEntry {
- /// Construct a new instance.
- pub fn new(frames: Vec<Constrained<Arc<Frame>>>, level: usize) -> Self {
- Self {
- frames,
- level,
- age: 1,
- temperature: [0; TEMP_LEN],
- ancient_hits: 0,
- used_cycles: 0,
- }
- }
-
- /// Checks if the cached frames are valid in the given regions and returns
- /// them if so.
- pub fn lookup(&mut self, regions: &Regions) -> Option<Vec<Constrained<Arc<Frame>>>> {
- self.check(regions).then(|| {
- self.temperature[0] = self.temperature[0].saturating_add(1);
- self.frames.clone()
- })
- }
-
- /// Checks if the cached frames are valid in the given regions.
- pub fn check(&self, regions: &Regions) -> bool {
- let mut iter = regions.iter();
- self.frames.iter().all(|frame| {
- iter.next().map_or(false, |(current, base)| {
- frame.cts.check(current, base, regions.expand)
- })
- })
- }
-
- /// How nested the frame was in the context is was originally appearing in.
- pub fn level(&self) -> usize {
- self.level
- }
-
- /// The number of compilation cycles this item has remained in the cache.
- pub fn age(&self) -> usize {
- self.age
- }
-
- /// Whether this element was used in the last compilation cycle.
- pub fn hit(&self) -> bool {
- self.temperature[0] != 0
- }
-
- /// Get the total amount of hits over the lifetime of this item.
- pub fn hits(&self) -> usize {
- self.temperature.into_iter().map(usize::from).sum::<usize>() + self.ancient_hits
- }
-
- /// The amount of consecutive cycles in which this item has not been used.
- pub fn cooldown(&self) -> usize {
- let mut cycle = 0;
- for &temp in &self.temperature[.. self.age.min(TEMP_LEN)] {
- if temp > 0 {
- return cycle;
- }
- cycle += 1;
- }
- cycle
- }
-
- /// Properties that describe how this entry's temperature evolved.
- pub fn properties(&self) -> PatternProperties {
- let mut all_zeros = true;
- let mut multi_use = false;
- let mut decreasing = true;
- let mut sparse = false;
- let mut abandoned = false;
-
- let mut last = None;
- let mut all_same = true;
-
- for (i, &temp) in self.temperature.iter().enumerate() {
- if temp == 0 && !all_zeros {
- sparse = true;
- }
-
- if temp != 0 {
- all_zeros = false;
- }
-
- if all_zeros && i == 1 {
- abandoned = true;
- }
-
- if temp > 1 {
- multi_use = true;
- }
-
- if let Some(prev) = last {
- if prev > temp {
- decreasing = false;
- }
-
- if temp != prev {
- all_same = false;
- }
- }
-
- last = Some(temp);
- }
-
- if self.age > TEMP_LEN && self.age - TEMP_LEN <= self.ancient_hits {
- multi_use = true;
- }
-
- if self.ancient_hits > 0 {
- all_zeros = false;
- }
-
- PatternProperties {
- mature: self.age > TEMP_LEN,
- hit: self.temperature[0] >= 1,
- top_level: self.level == 0,
- all_zeros,
- multi_use,
- decreasing: decreasing && !all_same,
- sparse,
- abandoned,
- }
- }
-}
-
-/// Cache eviction strategies.
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
-pub enum EvictionPolicy {
- /// Evict the least recently used item.
- LeastRecentlyUsed,
- /// Evict the least frequently used item.
- LeastFrequentlyUsed,
- /// Use the pattern verdicts.
- Patterns,
- /// Do not evict.
- None,
-}
-
-impl Default for EvictionPolicy {
- fn default() -> Self {
- Self::Patterns
- }
-}
-
-/// Describes the properties that this entry's temperature array has.
-#[derive(Debug, Copy, Clone, Eq, PartialEq)]
-pub struct PatternProperties {
- /// There only are zero values.
- pub all_zeros: bool,
- /// The entry exists for more or equal time as the temperature array is long.
- pub mature: bool,
- /// The entry was used more than one time in at least one compilation.
- pub multi_use: bool,
- /// The entry was used in the last compilation.
- pub hit: bool,
- /// The temperature is monotonously decreasing in non-terminal temperature fields.
- pub decreasing: bool,
- /// There are zero temperatures after non-zero temperatures.
- pub sparse: bool,
- /// There are multiple zero temperatures at the front of the temperature array.
- pub abandoned: bool,
- /// If the item is on the top level.
- pub top_level: bool,
-}
-
-impl PatternProperties {
- /// Check if it is vital to keep an entry based on its properties.
- pub fn must_keep(&self) -> bool {
- // Keep an undo stack.
- (self.top_level && !self.mature)
- // Keep the most recently created items, even if they have not yet
- // been used.
- || (self.all_zeros && !self.mature)
- || (self.multi_use && !self.abandoned)
- || self.hit
- || self.sparse
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
- use crate::geom::{Size, Spec};
- use crate::layout::Constraints;
-
- fn empty_frames() -> Vec<Constrained<Arc<Frame>>> {
- vec![Constrained {
- item: Arc::new(Frame::default()),
- cts: Constraints::new(Spec::splat(false)),
- }]
- }
-
- fn zero_regions() -> Regions {
- Regions::one(Size::zero(), Size::zero(), Spec::splat(false))
- }
-
- #[test]
- fn test_layout_incremental_temperature() {
- let mut cache = LayoutCache::new(EvictionPolicy::None, 20);
- let regions = zero_regions();
- cache.policy = EvictionPolicy::None;
- cache.insert(0, FramesEntry::new(empty_frames(), 0));
-
- let entry = cache.frames.get(&0).unwrap().first().unwrap();
- assert_eq!(entry.age(), 1);
- assert_eq!(entry.temperature, [0, 0, 0, 0]);
- assert_eq!(entry.ancient_hits, 0);
- assert_eq!(entry.used_cycles, 0);
- assert_eq!(entry.level, 0);
-
- cache.get(0, &regions).unwrap();
- let entry = cache.frames.get(&0).unwrap().first().unwrap();
- assert_eq!(entry.age(), 1);
- assert_eq!(entry.temperature, [1, 0, 0, 0]);
- assert_eq!(entry.ancient_hits, 0);
-
- cache.turnaround();
- let entry = cache.frames.get(&0).unwrap().first().unwrap();
- assert_eq!(entry.age(), 2);
- assert_eq!(entry.temperature, [0, 1, 0, 0]);
- assert_eq!(entry.ancient_hits, 0);
- assert_eq!(entry.used_cycles, 1);
-
- cache.get(0, &regions).unwrap();
- for _ in 0 .. 4 {
- cache.turnaround();
- }
-
- let entry = cache.frames.get(&0).unwrap().first().unwrap();
- assert_eq!(entry.age(), 6);
- assert_eq!(entry.temperature, [0, 0, 0, 0]);
- assert_eq!(entry.ancient_hits, 2);
- assert_eq!(entry.used_cycles, 2);
- }
-
- #[test]
- fn test_layout_incremental_properties() {
- let mut cache = LayoutCache::new(EvictionPolicy::None, 20);
- cache.policy = EvictionPolicy::None;
- cache.insert(0, FramesEntry::new(empty_frames(), 1));
-
- let props = cache.frames.get(&0).unwrap().first().unwrap().properties();
- assert_eq!(props.top_level, false);
- assert_eq!(props.mature, false);
- assert_eq!(props.multi_use, false);
- assert_eq!(props.hit, false);
- assert_eq!(props.decreasing, false);
- assert_eq!(props.sparse, false);
- assert_eq!(props.abandoned, true);
- assert_eq!(props.all_zeros, true);
- assert_eq!(props.must_keep(), true);
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-15 17:57:41 +0000