Render underline and strikeout rects in batches

Currently Alacritty requires a separate `draw` call to OpenGL whenever a
new rectangle is rendered to the screen. With many rectangles visible,
this has a significant impact on rendering performance.

Instead of using separate draw calls, the new `RectRenderer` will build
a batch of rectangles for rendering. This makes sure that multiple
rectangles can be grouped together for single draw calls allowing a
reduced impact on rendering time.

Since this change is OpenGL 2 friendly, it should not make it more
complicated to transition away from the 3.3+ requirements like an
alternative instancing based implementation might have.

5 files changed, 234 insertions, 169 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 32844199..0a53ee90 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -24,6 +24,7 @@ The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/).
 - Preserve vi mode across terminal `reset`
 - Escapes `CSI Ps b` and `CSI Ps Z` with large parameters locking up Alacritty
 - Dimming colors which use the indexed `CSI 38 : 5 : Ps m` notation
+- Slow rendering performance with a lot of cells with underline/strikeout attributes
 - Performance of scrolling regions with offset from the bottom
 
 ### Removed
diff --git a/alacritty/res/rect.f.glsl b/alacritty/res/rect.f.glsl
index edea07dc..945eaf2d 100644
--- a/alacritty/res/rect.f.glsl
+++ b/alacritty/res/rect.f.glsl
@@ -1,6 +1,6 @@
 #version 330 core
 
-uniform vec4 color;
+flat in vec4 color;
 
 out vec4 FragColor;
 
diff --git a/alacritty/res/rect.v.glsl b/alacritty/res/rect.v.glsl
index 02be0bee..bf9a97d3 100644
--- a/alacritty/res/rect.v.glsl
+++ b/alacritty/res/rect.v.glsl
@@ -1,7 +1,11 @@
 #version 330 core
 layout (location = 0) in vec2 aPos;
+layout (location = 1) in vec4 aColor;
+
+flat out vec4 color;
 
 void main()
 {
+    color = aColor;
     gl_Position = vec4(aPos.x, aPos.y, 0.0, 1.0);
 }
diff --git a/alacritty/src/renderer/mod.rs b/alacritty/src/renderer/mod.rs
index af1f3c3e..ccdd2812 100644
--- a/alacritty/src/renderer/mod.rs
+++ b/alacritty/src/renderer/mod.rs
@@ -30,21 +30,17 @@ use crate::config::ui_config::{Delta, UIConfig};
 use crate::cursor;
 use crate::gl;
 use crate::gl::types::*;
-use crate::renderer::rects::RenderRect;
+use crate::renderer::rects::{RectRenderer, RectShaderProgram, RenderRect};
 
 pub mod rects;
 
 // Shader paths for live reload.
 static TEXT_SHADER_F_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/text.f.glsl");
 static TEXT_SHADER_V_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/text.v.glsl");
-static RECT_SHADER_F_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/rect.f.glsl");
-static RECT_SHADER_V_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/rect.v.glsl");
 
 // Shader source which is used when live-shader-reload feature is disable.
 static TEXT_SHADER_F: &str = include_str!("../../res/text.f.glsl");
 static TEXT_SHADER_V: &str = include_str!("../../res/text.v.glsl");
-static RECT_SHADER_F: &str = include_str!("../../res/rect.f.glsl");
-static RECT_SHADER_V: &str = include_str!("../../res/rect.v.glsl");
 
 /// `LoadGlyph` allows for copying a rasterized glyph into graphics memory.
 pub trait LoadGlyph {
@@ -110,17 +106,6 @@ pub struct TextShaderProgram {
     u_background: GLint,
 }
 
-/// Rectangle drawing program.
-///
-/// Uniforms are prefixed with "u".
-#[derive(Debug)]
-pub struct RectShaderProgram {
-    /// Program id.
-    id: GLuint,
-    /// Rectangle color.
-    u_color: GLint,
-}
-
 #[derive(Copy, Debug, Clone)]
 pub struct Glyph {
     tex_id: GLuint,
@@ -410,17 +395,16 @@ struct InstanceData {
 #[derive(Debug)]
 pub struct QuadRenderer {
     program: TextShaderProgram,
-    rect_program: RectShaderProgram,
     vao: GLuint,
     ebo: GLuint,
     vbo_instance: GLuint,
-    rect_vao: GLuint,
-    rect_vbo: GLuint,
     atlas: Vec<Atlas>,
     current_atlas: usize,
     active_tex: GLuint,
     batch: Batch,
     rx: mpsc::Receiver<Msg>,
+
+    rect_renderer: RectRenderer,
 }
 
 #[derive(Debug)]
@@ -526,17 +510,12 @@ const ATLAS_SIZE: i32 = 1024;
 impl QuadRenderer {
     pub fn new() -> Result<QuadRenderer, Error> {
         let program = TextShaderProgram::new()?;
-        let rect_program = RectShaderProgram::new()?;
 
         let mut vao: GLuint = 0;
         let mut ebo: GLuint = 0;
 
         let mut vbo_instance: GLuint = 0;
 
-        let mut rect_vao: GLuint = 0;
-        let mut rect_vbo: GLuint = 0;
-        let mut rect_ebo: GLuint = 0;
-
         unsafe {
             gl::Enable(gl::BLEND);
             gl::BlendFunc(gl::SRC1_COLOR, gl::ONE_MINUS_SRC1_COLOR);
@@ -617,20 +596,6 @@ impl QuadRenderer {
             // Background color.
             add_attr!(4, gl::UNSIGNED_BYTE, u8);
 
-            // Rectangle setup.
-            gl::GenVertexArrays(1, &mut rect_vao);
-            gl::GenBuffers(1, &mut rect_vbo);
-            gl::GenBuffers(1, &mut rect_ebo);
-            gl::BindVertexArray(rect_vao);
-            let indices: [i32; 6] = [0, 1, 3, 1, 2, 3];
-            gl::BindBuffer(gl::ELEMENT_ARRAY_BUFFER, rect_ebo);
-            gl::BufferData(
-                gl::ELEMENT_ARRAY_BUFFER,
-                (size_of::<i32>() * indices.len()) as _,
-                indices.as_ptr() as *const _,
-                gl::STATIC_DRAW,
-            );
-
             // Cleanup.
             gl::BindVertexArray(0);
             gl::BindBuffer(gl::ARRAY_BUFFER, 0);
@@ -651,6 +616,12 @@ impl QuadRenderer {
                 watcher
                     .watch(TEXT_SHADER_V_PATH, RecursiveMode::NonRecursive)
                     .expect("watch vertex shader");
+                watcher
+                    .watch(rects::RECT_SHADER_V_PATH, RecursiveMode::NonRecursive)
+                    .expect("watch rect vertex shader");
+                watcher
+                    .watch(rects::RECT_SHADER_F_PATH, RecursiveMode::NonRecursive)
+                    .expect("watch rect fragment shader");
 
                 loop {
                     let event = rx.recv().expect("watcher event");
@@ -670,12 +641,10 @@ impl QuadRenderer {
 
         let mut renderer = Self {
             program,
-            rect_program,
+            rect_renderer: RectRenderer::new()?,
             vao,
             ebo,
             vbo_instance,
-            rect_vao,
-            rect_vbo,
             atlas: Vec::new(),
             current_atlas: 0,
             active_tex: 0,
@@ -690,56 +659,31 @@ impl QuadRenderer {
     }
 
     /// Draw all rectangles simultaneously to prevent excessive program swaps.
-    pub fn draw_rects(&mut self, props: &SizeInfo, rects: Vec<RenderRect>) {
-        // Swap to rectangle rendering program.
-        unsafe {
-            // Swap program.
-            gl::UseProgram(self.rect_program.id);
+    pub fn draw_rects(&mut self, size_info: &SizeInfo, rects: Vec<RenderRect>) {
+        if rects.is_empty() {
+            return;
+        }
 
+        // Prepare rect rendering state.
+        unsafe {
             // Remove padding from viewport.
-            gl::Viewport(0, 0, props.width() as i32, props.height() as i32);
-
-            // Change blending strategy.
+            gl::Viewport(0, 0, size_info.width() as i32, size_info.height() as i32);
             gl::BlendFuncSeparate(gl::SRC_ALPHA, gl::ONE_MINUS_SRC_ALPHA, gl::SRC_ALPHA, gl::ONE);
-
-            // Setup data and buffers.
-            gl::BindVertexArray(self.rect_vao);
-            gl::BindBuffer(gl::ARRAY_BUFFER, self.rect_vbo);
-
-            // Position.
-            gl::VertexAttribPointer(
-                0,
-                2,
-                gl::FLOAT,
-                gl::FALSE,
-                (size_of::<f32>() * 2) as _,
-                ptr::null(),
-            );
-            gl::EnableVertexAttribArray(0);
         }
 
-        // Draw all the rects.
-        for rect in rects {
-            self.render_rect(&rect, props);
-        }
+        self.rect_renderer.draw(size_info, rects);
 
-        // Deactivate rectangle program again.
+        // Activate regular state again.
         unsafe {
             // Reset blending strategy.
             gl::BlendFunc(gl::SRC1_COLOR, gl::ONE_MINUS_SRC1_COLOR);
 
-            // Reset data and buffers.
-            gl::BindBuffer(gl::ARRAY_BUFFER, 0);
-            gl::BindVertexArray(0);
-
-            let padding_x = props.padding_x() as i32;
-            let padding_y = props.padding_y() as i32;
-            let width = props.width() as i32;
-            let height = props.height() as i32;
+            // Restore viewport with padding.
+            let padding_x = size_info.padding_x() as i32;
+            let padding_y = size_info.padding_y() as i32;
+            let width = size_info.width() as i32;
+            let height = size_info.height() as i32;
             gl::Viewport(padding_x, padding_y, width - 2 * padding_x, height - 2 * padding_y);
-
-            // Disable program.
-            gl::UseProgram(0);
         }
     }
 
@@ -832,7 +776,7 @@ impl QuadRenderer {
 
         self.active_tex = 0;
         self.program = program;
-        self.rect_program = rect_program;
+        self.rect_renderer.set_program(rect_program);
     }
 
     pub fn resize(&mut self, size: &SizeInfo) {
@@ -856,43 +800,6 @@ impl QuadRenderer {
             gl::UseProgram(0);
         }
     }
-
-    /// Render a rectangle.
-    ///
-    /// This requires the rectangle program to be activated.
-    fn render_rect(&mut self, rect: &RenderRect, size: &SizeInfo) {
-        // Do nothing when alpha is fully transparent.
-        if rect.alpha == 0. {
-            return;
-        }
-
-        // Calculate rectangle position.
-        let center_x = size.width() / 2.;
-        let center_y = size.height() / 2.;
-        let x = (rect.x - center_x) / center_x;
-        let y = -(rect.y - center_y) / center_y;
-        let width = rect.width / center_x;
-        let height = rect.height / center_y;
-
-        unsafe {
-            // Setup vertices.
-            let vertices: [f32; 8] = [x + width, y, x + width, y - height, x, y - height, x, y];
-
-            // Load vertex data into array buffer.
-            gl::BufferData(
-                gl::ARRAY_BUFFER,
-                (size_of::<f32>() * vertices.len()) as _,
-                vertices.as_ptr() as *const _,
-                gl::STATIC_DRAW,
-            );
-
-            // Color.
-            self.rect_program.set_color(rect.color, rect.alpha);
-
-            // Draw the rectangle.
-            gl::DrawElements(gl::TRIANGLES, 6, gl::UNSIGNED_INT, ptr::null());
-        }
-    }
 }
 
 impl<'a> RenderApi<'a> {
@@ -1237,55 +1144,7 @@ impl Drop for TextShaderProgram {
     }
 }
 
-impl RectShaderProgram {
-    pub fn new() -> Result<Self, ShaderCreationError> {
-        let (vertex_src, fragment_src) = if cfg!(feature = "live-shader-reload") {
-            (None, None)
-        } else {
-            (Some(RECT_SHADER_V), Some(RECT_SHADER_F))
-        };
-        let vertex_shader = create_shader(RECT_SHADER_V_PATH, gl::VERTEX_SHADER, vertex_src)?;
-        let fragment_shader = create_shader(RECT_SHADER_F_PATH, gl::FRAGMENT_SHADER, fragment_src)?;
-        let program = create_program(vertex_shader, fragment_shader)?;
-
-        unsafe {
-            gl::DeleteShader(fragment_shader);
-            gl::DeleteShader(vertex_shader);
-            gl::UseProgram(program);
-        }
-
-        // Get uniform locations.
-        let u_color = unsafe { gl::GetUniformLocation(program, b"color\0".as_ptr() as *const _) };
-
-        let shader = Self { id: program, u_color };
-
-        unsafe { gl::UseProgram(0) }
-
-        Ok(shader)
-    }
-
-    fn set_color(&self, color: Rgb, alpha: f32) {
-        unsafe {
-            gl::Uniform4f(
-                self.u_color,
-                f32::from(color.r) / 255.,
-                f32::from(color.g) / 255.,
-                f32::from(color.b) / 255.,
-                alpha,
-            );
-        }
-    }
-}
-
-impl Drop for RectShaderProgram {
-    fn drop(&mut self) {
-        unsafe {
-            gl::DeleteProgram(self.id);
-        }
-    }
-}
-
-fn create_program(vertex: GLuint, fragment: GLuint) -> Result<GLuint, ShaderCreationError> {
+pub fn create_program(vertex: GLuint, fragment: GLuint) -> Result<GLuint, ShaderCreationError> {
     unsafe {
         let program = gl::CreateProgram();
         gl::AttachShader(program, vertex);
@@ -1303,7 +1162,7 @@ fn create_program(vertex: GLuint, fragment: GLuint) -> Result<GLuint, ShaderCrea
     }
 }
 
-fn create_shader(
+pub fn create_shader(
     path: &str,
     kind: GLenum,
     source: Option<&'static str>,
diff --git a/alacritty/src/renderer/rects.rs b/alacritty/src/renderer/rects.rs
index 2a727b4c..040e0e4b 100644
--- a/alacritty/src/renderer/rects.rs
+++ b/alacritty/src/renderer/rects.rs
@@ -1,4 +1,5 @@
 use std::collections::HashMap;
+use std::mem;
 
 use crossfont::Metrics;
 
@@ -7,6 +8,10 @@ use alacritty_terminal::term::cell::Flags;
 use alacritty_terminal::term::color::Rgb;
 use alacritty_terminal::term::{RenderableCell, SizeInfo};
 
+use crate::gl;
+use crate::gl::types::*;
+use crate::renderer;
+
 #[derive(Debug, Copy, Clone)]
 pub struct RenderRect {
     pub x: f32,
@@ -190,3 +195,199 @@ impl RenderLines {
         }
     }
 }
+
+/// Shader sources for rect rendering program.
+pub static RECT_SHADER_F_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/rect.f.glsl");
+pub static RECT_SHADER_V_PATH: &str = concat!(env!("CARGO_MANIFEST_DIR"), "/res/rect.v.glsl");
+static RECT_SHADER_F: &str = include_str!("../../res/rect.f.glsl");
+static RECT_SHADER_V: &str = include_str!("../../res/rect.v.glsl");
+
+#[repr(C)]
+#[derive(Debug, Clone, Copy)]
+struct Vertex {
+    // Normalized screen coordinates.
+    x: f32,
+    y: f32,
+
+    // Color.
+    r: u8,
+    g: u8,
+    b: u8,
+    a: u8,
+}
+
+#[derive(Debug)]
+pub struct RectRenderer {
+    // GL buffer objects.
+    vao: GLuint,
+    vbo: GLuint,
+
+    program: RectShaderProgram,
+
+    vertices: Vec<Vertex>,
+}
+
+impl RectRenderer {
+    /// Update program when doing live-shader-reload.
+    pub fn set_program(&mut self, program: RectShaderProgram) {
+        self.program = program;
+    }
+
+    pub fn new() -> Result<Self, renderer::Error> {
+        let mut vao: GLuint = 0;
+        let mut vbo: GLuint = 0;
+        let program = RectShaderProgram::new()?;
+
+        unsafe {
+            // Allocate buffers.
+            gl::GenVertexArrays(1, &mut vao);
+            gl::GenBuffers(1, &mut vbo);
+
+            gl::BindVertexArray(vao);
+
+            // VBO binding is not part of VAO itself, but VBO binding is stored in attributes.
+            gl::BindBuffer(gl::ARRAY_BUFFER, vbo);
+
+            let mut attribute_offset = 0;
+
+            // Position.
+            gl::VertexAttribPointer(
+                0,
+                2,
+                gl::FLOAT,
+                gl::FALSE,
+                mem::size_of::<Vertex>() as i32,
+                attribute_offset as *const _,
+            );
+            gl::EnableVertexAttribArray(0);
+            attribute_offset += mem::size_of::<f32>() * 2;
+
+            // Color.
+            gl::VertexAttribPointer(
+                1,
+                4,
+                gl::UNSIGNED_BYTE,
+                gl::TRUE,
+                mem::size_of::<Vertex>() as i32,
+                attribute_offset as *const _,
+            );
+            gl::EnableVertexAttribArray(1);
+
+            // Reset buffer bindings.
+            gl::BindVertexArray(0);
+            gl::BindBuffer(gl::ARRAY_BUFFER, 0);
+        }
+
+        Ok(Self { vao, vbo, program, vertices: Vec::new() })
+    }
+
+    pub fn draw(&mut self, size_info: &SizeInfo, rects: Vec<RenderRect>) {
+        unsafe {
+            // Bind VAO to enable vertex attribute slots.
+            gl::BindVertexArray(self.vao);
+
+            // Bind VBO only once for buffer data upload only.
+            gl::BindBuffer(gl::ARRAY_BUFFER, self.vbo);
+
+            gl::UseProgram(self.program.id);
+        }
+
+        let half_width = size_info.width() / 2.;
+        let half_height = size_info.height() / 2.;
+
+        // Build rect vertices vector.
+        self.vertices.clear();
+        for rect in &rects {
+            self.add_rect(half_width, half_height, rect);
+        }
+
+        unsafe {
+            // Upload accumulated vertices.
+            gl::BufferData(
+                gl::ARRAY_BUFFER,
+                (self.vertices.len() * mem::size_of::<Vertex>()) as isize,
+                self.vertices.as_ptr() as *const _,
+                gl::STREAM_DRAW,
+            );
+
+            // Draw all vertices as list of triangles.
+            gl::DrawArrays(gl::TRIANGLES, 0, self.vertices.len() as i32);
+
+            // Disable program.
+            gl::UseProgram(0);
+
+            // Reset buffer bindings to nothing.
+            gl::BindBuffer(gl::ARRAY_BUFFER, 0);
+            gl::BindVertexArray(0);
+        }
+    }
+
+    fn add_rect(&mut self, half_width: f32, half_height: f32, rect: &RenderRect) {
+        // Calculate rectangle vertices positions in normalized device coordinates.
+        // NDC range from -1 to +1, with Y pointing up.
+        let x = rect.x / half_width - 1.0;
+        let y = -rect.y / half_height + 1.0;
+        let width = rect.width / half_width;
+        let height = rect.height / half_height;
+        let Rgb { r, g, b } = rect.color;
+        let a = (rect.alpha * 255.) as u8;
+
+        // Make quad vertices.
+        let quad = [
+            Vertex { x, y, r, g, b, a },
+            Vertex { x, y: y - height, r, g, b, a },
+            Vertex { x: x + width, y, r, g, b, a },
+            Vertex { x: x + width, y: y - height, r, g, b, a },
+        ];
+
+        // Append the vertices to form two triangles.
+        self.vertices.push(quad[0]);
+        self.vertices.push(quad[1]);
+        self.vertices.push(quad[2]);
+        self.vertices.push(quad[2]);
+        self.vertices.push(quad[3]);
+        self.vertices.push(quad[1]);
+    }
+}
+
+/// Rectangle drawing program.
+#[derive(Debug)]
+pub struct RectShaderProgram {
+    /// Program id.
+    id: GLuint,
+}
+
+impl RectShaderProgram {
+    pub fn new() -> Result<Self, renderer::ShaderCreationError> {
+        let (vertex_src, fragment_src) = if cfg!(feature = "live-shader-reload") {
+            (None, None)
+        } else {
+            (Some(RECT_SHADER_V), Some(RECT_SHADER_F))
+        };
+        let vertex_shader =
+            renderer::create_shader(RECT_SHADER_V_PATH, gl::VERTEX_SHADER, vertex_src)?;
+        let fragment_shader =
+            renderer::create_shader(RECT_SHADER_F_PATH, gl::FRAGMENT_SHADER, fragment_src)?;
+        let program = renderer::create_program(vertex_shader, fragment_shader)?;
+
+        unsafe {
+            gl::DeleteShader(fragment_shader);
+            gl::DeleteShader(vertex_shader);
+            gl::UseProgram(program);
+        }
+
+        let shader = Self { id: program };
+
+        unsafe { gl::UseProgram(0) }
+
+        Ok(shader)
+    }
+}
+
+impl Drop for RectShaderProgram {
+    fn drop(&mut self) {
+        unsafe {
+            gl::DeleteProgram(self.id);
+        }
+    }
+}