Optimize editing long text by caching each paragraph by afishhh · Pull Request #5411 · emilk/egui

afishhh · 2024-11-28T18:37:35Z

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, excluding CoW semantics for LayoutJob (but including them for Row).
It supersedes the previous unsuccessful attempt here: #4000.

Draft because:

Currently individual rows will have ends_with_newline always set to false.
This breaks selection with Ctrl+A (and probably many other things)
~~The whole block for doing the splitting and merging should probably become a function (I'll do that later).~~
~~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).~~
~~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 Rows. 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):

code

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())
            }
        });
    }
}

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 Optimizing re-layout of 1MB+ pieces of text in a TextEdit #3086
I have followed the instructions in the PR template

github-actions · 2024-11-28T19:50:48Z

Preview available at https://egui-pr-preview.github.io/pr/5411-cachegalleylines
Note that it might take a couple seconds for the update to show up after the preview_build workflow has completed.

afishhh · 2024-11-29T15:10:57Z

Okay, so I did the thing and implemented the Row wrapper. This turned out to be more difficult than expected, and requires changing the semantics of Rows themselves. glyphs and the mesh(_bounds) must be relative to the Row itself, instead of the whole Galley, as otherwise repositioning them wouldn't work (unless we did something hacky like store two different offsets). Currently I also implemented Deref<Target = Row> for the PlacedRow wrapper (bike-shedding appreciated) which may not be the best idea as it makes it easy to confuse the different coordinate systems of the offset and non-offset Row.

Currently this "somewhat" works, I've managed to fix the selection issues I was seeing, but there is some layout issues you can actually see in the live demo above where the text is overlapping sometimes when wrapped (since this was present before the whole PlacedRow mess, I think this may be related to galley-merging).

afishhh · 2024-11-30T16:07:34Z

So I've managed to make this look pretty correct, these are the remaining issues:

Rows now have very weird semantics because an empty Row that is in-between two non-empty lines will actually have a size of zero. This could be solved by actually incorporating the line-terminating newline into the cached job, but there is one issue with that approach because then each of the line galleys will now contain a trailing Row that would have to be treated specially by the merging code.
~~I've definitely introduced changes in rounding which is probably what makes the snapshot tests fail (apart from the fact that they sometimes segfault on my machine).~~
Issues now solved (except the rendering_tests are still utterly broken on my machine)

afishhh · 2024-11-30T17:34:39Z

I think I've made some good progress:

Made Row hold ends_with_newline again and just dropped excess rows during galley-merging, this means Row once again has pretty sensible semantics.
Properly respecting LayoutJob::round_output_size_to_nearest_ui_point fixed a lot of the snapshot test failures.

The remaining test failures are:

~~All rendering tests seem to have slight differences but in separators not in text which suggests that sizing might be ever so slightly wrong.~~ Turns out this also happens on master for me, so it probably is unrelated to my changes.
It looks like I can make more tests pass by using software rendering (WGPU_ADAPTER_NAME=llvmpipe) but still not all of them (dpi_1.25 and dpi_1.75 fail), so I'm going to pass this off as the graphics driver's fault.
~~The "Misc Demos" snapshot test also seems to fail, possibly due to a slightly incorrect alignment after the button widget?~~ I've managed to remove the most hacky line of this patch and fix this in one fell swoop!.

~~I'm wondering whether it is worth fixing fixing these tests, should I just regenerate the snapshots instead?~~
Also I think stats don't take into account the fact multiple Galleys can point to the same Row.

emilk

This looks good! I haven't reviewed all of GalleyCache yet, because it is a very dense and complex function.

I wonder how we best test and/or benchmark this though 🤔

I defiantly feel we should have a benchmark to justify this code, i.e. something that shows a big speedup before/after this PR.

emilk · 2024-12-04T14:43:28Z

crates/epaint/src/text/text_layout.rs

+    // Note we **don't** ignore the leading/trailing whitespace here!
+    row.size.x = target_max_x - target_min_x;


Why? What does this affect?

Ah, now that I think about it changing this comment was a mistake, leading and trailing whitespace is actually still ignored (I don't know why I thought otherwise). I'll change it back.
However ignoring whitespace here does seem kind of strange since the current docs for Row::rect say that it includes whitespace. Wouldn't this be wrong after it passes through this function? Maybe at least that documentation could be adjusted to clarify this is only true for left-aligned non-justified text.

I also noticed a more important issue though I think, this function actually makes Rows have glyphs that are outside their PlacedRow::pos + Row::size rectangle (because it just repositions the glyphs and leaves the position unchanged). This currently breaks selecting such text. I'll try to fix this soon.

Fixed the issue found above and the comment. Although I still want to know what you think about changing the Row::size comment, in general halign is surprising with how it suddenly totally changes how the coordinates work even though it makes perfect sense in hindsight.

crates/epaint/src/tessellator.rs

crates/epaint/src/text/fonts.rs

afishhh · 2024-12-04T18:26:00Z

I wonder how we best test and/or benchmark this though 🤔

I defiantly feel we should have a benchmark to justify this code, i.e. something that shows a big speedup before/after this PR.

I agree having a benchmark would be nice, currently the only thing I have is "it looks quicker" when you have a lot of text (deletion of small segments works instantly for example).
At first I wanted to suggest a kittest benchmark but then I looked in crates/egui_demo_lib/benches/benchmark.rs and noticed there already seem to be text layout benchmarks, so it'd probably be relatively easy to do something like:

Have a big (few megabytes) block of text
Lay it out
In the benchmark loop:
- Randomly remove an N-byte segment from it (into a copy)
- Lay it out

As for tests, I've encountered issues with selection drawing multiple times while working on this at this point, so maybe it would be beneficial if this was actually checked by the test suite, it looks like mouse events are supported in kittest so maybe that's a good start. Especially since I also think selection visuals might be another good place for optimization because currently selecting the whole text will force all Rows to be cloned again.

It also looks like the rendering_test tests still seem to be failing on CI. The diffs seem to contain three lines near the middle that look like the bottom of the text background, maybe the background is slightly too small/large? I have no idea why that might be though.

emilk

Nice, let's get this in!

emilk

Nice, let's get this in!

)" This reverts commit 557bd56.

* Closes <#6904> * [x] I have followed the instructions in the PR template This was broken in #5411. Not sure if this is the best fix or if `PlacedRow::rect` should be updated, but I think it makes sense that PlacedRow::rect ignores leading space.

#7031) Fixes a regression introduced in #5411 (possibly d74bee5) that breaks `leading_space` handling. I think this is what the condition should be but I haven't touched this code in a while.

)" This reverts commit 557bd56.

scvalex · 2025-07-30T08:11:46Z

I think this broke multi-line TextShape rotation. Could I ask one of you to have a look at #7397, please?

* Closes <#7397> * [X] I have followed the instructions in the PR template I do admit I got a peak NixOS `RequestDeviceError` and deemed it entirely not worth it to think about that. #5411 broke rotation of multi-line `TextShape`s because `PlacedRow::pos` was no longer being rotated, so let's rotate it. --------- Co-authored-by: Emil Ernerfeldt <[email protected]> Co-authored-by: Lucas Meurer <[email protected]>

@emilk

## 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](<emilk#3086 (comment)>), excluding CoW semantics for `LayoutJob` (but including them for `Row`). It supersedes the previous unsuccessful attempt here: emilk#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 <emilk#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 <emilk#3086> * [X] I have followed the instructions in the PR template --------- Co-authored-by: Emil Ernerfeldt <[email protected]>

* Closes <emilk#6904> * [x] I have followed the instructions in the PR template This was broken in emilk#5411. Not sure if this is the best fix or if `PlacedRow::rect` should be updated, but I think it makes sense that PlacedRow::rect ignores leading space.

emilk#7031) Fixes a regression introduced in emilk#5411 (possibly emilk@d74bee5) that breaks `leading_space` handling. I think this is what the condition should be but I haven't touched this code in a while.

Moves `ends_with_newline` into `PlacedRow` to avoid clones during layout. I don't think there was a rationale stronger than "don't change too much" for not doing this in #5411, so I should've just done this from the start. This was a significant part of the profile for text layout (as it cloned almost every `Row`, even though it only needed to change a single boolean). Before: <img width="757" height="250" alt="image" src="https://github.com/user-attachments/assets/d1c2afd1-f1ec-4cf5-9d05-f5a5a78052df" /> After: <img width="615" height="249" alt="image" src="https://github.com/user-attachments/assets/c70966da-c892-4e84-adba-494d0f37f263" /> (note that these profiles focus solely on the top-level `Galley::layout_inline` subtree, also don't compare sample count as the duration of these tests was completely arbitrary) egui_demo_lib `*text_layout*` benches: <img width="791" height="461" alt="image" src="https://github.com/user-attachments/assets/4f97ce84-2768-4876-9488-d42f8f358ed1" /> * [X] I have followed the instructions in the PR template (As usual, the tests fail for me even on master but the failures on master and with these changes seem the same :))

* Closes <emilk#7397> * [X] I have followed the instructions in the PR template I do admit I got a peak NixOS `RequestDeviceError` and deemed it entirely not worth it to think about that. emilk#5411 broke rotation of multi-line `TextShape`s because `PlacedRow::pos` was no longer being rotated, so let's rotate it. --------- Co-authored-by: Emil Ernerfeldt <[email protected]> Co-authored-by: Lucas Meurer <[email protected]>

Moves `ends_with_newline` into `PlacedRow` to avoid clones during layout. I don't think there was a rationale stronger than "don't change too much" for not doing this in emilk#5411, so I should've just done this from the start. This was a significant part of the profile for text layout (as it cloned almost every `Row`, even though it only needed to change a single boolean). Before: <img width="757" height="250" alt="image" src="https://github.com/user-attachments/assets/d1c2afd1-f1ec-4cf5-9d05-f5a5a78052df" /> After: <img width="615" height="249" alt="image" src="https://github.com/user-attachments/assets/c70966da-c892-4e84-adba-494d0f37f263" /> (note that these profiles focus solely on the top-level `Galley::layout_inline` subtree, also don't compare sample count as the duration of these tests was completely arbitrary) egui_demo_lib `*text_layout*` benches: <img width="791" height="461" alt="image" src="https://github.com/user-attachments/assets/4f97ce84-2768-4876-9488-d42f8f358ed1" /> * [X] I have followed the instructions in the PR template (As usual, the tests fail for me even on master but the failures on master and with these changes seem the same :))

afishhh added 3 commits November 28, 2024 16:47

Fix typo

622b848

Cache individual lines of text in GalleyCache

150c0f6

Make Galleys share Rows and store their offsets

db32a1e

afishhh added 4 commits November 29, 2024 11:50

Fix lints

4e3f162

Don't add leading space to more than one split layout section

3de1723

Move cached-multiline-layout code into a helper function

f028154

Properly handle row repositioning

bc86bec

afishhh added 3 commits November 30, 2024 15:59

Correctly handle empty lines

abbc561

Respect first_row_min_height during multiline Galley layout

6d6bc3b

Round PlacedRow positions to pixels during multiline layout

6147ff3

afishhh added 5 commits November 30, 2024 17:51

Move ends_with_newline back into Row

66c83c3

Respect LayoutJob::round_output_size_to_nearest_ui_point

1be24ba

Simplify layout_multiline loop loop into a while loop

fd8413c

Fix Row::ends_with_newline docs, explain skipping of last galley row

bbe5662

Move some PlacedRow methods back to Row

110a9c3

Replace a hack with a proper implementation

139f286

afishhh force-pushed the cache_galley_lines branch from 06e639e to 139f286 Compare November 30, 2024 18:30

Slightly simplify paint_text_selection code

e15b34b

afishhh marked this pull request as ready for review December 1, 2024 23:57

emilk reviewed Dec 4, 2024

View reviewed changes

afishhh added 3 commits December 4, 2024 19:30

Fix nits

c6592ec

Fix text horizontal alignment

25da822

Add comment and check for newline before multiline layout

40f237d

afishhh force-pushed the cache_galley_lines branch from f406701 to 40f237d Compare December 5, 2024 17:45

Fix incorrect behavior with LayoutJob::max_rows

17a5f1f

emilk added 2 commits April 1, 2025 18:41

cargo fmt

6a5f6d3

Code cleanup

e71d09a

emilk approved these changes Apr 1, 2025

View reviewed changes

emilk merged commit 557bd56 into emilk:master Apr 1, 2025
25 checks passed

valadaptive mentioned this pull request Apr 1, 2025

[WIP] Render text with Parley #5784

Draft

13 tasks

valadaptive added a commit to valadaptive/egui that referenced this pull request Apr 2, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

fe57016

)" This reverts commit 557bd56.

valadaptive added a commit to valadaptive/egui that referenced this pull request Apr 24, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

9056dc0

)" This reverts commit 557bd56.

This was referenced Apr 30, 2025

Links are broken if they aren't the last thing in a line #6904

Closed

Fix links and text selection in horizontal_wrapped layout #6905

Merged

afishhh mentioned this pull request May 7, 2025

Fix leading_space sometimes being ignored during paragraph splitting #7031

Merged

valadaptive added a commit to valadaptive/egui that referenced this pull request May 9, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

86a989a

)" This reverts commit 557bd56.

valadaptive added a commit to valadaptive/egui that referenced this pull request May 20, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

8a2093b

)" This reverts commit 557bd56.

valadaptive added a commit to valadaptive/egui that referenced this pull request May 24, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

e0918ef

)" This reverts commit 557bd56.

valadaptive added a commit to valadaptive/egui that referenced this pull request May 26, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

979d73b

)" This reverts commit 557bd56.

valadaptive added a commit to valadaptive/egui that referenced this pull request Jun 12, 2025

Revert "Optimize editing long text by caching each paragraph (emilk#5411

3c128ce

)" This reverts commit 557bd56.

scvalex mentioned this pull request Jul 30, 2025

Multi-line TextShape rotation newly broken in 0.32 #7397

Closed

afishhh mentioned this pull request Aug 2, 2025

Fix multi-line TextShape rotation #7404

Merged

1 task

afishhh mentioned this pull request Oct 17, 2025

Avoid cloning Rows during Galley::concat #7649

Merged

1 task

		// Note we don't ignore the leading/trailing whitespace here!
		row.size.x = target_max_x - target_min_x;

Conversation

afishhh commented Nov 28, 2024 • edited by emilk Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What

Details

Uh oh!

github-actions bot commented Nov 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

afishhh commented Nov 29, 2024

Uh oh!

afishhh commented Nov 30, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

afishhh commented Nov 30, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

emilk left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

emilk Dec 4, 2024

Choose a reason for hiding this comment

Uh oh!

afishhh Dec 4, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

afishhh Dec 5, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

afishhh commented Dec 4, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

emilk left a comment

Choose a reason for hiding this comment

Uh oh!

emilk left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

scvalex commented Jul 30, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

afishhh commented Nov 28, 2024 •

edited by emilk

Loading

github-actions bot commented Nov 28, 2024 •

edited

Loading

afishhh commented Nov 30, 2024 •

edited

Loading

afishhh commented Nov 30, 2024 •

edited

Loading

emilk left a comment •

edited

Loading

afishhh Dec 4, 2024 •

edited

Loading

afishhh commented Dec 4, 2024 •

edited

Loading