Bug 52380 – Lazily generate and store logical ordering of InlineBoxes

• Status: RESOLVED
• Resolution: CONFIGURATION CHANGED
• Component: Layout and Rendering

[Levi Weintraub]

Created attachment 78828 [details]
Proposed patch

Currently, iterating across InlineBoxes logically involves an n^2 algorithm and the result isn't stored. For RTL and BiDi content, this can represent a lot of wasted work, particularly as new places pop up that need access to this info (see https://bugs.webkit.org/show_bug.cgi?id=38087).

I propose lazily generating this ordering and storing it so future lookups and iteration are O(1). I've also moved the algorithm to RootInlineBox so it hopefully will be updated with Rendering changes.

[Ryosuke Niwa]

This is very exciting patch!  I talked with Levi in person, and we realized that it has many use cases because it allows us to binary search an inline box.

This may allow us to resolve https://bugs.webkit.org/show_bug.cgi?id=25298 easily.

[Levi Weintraub]

Created attachment 78836 [details]
Proposed Patch

Fixing a comment.

This could be used, for example, to speed up getInlineBoxAndOffset to Log(N) time from its current O(N) by looking at the start/end position of inline boxes compared to the offset.

[Eric Seidel (no email)]

Comment on attachment 78836 [details]
Proposed Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=78836&action=review

I suspect this is not invalidating when necessary.

> Source/WebCore/editing/visible_units.cpp:1039
> +    const Vector<InlineBox*> leafBoxesInLogicalOrder = rootBox->leafBoxesInLogicalOrder();

I don't think you want the const here. seems meaningless.

> Source/WebCore/rendering/RootInlineBox.cpp:219
> +    m_leafBoxesInLogicalOrder.clear();

Don't we need to invalidate thsi when adding children too?

> Source/WebCore/rendering/RootInlineBox.cpp:566
> +void RootInlineBox::determineLogicalOrderOfLeafBoxes() const

I assume this is just copied from the previous location and otherwise not modified (except to store in a vector)?

[Levi Weintraub]

Thanks for taking a look at this!

(In reply to comment #3)
> (From update of attachment 78836 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=78836&action=review
> 
> I suspect this is not invalidating when necessary.
> 
> > Source/WebCore/editing/visible_units.cpp:1039
> > +    const Vector<InlineBox*> leafBoxesInLogicalOrder = rootBox->leafBoxesInLogicalOrder();
> 
> I don't think you want the const here. seems meaningless.
> 
> > Source/WebCore/rendering/RootInlineBox.cpp:219
> > +    m_leafBoxesInLogicalOrder.clear();
> 
> Don't we need to invalidate thsi when adding children too?

For sure. Currently we only ever add line boxes on line creation so we wouldn't get into this case, but not doing this would be leaving us open for future problems.

> > Source/WebCore/rendering/RootInlineBox.cpp:566
> > +void RootInlineBox::determineLogicalOrderOfLeafBoxes() const
> 
> I assume this is just copied from the previous location and otherwise not modified (except to store in a vector)?

Correct. The relevance of this patch is that it speeds up access to logical InlineBox ordering, which is information we iterate through in several places. Caching it and using this source should allow us to speed up and simplify these code paths.

[Eric Seidel (no email)]

Yeah, I'm a big fan of the patch.   Just need to be cautious when adding caches like this that we don't end up with them invalid (and thus causing security bugs). :)

[Levi Weintraub]

Created attachment 79005 [details]
Patch

[Eric Seidel (no email)]

Comment on attachment 79005 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=79005&action=review

Looks good.  tis OK as is, but we could go another round now, or we can clean up more of this (old ugly!) code in later patches.

> Source/WebCore/rendering/RootInlineBox.cpp:209
> +void RootInlineBox::childAdded()

Seems if we're adding this method we might as well pass the InlineBox*, even if it's ignored.

> Source/WebCore/rendering/RootInlineBox.cpp:587
> +        if (r->bidiLevel() > maxLevel)
> +            maxLevel = r->bidiLevel();
> +        if (r->bidiLevel() < minLevel)
> +            minLevel = r->bidiLevel();

Hah.  These are just std::min, std::max :)

> Source/WebCore/rendering/RootInlineBox.cpp:615
> +            while (iter != end) {
> +                if ((*iter)->bidiLevel() >= minLevel)
> +                    break;
> +                ++iter;
> +            }

This is repeated twice and should be an inline which returns a bool or similar maybe?

> Source/WebCore/rendering/RootInlineBox.h:79
>      void childRemoved(InlineBox* box);

"box" can be removed.

[Levi Weintraub]

(In reply to comment #7)
> (From update of attachment 79005 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=79005&action=review
> 
> Looks good.  tis OK as is, but we could go another round now, or we can clean up more of this (old ugly!) code in later patches.
> 
> > Source/WebCore/rendering/RootInlineBox.cpp:209
> > +void RootInlineBox::childAdded()
> 
> Seems if we're adding this method we might as well pass the InlineBox*, even if it's ignored.
> 
> > Source/WebCore/rendering/RootInlineBox.cpp:587
> > +        if (r->bidiLevel() > maxLevel)
> > +            maxLevel = r->bidiLevel();
> > +        if (r->bidiLevel() < minLevel)
> > +            minLevel = r->bidiLevel();
> 
> Hah.  These are just std::min, std::max :)
> 
> > Source/WebCore/rendering/RootInlineBox.cpp:615
> > +            while (iter != end) {
> > +                if ((*iter)->bidiLevel() >= minLevel)
> > +                    break;
> > +                ++iter;
> > +            }
> 
> This is repeated twice and should be an inline which returns a bool or similar maybe?
> 
> > Source/WebCore/rendering/RootInlineBox.h:79
> >      void childRemoved(InlineBox* box);
> 
> "box" can be removed.

All great points, thanks for the review!

What’s the memory use impact of adding 8 bytes to every root box in every page? What’s the running time impact of this change? Is this a good time/space trade-off?

[Ryosuke Niwa]

(In reply to comment #9)
> What’s the memory use impact of adding 8 bytes to every root box in every page? What’s the running time impact of this change? Is this a good time/space trade-off?

In the case of selection / cursor movement, we're not modifying the DOM so being able to avoid running O(n^2) algorithm every time user changes selection will likely improve the performance quite significantly.  We can also use profiler to see how much time/space trade-off we have.

[Eric Seidel (no email)]

Comment on attachment 79005 [details]
Patch

Wow, I feel like  noob.

There are a lot of lineboxes on the page.  I suspect this cache is very expensive.

(In reply to comment #10)
> (In reply to comment #9)
> being able to avoid running O(n^2) algorithm every time user changes selection will likely improve the performance quite significantly.

What are typical values of n for this sort of operation? Are there bugs in bugs.webkit.org or other publically-accessible bug databases showing bad responsiveness of selection operations that have been tracked down to this computation?

You might want to consider replacing m_floats with an m_rareData that encompasses a vector for floats and this new cache.

[Antti Koivisto]

If these caches are actually used the memory will balloon far beyond the already bad pointer-per-root-inline-box. All those pointer vectors (in this patch each cache is at least 128 bytes even if it has just one item, though that could be optimized) will add up. On the other hand if the caches are not used then all those null pointers are wasted space. 

A better approach would be to have a non-member cache. Search for "RareData" in WebCore to find a number of examples. You would still need to take care that it won't bloat too much even if someone touches all nodes in a huge document.

First thing to do however is to make sure you are fixing a real problem. You should do profiling before writing performance patches.

[Ahmad Saleem]

@Alan - is this needed anymore?

[zalan]

(In reply to Ahmad Saleem from comment #14)
> @Alan - is this needed anymore?
nope. Thank you.