Perf-sc: tdf#100709 avoid segment tree with ScMultiSelIter where possible

* create ScFlatBoolRowSegments in ScMultiSelIter only if necessary
* create ScMultiSelIter only for affected columns in
  ScTable::MergeSelectionPattern() using ScMarkData::GetMarkedColSpans()
* obtaining a full ScRangeList in ScMarkData::GetMarkedColSpans() was
  completely unnecessary, use existing selection containers instead and also
  if possible avoid creating a segment tree that needs to be converted to
  vector, directly use a vector instead

Improvement:
* under ScDocShell::Load()
  previous: Ir:  26 454 571 612
       now: Ir:  18 811 368 362

* thereof under ScTable::MergeSelectionPattern()
  previous: Ir:   4 104 164 533
       now: Ir:     664 738 808

Change-Id: I95895a3a000c1a0b7895fb0696b0889c6d6b4d49
(cherry picked from commit bb9b6cb4e6cfc5fbb4733abb8e9f5758987c197a)
Reviewed-on: https://gerrit.libreoffice.org/38376
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Jenkins <ci@libreoffice.org>

6 files changed, 165 insertions, 40 deletions

diff --git a/sc/inc/markarr.hxx b/sc/inc/markarr.hxx
index 33a7b9031128..548d023db4d4 100644
--- a/sc/inc/markarr.hxx
+++ b/sc/inc/markarr.hxx
@@ -71,6 +71,7 @@ public:
                 ~ScMarkArrayIter();
 
     bool        Next( SCROW& rTop, SCROW& rBottom );
+    void        reset( const ScMarkArray* pNewArray );
 };
 
 #endif
diff --git a/sc/inc/markmulti.hxx b/sc/inc/markmulti.hxx
index 4999df5c5708..6ada78c243e6 100644
--- a/sc/inc/markmulti.hxx
+++ b/sc/inc/markmulti.hxx
@@ -63,20 +63,28 @@ public:
     void Clear();
     void MarkAllCols( SCROW nStartRow, SCROW nEndRow );
     bool HasAnyMarks() const;
+
+    // For faster access from within ScMarkData, instead of creating
+    // ScMultiSelIter with ScFlatBoolRowSegments bottleneck.
+    const ScMarkArray& GetRowSelArray() const;
+    const ScMarkArray* GetMultiSelArray( SCCOL nCol ) const;
 };
 
 class ScMultiSelIter
 {
 
 private:
-    ScFlatBoolRowSegments aRowSegs;
+    std::unique_ptr<ScFlatBoolRowSegments>  pRowSegs;
+    ScMarkArrayIter                         aMarkArrayIter;
     SCROW nNextSegmentStart;
 public:
     ScMultiSelIter( const ScMultiSel& rMultiSel, SCCOL nCol );
     ~ScMultiSelIter();
 
     bool Next( SCROW& rTop, SCROW& rBottom );
-    const ScFlatBoolRowSegments& GetRowSegments() const { return aRowSegs; }
+    /** Only to be used by ScMultiSel::IsAllMarked() or otherwise sure that a
+        segment tree is actually used. */
+    bool GetRangeData( SCROW nRow, ScFlatBoolRowSegments::RangeData& rRowRange ) const;
 };
 
 #endif
diff --git a/sc/source/core/data/markarr.cxx b/sc/source/core/data/markarr.cxx
index b95cf07c9e6d..52b7597fe1cd 100644
--- a/sc/source/core/data/markarr.cxx
+++ b/sc/source/core/data/markarr.cxx
@@ -372,8 +372,16 @@ ScMarkArrayIter::~ScMarkArrayIter()
 {
 }
 
+void ScMarkArrayIter::reset( const ScMarkArray* pNewArray )
+{
+    pArray = pNewArray;
+    nPos = 0;
+}
+
 bool ScMarkArrayIter::Next( SCROW& rTop, SCROW& rBottom )
 {
+    if (!pArray)
+        return false;
     if ( nPos >= pArray->nCount )
         return false;
     while (!pArray->pData[nPos].bMarked)
diff --git a/sc/source/core/data/markdata.cxx b/sc/source/core/data/markdata.cxx
index e2e89e829d09..67c309169c53 100644
--- a/sc/source/core/data/markdata.cxx
+++ b/sc/source/core/data/markdata.cxx
@@ -468,19 +468,86 @@ std::vector<sc::ColRowSpan> ScMarkData::GetMarkedRowSpans() const
 
 std::vector<sc::ColRowSpan> ScMarkData::GetMarkedColSpans() const
 {
-    typedef mdds::flat_segment_tree<SCCOLROW, bool> SpansType;
 
-    ScRangeList aRanges = GetMarkedRanges();
-    SpansType aSpans(0, MAXCOL+1, false);
-    SpansType::const_iterator itPos = aSpans.begin();
-
-    for (size_t i = 0, n = aRanges.size(); i < n; ++i)
+    if (bMultiMarked)
     {
-        const ScRange& r = *aRanges[i];
-        itPos = aSpans.insert(itPos, r.aStart.Col(), r.aEnd.Col()+1, true).first;
+        SCCOL nStartCol = aMultiRange.aStart.Col();
+        SCCOL nEndCol = aMultiRange.aEnd.Col();
+        if (bMarked)
+        {
+            // Use segment tree to merge marked with multi marked.
+            typedef mdds::flat_segment_tree<SCCOLROW, bool> SpansType;
+            SpansType aSpans(0, MAXCOL+1, false);
+            SpansType::const_iterator itPos = aSpans.begin();
+            do
+            {
+                if (aMultiSel.GetRowSelArray().HasMarks())
+                {
+                    itPos = aSpans.insert(itPos, nStartCol, nEndCol+1, true).first;
+                    break;  // do; all columns marked
+                }
+
+                /* XXX if it turns out that span insert is too slow for lots of
+                 * subsequent columns we could gather each span first and then
+                 * insert. */
+                for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol)
+                {
+                    const ScMarkArray* pMultiArray = aMultiSel.GetMultiSelArray( nCol );
+                    if (pMultiArray && pMultiArray->HasMarks())
+                        itPos = aSpans.insert(itPos, nCol, nCol+1, true).first;
+                }
+            }
+            while(false);
+
+            // Merge marked.
+            itPos = aSpans.insert(itPos, aMarkRange.aStart.Col(), aMarkRange.aEnd.Col()+1, true).first;
+
+            return sc::toSpanArray<SCCOLROW,sc::ColRowSpan>(aSpans);
+        }
+        else
+        {
+            // A plain vector is sufficient, avoid segment tree and conversion
+            // to vector overhead.
+            std::vector<sc::ColRowSpan> aVec;
+            if (aMultiSel.GetRowSelArray().HasMarks())
+            {
+                aVec.push_back( sc::ColRowSpan( nStartCol, nEndCol));
+                return aVec;    // all columns marked
+            }
+            sc::ColRowSpan aSpan( -1, -1);
+            for (SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol)
+            {
+                const ScMarkArray* pMultiArray = aMultiSel.GetMultiSelArray( nCol );
+                if (pMultiArray && pMultiArray->HasMarks())
+                {
+                    if (aSpan.mnStart == -1)
+                        aSpan.mnStart = nCol;
+                    aSpan.mnEnd = nCol;
+                }
+                else
+                {
+                    // Add span gathered so far, if any.
+                    if (aSpan.mnStart != -1)
+                    {
+                        aVec.push_back( aSpan);
+                        aSpan.mnStart = -1;
+                    }
+                }
+            }
+            // Add last span, if any.
+            if (aSpan.mnStart != -1)
+                aVec.push_back( aSpan);
+            return aVec;
+        }
     }
 
-    return sc::toSpanArray<SCCOLROW,sc::ColRowSpan>(aSpans);
+    // Only reached if not multi marked.
+    std::vector<sc::ColRowSpan> aVec;
+    if (bMarked)
+    {
+        aVec.push_back( sc::ColRowSpan( aMarkRange.aStart.Col(), aMarkRange.aEnd.Col()));
+    }
+    return aVec;
 }
 
 bool ScMarkData::IsAllMarked( const ScRange& rRange ) const
diff --git a/sc/source/core/data/markmulti.cxx b/sc/source/core/data/markmulti.cxx
index 217753b1d5b6..091c91eae9ff 100644
--- a/sc/source/core/data/markmulti.cxx
+++ b/sc/source/core/data/markmulti.cxx
@@ -143,7 +143,7 @@ bool ScMultiSel::IsAllMarked( SCCOL nCol, SCROW nStartRow, SCROW nEndRow ) const
             return true;
         ScMultiSelIter aMultiIter( *this, nCol );
         ScFlatBoolRowSegments::RangeData aRowRange;
-        bool bRet = aMultiIter.GetRowSegments().getRangeData( nStartRow, aRowRange );
+        bool bRet = aMultiIter.GetRangeData( nStartRow, aRowRange );
         return bRet && aRowRange.mbValue && aRowRange.mnRow2 >= nEndRow;
     }
 
@@ -296,31 +296,53 @@ bool ScMultiSel::HasAnyMarks() const
     return false;
 }
 
+const ScMarkArray& ScMultiSel::GetRowSelArray() const
+{
+    return aRowSel;
+}
+
+const ScMarkArray* ScMultiSel::GetMultiSelArray( SCCOL nCol ) const
+{
+    ScMultiSel::MapType::const_iterator aIter = aMultiSelContainer.find( nCol );
+    return (aIter != aMultiSelContainer.end()) ? &aIter->second : nullptr;
+}
+
 ScMultiSelIter::ScMultiSelIter( const ScMultiSel& rMultiSel, SCCOL nCol ) :
-    aRowSegs(),
+    aMarkArrayIter(nullptr),
     nNextSegmentStart(0)
 {
-    aRowSegs.setFalse( 0, MAXROW );
     bool bHasMarks1 = rMultiSel.aRowSel.HasMarks();
     ScMultiSel::MapType::const_iterator aIter = rMultiSel.aMultiSelContainer.find( nCol );
     bool bHasMarks2 = ( ( aIter != rMultiSel.aMultiSelContainer.end() ) && aIter->second.HasMarks() );
 
-    if ( bHasMarks1 )
+    if (bHasMarks1 && bHasMarks2)
     {
-        ScMarkArrayIter aMarkIter( &rMultiSel.aRowSel );
-        SCROW nTop, nBottom;
-        while ( aMarkIter.Next( nTop, nBottom ) )
-            aRowSegs.setTrue( nTop, nBottom );
-    }
+        pRowSegs.reset( new ScFlatBoolRowSegments);
+        pRowSegs->setFalse( 0, MAXROW );
+        if ( bHasMarks1 )
+        {
+            ScMarkArrayIter aMarkIter( &rMultiSel.aRowSel );
+            SCROW nTop, nBottom;
+            while ( aMarkIter.Next( nTop, nBottom ) )
+                pRowSegs->setTrue( nTop, nBottom );
+        }
 
-    if ( bHasMarks2 )
+        if ( bHasMarks2 )
+        {
+            ScMarkArrayIter aMarkIter( &aIter->second );
+            SCROW nTop, nBottom;
+            while ( aMarkIter.Next( nTop, nBottom ) )
+                pRowSegs->setTrue( nTop, nBottom );
+        }
+    }
+    else if (bHasMarks1)
     {
-        ScMarkArrayIter aMarkIter( &aIter->second );
-        SCROW nTop, nBottom;
-        while ( aMarkIter.Next( nTop, nBottom ) )
-            aRowSegs.setTrue( nTop, nBottom );
+        aMarkArrayIter.reset( &rMultiSel.aRowSel);
+    }
+    else if (bHasMarks2)
+    {
+        aMarkArrayIter.reset( &aIter->second);
     }
-
 }
 
 ScMultiSelIter::~ScMultiSelIter()
@@ -329,20 +351,32 @@ ScMultiSelIter::~ScMultiSelIter()
 
 bool ScMultiSelIter::Next( SCROW& rTop, SCROW& rBottom )
 {
-    ScFlatBoolRowSegments::RangeData aRowRange;
-    bool bRet = aRowSegs.getRangeData( nNextSegmentStart, aRowRange );
-    if ( bRet && !aRowRange.mbValue )
-    {
-        nNextSegmentStart = aRowRange.mnRow2 + 1;
-        bRet = aRowSegs.getRangeData( nNextSegmentStart, aRowRange );
-    }
-    if ( bRet )
+    if (pRowSegs)
     {
-        rTop = aRowRange.mnRow1;
-        rBottom = aRowRange.mnRow2;
-        nNextSegmentStart = rBottom + 1;
+        ScFlatBoolRowSegments::RangeData aRowRange;
+        bool bRet = pRowSegs->getRangeData( nNextSegmentStart, aRowRange );
+        if ( bRet && !aRowRange.mbValue )
+        {
+            nNextSegmentStart = aRowRange.mnRow2 + 1;
+            bRet = pRowSegs->getRangeData( nNextSegmentStart, aRowRange );
+        }
+        if ( bRet )
+        {
+            rTop = aRowRange.mnRow1;
+            rBottom = aRowRange.mnRow2;
+            nNextSegmentStart = rBottom + 1;
+        }
+        return bRet;
     }
-    return bRet;
+
+    return aMarkArrayIter.Next( rTop, rBottom);
 }
 
+bool ScMultiSelIter::GetRangeData( SCROW nRow, ScFlatBoolRowSegments::RangeData& rRowRange ) const
+{
+    assert(pRowSegs);
+    return pRowSegs->getRangeData( nRow, rRowRange);
+}
+
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index fd6acb8447b6..49f040d5e5de 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -2441,8 +2441,15 @@ void ScTable::UnlockTable()
 
 void ScTable::MergeSelectionPattern( ScMergePatternState& rState, const ScMarkData& rMark, bool bDeep ) const
 {
-    for (SCCOL i=0; i < aCol.size(); i++)
-        aCol[i].MergeSelectionPattern( rState, rMark, bDeep );
+    std::vector<sc::ColRowSpan> aSpans = rMark.GetMarkedColSpans();
+
+    for (const sc::ColRowSpan & rSpan : aSpans)
+    {
+        for (SCCOLROW i = rSpan.mnStart; i <= rSpan.mnEnd; ++i)
+        {
+            aCol[i].MergeSelectionPattern( rState, rMark, bDeep );
+        }
+    }
 }
 
 void ScTable::MergePatternArea( ScMergePatternState& rState, SCCOL nCol1, SCROW nRow1,