tdf#125254 Performance: A spreadsheet opens too slow, part2

Optimise bulk construction of ScMarkArray.

This takes the opening time from 46s to 40.5s for me.

Change-Id: I3955fe9b2c3113dac2ae3cda97d692de1975e762
Reviewed-on: https://gerrit.libreoffice.org/72418
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

9 files changed, 110 insertions, 4 deletions

diff --git a/sc/inc/address.hxx b/sc/inc/address.hxx
index ea047866e1e3..b7baaa4c0bc0 100644
--- a/sc/inc/address.hxx
+++ b/sc/inc/address.hxx
@@ -946,7 +946,7 @@ inline bool ScRefAddress::operator==( const ScRefAddress& rRefAddress ) const
 #define BCA_BRDCST_ALWAYS ScAddress( 0, SCROW_MAX, 0 )
 #define BCA_LISTEN_ALWAYS ScRange( BCA_BRDCST_ALWAYS, BCA_BRDCST_ALWAYS )
 
-template< typename T > void PutInOrder( T& nStart, T& nEnd )
+template< typename T > inline void PutInOrder( T& nStart, T& nEnd )
 {
     if (nEnd < nStart)
     {
diff --git a/sc/inc/markarr.hxx b/sc/inc/markarr.hxx
index 54059fcbb04a..588c26bcce49 100644
--- a/sc/inc/markarr.hxx
+++ b/sc/inc/markarr.hxx
@@ -23,6 +23,8 @@
 #include "address.hxx"
 #include <memory>
 
+class ScRangeList;
+
 #define SC_MARKARRAY_DELTA    4
 
 struct ScMarkEntry
@@ -53,6 +55,7 @@ public:
     void    Reset( bool bMarked = false, SCSIZE nNeeded = 1 );
     bool    GetMark( SCROW nRow ) const;
     void    SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked );
+    void    Set( std::vector<ScMarkEntry> const & );
     bool    IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const;
     bool    HasOneMark( SCROW& rStartRow, SCROW& rEndRow ) const;
 
diff --git a/sc/inc/markdata.hxx b/sc/inc/markdata.hxx
index ca1443a5ace0..2052c23daa52 100644
--- a/sc/inc/markdata.hxx
+++ b/sc/inc/markdata.hxx
@@ -60,10 +60,10 @@ private:
     ScRangeList     aLeftEnvelope;            // list of ranges in the left envelope of the multi selection
     ScRangeList     aRightEnvelope;           // list of ranges in the right envelope of the multi selection
 
-
 public:
                 ScMarkData();
                 ScMarkData(const ScMarkData& rData);
+                ScMarkData(const ScRangeList& rList);
                 ~ScMarkData();
 
     ScMarkData& operator=(const ScMarkData& rData);
diff --git a/sc/inc/markmulti.hxx b/sc/inc/markmulti.hxx
index dc0f0b23ce35..386f7b135f5a 100644
--- a/sc/inc/markmulti.hxx
+++ b/sc/inc/markmulti.hxx
@@ -25,6 +25,8 @@
 
 #include <vector>
 
+class ScRangeList;
+
 class ScMultiSel
 {
 
@@ -51,6 +53,7 @@ public:
     bool HasEqualRowsMarked( SCCOL nCol1, SCCOL nCol2 ) const;
     SCROW GetNextMarked( SCCOL nCol, SCROW nRow, bool bUp ) const;
     void SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark );
+    void Set( ScRangeList const & );
     bool IsRowMarked( SCROW nRow ) const;
     bool IsRowRangeMarked( SCROW nStartRow, SCROW nEndRow ) const;
     bool IsEmpty() const { return ( aMultiSelContainer.empty() && !aRowSel.HasMarks() ); }
diff --git a/sc/inc/rangelst.hxx b/sc/inc/rangelst.hxx
index 50fb4645d0c7..4aff9611e885 100644
--- a/sc/inc/rangelst.hxx
+++ b/sc/inc/rangelst.hxx
@@ -92,6 +92,10 @@ public:
     ScRange&        back() { return maRanges.back(); }
     const ScRange&  back() const { return maRanges.back(); }
     void            push_back(const ScRange & rRange);
+    ::std::vector<ScRange>::const_iterator begin() const { return maRanges.begin(); }
+    ::std::vector<ScRange>::const_iterator end() const { return maRanges.end(); }
+    ::std::vector<ScRange>::iterator begin() { return maRanges.begin(); }
+    ::std::vector<ScRange>::iterator end() { return maRanges.end(); }
 
     void swap( ScRangeList& r );
 
diff --git a/sc/source/core/data/markarr.cxx b/sc/source/core/data/markarr.cxx
index c981c9841e13..9f25769c288c 100644
--- a/sc/source/core/data/markarr.cxx
+++ b/sc/source/core/data/markarr.cxx
@@ -19,6 +19,7 @@
 
 #include <markarr.hxx>
 #include <address.hxx>
+#include <rangelst.hxx>
 #include <vector>
 
 #include <osl/diagnose.h>
@@ -243,6 +244,19 @@ void ScMarkArray::SetMarkArea( SCROW nStartRow, SCROW nEndRow, bool bMarked )
     }
 }
 
+/**
+  optimised init-from-range-list. Specifically this is optimised for cases
+  where we have very large data columns with lots and lots of ranges.
+*/
+void ScMarkArray::Set( const std::vector<ScMarkEntry> & rMarkEntries )
+{
+    nCount = rMarkEntries.size()+1;
+    nLimit = nCount;
+    pData.reset( new ScMarkEntry[nLimit] );
+    memcpy(pData.get(), rMarkEntries.data(), sizeof(ScMarkEntry) * rMarkEntries.size());
+    pData[nCount-1] = ScMarkEntry{MAXROW, false};
+}
+
 bool ScMarkArray::IsAllMarked( SCROW nStartRow, SCROW nEndRow ) const
 {
     SCSIZE nStartIndex;
diff --git a/sc/source/core/data/markdata.cxx b/sc/source/core/data/markdata.cxx
index daccf44f62a6..60e7db0fb0ca 100644
--- a/sc/source/core/data/markdata.cxx
+++ b/sc/source/core/data/markdata.cxx
@@ -356,6 +356,23 @@ void ScMarkData::MarkFromRangeList( const ScRangeList& rList, bool bReset )
     }
 }
 
+/**
+  Optimise the case of constructing from a range list, speeds up import.
+*/
+ScMarkData::ScMarkData(const ScRangeList& rList)
+{
+    ResetMark();
+
+    for (const ScRange& rRange : rList)
+        maTabMarked.insert( rRange.aStart.Tab() );
+
+    bMultiMarked = true;
+    aMultiRange = rList.Combine();
+
+    aMultiSel.Set( rList );
+}
+
+
 void ScMarkData::FillRangeListWithMarks( ScRangeList* pList, bool bClear, SCTAB nForTab ) const
 {
     if (!pList)
diff --git a/sc/source/core/data/markmulti.cxx b/sc/source/core/data/markmulti.cxx
index 61a77acbbd47..a4a66933dba6 100644
--- a/sc/source/core/data/markmulti.cxx
+++ b/sc/source/core/data/markmulti.cxx
@@ -19,7 +19,10 @@
 
 #include <markmulti.hxx>
 #include <markarr.hxx>
+#include <rangelst.hxx>
 #include <segmenttree.hxx>
+#include <sal/log.hxx>
+#include <o3tl/sorted_vector.hxx>
 
 #include <algorithm>
 
@@ -235,6 +238,69 @@ void ScMultiSel::SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, S
         aMultiSelContainer[nColIter].SetMarkArea( nStartRow, nEndRow, bMark );
 }
 
+/**
+  optimised init-from-range-list. Specifically this is optimised for cases
+  where we have very large data columns with lots and lots of ranges.
+*/
+void ScMultiSel::Set( ScRangeList const & rList )
+{
+    Clear();
+    if (rList.size() == 0)
+        return;
+
+    // sort by row to make the combining/merging faster
+    auto aNewList = rList;
+    std::sort(aNewList.begin(), aNewList.end(),
+        [](const ScRange& lhs, const ScRange& rhs)
+        {
+            return lhs.aStart.Row() < rhs.aStart.Row();
+        });
+
+    std::vector<std::vector<ScMarkEntry>> aMarkEntriesPerCol(MAXCOL+1);
+
+    SCCOL nMaxCol = -1;
+    int i = 0;
+    for (const ScRange& rRange : aNewList)
+    {
+        SCCOL nStartCol = rRange.aStart.Col();
+        SCROW nStartRow = rRange.aStart.Row();
+        SCCOL nEndCol = rRange.aEnd.Col();
+        SCROW nEndRow = rRange.aEnd.Row();
+        assert( nEndRow >= nStartRow && "this method assumes the input data has ranges with endrow>=startrow");
+        assert( nEndCol >= nStartCol && "this method assumes the input data has ranges with endcol>=startcol");
+        if ( nStartCol == 0 && nEndCol == MAXCOL )
+            aRowSel.SetMarkArea( nStartRow, nEndRow, /*bMark*/true );
+        else
+        {
+            for ( SCCOL nCol = nStartCol; nCol <= nEndCol; ++nCol )
+            {
+                auto & rMarkEntries = aMarkEntriesPerCol[nCol];
+                int nEntries = rMarkEntries.size();
+                if (nEntries > 1 && nStartRow >= rMarkEntries[nEntries-2].nRow+1
+                   && nStartRow <= rMarkEntries[nEntries-1].nRow)
+                {
+                    // overlaps previous range
+                    rMarkEntries.back().nRow = nEndRow;
+                }
+                else
+                {
+                    // new range
+                    if (nStartRow > 0)
+	                    rMarkEntries.emplace_back(ScMarkEntry{nStartRow-1, false});
+                    rMarkEntries.emplace_back(ScMarkEntry{nEndRow, true});
+                }
+            }
+            nMaxCol = std::max(nMaxCol, nEndCol);
+        }
+        ++i;
+    }
+
+    aMultiSelContainer.resize(nMaxCol+1);
+    for (SCCOL nCol = 0; nCol<=nMaxCol; ++nCol)
+        if (!aMarkEntriesPerCol[nCol].empty())
+            aMultiSelContainer[nCol].Set( aMarkEntriesPerCol[nCol] );
+}
+
 bool ScMultiSel::IsRowMarked( SCROW nRow ) const
 {
     return aRowSel.GetMark( nRow );
diff --git a/sc/source/ui/unoobj/cellsuno.cxx b/sc/source/ui/unoobj/cellsuno.cxx
index c51eb115b0aa..2948db62e5c3 100644
--- a/sc/source/ui/unoobj/cellsuno.cxx
+++ b/sc/source/ui/unoobj/cellsuno.cxx
@@ -1538,8 +1538,7 @@ const ScMarkData* ScCellRangesBase::GetMarkData()
 {
     if (!pMarkData)
     {
-        pMarkData.reset( new ScMarkData() );
-        pMarkData->MarkFromRangeList( aRanges, false );
+        pMarkData.reset( new ScMarkData(aRanges) );
     }
     return pMarkData.get();
 }