Improve rendering performance

This PR combines a couple of optimizations to drastically reduce the
time it takes to gather everything necessary for rendering Alacritty's
terminal grid.

To help with the iteration over the grid, the `DisplayIter` which made
heavy use of dynamic dispatch has been replaced with a simple addition
to the `GridIterator` which also had the benefit of making the code a
little easier to understand.

The hints/search check for each cell was always performing an array
lookup before figuring out that the cell is not part of a hint or
search. Since the general case is that the cell is neither part of hints
or search, they've been wrapped in an `Option` to make verifying their
activity a simple `is_some()` check.

For some reason the compiler was also struggling with the `cursor`
method of the `RenderableContent`. Since the iterator is explicitly
drained, the performance took a hit of multiple milliseconds for a
single branch. Our implementation does never reach the case where
draining the iterator would be necessary, so this sanity check has just
been replaced with a `debug_assert`.

Overall this has managed to reduce the time it takes to collect all
renderable content from ~7-8ms in my large grid test to just ~3-4ms.

6 files changed, 77 insertions, 65 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 45f58d57..14984fd5 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,10 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/).
 
 - Support for `ipfs`/`ipns` URLs
 
+### Fixed
+
+- Regression in rendering performance with dense grids since 0.6.0
+
 ## 0.8.0
 
 ### Packaging
diff --git a/alacritty/src/display/content.rs b/alacritty/src/display/content.rs
index 4bef44f5..926ac7bd 100644
--- a/alacritty/src/display/content.rs
+++ b/alacritty/src/display/content.rs
@@ -11,9 +11,7 @@ use alacritty_terminal::index::{Column, Direction, Line, Point};
 use alacritty_terminal::term::cell::{Cell, Flags};
 use alacritty_terminal::term::color::{CellRgb, Rgb};
 use alacritty_terminal::term::search::{Match, RegexIter, RegexSearch};
-use alacritty_terminal::term::{
-    RenderableContent as TerminalContent, RenderableCursor as TerminalCursor, Term, TermMode,
-};
+use alacritty_terminal::term::{RenderableContent as TerminalContent, Term, TermMode};
 
 use crate::config::ui_config::UiConfig;
 use crate::display::color::{List, DIM_FACTOR};
@@ -29,10 +27,11 @@ pub const MIN_CURSOR_CONTRAST: f64 = 1.5;
 /// This provides the terminal cursor and an iterator over all non-empty cells.
 pub struct RenderableContent<'a> {
     terminal_content: TerminalContent<'a>,
-    terminal_cursor: TerminalCursor,
     cursor: Option<RenderableCursor>,
-    search: Regex<'a>,
-    hint: Hint<'a>,
+    cursor_shape: CursorShape,
+    cursor_point: Point<usize>,
+    search: Option<Regex<'a>>,
+    hint: Option<Hint<'a>>,
     config: &'a Config<UiConfig>,
     colors: &'a List,
     focused_match: Option<&'a Match>,
@@ -45,31 +44,41 @@ impl<'a> RenderableContent<'a> {
         term: &'a Term<T>,
         search_state: &'a SearchState,
     ) -> Self {
-        let search = search_state.dfas().map(|dfas| Regex::new(&term, dfas)).unwrap_or_default();
+        let search = search_state.dfas().map(|dfas| Regex::new(&term, dfas));
         let focused_match = search_state.focused_match();
         let terminal_content = term.renderable_content();
 
-        // Copy the cursor and override its shape if necessary.
-        let mut terminal_cursor = terminal_content.cursor;
-
-        if terminal_cursor.shape == CursorShape::Hidden
+        // Find terminal cursor shape.
+        let cursor_shape = if terminal_content.cursor.shape == CursorShape::Hidden
             || display.cursor_hidden
             || search_state.regex().is_some()
         {
-            terminal_cursor.shape = CursorShape::Hidden;
+            CursorShape::Hidden
         } else if !term.is_focused && config.cursor.unfocused_hollow {
-            terminal_cursor.shape = CursorShape::HollowBlock;
-        }
+            CursorShape::HollowBlock
+        } else {
+            terminal_content.cursor.shape
+        };
+
+        // Convert terminal cursor point to viewport position.
+        let cursor_point = terminal_content.cursor.point;
+        let display_offset = terminal_content.display_offset;
+        let cursor_point = display::point_to_viewport(display_offset, cursor_point).unwrap();
 
-        display.hint_state.update_matches(term);
-        let hint = Hint::from(&display.hint_state);
+        let hint = if display.hint_state.active() {
+            display.hint_state.update_matches(term);
+            Some(Hint::from(&display.hint_state))
+        } else {
+            None
+        };
 
         Self {
             colors: &display.colors,
             cursor: None,
             terminal_content,
-            terminal_cursor,
             focused_match,
+            cursor_shape,
+            cursor_point,
             search,
             config,
             hint,
@@ -83,8 +92,8 @@ impl<'a> RenderableContent<'a> {
 
     /// Get the terminal cursor.
     pub fn cursor(mut self) -> Option<RenderableCursor> {
-        // Drain the iterator to make sure the cursor is created.
-        while self.next().is_some() && self.cursor.is_none() {}
+        // Assure this function is only called after the iterator has been drained.
+        debug_assert!(self.next().is_none());
 
         self.cursor
     }
@@ -98,7 +107,7 @@ impl<'a> RenderableContent<'a> {
     ///
     /// This will return `None` when there is no cursor visible.
     fn renderable_cursor(&mut self, cell: &RenderableCell) -> Option<RenderableCursor> {
-        if self.terminal_cursor.shape == CursorShape::Hidden {
+        if self.cursor_shape == CursorShape::Hidden {
             return None;
         }
 
@@ -125,17 +134,12 @@ impl<'a> RenderableContent<'a> {
         let text_color = text_color.color(cell.fg, cell.bg);
         let cursor_color = cursor_color.color(cell.fg, cell.bg);
 
-        // Convert cursor point to viewport position.
-        let cursor_point = self.terminal_cursor.point;
-        let display_offset = self.terminal_content.display_offset;
-        let point = display::point_to_viewport(display_offset, cursor_point).unwrap();
-
         Some(RenderableCursor {
             is_wide: cell.flags.contains(Flags::WIDE_CHAR),
-            shape: self.terminal_cursor.shape,
+            shape: self.cursor_shape,
+            point: self.cursor_point,
             cursor_color,
             text_color,
-            point,
         })
     }
 }
@@ -151,10 +155,9 @@ impl<'a> Iterator for RenderableContent<'a> {
     fn next(&mut self) -> Option<Self::Item> {
         loop {
             let cell = self.terminal_content.display_iter.next()?;
-            let cell_point = cell.point;
             let mut cell = RenderableCell::new(self, cell);
 
-            if self.terminal_cursor.point == cell_point {
+            if self.cursor_point == cell.point {
                 // Store the cursor which should be rendered.
                 self.cursor = self.renderable_cursor(&cell).map(|cursor| {
                     if cursor.shape == CursorShape::Block {
@@ -203,17 +206,22 @@ impl RenderableCell {
             Self::compute_bg_alpha(cell.bg)
         };
 
-        let is_selected = content
-            .terminal_content
-            .selection
-            .map_or(false, |selection| selection.contains_cell(&cell, content.terminal_cursor));
+        let is_selected = content.terminal_content.selection.map_or(false, |selection| {
+            selection.contains_cell(
+                &cell,
+                content.terminal_content.cursor.point,
+                content.cursor_shape,
+            )
+        });
 
         let display_offset = content.terminal_content.display_offset;
         let viewport_start = Point::new(Line(-(display_offset as i32)), Column(0));
         let colors = &content.config.ui_config.colors;
         let mut character = cell.c;
 
-        if let Some((c, is_first)) = content.hint.advance(viewport_start, cell.point) {
+        if let Some((c, is_first)) =
+            content.hint.as_mut().and_then(|hint| hint.advance(viewport_start, cell.point))
+        {
             let (config_fg, config_bg) = if is_first {
                 (colors.hints.start.foreground, colors.hints.start.background)
             } else {
@@ -233,7 +241,7 @@ impl RenderableCell {
                 bg = content.color(NamedColor::Foreground as usize);
                 bg_alpha = 1.0;
             }
-        } else if content.search.advance(cell.point) {
+        } else if content.search.as_mut().map_or(false, |search| search.advance(cell.point)) {
             let focused = content.focused_match.map_or(false, |fm| fm.contains(&cell.point));
             let (config_fg, config_bg) = if focused {
                 (colors.search.focused_match.foreground, colors.search.focused_match.background)
@@ -261,9 +269,9 @@ impl RenderableCell {
     /// Check if cell contains any renderable content.
     fn is_empty(&self) -> bool {
         self.bg_alpha == 0.
-            && !self.flags.intersects(Flags::UNDERLINE | Flags::STRIKEOUT | Flags::DOUBLE_UNDERLINE)
             && self.character == ' '
             && self.zerowidth.is_none()
+            && !self.flags.intersects(Flags::UNDERLINE | Flags::STRIKEOUT | Flags::DOUBLE_UNDERLINE)
     }
 
     /// Apply [`CellRgb`] colors to the cell's colors.
diff --git a/alacritty/src/input.rs b/alacritty/src/input.rs
index 3559b85e..948ec67f 100644
--- a/alacritty/src/input.rs
+++ b/alacritty/src/input.rs
@@ -996,7 +996,6 @@ mod tests {
     use glutin::event::{Event as GlutinEvent, VirtualKeyCode, WindowEvent};
 
     use alacritty_terminal::event::Event as TerminalEvent;
-    use alacritty_terminal::selection::Selection;
 
     use crate::config::Binding;
     use crate::message_bar::MessageBuffer;
@@ -1008,7 +1007,6 @@ mod tests {
 
     struct ActionContext<'a, T> {
         pub terminal: &'a mut Term<T>,
-        pub selection: &'a mut Option<Selection>,
         pub size_info: &'a SizeInfo,
         pub mouse: &'a mut Mouse,
         pub clipboard: &'a mut Clipboard,
@@ -1145,13 +1143,10 @@ mod tests {
                     ..Mouse::default()
                 };
 
-                let mut selection = None;
-
                 let mut message_buffer = MessageBuffer::new();
 
                 let context = ActionContext {
                     terminal: &mut terminal,
-                    selection: &mut selection,
                     mouse: &mut mouse,
                     size_info: &size,
                     clipboard: &mut clipboard,
diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 06af3bea..df83d7e3 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -1,7 +1,6 @@
 //! A specialized 2D grid implementation optimized for use in a terminal.
 
 use std::cmp::{max, min};
-use std::iter::TakeWhile;
 use std::ops::{Bound, Deref, Index, IndexMut, Range, RangeBounds};
 
 use serde::{Deserialize, Serialize};
@@ -398,22 +397,25 @@ impl<T> Grid<T> {
         self.raw.truncate();
     }
 
+    /// Iterate over all cells in the grid starting at a specific point.
     #[inline]
     pub fn iter_from(&self, point: Point) -> GridIterator<'_, T> {
-        GridIterator { grid: self, point }
+        let end = Point::new(self.bottommost_line(), self.last_column());
+        GridIterator { grid: self, point, end }
     }
 
-    /// Iterator over all visible cells.
+    /// Iterate over all visible cells.
+    ///
+    /// This is slightly more optimized than calling `Grid::iter_from` in combination with
+    /// `Iterator::take_while`.
     #[inline]
-    pub fn display_iter(&self) -> DisplayIter<'_, T> {
-        let start = Point::new(Line(-(self.display_offset as i32) - 1), self.last_column());
-        let end = Point::new(start.line + self.lines, Column(self.columns));
-
-        let iter = GridIterator { grid: self, point: start };
+    pub fn display_iter(&self) -> GridIterator<'_, T> {
+        let last_column = self.last_column();
+        let start = Point::new(Line(-(self.display_offset() as i32) - 1), last_column);
+        let end_line = min(start.line + self.screen_lines(), self.bottommost_line());
+        let end = Point::new(end_line, last_column);
 
-        let take_while: DisplayIterTakeFun<'_, T> =
-            Box::new(move |indexed: &Indexed<&T>| indexed.point <= end);
-        iter.take_while(take_while)
+        GridIterator { grid: self, point: start, end }
     }
 
     #[inline]
@@ -560,6 +562,9 @@ pub struct GridIterator<'a, T> {
 
     /// Current position of the iterator within the grid.
     point: Point,
+
+    /// Last cell included in the iterator.
+    end: Point,
 }
 
 impl<'a, T> GridIterator<'a, T> {
@@ -578,15 +583,13 @@ impl<'a, T> Iterator for GridIterator<'a, T> {
     type Item = Indexed<&'a T>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        let last_column = self.grid.last_column();
-
         // Stop once we've reached the end of the grid.
-        if self.point == Point::new(self.grid.bottommost_line(), last_column) {
+        if self.point >= self.end {
             return None;
         }
 
         match self.point {
-            Point { column, .. } if column == last_column => {
+            Point { column, .. } if column == self.grid.last_column() => {
                 self.point.column = Column(0);
                 self.point.line += 1;
             },
@@ -623,6 +626,3 @@ impl<'a, T> BidirectionalIterator for GridIterator<'a, T> {
         Some(Indexed { cell: &self.grid[self.point], point: self.point })
     }
 }
-
-pub type DisplayIter<'a, T> = TakeWhile<GridIterator<'a, T>, DisplayIterTakeFun<'a, T>>;
-type DisplayIterTakeFun<'a, T> = Box<dyn Fn(&Indexed<&'a T>) -> bool>;
diff --git a/alacritty_terminal/src/selection.rs b/alacritty_terminal/src/selection.rs
index 428b3f0e..47a49910 100644
--- a/alacritty_terminal/src/selection.rs
+++ b/alacritty_terminal/src/selection.rs
@@ -13,7 +13,7 @@ use crate::ansi::CursorShape;
 use crate::grid::{Dimensions, GridCell, Indexed};
 use crate::index::{Boundary, Column, Line, Point, Side};
 use crate::term::cell::{Cell, Flags};
-use crate::term::{RenderableCursor, Term};
+use crate::term::Term;
 
 /// A Point and side within that point.
 #[derive(Debug, Copy, Clone, PartialEq)]
@@ -56,10 +56,15 @@ impl SelectionRange {
     }
 
     /// Check if the cell at a point is part of the selection.
-    pub fn contains_cell(&self, indexed: &Indexed<&Cell>, cursor: RenderableCursor) -> bool {
+    pub fn contains_cell(
+        &self,
+        indexed: &Indexed<&Cell>,
+        point: Point,
+        shape: CursorShape,
+    ) -> bool {
         // Do not invert block cursor at selection boundaries.
-        if cursor.shape == CursorShape::Block
-            && cursor.point == indexed.point
+        if shape == CursorShape::Block
+            && point == indexed.point
             && (self.start == indexed.point
                 || self.end == indexed.point
                 || (self.is_block
diff --git a/alacritty_terminal/src/term/mod.rs b/alacritty_terminal/src/term/mod.rs
index 409d4ebe..2fb4da34 100644
--- a/alacritty_terminal/src/term/mod.rs
+++ b/alacritty_terminal/src/term/mod.rs
@@ -15,7 +15,7 @@ use crate::ansi::{
 };
 use crate::config::Config;
 use crate::event::{Event, EventListener};
-use crate::grid::{Dimensions, DisplayIter, Grid, Scroll};
+use crate::grid::{Dimensions, Grid, GridIterator, Scroll};
 use crate::index::{self, Boundary, Column, Direction, Line, Point, Side};
 use crate::selection::{Selection, SelectionRange};
 use crate::term::cell::{Cell, Flags, LineLength};
@@ -1828,7 +1828,7 @@ impl RenderableCursor {
 ///
 /// This contains all content required to render the current terminal view.
 pub struct RenderableContent<'a> {
-    pub display_iter: DisplayIter<'a, Cell>,
+    pub display_iter: GridIterator<'a, Cell>,
     pub selection: Option<SelectionRange>,
     pub cursor: RenderableCursor,
     pub display_offset: usize,