Dynamically initialize grid storage

Previously Alacritty has initialized all lines in the buffer as soon as
it is started. This had the effect that terminals which aren't making
use of the scrollback buffer yet, would still consume large amounts of
memory, potentially even freezing the system at startup.

To resolve this problem, the grid is now dynamically resized in chunks
of `1000` rows. The initial size is just the visible area itself, then
every time lines are written to the terminal emulator, the grid storage
is grown when required.

With the worst-case scenario of having 100_000 lines scrollback
configured, this change improves startup performance at the cost of
scrolling performance.

On my machine the startup changes from ~0.3 to ~0.2 seconds.

The scrolling performance with large throughput is not affected, however
it is slowed down when the number of lines scrolled are close to the
100_000 configured as scrollback. The most taxing benchmark I've found
for this was running `yes | dd count=500 > 500.txt` (note the relatively
small file size). This will cause a slowdown on the first run from 0.05s
to 0.15s. While this is significant, it lines up with the time saved at
startup.

This fixes #1236.

2 files changed, 82 insertions, 25 deletions

diff --git a/src/grid/mod.rs b/src/grid/mod.rs
index 680aa7bd..b8feb421 100644
--- a/src/grid/mod.rs
+++ b/src/grid/mod.rs
@@ -29,6 +29,8 @@ mod tests;
 mod storage;
 use self::storage::Storage;
 
+const MIN_INIT_SIZE: usize = 1_000;
+
 /// Bidirection iterator
 pub trait BidirectionalIterator: Iterator {
     fn prev(&mut self) -> Option<Self::Item>;
@@ -92,6 +94,9 @@ pub struct Grid<T> {
     /// Selected region
     #[serde(skip)]
     pub selection: Option<Selection>,
+
+    #[serde(default)]
+    max_scroll_limit: usize,
 }
 
 pub struct GridIterator<'a, T: 'a> {
@@ -113,7 +118,7 @@ pub enum Scroll {
 
 impl<T: Copy + Clone> Grid<T> {
     pub fn new(lines: index::Line, cols: index::Column, scrollback: usize, template: T) -> Grid<T> {
-        let raw = Storage::with_capacity(*lines + scrollback, lines, Row::new(cols, &template));
+        let raw = Storage::with_capacity(lines, Row::new(cols, &template));
         Grid {
             raw,
             cols,
@@ -121,6 +126,7 @@ impl<T: Copy + Clone> Grid<T> {
             display_offset: 0,
             scroll_limit: 0,
             selection: None,
+            max_scroll_limit: scrollback,
         }
     }
 
@@ -206,11 +212,19 @@ impl<T: Copy + Clone> Grid<T> {
         }
     }
 
-    fn increase_scroll_limit(&mut self, count: usize) {
-        self.scroll_limit = min(
-            self.scroll_limit + count,
-            self.raw.len().saturating_sub(*self.lines),
-        );
+    fn increase_scroll_limit(&mut self, count: usize, template: &T)
+    {
+        self.scroll_limit = min(self.scroll_limit + count, self.max_scroll_limit);
+
+        // Initialize new lines when the history buffer is smaller than the scroll limit
+        let history_size = self.raw.len().saturating_sub(*self.lines);
+        if history_size < self.scroll_limit {
+            let new = min(
+                max(self.scroll_limit - history_size, MIN_INIT_SIZE),
+                self.max_scroll_limit - history_size,
+            );
+            self.raw.initialize(new, Row::new(self.cols, template));
+        }
     }
 
     fn decrease_scroll_limit(&mut self, count: usize) {
@@ -356,7 +370,7 @@ impl<T: Copy + Clone> Grid<T> {
                 );
             }
 
-            self.increase_scroll_limit(*positions);
+            self.increase_scroll_limit(*positions, template);
 
             // Rotate the entire line buffer. If there's a scrolling region
             // active, the bottom lines are restored in the next step.
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
index 55c73b87..a23f0f37 100644
--- a/src/grid/storage.rs
+++ b/src/grid/storage.rs
@@ -79,18 +79,18 @@ impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
 
 impl<T> Storage<T> {
     #[inline]
-    pub fn with_capacity(cap: usize, lines: Line, template: Row<T>) -> Storage<T>
+    pub fn with_capacity(lines: Line, template: Row<T>) -> Storage<T>
     where
         T: Clone,
     {
-        // Allocate all lines in the buffer, including scrollback history
-        let inner = vec![template; cap];
+        // Initialize visible lines, the scrollback buffer is initialized dynamically
+        let inner = vec![template; lines.0];
 
         Storage {
             inner,
             zero: 0,
             visible_lines: lines - 1,
-            len: cap,
+            len: lines.0,
         }
     }
 
@@ -169,23 +169,24 @@ impl<T> Storage<T> {
 
     /// Truncate the invisible elements from the raw buffer
     pub fn truncate(&mut self) {
-        // Calculate shrinkage/offset for indexing
-        let shrinkage = self.inner.len() - self.len;
-        let shrinkage_start = ::std::cmp::min(self.zero, shrinkage);
+        self.inner.rotate_left(self.zero);
+        self.inner.truncate(self.len);
 
-        // Create two vectors with correct ordering
-        let mut split = self.inner.split_off(self.zero);
+        self.zero = 0;
+    }
 
-        // Truncate the buffers
-        let len = self.inner.len();
-        let split_len = split.len();
-        self.inner.truncate(len - shrinkage_start);
-        split.truncate(split_len - (shrinkage - shrinkage_start));
+    /// Dynamically grow the storage buffer at runtime
+    pub fn initialize(&mut self, num_rows: usize, template_row: Row<T>)
+        where T: Clone
+    {
+        let mut new = vec![template_row; num_rows];
 
-        // Merge buffers again and reset zero
-        split.append(&mut self.inner);
-        self.inner = split;
-        self.zero = 0;
+        let mut split = self.inner.split_off(self.zero);
+        self.inner.append(&mut new);
+        self.inner.append(&mut split);
+
+        self.zero += num_rows;
+        self.len += num_rows;
     }
 
     #[inline]
@@ -649,3 +650,45 @@ fn shrink_then_grow() {
     assert_eq!(storage.zero, growing_expected.zero);
     assert_eq!(storage.len, growing_expected.len);
 }
+
+#[test]
+fn initialize() {
+    // Setup storage area
+    let mut storage = Storage {
+        inner: vec![
+            Row::new(Column(1), &'4'),
+            Row::new(Column(1), &'5'),
+            Row::new(Column(1), &'0'),
+            Row::new(Column(1), &'1'),
+            Row::new(Column(1), &'2'),
+            Row::new(Column(1), &'3'),
+        ],
+        zero: 2,
+        visible_lines: Line(0),
+        len: 6,
+    };
+
+    // Initialize additional lines
+    storage.initialize(3, Row::new(Column(1), &'-'));
+
+    // Make sure the lines are present and at the right location
+    let shrinking_expected = Storage {
+        inner: vec![
+            Row::new(Column(1), &'4'),
+            Row::new(Column(1), &'5'),
+            Row::new(Column(1), &'-'),
+            Row::new(Column(1), &'-'),
+            Row::new(Column(1), &'-'),
+            Row::new(Column(1), &'0'),
+            Row::new(Column(1), &'1'),
+            Row::new(Column(1), &'2'),
+            Row::new(Column(1), &'3'),
+        ],
+        zero: 5,
+        visible_lines: Line(0),
+        len: 9,
+    };
+    assert_eq!(storage.inner, shrinking_expected.inner);
+    assert_eq!(storage.zero, shrinking_expected.zero);
+    assert_eq!(storage.len, shrinking_expected.len);
+}