1823270 - gfxTextRun::SortGlyphRuns may be inefficient

Status: RESOLVED FIXED

(Core :: Graphics: Text, defect)

Description

[Jonathan Kew [:jfkthame]]

In some cases, gfxTextRun::SortGlyphRuns ends up finding numerous GlyphRun records that can be coalesced with their neighbors; but the use of nsTArray::RemoveElementAt(index) to remove the redundant ones individually becomes inefficient if the array is large, and multiple removals are needed, as each operation will move all the following elements.

We have nsTArray::RemoveElementsBy(predicate) to do this more efficiently as a single pass over the array, so we should adapt SortGlyphRuns to use this.

Comment 1

[Jonathan Kew [:jfkthame]]

Attachment: Bug 1823270 - Rewrite gfxTextRun::SortGlyphRuns to use RemoveElementsBy instead of RemoveElementAt when merging adjacent runs, to minimize array-data shifting. r=#gfx-reviewers

In the patches for bug 1823215, we eliminated the use of a local copy of the glyph runs array
during SortGlyphRuns; but we call RemoveElementAt individually for each run to be coalesced,
which means potentially moving all the rest of the array multiple times. Instrumentation shows
that we sometimes end up with dozens of glyphruns to be coalesced (or even hundreds/thousands,
in pathological cases), which becomes quite inefficient.

Using RemoveElementsBy(predicate) instead will minimize the copying/moving of the remaining
array elements.

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/48b90cfc92d5
Rewrite gfxTextRun::SortGlyphRuns to use RemoveElementsBy instead of RemoveElementAt when merging adjacent runs, to minimize array-data shifting. r=gfx-reviewers,lsalzman

Comment 3

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/48b90cfc92d5