Use dynamic storage for zerowidth characters

The zerowidth characters were conventionally stored in a [char; 5].
This creates problems both by limiting the maximum number of zerowidth
characters and by increasing the cell size beyond what is necessary even
when no zerowidth characters are used.

Instead of storing zerowidth characters as a slice, a new CellExtra
struct is introduced which can store arbitrary optional cell data that
is rarely required. Since this is stored behind an optional pointer
(Option<Box<CellExtra>>), the initialization and dropping in the case
of no extra data are extremely cheap and the size penalty to cells
without this extra data is limited to 8 instead of 20 bytes.

The most noticible difference with this PR should be a reduction in
memory size of up to at least 30% (1.06G -> 733M, 100k scrollback, 72
lines, 280 columns). Since the zerowidth characters are now stored
dynamically, the limit of 5 per cell is also no longer present.

1 files changed, 80 insertions, 71 deletions

diff --git a/alacritty_terminal/src/term/cell.rs b/alacritty_terminal/src/term/cell.rs
index ee95fcba..8ac3edd0 100644
--- a/alacritty_terminal/src/term/cell.rs
+++ b/alacritty_terminal/src/term/cell.rs
@@ -1,14 +1,12 @@
-use bitflags::bitflags;
+use std::boxed::Box;
 
+use bitflags::bitflags;
 use serde::{Deserialize, Serialize};
 
 use crate::ansi::{Color, NamedColor};
 use crate::grid::{self, GridCell};
 use crate::index::Column;
 
-/// Maximum number of zerowidth characters which will be stored per cell.
-pub const MAX_ZEROWIDTH_CHARS: usize = 5;
-
 bitflags! {
     #[derive(Serialize, Deserialize)]
     pub struct Flags: u16 {
@@ -29,23 +27,77 @@ bitflags! {
     }
 }
 
-const fn default_extra() -> [char; MAX_ZEROWIDTH_CHARS] {
-    [' '; MAX_ZEROWIDTH_CHARS]
+/// Trait for determining if a reset should be performed.
+pub trait ResetDiscriminant<T> {
+    /// Value based on which equality for the reset will be determined.
+    fn discriminant(&self) -> T;
+}
+
+impl<T: Copy> ResetDiscriminant<T> for T {
+    fn discriminant(&self) -> T {
+        *self
+    }
+}
+
+impl ResetDiscriminant<Color> for Cell {
+    fn discriminant(&self) -> Color {
+        self.bg
+    }
+}
+
+/// Dynamically allocated cell content.
+///
+/// This storage is reserved for cell attributes which are rarely set. This allows reducing the
+/// allocation required ahead of time for every cell, with some additional overhead when the extra
+/// storage is actually required.
+#[derive(Serialize, Deserialize, Default, Debug, Clone, Eq, PartialEq)]
+struct CellExtra {
+    zerowidth: Vec<char>,
 }
 
-#[derive(Copy, Clone, Debug, Serialize, Deserialize, Eq, PartialEq)]
+/// Content and attributes of a single cell in the terminal grid.
+#[derive(Serialize, Deserialize, Debug, Clone, Eq, PartialEq)]
 pub struct Cell {
     pub c: char,
     pub fg: Color,
     pub bg: Color,
     pub flags: Flags,
-    #[serde(default = "default_extra")]
-    pub extra: [char; MAX_ZEROWIDTH_CHARS],
+    #[serde(default)]
+    extra: Option<Box<CellExtra>>,
 }
 
 impl Default for Cell {
+    #[inline]
     fn default() -> Cell {
-        Cell::new(' ', Color::Named(NamedColor::Foreground), Color::Named(NamedColor::Background))
+        Cell {
+            c: ' ',
+            bg: Color::Named(NamedColor::Background),
+            fg: Color::Named(NamedColor::Foreground),
+            flags: Flags::empty(),
+            extra: None,
+        }
+    }
+}
+
+impl Cell {
+    /// Zerowidth characters stored in this cell.
+    #[inline]
+    pub fn zerowidth(&self) -> Option<&[char]> {
+        self.extra.as_ref().map(|extra| extra.zerowidth.as_slice())
+    }
+
+    /// Write a new zerowidth character to this cell.
+    #[inline]
+    pub fn push_zerowidth(&mut self, c: char) {
+        self.extra.get_or_insert_with(Default::default).zerowidth.push(c);
+    }
+
+    /// Free all dynamically allocated cell storage.
+    #[inline]
+    pub fn drop_extra(&mut self) {
+        if self.extra.is_some() {
+            self.extra = None;
+        }
     }
 }
 
@@ -53,7 +105,6 @@ impl GridCell for Cell {
     #[inline]
     fn is_empty(&self) -> bool {
         (self.c == ' ' || self.c == '\t')
-            && self.extra[0] == ' '
             && self.bg == Color::Named(NamedColor::Background)
             && self.fg == Color::Named(NamedColor::Foreground)
             && !self.flags.intersects(
@@ -65,6 +116,7 @@ impl GridCell for Cell {
                     | Flags::WIDE_CHAR_SPACER
                     | Flags::LEADING_WIDE_CHAR_SPACER,
             )
+            && self.extra.as_ref().map(|extra| extra.zerowidth.is_empty()) != Some(false)
     }
 
     #[inline]
@@ -78,8 +130,15 @@ impl GridCell for Cell {
     }
 
     #[inline]
-    fn fast_eq(&self, other: Self) -> bool {
-        self.bg == other.bg
+    fn reset(&mut self, template: &Self) {
+        *self = Cell { bg: template.bg, ..Cell::default() };
+    }
+}
+
+impl From<Color> for Cell {
+    #[inline]
+    fn from(color: Color) -> Self {
+        Self { bg: color, ..Cell::default() }
     }
 }
 
@@ -98,7 +157,9 @@ impl LineLength for grid::Row<Cell> {
         }
 
         for (index, cell) in self[..].iter().rev().enumerate() {
-            if cell.c != ' ' || cell.extra[0] != ' ' {
+            if cell.c != ' '
+                || cell.extra.as_ref().map(|extra| extra.zerowidth.is_empty()) == Some(false)
+            {
                 length = Column(self.len() - index);
                 break;
             }
@@ -108,57 +169,6 @@ impl LineLength for grid::Row<Cell> {
     }
 }
 
-impl Cell {
-    #[inline]
-    pub fn bold(&self) -> bool {
-        self.flags.contains(Flags::BOLD)
-    }
-
-    #[inline]
-    pub fn inverse(&self) -> bool {
-        self.flags.contains(Flags::INVERSE)
-    }
-
-    #[inline]
-    pub fn dim(&self) -> bool {
-        self.flags.contains(Flags::DIM)
-    }
-
-    pub fn new(c: char, fg: Color, bg: Color) -> Cell {
-        Cell { extra: [' '; MAX_ZEROWIDTH_CHARS], c, bg, fg, flags: Flags::empty() }
-    }
-
-    #[inline]
-    pub fn reset(&mut self, template: &Cell) {
-        // memcpy template to self.
-        *self = Cell { c: template.c, bg: template.bg, ..Cell::default() };
-    }
-
-    #[inline]
-    pub fn chars(&self) -> [char; MAX_ZEROWIDTH_CHARS + 1] {
-        unsafe {
-            let mut chars = [std::mem::MaybeUninit::uninit(); MAX_ZEROWIDTH_CHARS + 1];
-            std::ptr::write(chars[0].as_mut_ptr(), self.c);
-            std::ptr::copy_nonoverlapping(
-                self.extra.as_ptr() as *mut std::mem::MaybeUninit<char>,
-                chars.as_mut_ptr().offset(1),
-                self.extra.len(),
-            );
-            std::mem::transmute(chars)
-        }
-    }
-
-    #[inline]
-    pub fn push_extra(&mut self, c: char) {
-        for elem in self.extra.iter_mut() {
-            if elem == &' ' {
-                *elem = c;
-                break;
-            }
-        }
-    }
-}
-
 #[cfg(test)]
 mod tests {
     use super::{Cell, LineLength};
@@ -168,8 +178,7 @@ mod tests {
 
     #[test]
     fn line_length_works() {
-        let template = Cell::default();
-        let mut row = Row::new(Column(10), template);
+        let mut row = Row::<Cell>::new(Column(10));
         row[Column(5)].c = 'a';
 
         assert_eq!(row.line_length(), Column(6));
@@ -177,8 +186,7 @@ mod tests {
 
     #[test]
     fn line_length_works_with_wrapline() {
-        let template = Cell::default();
-        let mut row = Row::new(Column(10), template);
+        let mut row = Row::<Cell>::new(Column(10));
         row[Column(9)].flags.insert(super::Flags::WRAPLINE);
 
         assert_eq!(row.line_length(), Column(10));
@@ -188,7 +196,8 @@ mod tests {
 #[cfg(all(test, feature = "bench"))]
 mod benches {
     extern crate test;
-    use super::Cell;
+
+    use super::*;
 
     #[bench]
     fn cell_reset(b: &mut test::Bencher) {
@@ -196,7 +205,7 @@ mod benches {
             let mut cell = Cell::default();
 
             for _ in 0..100 {
-                cell.reset(test::black_box(&Cell::default()));
+                cell = test::black_box(Color::Named(NamedColor::Foreground).into());
             }
 
             test::black_box(cell);