Defer reflow for rows above viewport to idle callbacks

[Tyriar]

Resize is one of the bigger bottlenecks, especially in an embedder that has many terminal tabs or when terminal columns is high. We could use a task queue to defer any pending resize operations and either drop or flush when the row is actually needed.

[jerch]

Will the deferred array buffer resizes in #4115 already do here? They give me ~4 times faster resize runtime. But there is still some work needed over there (got some errors on the DebouncedIdleTask object there).

[Tyriar]

Delaying the resizing of the buffer would help a lot, combining that with also only resizing/reflowing until either it's needed or an idle callback would speed things up even more. I had a look at this and it's quite a bit more difficult than I initially anticipated, I think a pre-requisite to this is simplifying reflow to be able to run on a range of rows and changing that code always scares me 😅

[jerch]

Hmm reflowing only the viewport (in a sense of currently visible area) when resizing occurs, and postponing everything else should remove most of main thread stalls from resizing.

The ugly part would be the state holding and dealing with different resize states on the ringbuffer. I wonder if it would be possible to keep the current logic as it is, but just shard the reflow into smaller buffer pieces backwards on the scrollbuffer - by decorating the buffer with a helper structure that maintains the reflow state? Well postponing reflow will introduce several awkward situations, where reflow has to be realized immediately:

• on viewport scroll: When the user scrolls back in scrollbuffer, content must be aligned already. So there must be a way to stop the idle callback mechs and go into a forced reflow up to the scroll position.
• on data input: The line recycling during data input may not pull shorter or bigger lines from top of scrollbuffer. Thats not a biggie at all, the line length can simply be realigned as they get recycled.
• on serialize: Any buffer area for serialization must be reflowed already. Basically the same as on viewport scroll.

As shrinking reflow always removes data from the top of the buffer, we cannot do partial reflow in the middle, but always have to progress sequentially backwards. It gets interesting when several reflows come in in short progression - I think here it would be possible to skip finishing earlier reflows, and just jump to the new sizes.

To put this all together, would something like this work? Schematically:

• onResize:
  • update .cols/.rows immediately (meaning now: thats the supposed buffer metrics)
  • place a reflow state object on the buffer, if none existing, e.g. ReflowState
  • update requested metrics on ReflowState saving new cols/rows
  • set ReflowState to scrollbuffer.height meaning nothing got reflowed yet to new metrics (counting backwards)
  • reflow lower viewport part immediately, set state to viewport.height (better here - last stop of hard NL before viewport height)
  • place chaining idle callback to chew through next higher buffer piece until done
• onViewportScroll/onSerialize:
  • if ReflowState > scroll position - stop idle callback, reflow immediately to scroll position, place chaining idle callback for higher lines
  • if ReflowState < scroll position - nothing to be done, as scroll area already got reflowed
• onDataInput/lineRecycling:
  • take single line from recycling, adjust its length to new one
  • decrement ReflowState by one until == 0
• final state:
  • if ReflowState is at 0 the buffer is in sync with col/row metrics

While writing this down I kinda spotted, that we will get issues with our .cols and .rows properties on the buffer, as these values dont reflect the real buffer state for a given line anymore. Means we'd have to revisit every place using those buffer globals and re-eval, whether they need the true global or the more fine-grained line values. Eww - that last part sounds like a snake pit introducing tons of errors 🙀

[Tyriar]

That's basically I was thinking but wrapping all access of buffer lines in a check that ensures the reflow state, so whenever they're accessed that would need the reflow to be done it's performed then.

The ugly part would be the state holding and dealing with different resize states on the ringbuffer

This is the part I can't really get my head around currently since reflow shifts rows around in the buffer as 1 may become n when reflowing smaller and n may become 1 when reflowing larger.

[PerBothner]

I'm hoping to do lazy reflow in conjunction with the BufferLine rewrite (issue #4800). Each logical line will contain a logicalWidth property, which is the number of columns needed assuming an infinitely-wide buffer.
When the number of buffer columns changes, we will mark all lines as reflowNeeded, unless it's trivially not needed. (I.e. line.logicalWidth <= buffer.cols and line was not wrapped.) A reflow(start, end) procedure will reflow all lines in the start...end range that have reflowNeeded set. It needs to be called before redisplay, and some InputHandler operations.

For what it's worth, I've already implemented this logic in DomTerm. (Necessary because DomTerm reflow is quite expensive, involving DOM updates and handling pretty-printing, and optionally variable-width fonts.)

[jerch]

@PerBothner Yes your line rewrite also sounds like it makes the reflow itself much more light-weighted - isnt that just a recalc of the soft-wrap "stops" in the end (thus saving the annoying and exp. data moving part)?
(Sorry, still got not further into the PR, thx for the reminder.)

[PerBothner]

@jerch While in the re-write figuring out where the soft-breaks may require a linear search, that should be more than made up by reduced coping. Partly because the length of the _data array does not depend on the terminal width; only the logical line length.

[jerch]

I hope we can get away with a simple divmod calc here on the logical length w'o introspection of all cells - here the constant part of the O(n) search would be really tiny. But I'm not quite sure, if thats feasible, because of the ugly wider clusters forcing earlier soft-wrapping with follow-up offsets. A solution to that might be to use a skiplist or a binary tree with a certain width/pos resolution to find the cells at the breaks faster.

[PerBothner]

I implemented lazy reflow in my LineBuffer-rewrite fork.