tdf#64991 speed up loading large RTL documents

takes load time from 2min49 to 2min5 for me

Use a vector for the PortionMap since
that has better cache density, and we always add
to the end of it, and always in the correct
order, so no sorting is necessary

Change-Id: Id28e86144a86f0f1361ef4e828f925694eb3bb11
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/120942
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

1 files changed, 39 insertions, 23 deletions

diff --git a/sw/source/core/txtnode/thints.cxx b/sw/source/core/txtnode/thints.cxx
index 88be32686deb..1d3791b119a9 100644
--- a/sw/source/core/txtnode/thints.cxx
+++ b/sw/source/core/txtnode/thints.cxx
@@ -2611,14 +2611,19 @@ void SwpHints::NoteInHistory( SwTextAttr *pAttr, const bool bNew )
 }
 
 namespace {
-typedef std::multimap< int, std::pair<SwTextAttr*, bool> > PortionMap;
+struct Portion {
+    SwTextAttr* pTextAttr;
+    int nKey;
+    bool isRsidOnlyAutoFormat;
+};
+typedef std::vector< Portion > PortionMap;
 enum MergeResult { MATCH, DIFFER_ONLY_RSID, DIFFER };
 }
 
 static MergeResult lcl_Compare_Attributes(
         int i, int j,
-        const std::pair< PortionMap::iterator, PortionMap::iterator >& aRange1,
-        const std::pair< PortionMap::iterator, PortionMap::iterator >& aRange2,
+        const std::pair< PortionMap::const_iterator, PortionMap::const_iterator >& aRange1,
+        const std::pair< PortionMap::const_iterator, PortionMap::const_iterator >& aRange2,
         std::vector<bool>& RsidOnlyAutoFormatFlagMap);
 
 bool SwpHints::MergePortions( SwTextNode& rNode )
@@ -2631,6 +2636,7 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
 
     bool bRet = false;
     PortionMap aPortionMap;
+    aPortionMap.reserve(Count() + 1);
     std::vector<bool> RsidOnlyAutoFormatFlagMap;
     RsidOnlyAutoFormatFlagMap.resize(Count() + 1);
     sal_Int32 nLastPorStart = COMPLETE_STRING;
@@ -2686,11 +2692,21 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
         if (nPorStart != nLastPorStart)
             ++nKey;
         nLastPorStart = nPorStart;
-        aPortionMap.insert(std::make_pair(nKey,
-                            std::make_pair(pHt, isRsidOnlyAutoFormat)));
+        aPortionMap.push_back(Portion {pHt, nKey, isRsidOnlyAutoFormat});
         RsidOnlyAutoFormatFlagMap[nKey] = isRsidOnlyAutoFormat;
     }
 
+    // we add data strictly in-order, so we can binary-search the vector
+    auto equal_range = [&aPortionMap](int i)
+    {
+        Portion key { nullptr, i, false  };
+        return std::equal_range(aPortionMap.begin(), aPortionMap.end(), key,
+            [] (const Portion& lhs, const Portion& rhs) -> bool
+            {
+                return lhs.nKey < rhs.nKey;
+            });
+    };
+
     // check if portion i can be merged with portion i+1:
     // note: need to include i=0 to set IgnoreStart and j=nKey+1 to reset
     // IgnoreEnd at first / last portion
@@ -2698,8 +2714,8 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
     int j = i + 1;
     while ( i <= nKey )
     {
-        std::pair< PortionMap::iterator, PortionMap::iterator > aRange1 = aPortionMap.equal_range( i );
-        std::pair< PortionMap::iterator, PortionMap::iterator > aRange2 = aPortionMap.equal_range( j );
+        std::pair< PortionMap::const_iterator, PortionMap::const_iterator > aRange1 = equal_range( i );
+        std::pair< PortionMap::const_iterator, PortionMap::const_iterator > aRange2 = equal_range( j );
 
         MergeResult eMerge = lcl_Compare_Attributes(i, j, aRange1, aRange2, RsidOnlyAutoFormatFlagMap);
 
@@ -2711,7 +2727,7 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
             sal_Int32 nNewPortionEnd = 0;
             for ( auto aIter2 = aRange2.first; aIter2 != aRange2.second; ++aIter2 )
             {
-                SwTextAttr *const p2 = aIter2->second.first;
+                SwTextAttr *const p2 = aIter2->pTextAttr;
                 nNewPortionEnd = *p2->GetEnd();
 
                 const size_t nCountBeforeDelete = Count();
@@ -2725,10 +2741,10 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
             ++j;
 
             // change all attributes with key i
-            aRange1 = aPortionMap.equal_range( i );
+            aRange1 = equal_range( i );
             for ( auto aIter1 = aRange1.first; aIter1 != aRange1.second; ++aIter1 )
             {
-                SwTextAttr *const p1 = aIter1->second.first;
+                SwTextAttr *const p1 = aIter1->pTextAttr;
                 NoteInHistory( p1 );
                 p1->SetEnd(nNewPortionEnd);
                 NoteInHistory( p1, true );
@@ -2747,9 +2763,9 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
             bool const bSetIgnoreFlag(DIFFER_ONLY_RSID == eMerge);
             for (auto aIter1 = aRange1.first; aIter1 != aRange1.second; ++aIter1)
             {
-                if (!aIter1->second.second) // already set above, don't change
+                if (!aIter1->isRsidOnlyAutoFormat) // already set above, don't change
                 {
-                    SwTextAttr *const pCurrent(aIter1->second.first);
+                    SwTextAttr *const pCurrent(aIter1->pTextAttr);
                     if (pCurrent->IsFormatIgnoreEnd() != bSetIgnoreFlag)
                     {
                         NoteInHistory(pCurrent);
@@ -2760,9 +2776,9 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
             }
             for (auto aIter2 = aRange2.first; aIter2 != aRange2.second; ++aIter2)
             {
-                if (!aIter2->second.second) // already set above, don't change
+                if (!aIter2->isRsidOnlyAutoFormat) // already set above, don't change
                 {
-                    SwTextAttr *const pCurrent(aIter2->second.first);
+                    SwTextAttr *const pCurrent(aIter2->pTextAttr);
                     if (pCurrent->IsFormatIgnoreStart() != bSetIgnoreFlag)
                     {
                         NoteInHistory(pCurrent);
@@ -2782,12 +2798,12 @@ bool SwpHints::MergePortions( SwTextNode& rNode )
 
 static MergeResult lcl_Compare_Attributes(
         int i, int j,
-        const std::pair< PortionMap::iterator, PortionMap::iterator >& aRange1,
-        const std::pair< PortionMap::iterator, PortionMap::iterator >& aRange2,
+        const std::pair< PortionMap::const_iterator, PortionMap::const_iterator >& aRange1,
+        const std::pair< PortionMap::const_iterator, PortionMap::const_iterator >& aRange2,
         std::vector<bool>& RsidOnlyAutoFormatFlagMap)
 {
-    PortionMap::iterator aIter1 = aRange1.first;
-    PortionMap::iterator aIter2 = aRange2.first;
+    PortionMap::const_iterator aIter1 = aRange1.first;
+    PortionMap::const_iterator aIter2 = aRange2.first;
 
     size_t const nAttributesInPor1 = std::distance(aRange1.first, aRange1.second);
     size_t const nAttributesInPor2 = std::distance(aRange2.first, aRange2.second);
@@ -2816,13 +2832,13 @@ static MergeResult lcl_Compare_Attributes(
     {
         // first of all test if there's no gap (before skipping stuff!)
         if (aIter1 != aRange1.second && aIter2 != aRange2.second &&
-            *aIter1->second.first->End() < aIter2->second.first->GetStart())
+            *aIter1->pTextAttr->End() < aIter2->pTextAttr->GetStart())
         {
             return DIFFER;
         }
         // skip it - cannot be equal if bSkipRsidOnlyAutoFormat is set
         if (bSkipRsidOnlyAutoFormat
-            && aIter1 != aRange1.second && aIter1->second.second)
+            && aIter1 != aRange1.second && aIter1->isRsidOnlyAutoFormat)
         {
             assert(DIFFER != eMerge);
             eMerge = DIFFER_ONLY_RSID;
@@ -2830,7 +2846,7 @@ static MergeResult lcl_Compare_Attributes(
             continue;
         }
         if (bSkipRsidOnlyAutoFormat
-            && aIter2 != aRange2.second && aIter2->second.second)
+            && aIter2 != aRange2.second && aIter2->isRsidOnlyAutoFormat)
         {
             assert(DIFFER != eMerge);
             eMerge = DIFFER_ONLY_RSID;
@@ -2838,8 +2854,8 @@ static MergeResult lcl_Compare_Attributes(
             continue;
         }
         assert(aIter1 != aRange1.second && aIter2 != aRange2.second);
-        SwTextAttr const*const p1 = aIter1->second.first;
-        SwTextAttr const*const p2 = aIter2->second.first;
+        SwTextAttr const*const p1 = aIter1->pTextAttr;
+        SwTextAttr const*const p2 = aIter2->pTextAttr;
         if (p1->Which() != p2->Which())
         {
             return DIFFER;