Fix colored row reset performance

This fixes a bug where a row would always get reset completely if its
background does not equal the default terminal background. This leads to
big performance bottlenecks when running commands like `echo "\e[41m" &&
yes`.

Instead of resetting the entire row whenever the template cell is not
empty, the template cell is now compared to the last cell in the row.
The last cell will always be equal to the previous template cell when
`row.occ < row.inner.len()` and if `occ` is equal to the row's length,
the entire row is always reset anyways.

Fixes #2989.

4 files changed, 65 insertions, 38 deletions

diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 09333b36..ad9d9b7b 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -70,6 +70,12 @@ pub trait GridCell {
     fn is_empty(&self) -> bool;
     fn is_wrap(&self) -> bool;
     fn set_wrap(&mut self, wrap: bool);
+
+    /// Fast equality approximation.
+    ///
+    /// This is a faster alternative to [`PartialEq`],
+    /// but might report inequal cells as equal.
+    fn fast_eq(&self, other: Self) -> bool;
 }
 
 /// Represents the terminal display contents
@@ -140,7 +146,7 @@ pub enum Scroll {
     Bottom,
 }
 
-impl<T: GridCell + Copy + Clone> Grid<T> {
+impl<T: GridCell + PartialEq + Copy> Grid<T> {
     pub fn new(lines: index::Line, cols: index::Column, scrollback: usize, template: T) -> Grid<T> {
         let raw = Storage::with_capacity(lines, Row::new(cols, &template));
         Grid {
diff --git a/alacritty_terminal/src/grid/row.rs b/alacritty_terminal/src/grid/row.rs
index daee4408..0bfa88d4 100644
--- a/alacritty_terminal/src/grid/row.rs
+++ b/alacritty_terminal/src/grid/row.rs
@@ -29,14 +29,10 @@ use crate::index::Column;
 pub struct Row<T> {
     inner: Vec<T>,
 
-    /// occupied entries
+    /// Maximum number of occupied entries.
     ///
-    /// Semantically, this value can be understood as the **end** of an
-    /// Exclusive Range. Thus,
-    ///
-    /// - Zero means there are no occupied entries
-    /// - 1 means there is a value at index zero, but nowhere else
-    /// - `occ == inner.len` means every value is occupied
+    /// This is the upper bound on the number of elements in the row, which have been modified
+    /// since the last reset. All cells after this point are guaranteed to be equal.
     pub(crate) occ: usize,
 }
 
@@ -85,21 +81,29 @@ impl<T: Copy> Row<T> {
         }
     }
 
-    /// Resets contents to the contents of `other`
+    /// Reset all cells in the row to the `template` cell.
+    #[inline]
     pub fn reset(&mut self, template: &T)
     where
-        T: GridCell,
+        T: GridCell + PartialEq,
     {
-        if template.is_empty() {
-            for item in &mut self.inner[..self.occ] {
-                *item = *template;
-            }
-            self.occ = 0;
-        } else {
-            let len = self.inner.len();
-            self.inner = vec![*template; len];
+        debug_assert!(!self.inner.is_empty());
+
+        let template = *template;
+
+        // Mark all cells as dirty if template cell changed
+        let len = self.inner.len();
+        if !self.inner[len - 1].fast_eq(template) {
             self.occ = len;
         }
+
+        // Reset every dirty in the row
+        // let template = *template;
+        for item in &mut self.inner[..self.occ] {
+            *item = template;
+        }
+
+        self.occ = 0;
     }
 }
 
diff --git a/alacritty_terminal/src/grid/storage.rs b/alacritty_terminal/src/grid/storage.rs
index 0161daff..8397f2c6 100644
--- a/alacritty_terminal/src/grid/storage.rs
+++ b/alacritty_terminal/src/grid/storage.rs
@@ -1,4 +1,4 @@
-use std::cmp::Ordering;
+use std::cmp::{Ordering, PartialEq};
 use std::ops::{Index, IndexMut};
 use std::vec::Drain;
 
@@ -50,7 +50,7 @@ pub struct Storage<T> {
     len: usize,
 }
 
-impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
+impl<T: PartialEq> PartialEq for Storage<T> {
     fn eq(&self, other: &Self) -> bool {
         // Make sure length is equal
         if self.inner.len() != other.inner.len() {
@@ -62,9 +62,8 @@ impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
             if self.zero >= other.zero { (self, other) } else { (other, self) };
 
         // Calculate the actual zero offset
-        let len = self.inner.len();
-        let bigger_zero = bigger.zero % len;
-        let smaller_zero = smaller.zero % len;
+        let bigger_zero = bigger.zero;
+        let smaller_zero = smaller.zero;
 
         // Compare the slices in chunks
         // Chunks:
@@ -79,6 +78,7 @@ impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
         //   Smaller Zero (3):
         //     7  8  9  | 0  1  2  3  | 4  5  6
         //     C3 C3 C3 | C1 C1 C1 C1 | C2 C2 C2
+        let len = self.inner.len();
         bigger.inner[bigger_zero..]
             == smaller.inner[smaller_zero..smaller_zero + (len - bigger_zero)]
             && bigger.inner[..bigger_zero - smaller_zero]
@@ -149,7 +149,7 @@ impl<T> Storage<T> {
         }
 
         // Update raw buffer length and zero offset
-        self.zero = (self.zero + new_growage) % self.inner.len();
+        self.zero += new_growage;
         self.len += growage;
     }
 
@@ -201,19 +201,11 @@ impl<T> Storage<T> {
         self.len
     }
 
-    #[inline]
     /// Compute actual index in underlying storage given the requested index.
+    #[inline]
     fn compute_index(&self, requested: usize) -> usize {
         debug_assert!(requested < self.len);
-        let zeroed = requested + self.zero;
-
-        // This part is critical for performance,
-        // so an if/else is used here instead of a moludo operation
-        if zeroed >= self.inner.len() {
-            zeroed - self.inner.len()
-        } else {
-            zeroed
-        }
+        self.wrap_index(self.zero + requested)
     }
 
     pub fn swap_lines(&mut self, a: Line, b: Line) {
@@ -256,31 +248,48 @@ impl<T> Storage<T> {
         }
     }
 
+    /// Rotate the grid, moving all lines up/down in history.
     #[inline]
     pub fn rotate(&mut self, count: isize) {
         debug_assert!(count.abs() as usize <= self.inner.len());
 
         let len = self.inner.len();
-        self.zero = (self.zero as isize + count + len as isize) as usize % len;
+        self.zero = self.wrap_index((self.zero as isize + count + len as isize) as usize);
     }
 
-    // Fast path
+    /// Rotate the grid up, moving all existing lines down in history.
+    ///
+    /// This is a faster, specialized version of [`rotate`].
     #[inline]
     pub fn rotate_up(&mut self, count: usize) {
-        self.zero = (self.zero + count) % self.inner.len();
+        self.zero = self.wrap_index(self.zero + count);
     }
 
+    /// Drain all rows in the grid.
     pub fn drain(&mut self) -> Drain<'_, Row<T>> {
         self.truncate();
         self.inner.drain(..)
     }
 
-    /// Update the raw storage buffer
+    /// Update the raw storage buffer.
     pub fn replace_inner(&mut self, vec: Vec<Row<T>>) {
         self.len = vec.len();
         self.inner = vec;
         self.zero = 0;
     }
+
+    /// Wrap index to be within the inner buffer.
+    ///
+    /// This uses if/else instead of the remainder to improve performance,
+    /// so the assumption is made that `index < self.inner.len() * 2`.
+    #[inline]
+    fn wrap_index(&self, index: usize) -> usize {
+        if index >= self.inner.len() {
+            index - self.inner.len()
+        } else {
+            index
+        }
+    }
 }
 
 impl<T> Index<usize> for Storage<T> {
@@ -335,6 +344,10 @@ mod test {
         }
 
         fn set_wrap(&mut self, _wrap: bool) {}
+
+        fn fast_eq(&self, other: Self) -> bool {
+            self == &other
+        }
     }
 
     #[test]
diff --git a/alacritty_terminal/src/grid/tests.rs b/alacritty_terminal/src/grid/tests.rs
index d28e7833..f3480b14 100644
--- a/alacritty_terminal/src/grid/tests.rs
+++ b/alacritty_terminal/src/grid/tests.rs
@@ -29,6 +29,10 @@ impl GridCell for usize {
     }
 
     fn set_wrap(&mut self, _wrap: bool) {}
+
+    fn fast_eq(&self, other: Self) -> bool {
+        self == &other
+    }
 }
 
 // Scroll up moves lines upwards