Potential Improvement to MultilineValues

[pvande]

MultilineValue (actually, mostly LineCollection) seems to contain a lot of hidden cost, and I'm curious about what alternatives have been considered or evaluated.

In particular, I'm looking at MultilineValue#to_s (delegated to LineCollection#text), which has to "reconstruct" the text value from the collection of lines. When dealing with relatively small values this isn't particularly problematic, but does become more so as the value grows. Calling this method every frame (for debugging, or data synchronization reasons) can be detrimental.

While joining the lines after every change is obviously problematic as well, I do wonder about a few other options…

• Use memoization to avoid recomputing text when the lines haven't changed.
  • This requires a little more cooperation with the mutation behaviors, but may be reasonable.
• Mirror updates to lines against the original input text String.
  • That is to say, retain a (mutable) copy of the input text, and write every update to both the lines and that copy of the text.
  • MultilineValue#to_s can then just return that update copy, with no additional work required.
• Make soft-wrapped "lines" conceptually less concrete.
  • The thought I'm trying to express here is that maybe we don't need to treat the value as a collection of Lines. In general, the lines presented onscreen are a projection of a particular String; can we use that String as the value internally?
  • To make this work, we would probably maintain a list of ranges/lengths/index pairs as our "display lines", which we can then slice out of the original value.
  • To avoid the cost of repeated slicing, we would probably want to memoize the values as we go.
  • When updates are made, only those slices within or after the update range would need invalidated (probably less?).
  • Only lines actually being displayed need sliced.
  • Reflow should become faster (since it's now only responsible for recording indices).
  • Display should become slower for small values, but faster overall (since slices aren't cut "eagerly", some work gets pushed to render-time, but less in general).
  • This is obviously a larger refactoring, but may provide significant net benefit.

I'd love to know if any of these options have been explored or rejected previously, or if there's any interest in seeing work in any of these directions.

[marcheiligers]

Great ideas. I honestly never expected anyone to push this beyond "Alice in Wonderland" (~170k characters) though I have experimented with "War and Peace" (~3.3M characters ... don't do it). At the time that MultilineValue was extracted, I needed something that was optimized for editing and quacked like a String, not fetching the complete value on every tick. The expectation was that consumers would fetch the complete value occasionally when the user hits "Save".

I like the idea of a less "concrete" model that keeps the original string in tact. This is worth exploring for me and thank you for the suggestions.

[marcheiligers]

Poking at the code a bit to remind myself of the evil I have done, and adding some notes here:

There are 2 passes over the string:

1. The first finds word breaks and does a few tweaks on the way: it converts all CRLF chars into \n (which is probably a mistake), adds leading whitespace after a new line and trailing whitespace to words (iow, foo bar becomes [' foo ', 'bar ']), and has a TODO on handling [TAB] which hasn't been dealt with.
2. The second uses that array of words and measures a word at a time to see if it fits on a line for the given w and font_style, with trailing white space ignored in the measurement since that seems to be how Word-like editors work.

@word_chars is not actually used in either of these. It is used in the #current_word and #find_word_break_* methods. I believe it can be eliminated completely, relying only on characters which are "special" in some other way, which would make i18n easier (and cheaper) in future.

These 2 passes could be combined. It would add make the code harder to follow, but nothing a bunch of comments can't fix.

There is, as far as I can tell, no reason it couldn't maintain indices in the original string rather than allocating new strings, except for the parts where it's mutating the original string (see comment about CLRF above). I'm guessing those mutations are bad anyway and that I need to deal with x-platform line-endings in a more sane way anyway.

I see no reason why this work couldn't be handled in a Fiber so the game remains responsive even when reflowing a very large value.

I need to noodle on this some more.

[marcheiligers]

Oh, there's a TODO to change a length search for a very long word (longer than the w) into a binary search ... I've done that already but I suspect tat something much stupider -- find an average character width and search from there -- will work even better.

[marcheiligers]

I had a go at changing the first pass over the string to produce indices instead of an array of words (it still returns an array of words in the end so the rest works), and that works very well and doesn't break anything. It also eliminated some code, so that's good I guess.