Optimize editing long text by caching each paragraph (#5411)

afishhh · emilk · web-flow · commit 557bd56e1962 · 2025-04-01T18:55:39.000+02:00
## What (written by @emilk) When editing long text (thousands of line), egui would previously re-layout the entire text on each edit. This could be slow. With this PR, we instead split the text into paragraphs (split on `\n`) and then cache each such paragraph. When editing text then, only the changed paragraph needs to be laid out again. Still, there is overhead from splitting the text, hashing each paragraph, and then joining the results, so the runtime complexity is still O(N). In our benchmark, editing a 2000 line string goes from ~8ms to ~300 ms, a speedup of ~25x. In the future, we could also consider laying out each paragraph in parallel, to speed up the initial layout of the text. ## Details This is an ~~almost complete~~ implementation of the approach described by emilk [in this comment](<#3086 (comment)>), excluding CoW semantics for `LayoutJob` (but including them for `Row`). It supersedes the previous unsuccessful attempt here: #4000. Draft because: - [X] ~~Currently individual rows will have `ends_with_newline` always set to false. This breaks selection with Ctrl+A (and probably many other things)~~ - [X] ~~The whole block for doing the splitting and merging should probably become a function (I'll do that later).~~ - [X] ~~I haven't run the check script, the tests, and haven't made sure all of the examples build (although I assume they probably don't rely on Galley internals).~~ - [x] ~~Layout is sometimes incorrect (missing empty lines, wrapping sometimes makes text overlap).~~ - A lot of text-related code had to be changed so this needs to be properly tested to ensure no layout issues were introduced, especially relating to the now row-relative coordinate system of `Row`s. Also this requires that we're fine making these very breaking changes. It does significantly improve the performance of rendering large blocks of text (if they have many newlines), this is the test program I used to test it (adapted from <#3086>): <details> <summary>code</summary> ```rust use eframe::egui::{self, CentralPanel, TextEdit}; use std::fmt::Write; fn main() -> Result<(), eframe::Error> { let options = eframe::NativeOptions { ..Default::default() }; eframe::run_native( "editor big file test", options, Box::new(|_cc| Ok(Box::<MyApp>::new(MyApp::new()))), ) } struct MyApp { text: String, } impl MyApp { fn new() -> Self { let mut string = String::new(); for line_bytes in (0..50000).map(|_| (0u8..50)) { for byte in line_bytes { write!(string, " {byte:02x}").unwrap(); } write!(string, "\n").unwrap(); } println!("total bytes: {}", string.len()); MyApp { text: string } } } impl eframe::App for MyApp { fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) { CentralPanel::default().show(ctx, |ui| { let start = std::time::Instant::now(); egui::ScrollArea::vertical().show(ui, |ui| { let code_editor = TextEdit::multiline(&mut self.text) .code_editor() .desired_width(f32::INFINITY) .desired_rows(40); let response = code_editor.show(ui).response; if response.changed() { println!("total bytes now: {}", self.text.len()); } }); let end = std::time::Instant::now(); let time_to_update = end - start; if time_to_update.as_secs_f32() > 0.5 { println!("Long update took {:.3}s", time_to_update.as_secs_f32()) } }); } } ``` </details> I think the way to proceed would be to make a new type, something like `PositionedRow`, that would wrap an `Arc<Row>` but have a separate `pos` ~~and `ends_with_newline`~~ (that would mean `Row` only holds a `size` instead of a `rect`). This type would of course have getters that would allow you to easily get a `Rect` from it and probably a `Deref` to the underlying `Row`. ~~I haven't done this yet because I wanted to get some opinions whether this would be an acceptable API first.~~ This is now implemented, but of course I'm still open to discussion about this approach and whether it's what we want to do. Breaking changes (currently): - The `Galley::rows` field has a different type. - There is now a `PlacedRow` wrapper for `Row`. - `Row` now uses a coordinate system relative to itself instead of the `Galley`. * Closes <#3086> * [X] I have followed the instructions in the PR template --------- Co-authored-by: Emil Ernerfeldt <emil.ernerfeldt@gmail.com>
diff --git a/Cargo.lock b/Cargo.lock
@@ -642,6 +642,17 @@ dependencies = [
  "piper",
 ]
 
+[[package]]
+name = "bstr"
+version = "1.11.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "531a9155a481e2ee699d4f98f43c0ca4ff8ee1bfd55c31e9e98fb29d2b176fe0"
+dependencies = [
+ "memchr",
+ "regex-automata",
+ "serde",
+]
+
 [[package]]
 name = "bumpalo"
 version = "3.16.0"
@@ -896,6 +907,18 @@ dependencies = [
  "env_logger",
 ]
 
+[[package]]
+name = "console"
+version = "0.15.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "054ccb5b10f9f2cbf51eb355ca1d05c2d279ce1804688d0db74b4733a5aeafd8"
+dependencies = [
+ "encode_unicode",
+ "libc",
+ "once_cell",
+ "windows-sys 0.59.0",
+]
+
 [[package]]
 name = "core-foundation"
 version = "0.9.4"
@@ -1331,6 +1354,7 @@ dependencies = [
  "egui",
  "egui_extras",
  "egui_kittest",
+ "rand",
  "serde",
  "unicode_names2",
 ]
@@ -1420,6 +1444,12 @@ dependencies = [
  "serde",
 ]
 
+[[package]]
+name = "encode_unicode"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34aa73646ffb006b8f5147f3dc182bd4bcb190227ce861fc4a4844bf8e3cb2c0"
+
 [[package]]
 name = "endi"
 version = "1.1.0"
@@ -1520,6 +1550,7 @@ dependencies = [
  "profiling",
  "rayon",
  "serde",
+ "similar-asserts",
 ]
 
 [[package]]
@@ -2389,7 +2420,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "4979f22fdb869068da03c9f7528f8297c6fd2606bc3a4affe42e6a823fdb8da4"
 dependencies = [
  "cfg-if",
- "windows-targets 0.48.5",
+ "windows-targets 0.52.6",
 ]
 
 [[package]]
@@ -3669,6 +3700,26 @@ version = "0.3.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d66dc143e6b11c1eddc06d5c423cfc97062865baf299914ab64caa38182078fe"
 
+[[package]]
+name = "similar"
+version = "2.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bbbb5d9659141646ae647b42fe094daf6c6192d1620870b449d9557f748b2daa"
+dependencies = [
+ "bstr",
+ "unicode-segmentation",
+]
+
+[[package]]
+name = "similar-asserts"
+version = "1.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b5b441962c817e33508847a22bd82f03a30cff43642dc2fae8b050566121eb9a"
+dependencies = [
+ "console",
+ "similar",
+]
+
 [[package]]
 name = "simplecss"
 version = "0.2.1"
diff --git a/Cargo.toml b/Cargo.toml
@@ -96,6 +96,7 @@ puffin_http = "0.16"
 raw-window-handle = "0.6.0"
 ron = "0.8"
 serde = { version = "1", features = ["derive"] }
+similar-asserts = "1.4.2"
 thiserror = "1.0.37"
 type-map = "0.5.0"
 wasm-bindgen = "0.2"
diff --git a/crates/egui/src/text_selection/accesskit_text.rs b/crates/egui/src/text_selection/accesskit_text.rs
@@ -45,7 +45,7 @@ pub fn update_accesskit_for_text_widget(
             let row_id = parent_id.with(row_index);
             ctx.accesskit_node_builder(row_id, |builder| {
                 builder.set_role(accesskit::Role::TextRun);
-                let rect = global_from_galley * row.rect;
+                let rect = global_from_galley * row.rect();
                 builder.set_bounds(accesskit::Rect {
                     x0: rect.min.x.into(),
                     y0: rect.min.y.into(),
@@ -76,14 +76,14 @@ pub fn update_accesskit_for_text_widget(
                     let old_len = value.len();
                     value.push(glyph.chr);
                     character_lengths.push((value.len() - old_len) as _);
-                    character_positions.push(glyph.pos.x - row.rect.min.x);
+                    character_positions.push(glyph.pos.x - row.pos.x);
                     character_widths.push(glyph.advance_width);
                 }
 
                 if row.ends_with_newline {
                     value.push('\n');
                     character_lengths.push(1);
-                    character_positions.push(row.rect.max.x - row.rect.min.x);
+                    character_positions.push(row.size.x);
                     character_widths.push(0.0);
                 }
                 word_lengths.push((character_lengths.len() - last_word_start) as _);
diff --git a/crates/egui/src/text_selection/label_text_selection.rs b/crates/egui/src/text_selection/label_text_selection.rs
@@ -186,7 +186,10 @@ impl LabelSelectionState {
                                 if let epaint::Shape::Text(text_shape) = &mut shape.shape {
                                     let galley = Arc::make_mut(&mut text_shape.galley);
                                     for row_selection in row_selections {
-                                        if let Some(row) = galley.rows.get_mut(row_selection.row) {
+                                        if let Some(placed_row) =
+                                            galley.rows.get_mut(row_selection.row)
+                                        {
+                                            let row = Arc::make_mut(&mut placed_row.row);
                                             for vertex_index in row_selection.vertex_indices {
                                                 if let Some(vertex) = row
                                                     .visuals
@@ -701,8 +704,8 @@ fn selected_text(galley: &Galley, cursor_range: &CCursorRange) -> String {
 }
 
 fn estimate_row_height(galley: &Galley) -> f32 {
-    if let Some(row) = galley.rows.first() {
-        row.rect.height()
+    if let Some(placed_row) = galley.rows.first() {
+        placed_row.height()
     } else {
         galley.size().y
     }
diff --git a/crates/egui/src/text_selection/visuals.rs b/crates/egui/src/text_selection/visuals.rs
@@ -31,11 +31,12 @@ pub fn paint_text_selection(
     let max = galley.layout_from_cursor(max);
 
     for ri in min.row..=max.row {
-        let row = &mut galley.rows[ri];
+        let row = Arc::make_mut(&mut galley.rows[ri].row);
+
         let left = if ri == min.row {
             row.x_offset(min.column)
         } else {
-            row.rect.left()
+            0.0
         };
         let right = if ri == max.row {
             row.x_offset(max.column)
@@ -45,10 +46,10 @@ pub fn paint_text_selection(
             } else {
                 0.0
             };
-            row.rect.right() + newline_size
+            row.size.x + newline_size
         };
 
-        let rect = Rect::from_min_max(pos2(left, row.min_y()), pos2(right, row.max_y()));
+        let rect = Rect::from_min_max(pos2(left, 0.0), pos2(right, row.size.y));
         let mesh = &mut row.visuals.mesh;
 
         // Time to insert the selection rectangle into the row mesh.
diff --git a/crates/egui/src/widget_text.rs b/crates/egui/src/widget_text.rs
@@ -671,8 +671,8 @@ impl WidgetText {
             Self::RichText(text) => text.font_height(fonts, style),
             Self::LayoutJob(job) => job.font_height(fonts),
             Self::Galley(galley) => {
-                if let Some(row) = galley.rows.first() {
-                    row.height().round_ui()
+                if let Some(placed_row) = galley.rows.first() {
+                    placed_row.height().round_ui()
                 } else {
                     galley.size().y.round_ui()
                 }
diff --git a/crates/egui/src/widgets/label.rs b/crates/egui/src/widgets/label.rs
@@ -1,8 +1,8 @@
 use std::sync::Arc;
 
 use crate::{
-    epaint, pos2, text_selection, vec2, Align, Direction, FontSelection, Galley, Pos2, Response,
-    Sense, Stroke, TextWrapMode, Ui, Widget, WidgetInfo, WidgetText, WidgetType,
+    epaint, pos2, text_selection, Align, Direction, FontSelection, Galley, Pos2, Response, Sense,
+    Stroke, TextWrapMode, Ui, Widget, WidgetInfo, WidgetText, WidgetType,
 };
 
 use self::text_selection::LabelSelectionState;
@@ -216,10 +216,10 @@ impl Label {
             let pos = pos2(ui.max_rect().left(), ui.cursor().top());
             assert!(!galley.rows.is_empty(), "Galleys are never empty");
             // collect a response from many rows:
-            let rect = galley.rows[0].rect.translate(vec2(pos.x, pos.y));
+            let rect = galley.rows[0].rect().translate(pos.to_vec2());
             let mut response = ui.allocate_rect(rect, sense);
-            for row in galley.rows.iter().skip(1) {
-                let rect = row.rect.translate(vec2(pos.x, pos.y));
+            for placed_row in galley.rows.iter().skip(1) {
+                let rect = placed_row.rect().translate(pos.to_vec2());
                 response |= ui.allocate_rect(rect, sense);
             }
             (pos, galley, response)
diff --git a/crates/egui_demo_lib/Cargo.toml b/crates/egui_demo_lib/Cargo.toml
@@ -58,6 +58,7 @@ serde = { workspace = true, optional = true }
 criterion.workspace = true
 egui_kittest = { workspace = true, features = ["wgpu", "snapshot"] }
 egui = { workspace = true, features = ["default_fonts"] }
+rand = "0.9"
 
 [[bench]]
 name = "benchmark"
diff --git a/crates/egui_demo_lib/benches/benchmark.rs b/crates/egui_demo_lib/benches/benchmark.rs
@@ -1,7 +1,10 @@
+use std::fmt::Write as _;
+
 use criterion::{criterion_group, criterion_main, Criterion};
 
 use egui::epaint::TextShape;
 use egui_demo_lib::LOREM_IPSUM_LONG;
+use rand::Rng as _;
 
 pub fn criterion_benchmark(c: &mut Criterion) {
     use egui::RawInput;
@@ -128,6 +131,30 @@ pub fn criterion_benchmark(c: &mut Criterion) {
             });
         });
 
+        c.bench_function("text_layout_cached_many_lines_modified", |b| {
+            const NUM_LINES: usize = 2_000;
+
+            let mut string = String::new();
+            for _ in 0..NUM_LINES {
+                for i in 0..30_u8 {
+                    write!(string, "{i:02X} ").unwrap();
+                }
+                string.push('\n');
+            }
+
+            let mut rng = rand::rng();
+            b.iter(|| {
+                fonts.begin_pass(pixels_per_point, max_texture_side);
+
+                // Delete a random character, simulating a user making an edit in a long file:
+                let mut new_string = string.clone();
+                let idx = rng.random_range(0..string.len());
+                new_string.remove(idx);
+
+                fonts.layout(new_string, font_id.clone(), text_color, wrap_width);
+            });
+        });
+
         let galley = fonts.layout(LOREM_IPSUM_LONG.to_owned(), font_id, text_color, wrap_width);
         let font_image_size = fonts.font_image_size();
         let prepared_discs = fonts.texture_atlas().lock().prepared_discs();
diff --git a/crates/emath/src/pos2.rs b/crates/emath/src/pos2.rs
@@ -1,5 +1,7 @@
-use std::fmt;
-use std::ops::{Add, AddAssign, Sub, SubAssign};
+use std::{
+    fmt,
+    ops::{Add, AddAssign, MulAssign, Sub, SubAssign},
+};
 
 use crate::{lerp, Div, Mul, Vec2};
 
@@ -305,6 +307,14 @@ impl Mul<Pos2> for f32 {
     }
 }
 
+impl MulAssign<f32> for Pos2 {
+    #[inline(always)]
+    fn mul_assign(&mut self, rhs: f32) {
+        self.x *= rhs;
+        self.y *= rhs;
+    }
+}
+
 impl Div<f32> for Pos2 {
     type Output = Self;
 
diff --git a/crates/emath/src/rect.rs b/crates/emath/src/rect.rs
@@ -710,7 +710,11 @@ impl Rect {
 
 impl fmt::Debug for Rect {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "[{:?} - {:?}]", self.min, self.max)
+        if let Some(precision) = f.precision() {
+            write!(f, "[{1:.0$?} - {2:.0$?}]", precision, self.min, self.max)
+        } else {
+            write!(f, "[{:?} - {:?}]", self.min, self.max)
+        }
     }
 }
 
diff --git a/crates/epaint/Cargo.toml b/crates/epaint/Cargo.toml
@@ -101,6 +101,7 @@ backtrace = { workspace = true, optional = true }
 
 [dev-dependencies]
 criterion.workspace = true
+similar-asserts.workspace = true
 
 
 [[bench]]
diff --git a/crates/epaint/src/shape_transform.rs b/crates/epaint/src/shape_transform.rs
@@ -89,7 +89,8 @@ pub fn adjust_colors(
 
             if !galley.is_empty() {
                 let galley = Arc::make_mut(galley);
-                for row in &mut galley.rows {
+                for placed_row in &mut galley.rows {
+                    let row = Arc::make_mut(&mut placed_row.row);
                     for vertex in &mut row.visuals.mesh.vertices {
                         adjust_color(&mut vertex.color);
                     }
diff --git a/crates/epaint/src/shapes/shape.rs b/crates/epaint/src/shapes/shape.rs
@@ -456,39 +456,7 @@ impl Shape {
                 rect_shape.blur_width *= transform.scaling;
             }
             Self::Text(text_shape) => {
-                let TextShape {
-                    pos,
-                    galley,
-                    underline,
-                    fallback_color: _,
-                    override_text_color: _,
-                    opacity_factor: _,
-                    angle: _,
-                } = text_shape;
-
-                *pos = transform * *pos;
-                underline.width *= transform.scaling;
-
-                let Galley {
-                    job: _,
-                    rows,
-                    elided: _,
-                    rect,
-                    mesh_bounds,
-                    num_vertices: _,
-                    num_indices: _,
-                    pixels_per_point: _,
-                } = Arc::make_mut(galley);
-
-                for row in rows {
-                    row.visuals.mesh_bounds = transform.scaling * row.visuals.mesh_bounds;
-                    for v in &mut row.visuals.mesh.vertices {
-                        v.pos = Pos2::new(transform.scaling * v.pos.x, transform.scaling * v.pos.y);
-                    }
-                }
-
-                *mesh_bounds = transform.scaling * *mesh_bounds;
-                *rect = transform.scaling * *rect;
+                text_shape.transform(transform);
             }
             Self::Mesh(mesh) => {
                 Arc::make_mut(mesh).transform(transform);
diff --git a/crates/epaint/src/shapes/text_shape.rs b/crates/epaint/src/shapes/text_shape.rs
diff --git a/crates/epaint/src/stats.rs b/crates/epaint/src/stats.rs
diff --git a/crates/epaint/src/tessellator.rs b/crates/epaint/src/tessellator.rs
diff --git a/crates/epaint/src/text/fonts.rs b/crates/epaint/src/text/fonts.rs
diff --git a/crates/epaint/src/text/mod.rs b/crates/epaint/src/text/mod.rs
diff --git a/crates/epaint/src/text/text_layout.rs b/crates/epaint/src/text/text_layout.rs
diff --git a/crates/epaint/src/text/text_layout_types.rs b/crates/epaint/src/text/text_layout_types.rs
