Improve storage comparison algorithm

Instead of iterating over the raw storage vector because the offsets
don't allow direct comparison, the comparison is now done in chunks.
Based on benchmarking this is a lot more efficient than using split_off
+ append or iterating over the elements of the buffer.

The `history_size` field has also been removed from the storage
structure because it can be easily calculated by substracting the number
of visible lines from the length of the raw storage vector.

4 files changed, 56 insertions, 25 deletions

diff --git a/src/grid/mod.rs b/src/grid/mod.rs
index b6cff604..f3c8ea79 100644
--- a/src/grid/mod.rs
+++ b/src/grid/mod.rs
@@ -52,23 +52,13 @@ impl<T> Deref for Indexed<T> {
 
 impl<T: PartialEq> ::std::cmp::PartialEq for Grid<T> {
     fn eq(&self, other: &Self) -> bool {
-        // Compare raw grid content
-        // TODO: This is pretty inefficient but only used in tests
-        let mut raw_match = true;
-        for i in 0..(self.lines.0 + self.history_size) {
-            for j in 0..self.cols.0 {
-                if self[i][Column(j)] != other[i][Column(j)] {
-                    raw_match = false;
-                    break;
-                }
-            }
-        }
-
         // Compare struct fields and check result of grid comparison
-        self.cols.eq(&other.cols) &&
+        self.raw.eq(&other.raw) &&
+            self.cols.eq(&other.cols) &&
             self.lines.eq(&other.lines) &&
-            self.history_size.eq(&other.history_size) &&
-            raw_match
+            self.display_offset.eq(&other.display_offset) &&
+            self.scroll_limit.eq(&other.scroll_limit) &&
+            self.selection.eq(&other.selection)
     }
 }
 
@@ -102,10 +92,6 @@ pub struct Grid<T> {
     /// Selected region
     #[serde(skip)]
     pub selection: Option<Selection>,
-
-    /// Maximum number of lines in the scrollback history
-    #[serde(default)]
-    history_size: usize,
 }
 
 pub struct GridIterator<'a, T: 'a> {
@@ -150,7 +136,6 @@ impl<T: Copy + Clone> Grid<T> {
             display_offset: 0,
             scroll_limit: 0,
             selection: None,
-            history_size: scrollback,
         }
     }
 
@@ -426,6 +411,12 @@ impl<T> Grid<T> {
         self.scroll_limit = 0;
     }
 
+    /// Total number of lines in the buffer, this includes scrollback + visible lines
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.raw.len()
+    }
+
     pub fn iter_from(&self, point: Point<usize>) -> GridIterator<T> {
         GridIterator {
             grid: self,
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
index 66e0ccc8..323d8ec4 100644
--- a/src/grid/storage.rs
+++ b/src/grid/storage.rs
@@ -22,6 +22,47 @@ pub struct Storage<T> {
     visible_lines: Line,
 }
 
+impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
+    fn eq(&self, other: &Self) -> bool {
+        // Make sure length is equal
+        if self.inner.len() != other.inner.len() {
+            return false;
+        }
+
+        // Check which vec has the bigger zero
+        let (ref bigger, ref smaller) = 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;
+
+        // Compare the slices in chunks
+        // Chunks:
+        //   - Bigger zero to the end
+        //   - Remaining lines in smaller zero vec
+        //   - Beginning of smaller zero vec
+        //
+        // Example:
+        //   Bigger Zero (6):
+        //     4  5  6  | 7  8  9  | 0  1  2  3
+        //     C2 C2 C2 | C3 C3 C3 | C1 C1 C1 C1
+        //   Smaller Zero (3):
+        //     7  8  9  | 0  1  2  3  | 4  5  6
+        //     C3 C3 C3 | C1 C1 C1 C1 | C2 C2 C2
+        &bigger.inner[bigger_zero..]
+            == &smaller.inner[smaller_zero..smaller_zero + (len - bigger_zero)]
+            && &bigger.inner[..bigger_zero - smaller_zero]
+                == &smaller.inner[smaller_zero + (len - bigger_zero)..]
+            && &bigger.inner[bigger_zero - smaller_zero..bigger_zero]
+                == &smaller.inner[..smaller_zero]
+    }
+}
+
 impl<T> Storage<T> {
     #[inline]
     pub fn with_capacity(cap: usize, lines: Line) -> Storage<T> {
diff --git a/src/selection.rs b/src/selection.rs
index 6f910bce..a54bd49d 100644
--- a/src/selection.rs
+++ b/src/selection.rs
@@ -38,7 +38,7 @@ use index::{Point, Column, Side};
 /// [`simple`]: enum.Selection.html#method.simple
 /// [`semantic`]: enum.Selection.html#method.semantic
 /// [`lines`]: enum.Selection.html#method.lines
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq)]
 pub enum Selection {
     Simple {
         /// The region representing start and end of cursor movement
@@ -64,7 +64,7 @@ pub enum Selection {
 }
 
 /// A Point and side within that point.
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq)]
 pub struct Anchor {
     point: Point<usize>,
     side: Side,
diff --git a/tests/ref.rs b/tests/ref.rs
index 0c8c9768..9ea0b80c 100644
--- a/tests/ref.rs
+++ b/tests/ref.rs
@@ -6,7 +6,6 @@ use std::io::{self, Read};
 use std::path::Path;
 
 use alacritty::Grid;
-use alacritty::grid::IndexRegion;
 use alacritty::Term;
 use alacritty::ansi;
 use alacritty::index::Column;
@@ -81,7 +80,7 @@ fn ref_test(dir: &Path) {
     let grid: Grid<Cell> = json::from_str(&serialized_grid).unwrap();
 
     let mut config: Config = Default::default();
-    config.set_history(grid.history_size() as u32);
+    config.set_history((grid.len() - grid.num_lines().0) as u32);
 
     let mut terminal = Term::new(&config, size);
     let mut parser = ansi::Processor::new();
@@ -91,7 +90,7 @@ fn ref_test(dir: &Path) {
     }
 
     if grid != *terminal.grid() {
-        for i in 0..(grid.num_lines().0 + grid.history_size()) {
+        for i in 0..grid.len() {
             for j in 0..grid.num_cols().0 {
                 let cell = terminal.grid()[i][Column(j)];
                 let original_cell = grid[i][Column(j)];