summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorEike Rathke <erack@redhat.com>2017-06-04 00:04:10 +0200
committerEike Rathke <erack@redhat.com>2017-06-04 00:11:34 +0200
commitbb9b6cb4e6cfc5fbb4733abb8e9f5758987c197a (patch)
tree35389756d96d6c30e4ad2eb469f1ffff15b57561
parenta21ec27fe5d8de3455522deeedc2dc43cb41c073 (diff)
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
-rw-r--r--sc/inc/markarr.hxx1
-rw-r--r--sc/inc/markmulti.hxx12
-rw-r--r--sc/source/core/data/markarr.cxx8
-rw-r--r--sc/source/core/data/markdata.cxx85
-rw-r--r--sc/source/core/data/markmulti.cxx88
-rw-r--r--sc/source/core/data/table2.cxx11
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,