Investigate a multipass (two-pass) version of egui

[emilk]

EDITED 2021-10-30: Expanded and added proposal
EDITED 2021-11-01: Realized input must be done in the second pass

Introduction

Problem

One downside of immediate mode is the difficulty in doing layouts where one needs to know the size of a section before positioning it, but to know the size of that section one needs to call the code that creates it - but that also positions it.

Consider the menus in egui: we use a justified layout to make sure the buttons cover the full width of the menu, but how wide should the menu be? We won't know until we put in all the buttons, and we don't know how wide to make the buttons until we know the width of the menu:

| Save        |
| Preferences |
| Quit        |

How do we know to make the "Save" button wide until we know there is a "Preferences" button? We don't!

Storing the size from the previous frame is also not a solution, because if we then remove the "Preferences" button, the menu will not shrink to the smaller size, but would stay at the widest it has ever been. We see this problem today with some Window:s in egui, which will auto-expand but never auto-shrink.

Because of issues like these, egui can feel janky an unreliable today. As a user it is difficult to understand why it is possible to center some widgets, but not other ("composite" widgets, which don't know their sizes beforehand). It also produces frame-delay jank (open a new window and it will often flicker the first frame, before "finding its size").

I want egui to "just work".

Two-pass

Some immediate mode UI:s take a two-pass approach to solving this a size pass and a layout pass. In the first pass, sizes of ui:s are calculated and stored, and in the second pass the sizes are used to nicely position things. This can be extended to even more passes, but with diminishing returns.

I believe a two-pass approach could solve most of the layout issues in egui.

It will also make some widgets easier to implement: instead of having to know all the sizes of its part beforehand, it can just have it automatically calculated in the first pass, and then use it in the second pass.

Things to consider

Consistency

Both passes should ideally act exactly the same, which will be impossible to guarantee when it comes to user code. For instance, say the user code checks "Is the async download complete?" before deciding to show a widget or not. What if the download completes right in the middle of the two passes? Then the layout pass would not have the stored size of the widget.

So the layout pass need to be robust against missing sizes, falling back to some "okish" behavior (e.g. what egui currently does).

Such inconsistency will always happen with input:

Input

Inputs events should only be handled in one of the passes, otherwise we would enter text twice in a TextEdit, scroll twice as much in ScrollArea etc. Inputs must be consumed, whereas currently in egui inputs are read.

We can't handle clicks in the first pass, since we don't know where the widgets are (yet), so for consistency we should probably handle all events in the second pass.

Performance

Running the UI code twice will of course be slower, but not necessarily twice as slow. We also need to store and load sizes, which adds some overhead.

However, the first pass requires no painting, so we can skip some painting code in the widgets, and of course skip the tessellation completely.

There may also be opportunities for simplifying the layout algorithms when we know the sizes of things, potentially giving some savings, though i doubt it will be much.

I expect something like 50%-100% overhead from adding a second pass.

Compatibility

Should the two-pass approach be the only thing egui support, or should we also support the single-pass approach?

What sizes are stored?

Should we store the size of each Button? Probably not - a button already knowns its own size!

---

Proposal

I propose we support both one-pass and two-pass modes, as a global setting to egui (or controlled by how you call it), with one-pass being default as a start. This will allow us to experiment with two-pass on master.

Example

Example for what should work:

ui.top_down_centered(add_content: impl FnOnce(Ui) -> R) -> InnerResponse<R> {
    ui.horizontal(|ui| {
        …
    });
    ui.horizontal(|ui| {
        …
    });
}

How: horizontal calls ui.scope which does all the magic:

impl Ui {
    fn scope(&mut self, add_content: impl FnOnce(Ui) -> R) -> InnerResponse<R> {
        // pseudo-code:
        let id = self.advance_scope_id();
        let size: Option<Vec2> = self.ctx.memory().sizes().get_prev_pass(id);
        let rect = self.layout.place_next(size);
        let mut child = self.child(rect);
        let r = add_content(&mut child);
        self.layout.advance_after_rect(child.min_rect());
        self.ctx.memory().sizes().set(id, rect.size());
    }
}

So a "scope" is the level at which we store sizes, and every time there is a |ui| { … } closure being passed in, the size of what is generated by that closure is being stored.

Behavior

In the first "size pass", layouts will do simplest/fastest that still calculates sizes correctly.
Centering will be ignored (left-aligned), and justified is ignored (so that the parent size can grow).
Auto-sized windows will assume zero size from the start.

User-code should almost never have to care about what pass is currently running, or even if we are running in one-pass or two-pass mode. Only layout code really cares (and should be able to check with e.g. if ctx.passes.is_first_of_two { … }.

What Context does:

fn run_two_pass(&mut self, raw_input):
    clear size memory

    run size_pass:
        read drained input (no clicks, zero scroll delta, …)
        ignore sizes (since it is empty)
        do simplified layout (left-aligned, no justified, …)
        store sizes of scopes

    update input state from raw_input
    clear any painted shapes

    run layout_pass:
        read sizes from previous pass (some may be missing)
        do proper layout
        use latest input

    drain input (*)


(*) Input draining is removing events and clearing deltas.

Future work

If this works reasonably well we can start considering if two-pass should be default.

We could also consider having one-pass as the default, but allow users to opt-in to two-pass for places where it is needed, e.g.

ui.two_pass(|ui| {
    …
});

This is a lot more work to get right though, so let's wait.

[mankinskin]

I think the single pass should definitely remain the default, beause it is the simpler option and is faster.

I think the best way to provide this functionality is to make it an explicit call on a specific Ui, selected by the user. This way they can take full responsibility for making it work how they desire.

I like that egui is an immediate mode Ui, and think using immediate mode should be encouraged. But having an extra size pass in the toolbelt can solve the problems you can get with immediate mode. With a proper documentation of how to use the size pass I think the risks are properly taken care of from the side of egui, and it should be very managable for users.

Maybe it is even possible to exclude some code from being executed inside a measured Ui? Something that knows if the Ui is being measured or rendered and executes code accordingly? This might make it easier for users to handle for example asynchronous calls, by only polling them on the first pass.

[parasyte]

I ended up solving my need for computing layouts in a simplified two-pass-alike model. What I ended up with is a container widget that borrows all of the text contents in its constructor (while computing widths). The second pass is the show method which allocates space in the Ui and adds the widgets with the borrowed contents.

The code is all here; it implements a table similar to Grid that has unique column widths. And it is used like this:

SetupGrid::new(ui, &setups, &colors, diff_colors).show(ui, car_name);

I'm interested how this proposal will compare. IIUC, it would mean that I could combine the constructor and show method into a single function that loops over my table rows. And of course, remove all of the layout bookkeeping.

Sounds good in theory, but I'm a little concerned about the "magic" of scoping, especially if I need to do any work that is relatively heavy. Like computing the intersection of keys in a slice of HashMaps, which is something that the constructor in the linked widget does. The rest of the code is trivial enough that I don't care how often it runs. Most of the allocations are for working around egui's one-pass design (except the aforementioned key intersection, which is unavoidable with my weakly-typed internal data structures).

[akhilman]

I think the single pass should definitely remain the default, beause it is the simpler option and is faster.

As soon as we have known bounding rectangles of all widgets we can have a way to avoid unnecessary re-rendering. Egui may become even less CPU hungry.

[mankinskin]

@akhilman you mean store bounding rectangles from the previous frame? This would not help in this case I think. A size pass would use the application state at the current frame (which may be different from the last frame) to find the bounding rectangle. If you used the last frame's bounding box the layout would use stale ones if the bounding rects are different this frame.

[akhilman]

Ok. I see your point. Thanks.

The state of the application may change and the next step of event loop may already be dealing with other bounding boxes.

[mankinskin]

It's just a solution to a different kind of problem I think. But probably the implementation will be very similar and a lot could be reused.

[coderedart]

there's a new gui project called Yakui which seems to use a single pass layout technique from flutter.

seems relevant to this issue.

[akhilman]

We can use adjacent frames as two passes to determine the size of the child widgets. This way, in most cases, we would not have any performance penalty at all, because the game engines still redraw the GUI every frame.

Suppose we have a table with widgets of different sizes inside.

• The first frame draws the table with equal cells. The child widgets are cut off, but the child widgets tell the parent table what sizes they would like to be.
• The table sees that the preferred cell sizes do not correspond to the actual ones and requests a new frame.
• The next frame is drawn with the preferred sizes of the child widgets in count. At this point, the table can pass own size expectations to descendants.

We can even make this kind of auto-sizing of containers an animation effect if we resize widgets gradually.

[DanielJoyce]

https://docs.flutter.dev/resources/inside-flutter

Seems like this might provide inspiration for single pass layout.

[John-Nagle]

Unless and until this gets implemented, we need better documentation of how to code for one-pass layout and what the layout engine can and can't do.

See #2796 where the layout engine broke. I may have done something wrong, but the documentation is inadequate to tell me what's right.

[FriederHannenheim]

Hey. Just a quick question: Is this still being considered / worked on? I really like egui and this would really improve it's usefulness to me

[emilk]

I have given this some thought, and I think that a multi-pass immediate GUI library should be designed for that from the start. It should probably be only multipass as well, i.e. not even support single-pass. This would yield some big simplifications in the design.

I believe multi-pass can solve most layout issues. Two-pass won't fix all layout problems, but might be a sweet-spot of simplicity, speed, and power. Still, it means user code is also run twice, which can cause performance issues as well as subtle bugs, so I suspect it will make the library somewhat less easy to use.

In the end, egui was conceived as a pure single-pass immediate mode library, and an experiment to see how far such a library could be pushed in terms of layout etc. I am surprised how well it works despite being single-pass, and I've discovered many tricks along the way, such as first-frame-hiding of certain widgets, effectively using the first frame as a sizing pass. I think there are more such tricks awaiting to be discovered and implemented, and I think that's where we should focus our efforts for egui.