tdf#81272 Improved CJK fallback rendering performance

This change includes the following performance fixes:

- Removes an expensive vector sort from fallback run computation.

- Reduces unnecessary BreakIterator use while collecting grapheme
  clusters requiring fallback.

Change-Id: I760825596e0609059ef0c5ca97e210ab6647e466
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/168175
Tested-by: Jenkins
Reviewed-by: Jonathan Clark <jonathan@libreoffice.org>

5 files changed, 93 insertions, 120 deletions

diff --git a/vcl/inc/ImplLayoutRuns.hxx b/vcl/inc/ImplLayoutRuns.hxx
index dec9ca59dcfc..fecf1957d5f2 100644
--- a/vcl/inc/ImplLayoutRuns.hxx
+++ b/vcl/inc/ImplLayoutRuns.hxx
@@ -26,8 +26,18 @@
 class VCL_DLLPUBLIC ImplLayoutRuns
 {
 private:
+    struct Run
+    {
+        int m_nMinRunPos;
+        int m_nEndRunPos;
+        bool m_bRTL;
+
+        Run(int nMinRunPos, int nEndRunPos, bool bRTL);
+        bool Contains(int nCharPos) const;
+    };
+
     int mnRunIndex;
-    boost::container::small_vector<int, 8> maRuns;
+    boost::container::small_vector<Run, 8> maRuns;
 
 public:
     ImplLayoutRuns() { mnRunIndex = 0; }
@@ -38,11 +48,14 @@ public:
 
     bool IsEmpty() const { return maRuns.empty(); }
     void ResetPos() { mnRunIndex = 0; }
-    void NextRun() { mnRunIndex += 2; }
+    void NextRun() { ++mnRunIndex; }
     bool GetRun(int* nMinRunPos, int* nEndRunPos, bool* bRTL) const;
     bool GetNextPos(int* nCharPos, bool* bRTL);
     bool PosIsInRun(int nCharPos) const;
     bool PosIsInAnyRun(int nCharPos) const;
+
+    inline auto begin() const { return maRuns.begin(); }
+    inline auto end() const { return maRuns.end(); }
 };
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/vcl/inc/sallayout.hxx b/vcl/inc/sallayout.hxx
index 49eb0c4ce93a..0b10629fcb3e 100644
--- a/vcl/inc/sallayout.hxx
+++ b/vcl/inc/sallayout.hxx
@@ -152,7 +152,8 @@ private:
     SAL_DLLPRIVATE void GetCharWidths(std::vector<double>& rCharWidths,
                                   const OUString& rStr) const;
 
-    SAL_DLLPRIVATE void SetNeedFallback(vcl::text::ImplLayoutArgs&, sal_Int32, bool);
+    SAL_DLLPRIVATE void SetNeedFallback(vcl::text::ImplLayoutArgs& rArgs, sal_Int32 nCharPos,
+                                        sal_Int32 nCharEnd, bool bRightToLeft);
 
     SAL_DLLPRIVATE bool HasVerticalAlternate(sal_UCS4 aChar, sal_UCS4 aNextChar);
 
diff --git a/vcl/source/gdi/CommonSalLayout.cxx b/vcl/source/gdi/CommonSalLayout.cxx
index a3646b69edc2..37a640645999 100644
--- a/vcl/source/gdi/CommonSalLayout.cxx
+++ b/vcl/source/gdi/CommonSalLayout.cxx
@@ -234,9 +234,10 @@ SalLayoutGlyphs GenericSalLayout::GetGlyphs() const
     return glyphs;
 }
 
-void GenericSalLayout::SetNeedFallback(vcl::text::ImplLayoutArgs& rArgs, sal_Int32 nCharPos, bool bRightToLeft)
+void GenericSalLayout::SetNeedFallback(vcl::text::ImplLayoutArgs& rArgs, sal_Int32 nCharPos,
+                                       sal_Int32 nCharEnd, bool bRightToLeft)
 {
-    if (nCharPos < 0 || mbFuzzing)
+    if (nCharPos < 0 || nCharPos == nCharEnd || mbFuzzing)
         return;
 
     using namespace ::com::sun::star;
@@ -250,9 +251,8 @@ void GenericSalLayout::SetNeedFallback(vcl::text::ImplLayoutArgs& rArgs, sal_Int
     //mark all glyphs as missing so the whole thing is rendered with the same
     //font
     sal_Int32 nDone;
-    int nGraphemeEndPos =
-        mxBreak->nextCharacters(rArgs.mrStr, nCharPos, aLocale,
-            i18n::CharacterIteratorMode::SKIPCELL, 1, nDone);
+    int nGraphemeEndPos = mxBreak->nextCharacters(rArgs.mrStr, nCharEnd - 1, aLocale,
+                                                  i18n::CharacterIteratorMode::SKIPCELL, 1, nDone);
     // Safely advance nCharPos in case it is a non-BMP character.
     rArgs.mrStr.iterateCodePoints(&nCharPos);
     int nGraphemeStartPos =
@@ -354,13 +354,22 @@ bool GenericSalLayout::LayoutText(vcl::text::ImplLayoutArgs& rArgs, const SalLay
     if (rArgs.mnEndCharPos - rArgs.mnMinCharPos <= 0)
         return true;
 
+    ImplLayoutRuns aFallbackRuns;
+
     if (pGlyphs)
     {
         // Work with pre-computed glyph items.
         m_GlyphItems = *pGlyphs;
+
         for(const GlyphItem& item : m_GlyphItems)
             if(!item.glyphId())
-                SetNeedFallback(rArgs, item.charPos(), item.IsRTLGlyph());
+                aFallbackRuns.AddPos(item.charPos(), item.IsRTLGlyph());
+
+        for (const auto& rRun : aFallbackRuns)
+        {
+            SetNeedFallback(rArgs, rRun.m_nMinRunPos, rRun.m_nEndRunPos, rRun.m_bRTL);
+        }
+
         // Some flags are set as a side effect of text layout, restore them here.
         rArgs.mnFlags |= pGlyphs->GetFlags();
         return true;
@@ -646,7 +655,7 @@ bool GenericSalLayout::LayoutText(vcl::text::ImplLayoutArgs& rArgs, const SalLay
                     // Only request fallback for grapheme clusters that are drawn
                     if (nCharPos >= rArgs.mnDrawMinCharPos && nCharPos < rArgs.mnDrawEndCharPos)
                     {
-                        SetNeedFallback(rArgs, nCharPos, bRightToLeft);
+                        aFallbackRuns.AddPos(nCharPos, bRightToLeft);
                         if (SalLayoutFlags::ForFallback & rArgs.mnFlags)
                             continue;
                     }
@@ -735,6 +744,11 @@ bool GenericSalLayout::LayoutText(vcl::text::ImplLayoutArgs& rArgs, const SalLay
 
     hb_buffer_destroy(pHbBuffer);
 
+    for (const auto& rRun : aFallbackRuns)
+    {
+        SetNeedFallback(rArgs, rRun.m_nMinRunPos, rRun.m_nEndRunPos, rRun.m_bRTL);
+    }
+
     // Some flags are set as a side effect of text layout, save them here.
     if (rArgs.mnFlags & SalLayoutFlags::GlyphItemsOnly)
         m_GlyphItems.SetFlags(rArgs.mnFlags);
diff --git a/vcl/source/text/ImplLayoutArgs.cxx b/vcl/source/text/ImplLayoutArgs.cxx
index dbe5f7fd5135..0b6199ac0e40 100644
--- a/vcl/source/text/ImplLayoutArgs.cxx
+++ b/vcl/source/text/ImplLayoutArgs.cxx
@@ -189,43 +189,12 @@ bool ImplLayoutArgs::PrepareFallback(const SalLayoutGlyphsImpl* pGlyphsImpl)
         return false;
     }
 
-    // convert the fallback requests to layout requests
-    bool bRTL;
-    int nMin, nEnd;
-
-    // get the individual fallback requests
-    std::vector<int> aPosVector;
-    aPosVector.reserve(mrStr.getLength());
-    maFallbackRuns.ResetPos();
-    for (; maFallbackRuns.GetRun(&nMin, &nEnd, &bRTL); maFallbackRuns.NextRun())
-        for (int i = nMin; i < nEnd; ++i)
-            aPosVector.push_back(i);
+    // the fallback runs already have the same order and limits of the original runs
+    std::swap(maRuns, maFallbackRuns);
     maFallbackRuns.Clear();
-
-    // sort the individual fallback requests
-    std::sort(aPosVector.begin(), aPosVector.end());
-
-    // adjust fallback runs to have the same order and limits of the original runs
-    ImplLayoutRuns aNewRuns;
+    maFallbackRuns.ResetPos();
     maRuns.ResetPos();
-    for (; maRuns.GetRun(&nMin, &nEnd, &bRTL); maRuns.NextRun())
-    {
-        if (!bRTL)
-        {
-            auto it = std::lower_bound(aPosVector.begin(), aPosVector.end(), nMin);
-            for (; (it != aPosVector.end()) && (*it < nEnd); ++it)
-                aNewRuns.AddPos(*it, bRTL);
-        }
-        else
-        {
-            auto it = std::upper_bound(aPosVector.begin(), aPosVector.end(), nEnd);
-            while ((it != aPosVector.begin()) && (*--it >= nMin))
-                aNewRuns.AddPos(*it, bRTL);
-        }
-    }
 
-    maRuns = aNewRuns; // TODO: use vector<>::swap()
-    maRuns.ResetPos();
     return true;
 }
 
diff --git a/vcl/source/text/ImplLayoutRuns.cxx b/vcl/source/text/ImplLayoutRuns.cxx
index 3e054f5c4082..ab1597b56449 100644
--- a/vcl/source/text/ImplLayoutRuns.cxx
+++ b/vcl/source/text/ImplLayoutRuns.cxx
@@ -20,30 +20,39 @@
 #include <ImplLayoutRuns.hxx>
 #include <algorithm>
 
+ImplLayoutRuns::Run::Run(int nMinRunPos, int nEndRunPos, bool bRTL)
+    : m_nMinRunPos(nMinRunPos)
+    , m_nEndRunPos(nEndRunPos)
+    , m_bRTL(bRTL)
+{
+}
+
+bool ImplLayoutRuns::Run::Contains(int nCharPos) const
+{
+    return (m_nMinRunPos <= nCharPos) && (nCharPos < m_nEndRunPos);
+}
+
 void ImplLayoutRuns::AddPos( int nCharPos, bool bRTL )
 {
     // check if charpos could extend current run
-    int nIndex = maRuns.size();
-    if( nIndex >= 2 )
+    if (!maRuns.empty())
     {
-        int nRunPos0 = maRuns[ nIndex-2 ];
-        int nRunPos1 = maRuns[ nIndex-1 ];
-        if( ((nCharPos + int(bRTL)) == nRunPos1) && ((nRunPos0 > nRunPos1) == bRTL) )
+        auto& rLastRun = maRuns.back();
+        if (bRTL == rLastRun.m_bRTL && nCharPos == rLastRun.m_nEndRunPos)
         {
             // extend current run by new charpos
-            maRuns[ nIndex-1 ] = nCharPos + int(!bRTL);
+            ++rLastRun.m_nEndRunPos;
             return;
         }
         // ignore new charpos when it is in current run
-        if( (nRunPos0 <= nCharPos) && (nCharPos < nRunPos1) )
-            return;
-        if( (nRunPos1 <= nCharPos) && (nCharPos < nRunPos0) )
+        if ((rLastRun.m_nMinRunPos <= nCharPos) && (nCharPos < rLastRun.m_nEndRunPos))
+        {
             return;
+        }
     }
 
     // else append a new run consisting of the new charpos
-    maRuns.push_back( nCharPos + (bRTL ? 1 : 0) );
-    maRuns.push_back( nCharPos + (bRTL ? 0 : 1) );
+    maRuns.emplace_back(nCharPos, nCharPos + 1, bRTL);
 }
 
 void ImplLayoutRuns::AddRun( int nCharPos0, int nCharPos1, bool bRTL )
@@ -51,19 +60,23 @@ void ImplLayoutRuns::AddRun( int nCharPos0, int nCharPos1, bool bRTL )
     if( nCharPos0 == nCharPos1 )
         return;
 
-    // swap if needed
-    if( bRTL == (nCharPos0 < nCharPos1) )
-        std::swap( nCharPos0, nCharPos1 );
+    auto nOrderedCharPos0 = std::min(nCharPos0, nCharPos1);
+    auto nOrderedCharPos1 = std::max(nCharPos0, nCharPos1);
 
-    if (maRuns.size() >= 2 && nCharPos0 == maRuns[maRuns.size() - 2] && nCharPos1 == maRuns[maRuns.size() - 1])
+    if (!maRuns.empty())
     {
-        //this run is the same as the last
-        return;
+        auto& rLastRun = maRuns.back();
+        if ((rLastRun.m_nMinRunPos <= nOrderedCharPos0)
+            && (nOrderedCharPos0 <= rLastRun.m_nEndRunPos)
+            && (nOrderedCharPos0 < rLastRun.m_nEndRunPos || bRTL == rLastRun.m_bRTL))
+        {
+            rLastRun.m_nEndRunPos = std::max(rLastRun.m_nEndRunPos, nOrderedCharPos1);
+            return;
+        }
     }
 
     // append new run
-    maRuns.push_back( nCharPos0 );
-    maRuns.push_back( nCharPos1 );
+    maRuns.emplace_back(nOrderedCharPos0, nOrderedCharPos1, bRTL);
 }
 
 bool ImplLayoutRuns::PosIsInRun( int nCharPos ) const
@@ -71,37 +84,13 @@ bool ImplLayoutRuns::PosIsInRun( int nCharPos ) const
     if( mnRunIndex >= static_cast<int>(maRuns.size()) )
         return false;
 
-    int nMinCharPos = maRuns[ mnRunIndex+0 ];
-    int nEndCharPos = maRuns[ mnRunIndex+1 ];
-    if( nMinCharPos > nEndCharPos ) // reversed in RTL case
-        std::swap( nMinCharPos, nEndCharPos );
-
-    if( nCharPos < nMinCharPos )
-        return false;
-    if( nCharPos >= nEndCharPos )
-        return false;
-    return true;
+    return maRuns.at(mnRunIndex).Contains(nCharPos);
 }
 
 bool ImplLayoutRuns::PosIsInAnyRun( int nCharPos ) const
 {
-    bool bRet = false;
-    int nRunIndex = mnRunIndex;
-
-    ImplLayoutRuns *pThis = const_cast<ImplLayoutRuns*>(this);
-
-    pThis->ResetPos();
-
-    for (size_t i = 0; i < maRuns.size(); i+=2)
-    {
-        bRet = PosIsInRun( nCharPos );
-        if( bRet )
-            break;
-        pThis->NextRun();
-    }
-
-    pThis->mnRunIndex = nRunIndex;
-    return bRet;
+    return std::any_of(maRuns.begin(), maRuns.end(),
+                       [nCharPos](const auto& rRun) { return rRun.Contains(nCharPos); });
 }
 
 bool ImplLayoutRuns::GetNextPos( int* nCharPos, bool* bRightToLeft )
@@ -114,37 +103,33 @@ bool ImplLayoutRuns::GetNextPos( int* nCharPos, bool* bRightToLeft )
     if( mnRunIndex >= static_cast<int>(maRuns.size()) )
         return false;
 
-    int nRunPos0 = maRuns[ mnRunIndex+0 ];
-    int nRunPos1 = maRuns[ mnRunIndex+1 ];
-    *bRightToLeft = (nRunPos0 > nRunPos1);
+    const auto& rRun = maRuns.at(mnRunIndex);
 
     if( *nCharPos < 0 )
     {
         // get first valid nCharPos in run
-        *nCharPos = nRunPos0;
+        *nCharPos = rRun.m_nMinRunPos;
     }
     else
     {
-        // advance to next nCharPos for LTR case
-        if( !*bRightToLeft )
-            ++(*nCharPos);
+        // advance to next nCharPos
+        ++(*nCharPos);
 
         // advance to next run if current run is completed
-        if( *nCharPos == nRunPos1 )
+        if (*nCharPos == rRun.m_nEndRunPos)
         {
-            if( (mnRunIndex += 2) >= static_cast<int>(maRuns.size()) )
+            ++mnRunIndex;
+            if (mnRunIndex >= static_cast<int>(maRuns.size()))
+            {
                 return false;
-            nRunPos0 = maRuns[ mnRunIndex+0 ];
-            nRunPos1 = maRuns[ mnRunIndex+1 ];
-            *bRightToLeft = (nRunPos0 > nRunPos1);
-            *nCharPos = nRunPos0;
+            }
+
+            const auto& rNextRun = maRuns.at(mnRunIndex);
+            *nCharPos = rNextRun.m_nMinRunPos;
+            *bRightToLeft = rNextRun.m_bRTL;
         }
     }
 
-    // advance to next nCharPos for RTL case
-    if( *bRightToLeft )
-        --(*nCharPos);
-
     return true;
 }
 
@@ -153,19 +138,10 @@ bool ImplLayoutRuns::GetRun( int* nMinRunPos, int* nEndRunPos, bool* bRightToLef
     if( mnRunIndex >= static_cast<int>(maRuns.size()) )
         return false;
 
-    int nRunPos0 = maRuns[ mnRunIndex+0 ];
-    int nRunPos1 = maRuns[ mnRunIndex+1 ];
-    *bRightToLeft = (nRunPos1 < nRunPos0) ;
-    if( !*bRightToLeft )
-    {
-        *nMinRunPos = nRunPos0;
-        *nEndRunPos = nRunPos1;
-    }
-    else
-    {
-        *nMinRunPos = nRunPos1;
-        *nEndRunPos = nRunPos0;
-    }
+    const auto& rRun = maRuns.at(mnRunIndex);
+    *nMinRunPos = rRun.m_nMinRunPos;
+    *nEndRunPos = rRun.m_nEndRunPos;
+    *bRightToLeft = rRun.m_bRTL;
     return true;
 }