Optimizing re-layout of 1MB+ pieces of text in a `TextEdit` #3086

NickHu · 2023-06-16T10:06:47Z

The problem

egui's TextEdit becomes sluggish when it holds large amounts of text; probably, this is due to it rendering all of the text without doing anything clever to cull text which doesn't make it on to the screen (apologies if this is the wrong terminology, I'm not an expert in graphics programming). Even without doing anything clever, there seem to be some optimisation opportunities inside the code, but I wanted to seek some guidance on whether this is worth doing or not before committing to working on this.

At least, with my test program (see end, adapted from #2799), when there are 15 million characters inside the widget, it is noticably laggy to use (>1s per character insert, compiled with --release).

I've done some crude println! profiling with std::time::Instant::now() to find the hot loops, as I will detail below.

Related issues: #1196 #2799 #2906

Profiling

Here are the measured slow parts of the result of inserting one 'a' into the middle of the buffer (took around ~2s on release mode):

egui/crates/epaint/src/text/text_layout.rs

Lines 110 to 136 in 9478e50

    
           for chr in job.text[byte_range.clone()].chars() { 
        
               if job.break_on_newline && chr == '\n' { 
        
                   out_paragraphs.push(Paragraph::default()); 
        
                   paragraph = out_paragraphs.last_mut().unwrap(); 
        
                   paragraph.empty_paragraph_height = font_height; // TODO(emilk): replace this hack with actually including `\n` in the glyphs? 
        
               } else { 
        
                   let (font_impl, glyph_info) = font.glyph_info_and_font_impl(chr); 
        
                   if let Some(font_impl) = font_impl { 
        
                       if let Some(last_glyph_id) = last_glyph_id { 
        
                           paragraph.cursor_x += font_impl.pair_kerning(last_glyph_id, glyph_info.id); 
        
                       } 
        
                   } 
        
                   paragraph.glyphs.push(Glyph { 
        
                       chr, 
        
                       pos: pos2(paragraph.cursor_x, f32::NAN), 
        
                       size: vec2(glyph_info.advance_width, glyph_info.row_height), 
        
                       ascent: glyph_info.ascent, 
        
                       uv_rect: glyph_info.uv_rect, 
        
                       section_index, 
        
                   }); 
        
                   paragraph.cursor_x += glyph_info.advance_width; 
        
                   paragraph.cursor_x = font.round_to_pixel(paragraph.cursor_x); 
        
                   last_glyph_id = Some(glyph_info.id); 
        
               } 
        
           }

Took ~0.5s to complete the loop, and reallocated paragraph.glyphs 23 times. I think with a call to Vec::reserve_exact the allocator pressure can be eliminated entirely, as it should be possible to determine how big each vector is supposed to be.

egui/crates/epaint/src/text/text_layout.rs

Line 64 in 9478e50

let mut rows = rows_from_paragraphs(fonts, paragraphs, &job);

Took ~0.5s to complete.

egui/crates/epaint/src/text/text_layout.rs

Lines 480 to 485 in 9478e50

    
           for row in &mut rows { 
        
               row.visuals = tessellate_row(point_scale, &job, &format_summary, row); 
        
               mesh_bounds = mesh_bounds.union(row.visuals.mesh_bounds); 
        
               num_vertices += row.visuals.mesh.vertices.len(); 
        
               num_indices += row.visuals.mesh.indices.len(); 
        
           }

Took ~1s to complete.

Test program

use eframe::egui::{self, CentralPanel, TextEdit};

fn main() -> Result<(), eframe::Error> {
    let options = eframe::NativeOptions {
        ..Default::default()
    };

    eframe::run_native(
        "editor big file test",
        options,
        Box::new(|_cc| Box::<MyApp>::new(MyApp::new())),
    )
}

struct MyApp {
    text: String,
}

impl MyApp {
    fn new() -> Self {
        let bytes = (0..500000).flat_map(|_| (0u8..10));
        let string: String = bytes.map(|b| format!(" {b:02x}")).collect();
        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 code_editor = TextEdit::multiline(&mut self.text)
                .code_editor()
                .desired_width(f32::INFINITY)
                .desired_rows(40);
            let _output = code_editor.show(ui);
        });
    }
}

The text was updated successfully, but these errors were encountered:

NickHu · 2023-06-16T10:11:43Z

As suggested in #2799, ideally there would be a way to only draw the visible text, similar to something like a ScrollArea::show_rows; I'm not sure if this would work for TextEdit as text can have variable-width characters, so the layout of the visible text depends on laying out all the text that comes before it at least. I think layout can end after it's finished the visible part though, but this optimisation may not be worth the complexity it adds.

I think this dependency ceases to exist if a monospace font is selected, which would actually work for my usecase (large-ish code editor), and then a show_rows method really could be exposed, but I'd seek design guidance before trying to implement something like that, so please consider this a feature request.

emilk · 2023-09-18T19:01:49Z

epaint memoizes text layout on a rather coarse level of a LayoutJob. This means that if you have a single 15MB string of text, epaint will lay it out once (slowly), then reuse it. When you edit it, it becomes a new string, and it will (slowly) be laid out again.

Each newline (\n) creates a new paragraph of text. A paragraph can span multiple rows if there is a wrap width (there usually is).

If we added another level of memoization at the paragraphs level, we could speed up text layout significantly, while still being immediate mode and without having to resort to exotic string types (like ropes). Each frame, we could split a string based on the newlines in it, then lay out each paragraph if needed (memoized), and the assemble the output by just appending the paragraphs after each other vertically. Editing a very long string would therefore be fast, as long as there are many newlines in the text.

This is not a perfect solution. If there are no newlines, we would still need to re-layout the full string (because editing the few characters may cause all subsequent rows to change!). Also, splitting the string on the newlines would still be an O(N) operation, but probably be several orders of magnitudes faster. But, it is a very simple solution that should work well for most use cases, and its easy to implement.

I suggest we add this to GalleyCache in crates/epaint/src/text/fonts.rs. GalleyCache::layout would first check if the full job was in cache, and if so return it. If not, it would check for newlines in the job. If there are none, lay it out, put it in the cache, and return (same as now). If there are newlines, split the job into a new job for each paragraph, then recurse on each paragraph. Finally, concatenate the Galleys of all the paragraphs into one big Galley, add it to the cache, and return it. To make this concatenation fast, we should probably store Arc<Row> with offsets in the Galley. To make the splitting of a LayoutJob fast, we could switch to using a string type that internally uses Arc<str> plus an offset and length.

dacid44 · 2024-02-07T15:00:15Z

I think I can get started on implementing this.

dacid44 · 2024-02-07T18:42:45Z

I'm guessing this will need to respect the LayoutJob::break_on_newline field? as in, if that field is false, this optimization should be skipped?

GodGotzi · 2024-07-12T14:41:28Z

Is something in work here?

emilk added good first issue Good for newcomers text Problems related to text labels Sep 18, 2023

emilk changed the title ~~Optimizing TextEdit~~ Optimizing re-layout of 1MB+ pieces of text in a TextEdit Sep 18, 2023

emilk added the performance Lower CPU/GPU usage (optimize) label Sep 22, 2023

dacid44 linked a pull request Feb 7, 2024 that will close this issue

epaint: Break up memozation of text layouts into paragraphs #4000

Draft

6 tasks

afishhh linked a pull request Nov 28, 2024 that will close this issue

epaint: Memoize individual lines during text layout #5411

Open

5 tasks

emilk mentioned this issue Jan 2, 2025

Optimize editing multi-line text #5560

Draft

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Optimizing re-layout of 1MB+ pieces of text in a `TextEdit` #3086

Optimizing re-layout of 1MB+ pieces of text in a `TextEdit` #3086

NickHu commented Jun 16, 2023

NickHu commented Jun 16, 2023

emilk commented Sep 18, 2023 •

edited

Loading

dacid44 commented Feb 7, 2024

dacid44 commented Feb 7, 2024

GodGotzi commented Jul 12, 2024

Optimizing re-layout of 1MB+ pieces of text in a TextEdit #3086

Optimizing re-layout of 1MB+ pieces of text in a TextEdit #3086

Comments

NickHu commented Jun 16, 2023

The problem

Profiling

Test program

NickHu commented Jun 16, 2023

emilk commented Sep 18, 2023 • edited Loading

dacid44 commented Feb 7, 2024

dacid44 commented Feb 7, 2024

GodGotzi commented Jul 12, 2024

Optimizing re-layout of 1MB+ pieces of text in a `TextEdit` #3086

Optimizing re-layout of 1MB+ pieces of text in a `TextEdit` #3086

emilk commented Sep 18, 2023 •

edited

Loading