Re: Progress of text system

[Alexander Malmberg]

Richard Frith-Macdonald wrote:
> 
> On Wednesday, February 19, 2003, at 10:03  am, Fred Kiefer wrote:
> 
> > Hi Alexander,
> >
> > you did include some of the needed layout reuse by now. I think this
> > is still on the wrong basis, so I will have to explain my point in
> > more detail. I was hoping that Richard would step in on this, as he
> > knows a lot more than me on the layout mechanism.
> 
> Sorry ... I just haven't had a chance to look through the new layout
> system, so I can't comment on the changes.

I'm working on commenting things as much as possible, hopefully making
it will be reasonably easy to follow the overall flow. I'm also working
on some overall documentation for the entire text system (from the pov
of a developer using GNUstep). This will also include a couple of
examples of what can be done using it.

[snip]
> > There used to be an implementation for this in GNUstep done by Richard.
> 
> I didn't know it had been removed ... yes the implementation was one
> based on quite a complex design that Nicola and I hammered out,
> The complexity was due to the need for decent performance on large
> files, and was mostly to do with ensuring that the runs of glyphs
> were safely segmented and managed so that sections of the glyph stream
> could be updated without having to regenerate all the rest.
> I never got it completely working/integrated onto the layout system
> though, because the layout system did not correctly use the
> glyph methods and was hard coded to assume than a unicode character was
> the same thing as a glyph.

Glyph stream handling is fully implemented. Basically:

The glyphs are stored in glyph runs. A glyph run corresponds to a run of
characters with the same attributes, and (using two glyph generation
backend methods) runs are guaranteed to be self-contained from a glyph
generation pov (so ligatures and other glyph substitutions can never
happen across a run border). Glyphs runs are generated on demand from
the text storage (this can be done very rapidly). There may not be glyph
runs up to the end of the text storage, but there will never be any gaps
in this structure; if invalidation occurs in the middle of the glyph
stream, new runs are created right away (note runs, not glyphs).

Glyph runs are stored in a skip list, which seems to be a relatively
unknown structure. See http://www.cs.umd.edu/~pugh/ for details. It's a
very nice structure, though. All the hairy parts ended up in the
invalidation method (otoh, it is _very_ hairy). As implemented, searches
are O(log(n)), linear walks in the list (next/previous run) are O(1),
and inserts and deletes (anywhere in the glyph stream, and even if they
cause length changes) are O(log(n)).

The actual glyphs are stored in plain arrays in each run. They are
generated on demand for entire runs, ie. when glyphs are needed for a
run, the range of characters and font to use are sent to a backend
method, and it allocates and fills in the glyph array. Searching by
glyph index is a simple array lookup, and by character index it's done
using a binary search.

[snip]
> >> This file would still contain internal details of the layout manager
> >> that are needed by eg. glyph generators in -back, but that a user of
> >> -gui should never see.
> >
> > Wrong, the glyph generation, be it in the backend or where ever,
> > should use the public method on NSLayoutManager to store glyphs,
> > [insertGlyph:atGlyphIndex:characterIndex:] to name it.
> 
> Yes. The layout system *NEEDS* to use these methods to decouple
> characters from glyphs.

Glyph generation does not use these methods; the interface used is
described here: http://wiki.gnustep.org/index.php/GlyphGenerationBackend
(names and arguments will change slightly when it's moved to a separate
class, but the basic methods and roles will remain). Doing it this way
is faster (in my early benchmarking, glyph generation was roughly one
order of magnitude faster than rendering, and roughly two orders of
magnitude faster than layout, using back-art, which does real glyph
lookups and basic ligatures), it's easier to handle in the layout
manager, and it's easier to get right in the glyph generator.

[snip]
> I'm guessing, but  performance problems are likely to be  down to -
> 1. lack of line fragment layout optimsation.

I've implemented soft-invalidation now, so layout information will be
reused as much as possible. I've also added a few other optimizations
(-setLocation:forStartOfGlyphRange: was a big bottleneck, but not
because of memory allocation; it did a pessimal search for the right
line frag, but that's fixed now).

> 2. lack of glyph storage optimisation

There may be a few bottlenecks left here, but I think I've fixed all the
important ones now (converted a few searches to binary searches, handle
linear walks over glyphs better, and a few other minor things).

> 3. inefficient backend rendering

More performance here never hurts, but I don't think this is a major
bottleneck. I can scroll around in very large texts without any
performance problems.

Anyway, after the latest changes, I can edit 150kb text files
comfortably (on my (relatively) slow system, a PII 400mhz). I've tested
with files of around 0.75mb, and there is a bit of lag when typing, but
performance is still, imo, acceptable.

A big remaining bottleneck is complete relayout, which is forced eg.
when the text view is resized. The best solution would be to fill in the
last parts for on-demand layout. There are two major problems:

1. Nearly all text views are placed in a scroll view and set to track
their text containers, at least vertically. Thus, after each change, the
text view notes that it may need to resize and asks the layout manager
how much space in the text container is used. To answer this, the layout
manager has to do layout for the entire container, thus making
demand-layout pointless.

2. Demand-layout really needs background layout support to work well. I
don't know how best to implement this. NSRunLoop extensions for
performers that are called when the run loop is idle is the most obvious
approach, though.

- Alexander Malmberg