Partial invalidation

[raphlinus]

One opportunity for performance optimization is partial invalidation: only repainting the region of the screen that has actually changed. This is a fairly far-reaching change, as it requires platform-specific plumbing to the drawing pipeline. Some platforms (mac) don't have good support for partial invalidation, so if we're going to do things to improve performance, we have to fake it (see #16 for a bit of discussion of the issues at the druid-shell level).

This issue is primarily concerned with how widgets can express finer grained invalidation. The proposal is very simple: in context with an invalidate method (currently event and update), we also have an invalidate_rect method that takes a Rect. To invalidate a more complex region, a widget could call invalidate_rect multiple times.

We will keep the existing invalidate function as a convenience, and it will be defined as invalidating the layout rect. (We could consider invalidating the paint bounds instead, see #401, but layout bounds seems simpler; it's likely that a widget with fancy paint bounds should probably be implementing more precise invalidation in any case).

This is quite similar to other APIs: on Windows it's called InvalidateRect and on macOS it's setNeedsDisplay.

The correctness criterion for widgets is basically that all pixels outside the requested region are identical to their value on previous paint. This only applies if there is a previous paint, so on first paint for a widget, no such requirement applies. Changing the layout size should also be considered a "free" invalidation. Lastly, when we implement show/hide lifecycle events (also a future architectural change), then the parent should be responsible for repainting the entire widget, so there is no requirement in that case.

As a minor style point, we might consider renaming "invalidate" to "request_paint", as we have a general naming scheme for requesting things.

[xStrom]

request_paint sounds great and communicates more clearly what will happen, in that the paint function will be called.

[jneem]

I'd like to take a stab at this, because I'm running into this performance issue.

It seems to me that there are two parts here. The first is to report the invalidated regions to the windowing system. The second is to allow widgets to access those invalidated regions in their paint functions. Now, I only have access to gtk/cairo, so what I'm saying next might not be fully cross-platform (but I did have a quick peek at the mac/win API docs).

In gtk, the paint callback receives a context with the clip region already set to the invalidated rects. Therefore, there should be some performance improvement just from the first step, because (at least in cairo, according to my tests) drawing is faster with a small clip, even if I'm not smart enough to ignore shapes outside the clip region. The second step should be more significant, however, because it will allow us to avoid recursing into un-invalidated children while drawing.

So anyway, I was planning to look into the first part first. As far as I can tell, all three platforms like to do their invalidation one rectangle at a time (as opposed to batching up those rectangles and submitting them once). This seems to be the opposite to what druid is currently doing (storing needs_inval in each widget's state, and then bubbling those up the tree). So my first question is: would it be ok to just get rid of BaseState::needs_inval and instead call the platform's invalidation function on every request_paint?

Regarding the second part (propagating the invalidated regions back to the widgets). Cairo hands the window a list of rectangles, but as far as I can tell windows and mac only give a single rectangle. So maybe a single rectangle is the best approach?

[xStrom]

Having every widget do their own platform invaldiation call seems potentially inefficient, although I haven't looked at the details at all here. I think there might be performance benefits to bubbling up the rects and then sending the platform only the rects that are required to describe the total complex shape.

For example let's consider a scenario where a container widget wants to repaint, and so do 50 of its children widgets. All of those children widgets are within the container's repaint request bounds anyway.

[jneem]

That's a good point, although I'm also worried about the other extreme, where 50 children want to repaint but none of its ancestors does, and so we end up copying a length-50 Vec<Rect> all the way up the widget tree. (This is assuming that we're storing the invalidation state in BaseState the way it is currently.)

Maybe a compromise would be to keep the needs_inval flag, which would be set to true whenever a widget or its parent requests repaint for its entire layout bounds. Then every request_paint can be ignored if needs_inval is already set. This will suppress redundant invalidation requests as long as parents request repaints before children. I will look to see how well this assumption holds in the current druid widgets, and I'll also take a look at what gtk does.

[raphlinus]

I have more thoughts about this but for now encourage you to think about scrolling.

[cmyr]

I wouldn't worry about the Vec<Rect>; I think we can store the invalidation region as a union Rect; if that proves inefficient we can consider the alternative, and the Vec<Rect> version wouldn't be horrible, if needed there are tricks we can do while merging up (such as mem::swapping from child to parent if parent is empty).

About scrolling: this is deep water. At least on the mac, doing this really well involves a bunch of platform-specific conventions which will not generalize well. I think to get serious performance in a cross platform way we're going to need gpu rendering; then we can control the whole thing. It's going to be very hard to come up with a single abstraction that takes advantage of all the different platform fast paths.